A graph-state based synthesis framework for Clifford isometries

Timothée Goubault de Brugière; Simon Martiel; Christophe Vuillot

doi:10.22331/q-2025-01-14-1589

A graph-state based synthesis framework for Clifford isometries

Timothée Goubault de Brugière¹, Simon Martiel², and Christophe Vuillot¹

¹Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
²Atos Quantum Lab, Les Clayes-sous-Bois, France

Published:	2025-01-14, volume 9, page 1589
Editor:	Yongshan Ding
Eprint:	arXiv:2212.06928v2
Doi:	https://doi.org/10.22331/q-2025-01-14-1589
Citation:	Quantum 9, 1589 (2025).

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

Abstract

We tackle the problem of Clifford isometry compilation, i.e, how to synthesize a Clifford isometry into an executable quantum circuit. We propose a simple framework for synthesis that only exploits the elementary properties of the Clifford group and one equation of the symplectic group. We highlight the versatility of our framework by showing that several normal forms of the literature are natural corollaries. We recover the state of the art two-qubit gate depth necessary for the execution of a Clifford circuit on an LNN architecture, concomitantly with another work. We also propose practical synthesis algorithms for Clifford isometries with a focus on Clifford operators, graph states and codiagonalization of Pauli rotations. Benchmarks show that in all three cases we improve the 2-qubit gate count and depth of random instances compared to the state-of-the-art methods. We also improve the execution of practical quantum chemistry experiments.

► BibTeX data

@article{GoubaultdeBrugiere2025graphstatebased,
  doi = {10.22331/q-2025-01-14-1589},
  url = {https://doi.org/10.22331/q-2025-01-14-1589},
  title = {A graph-state based synthesis framework for {C}lifford isometries},
  author = {Goubault de Brugi{\`{e}}re, Timoth{\'{e}}e and Martiel, Simon and Vuillot, Christophe},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1589},
  month = jan,
  year = {2025}
}

► References

[1] Daniel Gottesman. ``Stabilizer codes and quantum error correction''. PhD thesis. Caltech. (1997).

[2] E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland. ``Randomized benchmarking of quantum gates''. Phys. Rev. A 77, 012307 (2008).
https://doi.org/10.1103/PhysRevA.77.012307

[3] Easwar Magesan, J. M. Gambetta, and Joseph Emerson. ``Scalable and robust randomized benchmarking of quantum processes''. Phys. Rev. Lett. 106, 180504 (2011).
https://doi.org/10.1103/PhysRevLett.106.180504

[4] Sergey Bravyi and Alexei Kitaev. ``Universal quantum computation with ideal clifford gates and noisy ancillas''. Phys. Rev. A 71, 022316 (2005). url: https://doi.org/10.1103/PhysRevA.71.022316.
https://doi.org/10.1103/PhysRevA.71.022316

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

[6] Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters. ``Mixed-state entanglement and quantum error correction''. Phys. Rev. A 54, 3824–3851 (1996).
https://doi.org/10.1103/PhysRevA.54.3824

[7] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Phys. Rev. A 70, 052328 (2004).
https://doi.org/10.1103/PhysRevA.70.052328

[8] Daniel Gottesman. ``The heisenberg representation of quantum computers'' (1998). url: https://arxiv.org/abs/quant-ph/9807006.
arXiv:quant-ph/9807006

[9] P.W. Shor. ``Fault-tolerant quantum computation''. In Proceedings of 37th Conference on Foundations of Computer Science. Pages 56–65. (1996).
https://doi.org/10.1109/SFCS.1996.548464

[10] John Preskill. ``Fault-tolerant quantum computation''. In Introduction to quantum computation and information. Pages 213–269. World Scientific (1998).
https://doi.org/10.1142/9789812385253_0008

[11] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[12] Riccardo Manenti, Eyob A Sete, Angela Q Chen, Shobhan Kulshreshtha, Jen-Hao Yeh, Feyza Oruc, Andrew Bestwick, Mark Field, Keith Jackson, and Stefano Poletto. ``Full control of superconducting qubits with combined on-chip microwave and flux lines''. Applied Physics Letters 119, 144001 (2021).
https://doi.org/10.1063/5.0065517

[13] Jerry M. Chow, Jay M. Gambetta, Easwar Magesan, David W. Abraham, Andrew W. Cross, B. R. Johnson, Nicholas A. Masluk, Colm A. Ryan, John A. Smolin, Srikanth J. Srinivasan, and M. Steffen. ``Implementing a strand of a scalable fault-tolerant quantum computing fabric''. Nature Communications 5, 4015 (2014).
https://doi.org/10.1038/ncomms5015

[14] Christopher Chamberland, Guanyu Zhu, Theodore J. Yoder, Jared B. Hertzberg, and Andrew W. Cross. ``Topological and Subsystem Codes on Low-Degree Graphs with Flag Qubits''. Physical Review X 10, 011022 (2020).
https://doi.org/10.1103/PhysRevX.10.011022

[15] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5

[16] John van de Wetering. ``Constructing quantum circuits with global gates''. New Journal of Physics 23, 043015 (2021).
https://doi.org/10.1088/1367-2630/abf1b3

[17] Dmitri Maslov and Yunseong Nam. ``Use of global interactions in efficient quantum circuit constructions''. New Journal of Physics 20, 033018 (2018).
https://doi.org/10.1088/1367-2630/aaa398

[18] Simon Martiel and Timothée Goubault de Brugière. ``Architecture aware compilation of quantum circuits via lazy synthesis''. Quantum 6, 729 (2022).
https://doi.org/10.22331/q-2022-06-07-729

[19] Dmitri Maslov and Martin Roetteler. ``Shorter stabilizer circuits via bruhat decomposition and quantum circuit transformations''. IEEE Trans. Inf. Theory 64, 4729–4738 (2018).
https://doi.org/10.1109/TIT.2018.2825602

[20] 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).
https://doi.org/10.22331/q-2020-06-04-279

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

[22] Marc Bataille. ``Reduced quantum circuits for stabilizer states and graph states'' (2021). url: https://arxiv.org/abs/2107.00885.
arXiv:2107.00885

[23] Maarten Van den Nest. ``Classical simulation of quantum computation, the gottesman-knill theorem, and slightly beyond''. Quantum Inf. Comput. 10, 258–271 (2010).
https://doi.org/10.26421/QIC10.3-4-6

[24] Héctor J. García, Igor L. Markov, and Andrew W. Cross. ``On the geometry of stabilizer states''. Quantum Inf. Comput. 14, 683–720 (2014).
https://doi.org/10.26421/QIC14.7-8-9

[25] Matthew Amy, Parsiad Azimzadeh, and Michele Mosca. ``On the controlled-NOT complexity of controlled-NOT–phase circuits''. Quantum Science and Technology 4, 015002 (2018).
https://doi.org/10.1088/2058-9565/aad8ca

[26] Vivien Vandaele, Simon Martiel, and Timothée Goubault de Brugière. ``Phase polynomials synthesis algorithms for nisq architectures and beyond''. Quantum Science and Technology 7, 045027 (2022).
https://doi.org/10.1088/2058-9565/ac5a0e

[27] Sergey Bravyi, Joseph A Latone, and Dmitri Maslov. ``6-qubit optimal clifford circuits''. npj Quantum Information 8, 79 (2022).
https://doi.org/10.1038/s41534-022-00583-7

[28] Sarah Schneider, Lukas Burgholzer, and Robert Wille. ``A SAT encoding for optimal clifford circuit synthesis''. In Atsushi Takahashi, editor, Proceedings of the 28th Asia and South Pacific Design Automation Conference, ASPDAC 2023, Tokyo, Japan, January 16-19, 2023. Pages 190–195. ACM (2023).
https://doi.org/10.1145/3566097.3567929

[29] Tom Peham, Nina Brandl, Richard Kueng, Robert Wille, and Lukas Burgholzer. ``Depth-optimal synthesis of clifford circuits with SAT solvers''. In Brian La Cour, Lia Yeh, and Marek Osinski, editors, IEEE International Conference on Quantum Computing and Engineering, QCE 2023, Bellevue, WA, USA, September 17-22, 2023. Pages 802–813. IEEE (2023).
https://doi.org/10.1109/QCE57702.2023.00095

[30] Vadym Kliuchnikov and Dmitri Maslov. ``Optimization of clifford circuits''. Phys. Rev. A 88, 052307 (2013).
https://doi.org/10.1103/PhysRevA.88.052307

[31] Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov. ``Clifford Circuit Optimization with Templates and Symbolic Pauli Gates''. Quantum 5, 580 (2021).
https://doi.org/10.22331/q-2021-11-16-580

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

[33] Sergey Bravyi and Jeongwan Haah. ``Magic-state distillation with low overhead''. Physical Review A 86, 052329 (2012).
https://doi.org/10.1103/PhysRevA.86.052329

[34] Dmitri Maslov and Willers Yang. ``Cnot circuits need little help to implement arbitrary hadamard-free clifford transformations they generate''. npj Quantum Information 9, 96 (2023).
https://doi.org/10.1038/s41534-023-00760-2

[35] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. ``Graphical description of the action of local clifford transformations on graph states''. Phys. Rev. A 69, 022316 (2004).
https://doi.org/10.1103/PhysRevA.69.022316

[36] Samuel A. Kutin, David Petrie Moulton, and Lawren Smithline. ``Computation at a distance''. Chicago J. Theor. Comput. Sci. 2007 (2007).
https://doi.org/10.4086/cjtcs.2007.001

[37] Timothée Goubault de Brugière, Marc Baboulin, Benoı̂t Valiron, Simon Martiel, and Cyril Allouche. ``Quantum CNOT circuits synthesis for NISQ architectures using the syndrome decoding problem''. In Ivan Lanese and Mariusz Rawski, editors, Reversible Computation - 12th International Conference, RC 2020, Oslo, Norway, July 9-10, 2020, Proceedings. Volume 12227 of Lecture Notes in Computer Science, pages 189–205. Springer (2020).
https://doi.org/10.1007/978-3-030-52482-1_11

[38] Timothée Goubault de Brugière, Marc Baboulin, Benoı̂t Valiron, Simon Martiel, and Cyril Allouche. ``Decoding techniques applied to the compilation of CNOT circuits for NISQ architectures''. Sci. Comput. Program. 214, 102726 (2022).
https://doi.org/10.1016/J.SCICO.2021.102726

[39] Timothée Goubault de Brugière, Marc Baboulin, Benoît Valiron, Simon Martiel, and Cyril Allouche. ``Reducing the depth of linear reversible quantum circuits''. IEEE Transactions on Quantum Engineering 2, 1–22 (2021).
https://doi.org/10.1109/TQE.2021.3091648

[40] Cristopher Moore and Martin Nilsson. ``Parallel quantum computation and quantum codes''. SIAM J. Comput. 31, 799–815 (2001).
https://doi.org/10.1137/S0097539799355053

[41] Alexander Cowtan, Will Simmons, and Ross Duncan. ``A generic compilation strategy for the unitary coupled cluster ansatz'' (2020). url: https://arxiv.org/abs/2007.10515.
arXiv:2007.10515

[42] Dmitri Maslov and Ben Zindorf. ``Depth optimization of cz, cnot, and clifford circuits''. IEEE Transactions on Quantum Engineering 3, 1–8 (2022).
https://doi.org/10.1109/tqe.2022.3180900

Cited by

[1] Tristan Cam, Cyril Gavoille, Yvan Le Borgne, and Simon Martiel, Lecture Notes in Computer Science 15716, 54 (2025) ISBN:978-3-031-97062-7.

[2] Timothée Goubault de Brugière and Simon Martiel, "Faster and shorter synthesis of Hamiltonian simulation circuits", arXiv:2404.03280, (2024).

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

[4] Ayushi Dubal, David Kremer, Simon Martiel, Victor Villar, Derek Wang, and Juan Cruz-Benito, "Pauli Network Circuit Synthesis with Reinforcement Learning", arXiv:2503.14448, (2025).

[5] Vivien Vandaele, Simon Martiel, Simon Perdrix, and Christophe Vuillot, "Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences", arXiv:2302.07040, (2023).

[6] Nadish de Silva, Wilfred Salmon, and Ming Yin, "Fast algorithms for classical specifications of stabiliser states and Clifford gates", Quantum 9, 1586 (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-18 02:01:35) and SAO/NASA ADS (last updated successfully 2026-08-18 02:01:41). 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.