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

The DOI matches its DataCite record.

Reducing the CNOT count for Clifford+T circuits on NISQ architectures

Open access
Gheorghiu, Vlad, Huang, Jiaxin, Li, Sarah Meng, Mosca, Michele, Mukhopadhyay, Priyanka·2020·arXiv
DOI 10.48550/arxiv.2011.12191arXiv 2011.12191
Open this paper in CoChat — free accountOpen PDF

Abstract

While mapping a quantum circuit to the physical layer one has to consider the numerous constraints imposed by the underlying hardware architecture. Connectivity of the physical qubits is one such constraint that restricts two-qubit operations, such as CNOT, to "connected" qubits. SWAP gates can be used to place the logical qubits on admissible physical qubits, but they entail a significant increase in CNOT-count. In this paper we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity constrained architectures, like noisy intermediate-scale quantum (NISQ) computing devices. We "slice" the circuit at the position of Hadamard gates and "build" the intermediate {CNOT,T} sub-circuits using Steiner trees, significantly improving on previous methods. We compared the performance of our algorithms while mapping different benchmark and random circuits to some well-known architectures such as 9-qubit square grid, 16-qubit square grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5 and 20-qubit IBM Tokyo. Our methods give less CNOT-count compared to Qiskit and TKET transpiler as well as using SWAP gates. Assuming most of the errors in a NISQ circuit implementation are due to CNOT errors, then our method would allow circuits with few times more CNOT gates be reliably implemented than the previous methods would permit.

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.2011.12191

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?

  • In Gheorghiu et al. (2020), the strategy consists of slicing the circuit into smaller parts that can be adapted and transformed to fit into the particular topology.

    “In (Gheorghiu et al. , 2020), the strategy consists of slicing the circuit into smaller parts that can be adapted and transformed to fit into the particular topology.”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Gheorghiu et al., 2020

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: 51

  1. [1][1] Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review , 41(2):303-332, 1999. -
  2. [6][6] Richard Versluis, Stefano Poletto, Nader Khammassi, Brian Tarasinski, Nadia Haider, David J Michalak, Alessandro Bruno, Koen Bertels, and Leonardo DiCarlo. Scalable quantum circuit and control for a superconducting surface code. Physical Review Applied , 8(3):034021, 2017. -
  3. [7][7] 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. -
  4. [8][8] 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. -
  5. [9][9] John P Gaebler, Ting Rei Tan, Y Lin, Y Wan, R Bowler, Adam C Keith, S Glancy, K Coakley, E Knill, D Leibfried, et al. High-fidelity universal gate set for 9 Be + ion qubits. Physical Review Letters , 117(6):060505, 2016. -
  6. [10][10] 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. -
  7. [11][11] Beatrice Nash, Vlad Gheorghiu, and Michele Mosca. Quantum circuit optimizations for NISQ architectures. Quantum Science and Technology , 5(2):025010, 2020. -
  8. [12][12] Aleks Kissinger and Arianne Meijer-van de Griend. CNOT circuit extraction for topologicallyconstrained quantum memories. Quantum Information & Computation , 20(7-8):581-596, 2020. -
  9. [13][13] Matthew Amy, Parsiad Azimzadeh, and Michele Mosca. On the controlled-not complexity of controlled-not-phase circuits. Quantum Science and Technology , 4(1):015002, 2018. -
  10. [14][14] Ketan N Patel, Igor L Markov, and John P Hayes. Optimal synthesis of linear reversible circuits. Quantum Information & Computation , 8(3):282-294, 2008. -
  11. [15][15] 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. -
  12. [16][16] Timoth´ ee Goubault de Brugi` ere, Marc Baboulin, Benoˆ ıt Valiron, Simon Martiel, and Cyril Allouche. Quantum CNOT circuits synthesis for NISQ architectures using the syndrome decoding problem. In International Conference on Reversible Computation , pages 189-205. Springer, 2020. -
  13. [18][18] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. t | ket 〉 : a retargetable compiler for NISQ devices. Quantum Science and Technology , 6(1):014003, 2020. -
  14. [19][19] Kazuo Iwama, Yahiko Kambayashi, and Shigeru Yamashita. Transformation rules for designing CNOT-based quantum circuits. In Proceedings of the 39th Annual Design Automation Conference , pages 419-424, 2002. -
  15. [20][20] Vivek V Shende, Aditya K Prasad, Igor L Markov, and John P Hayes. Reversible logic circuit synthesis. In Proceedings of the 2002 IEEE/ACM International Conference on Computer-Aided Design , pages 353-360, 2002. -
  16. [21][21] Vivek V Shende and Igor L Markov. On the CNOT-cost of Toffoli gates. Quantum Information & Computation , 9(5):461-486, 2009. -
  17. [22][22] Ryan O'Donnell. Analysis of Boolean functions . Cambridge University Press, 2014. -
  18. [23][23] Jonathan Welch, Daniel Greenbaum, Sarah Mostame, and Al´ an Aspuru-Guzik. Efficient quantum circuits for diagonal unitaries without ancillas. New Journal of Physics , 16(3):033040, 2014. -
  19. [24][24] Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for NISQ-era quantum devices. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems , pages 1001-1014, 2019. -
  20. [25][25] Massoud Pedram and Alireza Shafaei. Layout optimization for quantum circuits with linear nearest neighbor architectures. IEEE Circuits and Systems Magazine , 16(2):62-74, 2016. -
  21. [26][26] Robert Wille, Oliver Keszocze, Marcel Walter, Patrick Rohrs, Anupam Chattopadhyay, and Rolf Drechsler. Look-ahead schemes for nearest neighbor optimization of 1D and 2D quantum circuits. In 2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC) , pages 292-297. IEEE, 2016. -
  22. [27][27] Toshinari Itoko, Rudy Raymond, Takashi Imamichi, Atsushi Matsuo, and Andrew W Cross. Quantum circuit compilers using gate commutation rules. In Proceedings of the 24th Asia and South Pacific Design Automation Conference , pages 191-196, 2019. -
  23. [29][29] Atsushi Matsuo and Shigeru Yamashita. Changing the gate order for optimal LNN conversion. In International Workshop on Reversible Computation , pages 89-101. Springer, 2011. -
  24. [30][30] Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita, and Yasuhiko Nakashima. An efficient conversion of quantum circuits to a linear nearest neighbor architecture. Quantum Information and Computation , 11(1):142, 2011. -
  25. [31][31] Mehdi Saeedi, Robert Wille, and Rolf Drechsler. Synthesis of quantum circuits for linear nearest neighbor architectures. Quantum Information Processing , 10(3):355-377, 2011. -
  26. [32][32] Amlan Chakrabarti, Susmita Sur-Kolay, and Ayan Chaudhury. Linear nearest neighbor synthesis of reversible circuits by graph partitioning. arXiv preprint arXiv:1112.0564 , 2011. - · arXiv
  27. [33][33] Alireza Shafaei, Mehdi Saeedi, and Massoud Pedram. Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures. In 2013 50th ACM/EDAC/IEEE Design Automation Conference (DAC) , pages 1-6. IEEE, 2013. -
  28. [34][34] Md Mazder Rahman and Gerhard W Dueck. Synthesis of linear nearest neighbor quantum circuits. arXiv preprint arXiv:1508.05430 , 2015. - · arXiv
  29. [35][35] Stephen Brierley. Efficient implementation of quantum circuits with limited qubit interactions. Quantum Information & Computation , 17(13-14):1096-1104, 2017. -
  30. [36][36] Alireza Shafaei, Mehdi Saeedi, and Massoud Pedram. Qubit placement to minimize communication overhead in 2D quantum architectures. In 2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC) , pages 495-500. IEEE, 2014. -
  31. [37][37] Aaron Lye, Robert Wille, and Rolf Drechsler. Determining the minimal number of SWAP gates for multi-dimensional nearest neighbor quantum circuits. In The 20th Asia and South Pacific Design Automation Conference , pages 178-183. IEEE, 2015. -
  32. [38][38] Daniel Ruffinelli and Benjam´ ın Bar´ an. Linear nearest neighbor optimization in quantum circuits: a multiobjective perspective. Quantum Information Processing , 16(9):220, 2017. -
  33. [39][39] 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 , 38(7):1226-1236, 2018. -
  34. [40][40] Debjyoti Bhattacharjee and Anupam Chattopadhyay. Depth-optimal quantum circuit placement for arbitrary topologies. arXiv preprint arXiv:1703.08540 , 2017. - · arXiv
  35. [41][41] Marcos Yukio Siraichi, Vin´ ıcius Fernandes dos Santos, Sylvain Collange, and Fernando Magno Quint˜ ao Pereira. Qubit allocation. In Proceedings of the 2018 International Symposium on Code Generation and Optimization , pages 113-125, 2018. -
  36. [42][42] Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the qubit routing problem. arXiv preprint arXiv:1902.08091 , 2019. - · arXiv
  37. [43][43] Robert Wille, Lukas Burgholzer, and Alwin Zulehner. Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations. In 2019 56th ACM/IEEE Design Automation Conference (DAC) , pages 1-6. IEEE, 2019. -
  38. [44][44] 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. -
  39. [47][47] Davide Ferrari and Michele Amoretti. Demonstration of envariance and parity learning on the IBM 16 qubit processor. arXiv preprint arXiv:1801.02363 , 2018. - · arXiv
  40. [48][48] Alexandru Paler. On the influence of initial qubit placement during NISQ circuit compilation. In International Workshop on Quantum Technology and Optimization Problems , pages 207217. Springer, 2019. -
  41. [49][49] Bujiao Wu, Xiaoyu He, Shuai Yang, Lifu Shou, Guojing Tian, Jialin Zhang, and Xiaoming Sun. Optimization of CNOT circuits on topological superconducting processors. arXiv preprint arXiv:1910.14478 , 2019. - · arXiv
  42. [50][50] Yao Tang. Efficient CNOT synthesis for NISQ devices. arXiv preprint arXiv:2011.06760 , 2020. - · arXiv
  43. [51][51] Ashley Montanaro. Quantum circuits and low-degree polynomials over F 2 . Journal of Physics A: Mathematical and Theoretical , 50(8):084002, 2017. -
  44. [52][52] Christopher M Dawson, Andrew P Hines, Duncan Mortimer, Henry L Haselgrove, Michael A Nielsen, and Tobias J Osborne. Quantum computing and polynomial equations over the finite field Z 2 . Quantum Information & Computation , 5(2):102-112, 2005. -
  45. [53][53] Dax E Koh, Mark D Penney, and Robert W Spekkens. Computing quopit Clifford circuit amplitudes by the sum-over-paths technique. Quantum Information & Computation , 17(1314):1081-1095, 2017. -
  46. [54][54] Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations , pages 85-103. Springer, 1972. -
  47. [55][55] Frank K Hwang and Dana S Richards. Steiner tree problems. Networks , 22(1):55-89, 1992. -
  48. [56][56] Gabriel Robins and Alexander Zelikovsky. Tighter bounds for graph Steiner tree approximation. SIAM Journal on Discrete Mathematics , 19(1):122-134, 2005. -
  49. [57][57] Jarosglyph[suppress] law Byrka, Fabrizio Grandoni, Thomas Rothvoss, and Laura Sanit` a. Steiner tree approximation via iterative randomized rounding. Journal of the ACM (JACM) , 60(1):1-33, 2013. -
  50. [58][58] Afshin Sadeghi and Holger Fr¨ ohlich. Steiner tree methods for optimal sub-network identification: an empirical study. BMC bioinformatics , 14(1):144, 2013. -
  51. [59][59] Victor J Rayward-Smith and A Clare. On finding steiner vertices. Networks , 16(3):283-294, 1986. -

Cited by

Sorted by citations

Metadata

Authors
Gheorghiu, V., Huang, J., Li, S. M., Mosca, M., & Mukhopadhyay, P.
Affiliations
University of Waterloo (CA)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
Volume
42
Issue
6
Pages
1873-1884
ISSN
0278-0070 (ISSN-L)
DOI
10.48550/arxiv.2011.12191
arXiv
2011.12191
OpenAlex
W4309054608
Cited by
31
References
0
Citations by year
2026: 2 · 2025: 12 · 2024: 4 · 2023: 6 · 2022: 7
FWCI
2.39
Type
journal article
Language
en
Open access
Licence
creativecommons.org/licenses/by-nc-nd/4.0/legalcode
Locations
  • IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Government of Canada
  • Dalhousie University
  • Institut Périmètre de physique théorique
  • Natural Sciences and Engineering Research Council of Canada
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
Clifford+T circuits, NISQ devices, circuit mapping, Steiner tree problem, SWAP gate, transpilation, noisy intermediate-scale quantum computing

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