{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T15:46:10Z","timestamp":1773848770276,"version":"3.50.1"},"reference-count":52,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T00:00:00Z","timestamp":1736294400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["RGPIN-2022-03103"],"award-info":[{"award-number":["RGPIN-2022-03103"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSERC-European Commission","award":["FoQaCiA"],"award-info":[{"award-number":["FoQaCiA"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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<\/mml:mn>n<\/mml:mi><\/mml:msup>&#x00D7;<\/mml:mo>2<\/mml:mn>n<\/mml:mi><\/mml:msup><\/mml:math> matrix, promised to be a Clifford gate, in O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>2<\/mml:mn>n<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:math> 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 Python<\/mml:mtext><\/mml:mrow><\/mml:math> and C++<\/mml:mtext><\/mml:mrow><\/mml:math> that exhibit vastly improved practical performance over existing algorithms in the cases where they exist.<\/jats:p>","DOI":"10.22331\/q-2025-01-08-1586","type":"journal-article","created":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T18:14:36Z","timestamp":1736360076000},"page":"1586","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":3,"title":["Fast algorithms for classical specifications of stabiliser states and Clifford gates"],"prefix":"10.22331","volume":"9","author":[{"given":"Nadish","family":"de Silva","sequence":"first","affiliation":[{"name":"Department of Mathematics, Simon Fraser University"}]},{"given":"Wilfred","family":"Salmon","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Theoretical Physics, University of Cambridge"}]},{"given":"Ming","family":"Yin","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Simon Fraser University"}]}],"member":"9598","published-online":{"date-parts":[[2025,1,8]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Scott Aaronsonand Alex Arkhipov ``The computational complexity of linear optics'' STOC '11 333-342 (2011).","DOI":"10.1145\/1993636.1993682"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Scott Aaronsonand Daniel Gottesman ``Improved simulation of stabilizer circuits'' Physical Review A 70, 052328 (2004).","DOI":"10.1103\/physreva.70.052328"},{"key":"2","unstructured":"Matthew Amy Personal communication (2024)."},{"key":"3","doi-asserted-by":"publisher","unstructured":"Matthew Amy, Owen Bennett-Gibbs, and Neil J. Ross, ``Symbolic Synthesis of Clifford Circuits and Beyond'' EPTCS 394, 343\u2013362 (2023).","DOI":"10.4204\/EPTCS.394.17"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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\u20131489 (2014).","DOI":"10.1109\/tcad.2014.2341953"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Simon Andersand Hans J Briegel ``Fast simulation of stabilizer circuits using a graph-state representation'' Physical Review A 73, 022334 (2006).","DOI":"10.1103\/physreva.73.022334"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Koenraad MR Audenaertand Martin B Plenio ``Entanglement on mixed stabilizer states: normal forms and reduction procedures'' New Journal of Physics 7, 170 (2005).","DOI":"10.1088\/1367-2630\/7\/1\/170"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Niel de Beaudrapand Steven Herbert ``Fast stabiliser simulation with quadratic form expansions'' Quantum 6, 803 (2022).","DOI":"10.22331\/q-2022-09-15-803"},{"key":"8","doi-asserted-by":"publisher","unstructured":"John S Bell ``On the Einstein-Podolsky-Rosen paradox'' Physics Physique Fizika 1, 195 (1964).","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Charles H Bennettand Gilles Brassard ``Quantum cryptography: Public key distribution and coin tossing'' IEEE ICSSP (1984).","DOI":"10.1016\/j.tcs.2014.05.025"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Charles H Bennettand Stephen J Wiesner ``Communication via one-and two-particle operators on Einstein-Podolsky-Rosen states'' Physical Review Letters 69, 2881 (1992).","DOI":"10.1103\/PhysRevLett.69.2881"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Charles H Bennett, Herbert J Bernstein, Sandu Popescu, and Benjamin Schumacher, ``Concentrating partial entanglement by local operations'' Physical Review A 53, 2046 (1996).","DOI":"10.1103\/PhysRevA.53.2046"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Charles H Bennett, Gilles Brassard, Claude Cr\u00e9peau, 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).","DOI":"10.1103\/PhysRevLett.70.1895"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Ethan Bernsteinand Umesh Vazirani ``Quantum complexity theory'' STOC '25 11\u201320 (1993).","DOI":"10.1145\/167088.167097"},{"key":"14","doi-asserted-by":"publisher","unstructured":"James R. Bitner, Gideon Ehrlich, and Edward M. Reingold, ``Efficient generation of the binary reflected Gray code and its applications'' Commun. ACM 19, 517\u2013521 (1976).","DOI":"10.1145\/360336.360343"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Sergey Bravyiand Jeongwan Haah ``Magic-state distillation with low overhead'' Physical Review A 86, 052329 (2012).","DOI":"10.1103\/physreva.86.052329"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Sergey Bravyiand Alexei Kitaev ``Universal quantum computation with ideal Clifford gates and noisy ancillas'' Physical Review A 71, 022316 (2005).","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Graeme Smith, and John A Smolin, ``Trading classical and quantum computational resources'' Physical Review X 6, 021043 (2016).","DOI":"10.1103\/PhysRevX.6.021043"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov, ``Clifford circuit optimization with templates and symbolic Pauli gates'' Quantum 5, 580 (2021).","DOI":"10.22331\/q-2021-11-16-580"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.22331\/q-2019-09-02-181"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Timoth\u00e9e Goubault de Brugi\u00e8re, Simon Martiel, and Christophe Vuillot, ``A graph-state based synthesis framework for Clifford isometries'' arXiv preprint (2022).","DOI":"10.48550\/arXiv.2212.06928"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Alexander Cowtan, Will Simmons, and Ross Duncan, ``A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz'' (2020).","DOI":"10.48550\/arXiv.2007.10515"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, Andr\u00e1s Gily\u00e9n, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brand\u00e3o, ``Quantum algorithms: A survey of applications and end-to-end complexities'' arXiv preprint (2023).","DOI":"10.48550\/arXiv.2310.03011"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Ninnat Dangniam, Yun-Guang Han, and Huangjun Zhu, ``Optimal verification of stabilizer states'' Physical Review Research 2 (2020).","DOI":"10.1103\/physrevresearch.2.043323"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Jeroen Dehaeneand Bart De Moor ``Clifford group, stabilizer states, and linear and quadratic operations over GF(2)'' Physical Review A 68, 042318 (2003).","DOI":"10.1103\/PhysRevA.68.042318"},{"key":"25","doi-asserted-by":"publisher","unstructured":"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\u2013558 (1992).","DOI":"10.1098\/rspa.1992.0167"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Bryan Eastinand Emanuel Knill ``Restrictions on transversal encoded quantum gate sets'' Physical Review Letters 102, 110502 (2009).","DOI":"10.1103\/physrevlett.102.110502"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Craig Gidney ``Stim: a fast stabilizer circuit simulator'' Quantum 5, 497 (2021).","DOI":"10.22331\/q-2021-07-06-497"},{"key":"28","doi-asserted-by":"publisher","unstructured":"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\u201358 (2010).","DOI":"10.1090\/psapm\/068\/2762145"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman ``Stabilizer Codes and Quantum Error Correction'' thesis (1997).","DOI":"10.48550\/arXiv.quant-ph\/9705052"},{"key":"30","unstructured":"Daniel Gottesman ``The Heisenberg representation of quantum computers'' 22nd International Colloquium on Group Theoretical Methods in Physics 32\u201343 (1998)."},{"key":"31","doi-asserted-by":"publisher","unstructured":"Daniel M Greenberger, Michael A Horne, Abner Shimony, and Anton Zeilinger, ``Bell\u2019s theorem without inequalities'' American Journal of Physics 58, 1131\u20131143 (1990).","DOI":"10.1119\/1.16243"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Hsin-Yuan Huang, Richard Kueng, and John Preskill, ``Predicting many properties of a quantum system from very few measurements'' Nature Physics 16, 1050\u20131057 (2020).","DOI":"10.1038\/s41567-020-0932-7"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Richard Jozsaand Maarten Van den Nest ``Classical simulation complexity of extended Clifford circuits'' Quantum Information and Computation 14, 633\u2013648 (2014).","DOI":"10.26421\/qic14.7-8-7"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Vadym Kliuchnikov, Michael Beverland, and Adam Paetznick, ``Stabilizer circuit verification'' arXiv preprint (2023).","DOI":"10.48550\/arXiv.2309.08676"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Vadym Kliuchnikovand Sebastian Sch\u00f6nnenbeck ``Stabilizer operators and Barnes-Wall lattices'' arXiv preprint (2024).","DOI":"10.48550\/arXiv.2404.17677"},{"key":"36","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.77.012307"},{"key":"37","unstructured":"Shane Mansfield Personal communication (2023)."},{"key":"38","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/s41534-018-0072-4"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Xiaotong Ni, Oliver Buerschaper, and Maarten Van den Nest, ``A non-commuting stabilizer formalism'' Journal of Mathematical Physics 56 (2015).","DOI":"10.1063\/1.4920923"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Qiskit contributors ``Qiskit: An Open-source Framework for Quantum Computing'' (2023).","DOI":"10.5281\/zenodo.2573505"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Robert Raussendorfand Hans J Briegel ``Quantum computing via measurements only'' arXiv preprint quant-ph\/0010033 (2000).","DOI":"10.48550\/arXiv.quant-ph\/0010033"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Nadish de Silva ``Efficient quantum gate teleportation in higher dimensions'' Proceedings of the Royal Society A 477, 20200865 (2021).","DOI":"10.1098\/rspa.2020.0865"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Daniel R Simon ``On the power of quantum computation'' SIAM Journal on Computing 26, 1474\u20131483 (1997).","DOI":"10.1137\/S0097539796298637"},{"key":"44","doi-asserted-by":"publisher","unstructured":"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\u201313 (2023).","DOI":"10.1145\/3579371.3589352"},{"key":"45","unstructured":"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."},{"key":"46","unstructured":"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."},{"key":"47","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.2.010307"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Quantum AI teamand collaborators ``qsim'' (2021).","DOI":"10.5281\/zenodo.5544365"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Stephen Wiesner ``Conjugate coding'' ACM Sigact News 15, 78\u201388 (1983).","DOI":"10.1145\/1008908.1008920"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Pei Zeng, You Zhou, and Zhenhuan Liu, ``Quantum gate verification and its application in property testing'' Phys. Rev. Res. 2, 023306 (2020).","DOI":"10.1103\/PhysRevResearch.2.023306"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Fang Zhangand Jianxin Chen ``Optimizing T gates in Clifford+T circuit as $\\pi\/4$ rotations around Paulis'' (2019).","DOI":"10.48550\/arXiv.1903.12456"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-01-08-1586\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T18:14:47Z","timestamp":1736360087000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-01-08-1586\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,8]]},"references-count":52,"URL":"https:\/\/doi.org\/10.22331\/q-2025-01-08-1586","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,8]]},"article-number":"1586"}}