License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.41
URN: urn:nbn:de:0030-drops-148434
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14843/
Go to the corresponding LIPIcs Volume Portal

G Sundaram, Ranjani ; Gupta, Himanshu ; Ramakrishnan, C. R.

Efficient Distribution of Quantum Circuits

pdf-format:
LIPIcs-DISC-2021-41.pdf (2 MB)

Abstract

Quantum computing hardware is improving in robustness, but individual computers still have small number of qubits (for storing quantum information). Computations needing a large number of qubits can only be performed by distributing them over a network of smaller quantum computers. In this paper, we consider the problem of distributing a quantum computation, represented as a quantum circuit, over a homogeneous network of quantum computers, minimizing the number of communication operations needed to complete every step of the computation. We propose a two-step solution: dividing the given circuit’s qubits among the computers in the network, and scheduling communication operations, called migrations, to share quantum information among the computers to ensure that every operation can be performed locally. While the first step is an intractable problem, we present a polynomial-time solution for the second step in a special setting, and a O(log n)-approximate solution in the general setting. We provide empirical results which show that our two-step solution outperforms existing heuristic for this problem by a significant margin (up to 90%, in some cases).

BibTeX - Entry

@InProceedings{gsundaram_et_al:LIPIcs.DISC.2021.41,
  author =	{G Sundaram, Ranjani and Gupta, Himanshu and Ramakrishnan, C. R.},
  title =	{{Efficient Distribution of Quantum Circuits}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14843},
  URN =		{urn:nbn:de:0030-drops-148434},
  doi =		{10.4230/LIPIcs.DISC.2021.41},
  annote =	{Keywords: Distributed Quantum Computing, Hypergraph Min-Cut}
}

Keywords: Distributed Quantum Computing, Hypergraph Min-Cut
Collection: 35th International Symposium on Distributed Computing (DISC 2021)
Issue Date: 2021
Date of publication: 04.10.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI