Clifford Circuit Optimization with Templates and Symbolic Pauli Gates

Sergey Bravyi1, Ruslan Shaydulin2, Shaohan Hu3, and Dmitri Maslov1

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

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


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

► References

[1] https:/​/​​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.

[3] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5), November 2004. 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.

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

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

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

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

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

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

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

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

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

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

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

[17] IBM. IBM Quantum Experience. last accessed 11/​9/​2020. URL https:/​/​​.

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

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

[20] Emanuel Knill. Quantum computing with realistically noisy devices. Nature, 434 (7029): 39–44, 2005. 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.

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

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

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

[25] Michael A. Nielsen and Isaac Chuang. Quantum computation and quantum information. 2002. 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.

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

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

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

Cited by

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

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

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

[4] Matthew DeCross, Eli Chertkov, Megan Kohagen, and Michael Foss-Feig, "Qubit-reuse compilation with mid-circuit measurement and reset", arXiv:2210.08039, (2022).

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

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

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

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

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

[10] Willers Yang and Patrick Rall, "Improved Synthesis of Clifford Circuits using Long-Range CAT States", arXiv:2302.06537, (2023).

[11] Luca Mondada and Pablo Andrés-Martínez, "The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits", arXiv:2302.06717, (2023).

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

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-08 14:42:32) and SAO/NASA ADS (last updated successfully 2023-06-08 14:42:33). The list may be incomplete as not all publishers provide suitable and complete citation data.