Fast algorithms for classical specifications of stabiliser states and Clifford gates
1Department of Mathematics, Simon Fraser University
2Department of Applied Mathematics and Theoretical Physics, University of Cambridge
| Published: | 2025-01-08, volume 9, page 1586 |
| Editor: | Alexander Dalzell |
| Eprint: | arXiv:2311.10357v5 |
| Doi: | https://doi.org/10.22331/q-2025-01-08-1586 |
| Citation: | Quantum 9, 1586 (2025). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
The stabiliser formalism plays a central role in quantum computing, error correction, and fault tolerance. Conversions between and verifications of different specifications of stabiliser states and Clifford gates are important components of many classical algorithms in quantum information, e.g. for gate synthesis, circuit optimisation, and simulating quantum circuits. These core functions are also used in the numerical experiments critical to formulating and testing mathematical conjectures on the stabiliser formalism.
We develop novel mathematical insights concerning stabiliser states and Clifford gates that significantly clarify their descriptions. We then utilise these to provide ten new fast algorithms which offer asymptotic advantages over any existing implementations. We show how to rapidly verify that a vector is a stabiliser state, and interconvert between its specification as amplitudes, a quadratic form, and a check matrix. These methods are leveraged to rapidly check if a given unitary matrix is a Clifford gate and to interconvert between the matrix of a Clifford gate and its compact specification as a stabiliser tableau.
For example, we extract the stabiliser tableau of a $2^n \times 2^n$ matrix, promised to be a Clifford gate, in $O(n 2^n)$ time. Remarkably, it is not necessary to read all the elements of a Clifford gate matrix to extract its stabiliser tableau. This is an asymptotic speedup over the best-known method that is exponential in the number of qubits.
We provide implementations of our algorithms in $\texttt{Python}$ and $\texttt{C++}$ that exhibit vastly improved practical performance over existing algorithms in the cases where they exist.
Featured image: A table summarising the asymptotic complexities of prior and new methods for converting (off-diagonal table entries) and verifying (diagonal table entries) specifications of stabiliser states and Clifford gates. Here n is the number of qubits and $N=2^{n}$. See page 5 for a full legend.
Popular summary
They admit standard specifications (wavefunction vectors, unitary matrices) that are exponentially-sized in the number of qubits as well as more compact specifications that are polynomially-sized. Both play important roles throughout quantum information.
We clarify the mathematical relationships between these specifications and given ten new algorithms that interconvert between different specifications and confirm the validity of a given specification. These have theoretical and practical applications within areas such as gate and circuit synthesis, quantum complexity theory, classical simulation algorithms, and mathematical investigations into the stabiliser formalism.
We provide implementations of our algorithms in Python and C++ that exhibit vastly improved practical performance over existing algorithms in the cases where they exist. These practical advantages are of some orders of magnitude for small cases; we prove asymptotic complexity separations that ensure our advantages grow substantially for larger cases.
► BibTeX data
► References
[1] Scott Aaronsonand Alex Arkhipov ``The computational complexity of linear optics'' STOC '11 333-342 (2011).
https://doi.org/10.1145/1993636.1993682
[2] Scott Aaronsonand Daniel Gottesman ``Improved simulation of stabilizer circuits'' Physical Review A 70, 052328 (2004).
https://doi.org/10.1103/physreva.70.052328
[3] Matthew Amy Personal communication (2024).
[4] Matthew Amy, Owen Bennett-Gibbs, and Neil J. Ross, ``Symbolic Synthesis of Clifford Circuits and Beyond'' EPTCS 394, 343–362 (2023).
https://doi.org/10.4204/EPTCS.394.17
arXiv:2204.14205
[5] Matthew Amy, Dmitri Maslov, and Michele Mosca, ``Polynomial-time T-depth optimization of Clifford+ T circuits via matroid partitioning'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 1476–1489 (2014).
https://doi.org/10.1109/tcad.2014.2341953
[6] Simon Andersand Hans J Briegel ``Fast simulation of stabilizer circuits using a graph-state representation'' Physical Review A 73, 022334 (2006).
https://doi.org/10.1103/physreva.73.022334
[7] Koenraad MR Audenaertand Martin B Plenio ``Entanglement on mixed stabilizer states: normal forms and reduction procedures'' New Journal of Physics 7, 170 (2005).
https://doi.org/10.1088/1367-2630/7/1/170
[8] Niel de Beaudrapand Steven Herbert ``Fast stabiliser simulation with quadratic form expansions'' Quantum 6, 803 (2022).
https://doi.org/10.22331/q-2022-09-15-803
[9] John S Bell ``On the Einstein-Podolsky-Rosen paradox'' Physics Physique Fizika 1, 195 (1964).
https://doi.org/10.1103/PhysicsPhysiqueFizika.1.195
[10] Charles H Bennettand Gilles Brassard ``Quantum cryptography: Public key distribution and coin tossing'' IEEE ICSSP (1984).
https://doi.org/10.1016/j.tcs.2014.05.025
[11] Charles H Bennettand Stephen J Wiesner ``Communication via one-and two-particle operators on Einstein-Podolsky-Rosen states'' Physical Review Letters 69, 2881 (1992).
https://doi.org/10.1103/PhysRevLett.69.2881
[12] Charles H Bennett, Herbert J Bernstein, Sandu Popescu, and Benjamin Schumacher, ``Concentrating partial entanglement by local operations'' Physical Review A 53, 2046 (1996).
https://doi.org/10.1103/PhysRevA.53.2046
[13] Charles H Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K Wootters, ``Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels'' Physical Review Letters 70, 1895 (1993).
https://doi.org/10.1103/PhysRevLett.70.1895
[14] Ethan Bernsteinand Umesh Vazirani ``Quantum complexity theory'' STOC '25 11–20 (1993).
https://doi.org/10.1145/167088.167097
[15] James R. Bitner, Gideon Ehrlich, and Edward M. Reingold, ``Efficient generation of the binary reflected Gray code and its applications'' Commun. ACM 19, 517–521 (1976).
https://doi.org/10.1145/360336.360343
[16] Sergey Bravyiand Jeongwan Haah ``Magic-state distillation with low overhead'' Physical Review A 86, 052329 (2012).
https://doi.org/10.1103/physreva.86.052329
[17] Sergey Bravyiand 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
[18] Sergey Bravyi, Graeme Smith, and John A Smolin, ``Trading classical and quantum computational resources'' Physical Review X 6, 021043 (2016).
https://doi.org/10.1103/PhysRevX.6.021043
[19] 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
[20] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard, ``Simulation of quantum circuits by low-rank stabilizer decompositions'' Quantum 3, 181 (2019).
https://doi.org/10.22331/q-2019-09-02-181
[21] Timothée Goubault de Brugière, Simon Martiel, and Christophe Vuillot, ``A graph-state based synthesis framework for Clifford isometries'' arXiv preprint (2022).
https://doi.org/10.48550/arXiv.2212.06928
arXiv:2212.06928
[22] Alexander Cowtan, Will Simmons, and Ross Duncan, ``A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz'' (2020).
https://doi.org/10.48550/arXiv.2007.10515
arXiv:2007.10515
[23] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, ``Quantum algorithms: A survey of applications and end-to-end complexities'' arXiv preprint (2023).
https://doi.org/10.48550/arXiv.2310.03011
arXiv:2310.03011
[24] Ninnat Dangniam, Yun-Guang Han, and Huangjun Zhu, ``Optimal verification of stabilizer states'' Physical Review Research 2 (2020).
https://doi.org/10.1103/physrevresearch.2.043323
[25] Jeroen Dehaeneand Bart De Moor ``Clifford group, stabilizer states, and linear and quadratic operations over GF(2)'' Physical Review A 68, 042318 (2003).
https://doi.org/10.1103/PhysRevA.68.042318
[26] David Deutschand Richard Jozsa ``Rapid solution of problems by quantum computation'' Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439, 553–558 (1992).
https://doi.org/10.1098/rspa.1992.0167
[27] Bryan Eastinand Emanuel Knill ``Restrictions on transversal encoded quantum gate sets'' Physical Review Letters 102, 110502 (2009).
https://doi.org/10.1103/physrevlett.102.110502
[28] Craig Gidney ``Stim: a fast stabilizer circuit simulator'' Quantum 5, 497 (2021).
https://doi.org/10.22331/q-2021-07-06-497
[29] Daniel Gottesman ``An introduction to quantum error correction and fault-tolerant quantum computation'' Quantum information science and its contributions to mathematics, Proceedings of Symposia in Applied Mathematics 68, 13–58 (2010).
https://doi.org/10.1090/psapm/068/2762145
[30] Daniel Gottesman ``Stabilizer Codes and Quantum Error Correction'' thesis (1997).
https://doi.org/10.48550/arXiv.quant-ph/9705052
[31] Daniel Gottesman ``The Heisenberg representation of quantum computers'' 22nd International Colloquium on Group Theoretical Methods in Physics 32–43 (1998).
[32] Daniel M Greenberger, Michael A Horne, Abner Shimony, and Anton Zeilinger, ``Bell’s theorem without inequalities'' American Journal of Physics 58, 1131–1143 (1990).
https://doi.org/10.1119/1.16243
[33] 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).
https://doi.org/10.1038/s41567-020-0932-7
[34] Richard Jozsaand Maarten Van den Nest ``Classical simulation complexity of extended Clifford circuits'' Quantum Information and Computation 14, 633–648 (2014).
https://doi.org/10.26421/qic14.7-8-7
[35] Vadym Kliuchnikov, Michael Beverland, and Adam Paetznick, ``Stabilizer circuit verification'' arXiv preprint (2023).
https://doi.org/10.48550/arXiv.2309.08676
arXiv:2309.08676
[36] Vadym Kliuchnikovand Sebastian Schönnenbeck ``Stabilizer operators and Barnes-Wall lattices'' arXiv preprint (2024).
https://doi.org/10.48550/arXiv.2404.17677
arXiv:2404.17677
[37] 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, 012307 (2008).
https://doi.org/10.1103/PhysRevA.77.012307
[38] Shane Mansfield Personal communication (2023).
[39] Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov, ``Automated optimization of large quantum circuits with continuous parameters'' npj Quantum Information 4 (2018).
https://doi.org/10.1038/s41534-018-0072-4
[40] Xiaotong Ni, Oliver Buerschaper, and Maarten Van den Nest, ``A non-commuting stabilizer formalism'' Journal of Mathematical Physics 56 (2015).
https://doi.org/10.1063/1.4920923
[41] Qiskit contributors ``Qiskit: An Open-source Framework for Quantum Computing'' (2023).
https://doi.org/10.5281/zenodo.2573505
[42] Robert Raussendorfand Hans J Briegel ``Quantum computing via measurements only'' arXiv preprint quant-ph/0010033 (2000).
https://doi.org/10.48550/arXiv.quant-ph/0010033
[43] Nadish de Silva ``Efficient quantum gate teleportation in higher dimensions'' Proceedings of the Royal Society A 477, 20200865 (2021).
https://doi.org/10.1098/rspa.2020.0865
[44] Daniel R Simon ``On the power of quantum computation'' SIAM Journal on Computing 26, 1474–1483 (1997).
https://doi.org/10.1137/S0097539796298637
[45] Kaitlin N Smith, Michael A Perlin, Pranav Gokhale, Paige Frederick, David Owusu-Antwi, Richard Rines, Victory Omole, and Frederic Chong, ``Clifford-based circuit cutting for quantum simulation'' Proceedings of the 50th Annual International Symposium on Computer Architecture 1–13 (2023).
https://doi.org/10.1145/3579371.3589352
[46] StackExchange ``How do I check if a gate represented by unitary $U$ is a Clifford Gate?'' (2020) https://quantumcomputing.stackexchange.com/questions/13157/how-do-i-check-if-a-gate-represented-by-unitary-u-is-a-clifford-gate.
https://quantumcomputing.stackexchange.com/questions/13157/how-do-i-check-if-a-gate-represented-by-unitary-u-is-a-clifford-gate
[47] StackExchange ``How to verify whether a state is a stabilizer state?'' (2018) https://quantumcomputing.stackexchange.com/questions/3861/how-to-verify-whether-a-state-is-a-stabilizer-state.
https://quantumcomputing.stackexchange.com/questions/3861/how-to-verify-whether-a-state-is-a-stabilizer-state
[48] G.I. Struchalin, Ya. A. Zagorovskii, E.V. Kovlakov, S.S. Straupe, and S.P. Kulik, ``Experimental Estimation of Quantum State Properties from Classical Shadows'' PRX Quantum 2, 010307 (2021).
https://doi.org/10.1103/PRXQuantum.2.010307
[49] Quantum AI teamand collaborators ``qsim'' (2021).
https://doi.org/10.5281/zenodo.5544365
[50] Stephen Wiesner ``Conjugate coding'' ACM Sigact News 15, 78–88 (1983).
https://doi.org/10.1145/1008908.1008920
[51] Pei Zeng, You Zhou, and Zhenhuan Liu, ``Quantum gate verification and its application in property testing'' Phys. Rev. Res. 2, 023306 (2020).
https://doi.org/10.1103/PhysRevResearch.2.023306
[52] Fang Zhangand Jianxin Chen ``Optimizing T gates in Clifford+T circuit as $\pi/4$ rotations around Paulis'' (2019).
https://doi.org/10.48550/arXiv.1903.12456
arXiv:1903.12456
Cited by
[1] Mahendra Kumar Das, Payal Bhardwaj, Bishnu Kumar, Swapan Kumar Ghorai, and Rajesh Kumar Lal, "Fault-Tolerant Quantum Communication Systems Using Clifford Hierarchy-based CSS Codes", (2026).
[2] Michael Zurel, Lawrence Z. Cohen, and Robert Raussendorf, "Simulation of quantum computation with magic states via Jordan-Wigner transformations", Physical Review A 112 4, 042602 (2025).
[3] Sergi Masot-Llima, Piotr Sierant, Paolo Stornati, and Artur Garcia-Saez, "Limits of Clifford disentangling in tensor network states", Physical Review B 114 2, 024311 (2026).
[4] Vincenzo Lipardi, Domenica Dibenedetto, Georgios Stamoulis, Evert van Nieuwenburg, and Mark H M Winands, "Nonstabilizerness estimation using graph neural networks", Machine Learning: Science and Technology 7 2, 025027 (2026).
[5] Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, and Ewin Tang, "Learning the closest product state", arXiv:2411.04283, (2024).
[6] Nadish de Silva, Ming Yin, and Sergii Strelchuk, "Bases for optimising stabiliser decompositions of quantum states", Quantum Science and Technology 9 4, 045004 (2024).
[7] Vadym Kliuchnikov and Sebastian Schönnenbeck, "Stabilizer operators and Barnes-Wall lattices", arXiv:2404.17677, (2024).
[8] Fernando Lima and Arcesio Castañeda Medina, "Clifford and Non-Clifford Splitting in Quantum Circuits: Applications and ZX-Calculus Detection Procedure", arXiv:2504.16004, (2025).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 14:41:32) and SAO/NASA ADS (last updated successfully 2026-08-10 14:41:43). 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.