Clifford Circuit Optimization with Templates and Symbolic Pauli Gates

Sergey Bravyi; Ruslan Shaydulin; Shaohan Hu; Dmitri Maslov

doi:10.22331/q-2021-11-16-580

Clifford Circuit Optimization with Templates and Symbolic Pauli Gates

Sergey Bravyi¹, Ruslan Shaydulin², Shaohan Hu³, and Dmitri Maslov¹

¹IBM Quantum, IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598
²Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL 60439
³JPMorgan Chase & Co., New York, NY 10017

Published:	2021-11-16, volume 5, page 580
Eprint:	arXiv:2105.02291v2
Doi:	https://doi.org/10.22331/q-2021-11-16-580
Citation:	Quantum 5, 580 (2021).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

The Clifford group is a finite subgroup of the unitary group generated by the Hadamard, the CNOT, and the Phase gates. This group plays a prominent role in quantum error correction, randomized benchmarking protocols, and the study of entanglement. Here we consider the problem of finding a short quantum circuit implementing a given Clifford group element. Our methods aim to minimize the entangling gate count assuming all-to-all qubit connectivity. First, we consider circuit optimization based on template matching and design Clifford-specific templates that leverage the ability to factor out Pauli and SWAP gates. Second, we introduce a symbolic peephole optimization method. It works by projecting the full circuit onto a small subset of qubits and optimally recompiling the projected subcircuit via dynamic programming. CNOT gates coupling the chosen subset of qubits with the remaining qubits are expressed using symbolic Pauli gates. Software implementation of these methods finds circuits that are only 0.2% away from optimal for 6 qubits and reduces the two-qubit gate count in circuits with up to 64 qubits by 64.7% on average, compared with the Aaronson-Gottesman canonical form.

► BibTeX data

@article{Bravyi2021cliffordcircuit,
  doi = {10.22331/q-2021-11-16-580},
  url = {https://doi.org/10.22331/q-2021-11-16-580},
  title = {Clifford {C}ircuit {O}ptimization with {T}emplates and {S}ymbolic {P}auli {G}ates},
  author = {Bravyi, Sergey and Shaydulin, Ruslan and Hu, Shaohan and Maslov, Dmitri},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {580},
  month = nov,
  year = {2021}
}

► References

[1] https://github.com/rsln-s/Clifford_Circuit_Optimization_with_Templates_and_Symbolic_Pauli_Gates.
https://github.com/rsln-s/Clifford_Circuit_Optimization_with_Templates_and_Symbolic_Pauli_Gates

[2] Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 325–338, New York, NY, USA, 2018. Association for Computing Machinery. 10.1145/3188745.3188802.
https://doi.org/10.1145/3188745.3188802

[3] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5), November 2004. 10.1103/PhysRevA.70.052328.
https://doi.org/10.1103/PhysRevA.70.052328

[4] Dorit Aharonov, Itai Arad, and Sandy Irani. Efficient algorithm for approximating one-dimensional ground states. Physical Review A, 82 (1): 012315, 2010. 10.1103/PhysRevA.82.012315.
https://doi.org/10.1103/PhysRevA.82.012315

[5] Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters. Mixed-state entanglement and quantum error correction. Physical Review A, 54 (5): 3824, 1996. 10.1103/PhysRevA.54.3824.
https://doi.org/10.1103/PhysRevA.54.3824

[6] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71 (2): 022316, 2005. 10.1103/PhysRevA.71.022316.
https://doi.org/10.1103/PhysRevA.71.022316

[7] Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the Clifford group. IEEE Transactions on Information Theory, 67 (7): 4546–4563, 2021. 10.1109/TIT.2021.3081415.
https://doi.org/10.1109/TIT.2021.3081415

[8] Sergey Bravyi, Jay M. Gambetta, Antonio Mezzacapo, and Kristan Temme. Tapering off qubits to simulate fermionic Hamiltonians. arXiv:1701.08213, 2017.
arXiv:1701.08213

[9] Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362 (6412): 308–311, 2018. 10.1126/science.aar3106.
https://doi.org/10.1126/science.aar3106

[10] Sergey Bravyi, Joseph A. Latone, and Dmitri Maslov. 6-qubit optimal Clifford circuits. arXiv:2012.06074, 2020.
arXiv:2012.06074

[11] Richard Cleve, Debbie Leung, Li Liu, and Chunhao Wang. Near-linear constructions of exact unitary 2-designs. Quantum Information and Computation, 16 (9 & 10): 0721–0756, 2016.

[12] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Physical Review A, 80 (1): 012304, 2009. 10.1103/PhysRevA.80.012304.
https://doi.org/10.1103/PhysRevA.80.012304

[13] Shantanu Debnath, Norbert M. Linke, Caroline Figgatt, Kevin A. Landsman, Kevin Wright, and Christopher Monroe. Demonstration of a small programmable quantum computer with atomic qubits. Nature, 536 (7614): 63–66, 2016. 10.1038/nature18648.
https://doi.org/10.1038/nature18648

[14] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. Graph-theoretic simplification of quantum circuits with the ZX-calculus. Quantum, 4: 279, 2020. 10.22331/q-2020-06-04-279.
https://doi.org/10.22331/q-2020-06-04-279

[15] Timothee Goubaultdebrugiere, Marc Baboulin, Benoit Valiron, Simon Martiel, and Cyril Allouche. Reducing the depth of linear reversible quantum circuits. IEEE Transactions on Quantum Engineering, 2021. 10.1109/TQE.2021.3091648.
https://doi.org/10.1109/TQE.2021.3091648

[16] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16: 1050––1057, 2020. 10.1038/s41567-020-0932-7.
https://doi.org/10.1038/s41567-020-0932-7

[17] IBM. IBM Quantum Experience. last accessed 11/9/2020. URL https://quantum-computing.ibm.com/.
https://quantum-computing.ibm.com/

[18] Raban Iten, Romain Moyard, Tony Metger, David Sutter, and Stefan Woerner. Exact and practical pattern matching for quantum circuit optimization. arXiv:1909.05270, 2019.
arXiv:1909.05270

[19] Vadym Kliuchnikov and Dmitri Maslov. Optimization of Clifford circuits. Physical Review A, 88 (5): 052307, 2013. 10.1103/PhysRevA.88.052307.
https://doi.org/10.1103/PhysRevA.88.052307

[20] Emanuel Knill. Quantum computing with realistically noisy devices. Nature, 434 (7029): 39–44, 2005. 10.1038/nature03350.
https://doi.org/10.1038/nature03350

[21] Emanuel Knill, Dietrich Leibfried, Rolf Reichle, Joe Britton, R. Brad Blakestad, John D. Jost, Chris Langer, Roee Ozeri, Signe Seidelin, and David J. Wineland. Randomized benchmarking of quantum gates. Physical Review A, 77 (1): 012307, 2008. 10.1103/PhysRevA.77.012307.
https://doi.org/10.1103/PhysRevA.77.012307

[22] Samuel A. Kutin, David Petrie Moulton, and Lawren M. Smithline. Computation at a distance. quant-ph/0701194, 2007.
arXiv:quant-ph/0701194

[23] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson. Scalable and robust randomized benchmarking of quantum processes. Physical Review Letters, 106 (18): 180504, 2011. 10.1103/PhysRevLett.106.180504.
https://doi.org/10.1103/PhysRevLett.106.180504

[24] Dmitri Maslov, D. Michael Miller, Gerhard W. Dueck, and Camille Negrevergne. Quantum circuit simplification and level compaction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27 (3): 436–444, March 2008. 10.1109/TCAD.2007.911334.
https://doi.org/10.1109/TCAD.2007.911334

[25] Michael A. Nielsen and Isaac Chuang. Quantum computation and quantum information. 2002. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[26] Ketan N. Patel, Igor L. Markov, and John P. Hayes. Optimal synthesis of linear reversible circuits. Quantum Information and Computation, 8 (3): 282–294, March 2008. ISSN 1533-7146.

[27] Aditya K. Prasad, Vivek V. Shende, Igor L. Markov, John P. Hayes, and Ketan N. Patel. Data structures and algorithms for simplifying reversible circuits. ACM Journal on Emerging Technologies in Computing Systems, 2 (4): 277–293, October 2006. 10.1145/1216396.1216399.
https://doi.org/10.1145/1216396.1216399

[28] Kanav Setia, Richard Chen, Julia E. Rice, Antonio Mezzacapo, Marco Pistoia, and James D. Whitfield. Reducing qubit requirements for quantum simulations using molecular point group symmetries. Journal of Chemical Theory and Computation, 16 (10): 6091–6097, 2020. 10.1021/acs.jctc.0c00113.
https://doi.org/10.1021/acs.jctc.0c00113

[29] 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. 10.1088/2058-9565/ab8e92.
https://doi.org/10.1088/2058-9565/ab8e92

[30] Ewout van den Berg and Kristan Temme. Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters. Quantum, 4: 322, 2020. 10.22331/q-2020-09-12-322.
https://doi.org/10.22331/q-2020-09-12-322

Cited by

[1] Tanvi P. Gujarati, Mario Motta, Triet Nguyen Friedhoff, Julia E. Rice, Nam Nguyen, Panagiotis Kl. Barkoutsos, Richard J. Thompson, Tyler Smith, Marna Kagele, Mark Brei, Barbara A. Jones, and Kristen Williams, "Quantum computation of reactions on surfaces using local embedding", npj Quantum Information 9 1, 88 (2023).

[2] Ruslan Shaydulin and Alexey Galda, 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) 291 (2021) ISBN:978-1-6654-1691-7.

[3] Ning Bao and Gavin S. Hartnett, "Twisty-puzzle-inspired approach to Clifford synthesis", Physical Review A 109 3, 032409 (2024).

[4] Toshinari Itoko and Rudy Raymond, 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) 188 (2021) ISBN:978-1-6654-1691-7.

[5] Xiaofeng Gao, Zhijin Guan, Shiguang Feng, and Yibo Jiang, "Quantum Circuit Template Matching Optimization Method for Constrained Connectivity", Axioms 12 7, 687 (2023).

[6] Sihyung Lee and Seung Yeob Nam, "Implementation of Grover’s Iterator for Quantum Searching With an Arbitrary Number of Qubits", IEEE Access 12, 43027 (2024).

[7] Jingyi Mei, Marcello Bonsangue, and Alfons Laarman, Lecture Notes in Computer Science 14683, 555 (2024) ISBN:978-3-031-65632-3.

[8] Kean Chen and Mingsheng Ying, "Automatic Test Pattern Generation for Robust Quantum Circuit Testing", ACM Transactions on Design Automation of Electronic Systems 3689333 (2024).

[9] Sihyung Lee and Seung Yeob Nam, "Quantum Program Synthesis Through Operator Learning and Selection", IEEE Access 11, 25755 (2023).

[10] Charles Yuan and Michael Carbin, "The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation", Proceedings of the ACM on Programming Languages 8 PLDI, 492 (2024).

[11] Tom Peham, Nina Brandl, Richard Kueng, Robert Wille, and Lukas Burgholzer, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 802 (2023) ISBN:979-8-3503-4323-6.

[12] Matthew DeCross, Eli Chertkov, Megan Kohagen, and Michael Foss-Feig, "Qubit-Reuse Compilation with Mid-Circuit Measurement and Reset", Physical Review X 13 4, 041057 (2023).

[13] Remmy Zen, Jan Olle, Luis Colmenarez, Matteo Puviani, Markus Müller, and Florian Marquardt, "Quantum Circuit Discovery for Fault-Tolerant Logical State Preparation with Reinforcement Learning", arXiv:2402.17761, (2024).

[14] Tom Peham, Ludwig Schmid, Lucas Berent, Markus Müller, and Robert Wille, "Automated Synthesis of Fault-Tolerant State Preparation Circuits for Quantum Error Correction Codes", arXiv:2408.11894, (2024).

[15] Giacomo Nannicini, Lev S Bishop, Oktay Gunluk, and Petar Jurcevic, "Optimal qubit assignment and routing via integer programming", arXiv:2106.06446, (2021).

[16] Kun Fang, Munan Zhang, Ruqi Shi, and Yinan Li, "Dynamic quantum circuit compilation", arXiv:2310.11021, (2023).

[17] Ruslan Shaydulin and Alexey Galda, "Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries", arXiv:2106.04410, (2021).

[18] Tom Peham, Nina Brandl, Richard Kueng, Robert Wille, and Lukas Burgholzer, "Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers", arXiv:2305.01674, (2023).

[19] Charles Yuan and Michael Carbin, "The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation", arXiv:2311.12772, (2023).

[20] Kean Chen and Mingsheng Ying, "Automatic Test Pattern Generation for Robust Quantum Circuit Testing", arXiv:2202.10697, (2022).

[21] Sarah Schneider, Lukas Burgholzer, and Robert Wille, "A SAT Encoding for Optimal Clifford Circuit Synthesis", arXiv:2208.11713, (2022).

[22] Toshinari Itoko and Rudy Raymond, "Sampling Strategy Optimization for Randomized Benchmarking", arXiv:2109.07653, (2021).

[23] Brendan Reid, "A simple method for compiling quantum stabilizer circuits", arXiv:2404.19408, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-09-16 14:16:46) and SAO/NASA ADS (last updated successfully 2024-09-16 14:16:47). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.