License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2019.3
URN: urn:nbn:de:0030-drops-103958
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10395/
Go to the corresponding LIPIcs Volume Portal

Childs, Andrew M. ; Schoute, Eddie ; Unsal, Cem M.

Circuit Transformations for Quantum Architectures

pdf-format:
LIPIcs-TQC-2019-3.pdf (0.7 MB)

Abstract

Quantum computer architectures impose restrictions on qubit interactions. We propose efficient circuit transformations that modify a given quantum circuit to fit an architecture, allowing for any initial and final mapping of circuit qubits to architecture qubits. To achieve this, we first consider the qubit movement subproblem and use the ROUTING VIA MATCHINGS framework to prove tighter bounds on parallel routing. In practice, we only need to perform partial permutations, so we generalize ROUTING VIA MATCHINGS to that setting. We give new routing procedures for common architecture graphs and for the generalized hierarchical product of graphs, which produces subgraphs of the Cartesian product. Secondly, for serial routing, we consider the TOKEN SWAPPING framework and extend a 4-approximation algorithm for general graphs to support partial permutations. We apply these routing procedures to give several circuit transformations, using various heuristic qubit placement subroutines. We implement these transformations in software and compare their performance for large quantum circuits on grid and modular architectures, identifying strategies that work well in practice.

BibTeX - Entry

@InProceedings{childs_et_al:LIPIcs:2019:10395,
  author =	{Andrew M. Childs and Eddie Schoute and Cem M. Unsal},
  title =	{{Circuit Transformations for Quantum Architectures}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{Wim van Dam and Laura Mancinska},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10395},
  URN =		{urn:nbn:de:0030-drops-103958},
  doi =		{10.4230/LIPIcs.TQC.2019.3},
  annote =	{Keywords: quantum circuit, quantum architectures, circuit mapping}
}

Keywords: quantum circuit, quantum architectures, circuit mapping
Collection: 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
Issue Date: 2019
Date of publication: 31.05.2019
Supplementary Material: Source code and result data available at https://gitlab.umiacs.umd.edu/amchilds/arct.

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