CoChat
Sign Up
PreprintCited by 60Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyVLSI and FPGA Design Techniques

The DOI matches its DataCite record.

CNOT circuit extraction for topologically-constrained quantum memories

Open access
Kissinger, Aleks, de Griend, Arianne Meijer-van·2019·arXiv
DOI 10.48550/arxiv.1904.00633arXiv 1904.00633
Open this paper in CoChat — free accountOpen PDF

Abstract

Many physical implementations of quantum computers impose stringent memory constraints in which 2-qubit operations can only be performed between qubits which are nearest neighbours in a lattice or graph structure. Hence, before a computation can be run on such a device, it must be mapped onto the physical architecture. That is, logical qubits must be assigned physical locations in the quantum memory, and the circuit must be replaced by an equivalent one containing only operations between nearest neighbours. In this paper, we give a new technique for quantum circuit mapping (a.k.a. routing), based on Gaussian elimination constrained to certain optimal spanning trees called Steiner trees. We give a reference implementation of the technique for CNOT circuits and show that it significantly out-performs general-purpose routines on CNOT circuits. We then comment on how the technique can be extended straightforwardly to the synthesis of CNOT+Rz circuits and as a modification to a recently-proposed circuit simplification/extraction procedure for generic circuits based on the ZX-calculus.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1904.00633

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 26

  1. [3][3] R Versluis, S Poletto, N Khammassi, N Haider, DJ Michalak, A Bruno, K Bertels, and L DiCarlo. Scalable quantum circuit and control for a superconducting surface code. arXiv:1612.08208 , 2016. - · arXiv
  2. [4][4] Joseph W Britton, Brian C Sawyer, Adam C Keith, C-C Joseph Wang, James K Freericks, Hermann Uys, Michael J Biercuk, and John J Bollinger. Engineered two-dimensional ising interactions in a trapped-ion quantum simulator with hundreds of spins. Nature , 484(7395):489, 2012. -
  3. [5][5] CJ Ballance, TP Harty, NM Linke, MA Sepiol, and DM Lucas. High-fidelity quantum logic gates using trapped-ion hyperfine qubits. Physical Review Letters , 117(6):060504, 2016. -
  4. [6][6] JP Gaebler, TR Tan, Y Lin, Y Wan, R Bowler, AC Keith, S Glancy, K Coakley, E Knill, D Leibfried, et al. High-fidelity universal gate set for be 9+ ion qubits. Physical Review Letters , 117(6):060505, 2016. -
  5. [7][7] WK Hensinger, S Olmschenk, D Stick, D Hucul, M Yeo, M Acton, L Deslauriers, C Monroe, and J Rabchuk. T-junction ion trap array for two-dimensional ion shuttling, storage, and manipulation. Applied Physics Letters , 88(3):034101, 2006. -
  6. [8][8] Alwin Zulehner, Alexandru Paler, and Robert Wille. An efficient methodology for mapping quantum circuits to the IBM QX architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2018. -
  7. [9][9] Steven Herbert and Akash Sengupta. Using reinforcement learning to find efficient qubit routing policies for deployment in near-term quantum computers. arXiv:1812.11619 , 2018. - · arXiv
  8. [10][10] Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the qubit routing problem. arXiv:1902.08091 , 2019. - · arXiv
  9. [11][11] Matthew Amy, Dmitri Maslov, and Michele Mosca. Polynomial-time T-depth optimization of Clifford+ T circuits via matroid partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 33(10):1476-1489, 2014. -
  10. [12][12] Ross Duncan, Alex Kissinger, Simon Perdrix, and John van de Wetering. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. https://arxiv.org/abs/1902.03178 , 2019. - · arXiv
  11. [13][13] B. Coecke and R. Duncan. Interacting quantum observables. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP) , Lecture Notes in Computer Science, 2008. -
  12. [15][15] Aleks Kissinger and John van de Wetering. Reducing t-count with the zx-calculus. arXiv:1903.10477 , 2019. - · arXiv
  13. [17][17] Davide Venturelli, Minh Do, Eleanor Rieffel, and Jeremy Frank. Compiling quantum circuits to realistic hardware architectures using temporal planners. Quantum Science and Technology , 3(2):025004, 2018. -
  14. [18][18] Alexandru Paler, Alwin Zulehner, and Robert Wille. NISQ circuit compilers: search space - structure and heuristics. arXiv:1806.07241 , 2018. - · arXiv
  15. [19][19] Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for NISQ-era quantum devices. arXiv:1809.02573 , 2018. - · arXiv
  16. [20][20] Davide Ferrari and Michele Amoretti. Demonstration of envariance and parity learning on the IBM 16 qubit processor. arXiv:1801.02363 , 2018. - · arXiv
  17. [21][21] Alexandru Paler. On the influence of initial qubit placement during NISQ circuit compilation. arXiv:1811.08985 , 2018. - · arXiv
  18. [22][22] Beatrice Nash, Vlad Gheorghiu, and Michele Mosca. Quantum circuit optimizations for NISQ architectures. arXiv preprint arXiv:1904.01972 , 2019. - · arXiv
  19. [23][23] Aleks Kissinger and Arianne Meijer-van de Griend. CNOT circuit extraction for topologicallyconstrained quantum memories. arXiv preprint arXiv:1904.00633 , 2019. -
  20. [24][24] Ketan N. Patel, Igor L. Markov, and John P. Hayes. Optimal synthesis of linear reversible circuits. Quantum Info. Comput. , 8(3):282-294, March 2008. -
  21. [25][25] Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations , pages 85-103. Springer, 1972. -
  22. [26][26] Gabriel Robins and Alexander Zelikovsky. Improved steiner tree approximation in graphs. In SODA , pages 770-779. Citeseer, 2000. -
  23. [27][27] Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanit` a. An Improved LP-based Approximation for Steiner Tree. In Proceedings of the Forty-second ACM Symposium on Theory of Computing , STOC '10, pages 583-592, New York, NY, USA, 2010. ACM. -
  24. [28][28] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms . MIT press, 2009. -
  25. [29][29] David E Golberg. Genetic algorithms in search, optimization, and machine learning. Addion wesley , 1989(102):36, 1989. -
  26. [30][30] Robert S Smith, Michael J Curtis, and William J Zeng. A practical quantum instruction set architecture. arXiv:1608.03355 , 2016. - · arXiv

Cited by

Metadata

Authors
Kissinger, A., & de Griend, A. M.-V.
Affiliations
Radboud University Nijmegen (NL)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
20
Issue
7&8
Pages
581-596
ISSN
1533-7146 (ISSN-L)
DOI
10.48550/arxiv.1904.00633
arXiv
1904.00633
OpenAlex
W2926638603
Cited by
60
References
0
Citations by year
2026: 1 · 2025: 5 · 2024: 6 · 2023: 8 · 2022: 12 · 2021: 10 · 2020: 12 · 2019: 6
FWCI
4.12
Type
journal article
Language
en
Open access
Licence
creativecommons.org/licenses/by/4.0/legalcode
Locations
  • Quantum Information and Computation (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • Työväentutkimus Vuosikirja (submittedVersion, other-oa)
  • Radboud Repository (Radboud University) (submittedVersion, other-oa)
  • arXiv (Cornell University) (cc-by)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Engineering › Electrical and Electronic Engineering › VLSI and FPGA Design Techniques
Keywords
quantum circuit mapping, quantum memory, Steiner tree problem, Gaussian elimination, circuit routing, ZX-calculus, circuit simplification

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review