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] Nadish de Silva, Wilfred Salmon, and Ming Yin, "Fast algorithms for classical specifications of stabiliser states and Clifford gates", Quantum 9, 1586 (2025).

[2] Timothée Goubault de Brugière, Simon Martiel, and Christophe Vuillot, "A graph-state based synthesis framework for Clifford isometries", Quantum 9, 1589 (2025).

[3] Kun Fang, Munan Zhang, Ruqi Shi, and Yinan Li, "Dynamic Quantum Circuit Compilation", IEEE Transactions on Computers 75 2, 748 (2026).

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

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

[6] Paul D. Nation, Abdullah Ash Saki, Sebastian Brandhofer, Luciano Bello, Shelly Garion, Matthew Treinish, and Ali Javadi-Abhari, "Benchmarking the performance of quantum computing software for quantum circuit creation, manipulation and compilation", Nature Computational Science 5 5, 427 (2025).

[7] Yun‐Jie Wang, Sheng Zhang, Tai‐Ping Sun, Ze‐An Zhao, Xiao‐Fan Xu, Xi‐Ning Zhuang, Huan‐Yu Liu, Cheng Xue, Peng Duan, Yu‐Chun Wu, Zhao‐Yun Chen, and Guo‐Ping Guo, "Hardware‐Efficient Quantum Random Access Memory Design with a Native Gate Set on Superconducting Platforms", Advanced Quantum Technologies 8 5, 2400519 (2025).

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

[9] Evangelia Takou, Edwin Barnes, and Sophia E. Economou, "Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols", npj Quantum Information 11 1, 108 (2025).

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

[11] Mu-Te Lau, Hsiang-Chun Yang, Hsin-Yu Chen, and Chung-Yang Huang, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 481 (2025) ISBN:979-8-3315-5736-2.

[12] Jingyi Mei, Dekel Zak, Muhammad Osama, Tim Coopmans, and Alfons Laarman, Lecture Notes in Computer Science 16684, 387 (2026) ISBN:978-3-032-32536-5.

[13] 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", PRX Quantum 6 2, 020330 (2025).

[14] Giovanni Acampora, Allegra Cuzzocrea, Marco Lapegna, Roberto Schiattarella, and Autilia Vitiello, 2025 International Joint Conference on Neural Networks (IJCNN) 1 (2025) ISBN:979-8-3315-1042-8.

[15] Siyuan Niu, Efekan Kökcü, Sonika Johri, Anurag Ramesh, Avimita Chatterjee, David E. Bernal Neira, Daan Camps, and Thomas Lubinski, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 375 (2025) ISBN:979-8-3315-5736-2.

[16] 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.

[17] 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).

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

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

[20] Hochang Lee, Kyung Chul Jeong, and Panjin Kim, "Quantum Circuit Optimization by Graph Coloring", Quantum 10, 1996 (2026).

[21] Meng Wang, Chenxu Liu, Samuel Stein, Yufei Ding, Poulami Das, Prashant J. Nair, and Ang Li, 2026 ACM/IEEE 53rd Annual International Symposium on Computer Architecture (ISCA) 889 (2026) ISBN:979-8-3315-5065-3.

[22] Giovanni Acampora, Allegra Cuzzocrea, Marco Lapegna, Roberto Schiattarella, and Autilia Vitiello, 2025 IEEE Symposium for Multidisciplinary Computational Intelligence Incubators (MCII) 1 (2025) ISBN:979-8-3315-0839-5.

[23] Mariia Makarova, Davide Pastorello, Valter Cavecchia, Enrico Blanzieri, Kamil Khadiev, and Alexander Rumyantsev, "Quantum Circuit Optimization Techniques: A Literature Survey", Quantum Information & Computation 26 1, 154 (2026).

[24] 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", Physical Review X 15 4, 041012 (2025).

[25] Son Dang, Youngje Son, and Brandon Kim, 2025 International Conference on Artificial Intelligence, Computer, Data Sciences and Applications (ACDSA) 1 (2025) ISBN:979-8-3315-3562-9.

[26] 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).

[27] Domenico Pomarico, Federico Dell’Anna, Riccardo Cioli, Saverio Pascazio, Francesco V. Pepe, Paolo Facchi, and Elisa Ercolessi, "Digital Rydberg simulation of dynamical quantum phase transitions in the Schwinger model", Physical Review Research 8 1, 013177 (2026).

[28] Arnaldo Rafael Camara Araujo, Ogobuchi Daniel Okey, Muhammad Saadi, Pablo Adasme, Renata Lopes Rosa, and Demóstenes Zegarra Rodríguez, "Quantum-assisted federated intelligent diagnosis algorithm with variational training supported by 5G networks", Scientific Reports 14 1, 26333 (2024).

[29] Zuoqiang Du, Xingjie Li, and Hui Li, "QELPS Algorithm: A Novel Dynamic Optimization Technology for Quantum Circuits Scheduling Engineering Problems", Applied Sciences 15 11, 6373 (2025).

[30] 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).

[31] Ben DalFavero, Rahul Sarkar, Jeremiah Rowland, Daan Camps, Nicolas P. D. Sawaya, and Ryan LaRose, "Measurement reduction for expectation values via fine-grained commutativity", Physical Review A 112 5, 052407 (2025).

[32] 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).

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

[34] Daniele Lizzio Bosco, Lukasz Cincio, Giuseppe Serra, and M. Cerezo, "Quantum Circuit Pre-Synthesis: Learning Local Edits to Reduce $T$-count", arXiv:2601.19738, (2026).

[35] Faisal Alam and Bryan K. Clark, "Learning dynamic quantum circuits for efficient state preparation", arXiv:2410.09030, (2024).

[36] Mark Webster, Stergios Koutsioumpas, and Dan E Browne, "Heuristic and Optimal Synthesis of CNOT and Clifford Circuits", arXiv:2503.14660, (2025).

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

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

[39] Nadish de Silva, Wilfred Salmon, and Ming Yin, "Fast algorithms for classical specifications of stabiliser states and Clifford gates", arXiv:2311.10357, (2023).

[40] Thierry N. Kaldenbach, Isaac D. Smith, Hendrik Poulsen Nautrup, Matthias Heller, and Hans J. Briegel, "Efficient Preparation of Resource States for Hamiltonian Simulation and Universal Quantum Computation", arXiv:2509.05404, (2025).

[41] David Winderl, Qunsheng Huang, Arianne Meijer-van de Griend, and Richie Yeung, "Architecture-Aware Synthesis of Stabilizer Circuits from Clifford Tableaus", arXiv:2309.08972, (2023).

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

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

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

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

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

[47] Jiangxue Xie, Jianan Wei, Haisong Huang, Shengwei Fu, and Ziteng Lu, "Enhanced binary grey wolf optimizer based on quantum computing and multi-strategy for feature selection on high-dimensional data classification", Chaos Solitons and Fractals 201, 117056 (2025).

[48] Richie Yeung, Aleks Kissinger, and Rob Cornish, "Equivariant Reinforcement Learning for Clifford Quantum Circuit Synthesis", arXiv:2605.10910, (2026).

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

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 04:31:11) and SAO/NASA ADS (last updated successfully 2026-08-09 16:30:11). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-10 04:31:11: Cannot retrieve data from ADS due to rate limitations.

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.