quantum-computing

Heuristic and Optimal Synthesis of CNOT and Clifford Circuits

Mark Webster, Stergios Koutsioumpas, and Dan E Browne

18 min read

0 likes

⚡ Quantum Brief

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractEfficiently implementing Clifford circuits is crucial for quantum error correction and quantum algorithms. Linear reversible circuits, equivalent to circuits composed of CNOT\xspace gates, have important applications in classical computing. In this work we present methods for CNOT\xspace and general Clifford circuit synthesis which can be used to minimise either the entangling two-qubit gate count or the circuit depth. We present three families of algorithms - optimal synthesis which works on small circuits, A* synthesis for intermediate-size circuits and greedy synthesis for large circuits. We benchmark against existing methods, including rustiq, tket and qiskit and show that our approach results in circuits with lower two-qubit gate count. For encoding circuits, our methods outperform previous reinforcement learning results and find a lower two-qubit gate count circuit for the Golay code than previously known. The algorithms have been implemented in a GitHub repository for use by the classical and quantum computing community.Featured image: Here we benchmark the two-qubit gate count of our optimal, A* and greedy algorithms versus existing Clifford synthesis algorithms using 400 randomly generated Cliffords. Two-qubit gate count is in terms of the percentage reduction in gate count from Aaronson and Gottesman synthesis (higher is better).GitHub Repository Popular summaryQuantum computers process information using circuits composed of quantum gates which are analogous to logic gates in classical computing. Clifford circuits are an important circuit type with applications in quantum error correction and quantum algorithms. They can be implemented using the CNOT gate (which entangles two qubits) and the single-qubit Hadamard and phase gates. The fewer gates a circuit requires, the faster it runs and the less noise it accumulates. Reducing the number of two-qubit gates is particularly important because they are generally more prone to error and propagate errors more than single-qubit gates. Optimising the two-qubit gate count of a circuit is a difficult problem because any circuit can be decomposed into gates in an astronomically large number of ways, with very different gate counts. In this work, we develop three families of algorithms for synthesising Clifford and CNOT circuits with minimal two-qubit gate counts. For small circuits, we generate complete databases of optimal circuits using a novel mapping to graph isomorphism, running orders of magnitude faster than existing optimal synthesis methods. For intermediate circuit sizes, we introduce an A* search algorithm which finds near-optimal solutions. For large circuits, we develop a greedy algorithm based on a new vector heuristic which outperforms all publicly available alternatives. All algorithms are released as an open-source Python package.► BibTeX data@article{Webster2026heuristicoptimal, doi = {10.22331/q-2026-09-21-2212}, url = {https://doi.org/10.22331/q-2026-09-21-2212}, title = {Heuristic and {O}ptimal {S}ynthesis of {CNOT} and {C}lifford {C}ircuits}, author = {Webster, Mark and Koutsioumpas, Stergios and Browne, Dan E}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2212}, month = sep, year = {2026} }► References [1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, November 2004. ISSN 1050-2947, 1094-1622. 10.1103/PhysRevA.70.052328. https://doi.org/10.1103/PhysRevA.70.052328 [2] Timothy A. Baart et al. Single-spin CCD. Nature nanotechnology, 11 4: 330–4, 2015. 10.1038/nnano.2015.291. https://doi.org/10.1038/nnano.2015.291 [3] Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov. Clifford circuit optimization with templates and symbolic Pauli gates. Quantum, 5: 580, November 2021. ISSN 2521-327X. 10.22331/q-2021-11-16-580. https://doi.org/10.22331/q-2021-11-16-580 [4] Sergey Bravyi, Joseph A. Latone, and Dmitri Maslov. 6-qubit optimal Clifford circuits. npj Quantum Information, 8 (1): 79, July 2022. ISSN 2056-6387. 10.1038/s41534-022-00583-7. https://doi.org/10.1038/s41534-022-00583-7 [5] Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, and Jaco van de Pol. On exact sizes of minimal CNOT circuits.

In Reversible Computation: 17th International Conference, RC 2025, Odense, Denmark, July 3–4, 2025, Proceedings, page 71–88, Berlin, Heidelberg, 2025. Springer-Verlag. ISBN 978-3-031-97062-7. 10.1007/978-3-031-97063-4_6. https://doi.org/10.1007/978-3-031-97063-4_6 [6] J. I. Cirac and P. Zoller. Quantum computations with cold trapped ions. Phys. Rev. Lett., 74: 4091–4094, May 1995. 10.1103/PhysRevLett.74.4091. https://doi.org/10.1103/PhysRevLett.74.4091 [7] Timothée Goubault De Brugière et al. Gaussian elimination versus greedy methods for the synthesis of linear reversible circuits. ACM Transactions on Quantum Computing, 2 (3), September 2021. 10.1145/3474226. https://doi.org/10.1145/3474226 [8] Nicholas Fazio, Mark Webster, and Zhenyu Cai. Low-overhead magic state circuits with transversal CNOTs. 2025. 10.48550/arXiv.2501.10291. https://doi.org/10.48550/arXiv.2501.10291 [9] Timothée Goubault de Brugière, Simon Martiel, and Christophe Vuillot. A graph-state based synthesis framework for Clifford isometries. Quantum, 9: 1589, January 2025. ISSN 2521-327X. 10.22331/q-2025-01-14-1589. https://doi.org/10.22331/q-2025-01-14-1589 [10] Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4 (2): 100–107, 1968. 10.1109/TSSC.1968.300136. https://doi.org/10.1109/TSSC.1968.300136 [11] Tommi Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs.

In David Applegate et al., editors, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics, pages 135–149. SIAM, 2007. 10.1137/1.9781611972870.13. https://doi.org/10.1137/1.9781611972870.13 [12] Tommi Junttila and Petteri Kaski. Conflict propagation and component recursion for canonical labeling.

In Alberto Marchetti-Spaccamela and Michael Segal, editors, Theory and Practice of Algorithms in (Computer) Systems – First International ICST Conference, TAPAS 2011, Rome, Italy, April 18–20, 2011. Proceedings, volume 6595 of Lecture Notes in Computer Science, pages 151–162. Springer, 2011. 10.1007/978-3-642-19754-3_16. https://doi.org/10.1007/978-3-642-19754-3_16 [13] David Kielpinski, C.R. Monroe, and D.J. Wineland. Architecture for a large-scale ion-trap quantum computer. Nature, 417: 709–11, 07 2002. 10.1038/nature00784. https://doi.org/10.1038/nature00784 [14] Aleks Kissinger and John van de Wetering. PyZX: Large scale automated diagrammatic reasoning. Electronic Proceedings in Theoretical Computer Science, 318: 229–241, May 2020. ISSN 2075-2180. 10.4204/eptcs.318.14. URL http://dx.doi.org/10.4204/EPTCS.318.14. https://doi.org/10.4204/eptcs.318.14 [15] E. Knill. Quantum computing with realistically noisy devices. Nature, 434 (7029): 39–44, March 2005. ISSN 1476-4687. 10.1038/nature03350. https://doi.org/10.1038/nature03350 [16] Robert Koenig and John A. Smolin. How to efficiently select an arbitrary Clifford group element. Journal of Mathematical Physics, 55 (12): 122202, December 2014. ISSN 0022-2488, 1089-7658. 10.1063/1.4903507. https://doi.org/10.1063/1.4903507 [17] Daniel Litinski. A game of surface codes: Large-scale quantum computing with lattice surgery. Quantum, 3: 128, March 2019. ISSN 2521-327X. 10.22331/q-2019-03-05-128. https://doi.org/10.22331/q-2019-03-05-128 [18] Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, ii. Journal of Symbolic Computation, 60: 94–112, 2014. ISSN 0747-7171. 10.1016/j.jsc.2013.09.003. https://doi.org/10.1016/j.jsc.2013.09.003 [19] Tristan Meunier, Victor E. Calado, and Lieven M. K. Vandersypen. Efficient controlled-phase gate for single-spin qubits in quantum dots. Phys. Rev. B, 83: 121403, Mar 2011. 10.1103/PhysRevB.83.121403. https://doi.org/10.1103/PhysRevB.83.121403 [20] Ewan Murphy and Aleks Kissinger. Global synthesis of CNOT circuits with holes. Electronic Proceedings in Theoretical Computer Science, 384: 75–88, August 2023. ISSN 2075-2180. 10.4204/EPTCS.384.5. https://doi.org/10.4204/EPTCS.384.5 [21] O.T. O'Meara. Symplectic Groups. Mathematical Surveys and Monographs.

American Mathematical Society, 1978. ISBN 9780821815168. 10.1090/surv/016. https://doi.org/10.1090/surv/016 [22] Adam Paetznick and Ben W. Reichardt. Fault-tolerant ancilla preparation and noise threshold lower boudds for the 23-qubit golay code. Quantum Info. Comput., 12 (11–12): 1034–1080, November 2012. ISSN 1533-7146. 10.48550/arXiv.1106.2190. https://doi.org/10.48550/arXiv.1106.2190 [23] K.N. Patel, I.L. Markov, and J.P. Hayes. Optimal synthesis of linear reversible circuits. Quantum Information and Computation, 8 (3 & 4): 282–294, March 2008. ISSN 15337146, 15337146. 10.26421/QIC8.3-4-4. https://doi.org/10.26421/QIC8.3-4-4 [24] 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: 020330, May 2025. 10.1103/PRXQuantum.6.020330. https://doi.org/10.1103/PRXQuantum.6.020330 [25] Tefjol Pllaha, Kalle Volanto, and Olav Tirkkonen. Decomposition of Clifford gates. In 2021 IEEE Global Communications Conference (GLOBECOM), page 01–06, December 2021. 10.1109/GLOBECOM46510.2021.9685501. https://doi.org/10.1109/GLOBECOM46510.2021.9685501 [26] Aditya K. Prasad, Vivek V. Shende, Igor L. Markov, John P. Hayes, and Ketan N. Patel. Data structures and algorithms for simplifying reversible circuits. J. Emerg. Technol. Comput. Syst., 2 (4): 277–293, October 2006. ISSN 1550-4832. 10.1145/1216396.1216399. https://doi.org/10.1145/1216396.1216399 [27] Narayanan Rengaswamy, Robert Calderbank, Henry D. Pfister, and Swanand Kadhe. Synthesis of logical Clifford operators via symplectic geometry. In 2018 IEEE International Symposium on Information Theory (ISIT), page 791–795, Vail, CO, USA, June 2018. IEEE. ISBN 978-1-5386-4781-3. 10.1109/ISIT.2018.8437652. https://doi.org/10.1109/ISIT.2018.8437652 [28] Pedro Sales Rodriguez, John M. Robinson, Paul Niklas Jepsen, et al. Experimental demonstration of logical magic state distillation. Nature, 645: 620–625, Sep 2025. 10.1038/s41586-025-09367-3. https://doi.org/10.1038/s41586-025-09367-3 [29] Hasan Sayginel, Stergios Koutsioumpas, Mark Webster, Abhishek Rajput, and Dan E. Browne. Fault-tolerant logical clifford gates from code automorphisms. PRX Quantum, 6: 030343, Sep 2025. 10.1103/vf7v-cpq9. https://doi.org/10.1103/vf7v-cpq9 [30] Ben Schaeffer and Marek Perkowski. A cost minimization approach to synthesis of linear reversible circuits. 2014. 10.48550/arXiv.1407.0070. https://doi.org/10.48550/arXiv.1407.0070 [31] Ludwig Schmid, Tom Peham, Lucas Berent, Markus Müller, and Robert Wille. Deterministic fault-tolerant state preparation for near-term quantum error correction: Automatic synthesis using boolean satisfiability. 2025. 10.48550/arXiv.2501.05527. https://doi.org/10.48550/arXiv.2501.05527 [32] Irfansha Shaik and Jaco van de Pol. CNOT-Optimal Clifford Synthesis as SAT.

In Jeremias Berg and Jakob Nordström, editors, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025), volume 341 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:21, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-381-2. 10.4230/LIPIcs.SAT.2025.28. https://doi.org/10.4230/LIPIcs.SAT.2025.28 [33] Stephanie Simmons. Scalable fault-tolerant quantum technologies with silicon color centers. PRX Quantum, 5: 010102, Mar 2024. 10.1103/PRXQuantum.5.010102. https://doi.org/10.1103/PRXQuantum.5.010102 [34] Seyon Sivarajah et al. t|ket⟩: a retargetable compiler for NISQ devices. Quantum Science and Technology, 6 (1): 014003, nov 2020. 10.1088/2058-9565/ab8e92. https://doi.org/10.1088/2058-9565/ab8e92 [35] A. M. Steane. Simple quantum error-correcting codes. Phys. Rev. A, 54: 4741–4751, Dec 1996. 10.1103/PhysRevA.54.4741. https://doi.org/10.1103/PhysRevA.54.4741 [36] A. M. Steane. Active stabilization, quantum computation, and quantum state synthesis. Phys. Rev. Lett., 78: 2252–2255, Mar 1997. 10.1103/PhysRevLett.78.2252. https://doi.org/10.1103/PhysRevLett.78.2252 [37] Andrew M. Steane. Fast fault-tolerant filtering of quantum codewords. 2004. 10.48550/arXiv.quant-ph/0202036. https://doi.org/10.48550/arXiv.quant-ph/0202036 arXiv:quant-ph/0202036 [38] Daniel R Stromberg. treap: Python implementation of treaps. URL http://stromberg.dnsalias.org/ dstromberg/treap/. http://stromberg.dnsalias.org/~dstromberg/treap/ [39] Ewout Van Den Berg. A simple method for sampling random Clifford operators. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 54–59, 2021. 10.1109/QCE52317.2021.00021. https://doi.org/10.1109/QCE52317.2021.00021 [40] Lieven M. K. Vandersypen and Isaac L. Chuang. NMR techniques for quantum control and computation. Rev. Mod. Phys., 76: 1037–1069, Jan 2005. 10.1103/RevModPhys.76.1037. https://doi.org/10.1103/RevModPhys.76.1037 [41] Kalle Volanto. Minimizing the number of two-qubit gates in Clifford circuits. Master's thesis, Aalto University, March 2023. URL https://urn.fi/URN:NBN:fi:aalto-202303262589. https://urn.fi/URN:NBN:fi:aalto-202303262589 [42] Mark Webster. CliffordOpt: Optimisation of Clifford Circuits, May 2025. URL https://doi.org/10.5281/zenodo.21904614. https://doi.org/10.5281/zenodo.21904614 [43] Yang Xiao et al. Effective nonadiabatic holonomic swap gate with Rydberg atoms using invariant-based reverse engineering. Phys. Rev. A, 109: 062610, Jun 2024. 10.1103/PhysRevA.109.062610. https://doi.org/10.1103/PhysRevA.109.062610 [44] 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. Phys. Rev. X, 15: 041012, Oct 2025. 10.1103/gqpr-dgz7. https://doi.org/10.1103/gqpr-dgz7 [45] Miodrag Živković. Classification of small (0,1) matrices. Linear Algebra and its Applications, 414 (1): 310–346, 2006. ISSN 0024-3795. 10.1016/j.laa.2005.10.010. https://doi.org/10.1016/j.laa.2005.10.010Cited byCould not fetch Crossref cited-by data during last attempt 2026-09-21 08:23:10: Could not fetch cited-by data for 10.22331/q-2026-09-21-2212 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-09-21 08:23:10: 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. AbstractEfficiently implementing Clifford circuits is crucial for quantum error correction and quantum algorithms. Linear reversible circuits, equivalent to circuits composed of CNOT\xspace gates, have important applications in classical computing. In this work we present methods for CNOT\xspace and general Clifford circuit synthesis which can be used to minimise either the entangling two-qubit gate count or the circuit depth. We present three families of algorithms - optimal synthesis which works on small circuits, A* synthesis for intermediate-size circuits and greedy synthesis for large circuits. We benchmark against existing methods, including rustiq, tket and qiskit and show that our approach results in circuits with lower two-qubit gate count. For encoding circuits, our methods outperform previous reinforcement learning results and find a lower two-qubit gate count circuit for the Golay code than previously known. The algorithms have been implemented in a GitHub repository for use by the classical and quantum computing community.Featured image: Here we benchmark the two-qubit gate count of our optimal, A* and greedy algorithms versus existing Clifford synthesis algorithms using 400 randomly generated Cliffords. Two-qubit gate count is in terms of the percentage reduction in gate count from Aaronson and Gottesman synthesis (higher is better).GitHub Repository Popular summaryQuantum computers process information using circuits composed of quantum gates which are analogous to logic gates in classical computing. Clifford circuits are an important circuit type with applications in quantum error correction and quantum algorithms. They can be implemented using the CNOT gate (which entangles two qubits) and the single-qubit Hadamard and phase gates. The fewer gates a circuit requires, the faster it runs and the less noise it accumulates. Reducing the number of two-qubit gates is particularly important because they are generally more prone to error and propagate errors more than single-qubit gates. Optimising the two-qubit gate count of a circuit is a difficult problem because any circuit can be decomposed into gates in an astronomically large number of ways, with very different gate counts. In this work, we develop three families of algorithms for synthesising Clifford and CNOT circuits with minimal two-qubit gate counts. For small circuits, we generate complete databases of optimal circuits using a novel mapping to graph isomorphism, running orders of magnitude faster than existing optimal synthesis methods. For intermediate circuit sizes, we introduce an A* search algorithm which finds near-optimal solutions. For large circuits, we develop a greedy algorithm based on a new vector heuristic which outperforms all publicly available alternatives. All algorithms are released as an open-source Python package.► BibTeX data@article{Webster2026heuristicoptimal, doi = {10.22331/q-2026-09-21-2212}, url = {https://doi.org/10.22331/q-2026-09-21-2212}, title = {Heuristic and {O}ptimal {S}ynthesis of {CNOT} and {C}lifford {C}ircuits}, author = {Webster, Mark and Koutsioumpas, Stergios and Browne, Dan E}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2212}, month = sep, year = {2026} }► References [1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, November 2004. ISSN 1050-2947, 1094-1622. 10.1103/PhysRevA.70.052328. https://doi.org/10.1103/PhysRevA.70.052328 [2] Timothy A. Baart et al. Single-spin CCD. Nature nanotechnology, 11 4: 330–4, 2015. 10.1038/nnano.2015.291. https://doi.org/10.1038/nnano.2015.291 [3] Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov. Clifford circuit optimization with templates and symbolic Pauli gates. Quantum, 5: 580, November 2021. ISSN 2521-327X. 10.22331/q-2021-11-16-580. https://doi.org/10.22331/q-2021-11-16-580 [4] Sergey Bravyi, Joseph A. Latone, and Dmitri Maslov. 6-qubit optimal Clifford circuits. npj Quantum Information, 8 (1): 79, July 2022. ISSN 2056-6387. 10.1038/s41534-022-00583-7. https://doi.org/10.1038/s41534-022-00583-7 [5] Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, and Jaco van de Pol. On exact sizes of minimal CNOT circuits.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Heuristic and Optimal Synthesis of CNOT and Clifford Circuits

Tags

Source Information