# Robustness of Magic and Symmetries of the Stabiliser Polytope

Markus Heinrich and David Gross

Institute for Theoretical Physics, University of Cologne, 50937 Cologne, Germany

### Abstract

We give a new algorithm for computing the $\textit{robustness of magic}$ - a measure of the utility of quantum states as a computational resource. Our work is motivated by the $\textit{magic state model}$ of fault-tolerant quantum computation. In this model, all unitaries belong to the Clifford group. Non-Clifford operations are effected by injecting non-stabiliser states, which are referred to as $\textit{magic states}$ in this context. The $\textit{robustness of magic}$ measures the complexity of simulating such a circuit using a classical Monte Carlo algorithm. It is closely related to the degree negativity that slows down Monte Carlo simulations through the infamous $\textit{sign problem}$. Surprisingly, the robustness of magic is $\textit{sub}$- multiplicative. This implies that the classical simulation overhead scales subexponentially with the number of injected magic states - better than a naive analysis would suggest. However, determining the robustness of $\textit{n}$ copies of a magic state is difficult, as its definition involves a convex optimisation problem in a 4${^n}$-dimensional space. In this paper, we make use of inherent symmetries to reduce the problem to $\textit{n}$ dimensions. The total run-time of our algorithm, while still exponential in $\textit{n}$, is super-polynomially faster than previously published methods. We provide a computer implementation and give the robustness of up to 10 copies of the most commonly used magic states. Guided by the exact results, we find a finite hierarchy of approximate solutions where each level can be evaluated in polynomial time and yields rigorous upper bounds to the robustness. Technically, we use symmetries of the stabiliser polytope to connect the robustness of magic to the geometry of a low-dimensional convex polytope generated by certain $\textit{signed quantum weight enumerators}$. As a by-product, we characterised the automorphism group of the stabiliser polytope, and, more generally, of projections onto complex projective 3-designs.

### ► References

[1] D. M. Appleby, Symmetric informationally completeâpositive operator valued measures and the extended Clifford group'' Journal of Mathematical Physics 46, 052107 (2005).
https:/​/​doi.org/​10.1063/​1.1896384

[2] Christine Bachoc, Dion C. Gijswijt, Alexander Schrijver, and Frank Vallentin, Invariant semidefinite programs'' Springer US (2012).
https:/​/​doi.org/​10.1007/​978-1-4614-0769-0

[3] Stephen Boydand Lieven Vandenberghe, Convex Optimization'' Cambridge University Press (2009).
https:/​/​doi.org/​10.1017/​CBO9780511804441.007

[4] Sergey Bravyi and David Gosset, Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates'' Physical Review Letters 116, 250501 (2016).
https:/​/​doi.org/​10.1103/​PhysRevLett.116.250501

[5] 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

[6] 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

[7] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard, Simulation of quantum circuits by low-rank stabilizer decompositions'' (2018).
arXiv:1808.00128

[8] Earl T. Campbell, Barbara M. Terhal, and Christophe Vuillot, Roads towards fault-tolerant universal quantum computation'' Nature 549, 172–179 (2017).
https:/​/​doi.org/​10.1038/​nature23460
https:/​/​www.nature.com/​articles/​nature23460

[9] Cecilia Cormick, Ernesto F. Galvão, Daniel Gottesman, Juan Pablo Paz, and Arthur O. Pittenger, Classicality in discrete Wigner functions'' Physical Review A 73, 012301 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.73.012301

[10] Lars Eirik Danielsen, Database of Self-Dual Quantum Codes''.
http:/​/​www.ii.uib.no/​~larsed/​vncorbits/​

[11] Lars Eirik Danielsen and Matthew G. Parker, On the classification of all self-dual additive codes over GF(4) of length up to 12'' Journal of Combinatorial Theory, Series A 113, 1351–1367 (2006).
https:/​/​doi.org/​10.1016/​j.jcta.2005.12.004
http:/​/​www.sciencedirect.com/​science/​article/​pii/​S0097316505002347

[12] J. H. Dulá and R. V. Helgason, A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space'' European Journal of Operational Research 92, 352–367 (1996).
https:/​/​doi.org/​10.1016/​0377-2217(94)00366-1
http:/​/​www.sciencedirect.com/​science/​article/​pii/​0377221794003661

[13] Bryan Eastin and Emanuel Knill, Restrictions on Transversal Encoded Quantum Gate Sets'' Physical Review Letters 102, 110502 (2009).
https:/​/​doi.org/​10.1103/​PhysRevLett.102.110502

[14] Matthew B. Elliott, Bryan Eastin, and Carlton M. Caves, Graphical description of the action of Clifford operators on stabilizer states'' Physical Review A 77, 042307 (2008).
https:/​/​doi.org/​10.1103/​PhysRevA.77.042307

[15] D. Gross, Hudsonâs theorem for finite-dimensional quantum systems'' Journal of Mathematical Physics 47, 122107 (2006).
https:/​/​doi.org/​10.1063/​1.2393152

[16] David Gross, Sepehr Nezami, and Michael Walter, Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations'' (2017).
arXiv:1712.08628

[17] J. Gubernatis, N. Kawashima, and P. Werner, Quantum Monte Carlo Methods: Algorithms for Lattice Models'' Cambridge University Press (2016).
https:/​/​doi.org/​10.1017/​CBO9780511902581

[18] Matthew B Hastings, Superadditivity of communication capacity using entangled inputs'' Nature Physics 5, 255 (2009).
https:/​/​doi.org/​10.1038/​nphys1224

[19] M. Hein, J. Eisert, and H. J. Briegel, Multiparty entanglement in graph states'' Physical Review A 69 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.69.062311

[20] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den M. Van den Nest, and H.-J. Briegel, Entanglement in Graph States and its Applications'' (2006).
http:/​/​arxiv.org/​abs/​quant-ph/​0602096

[21] Markus Heinrich and David Gross, Robustness of Magic and Symmetries of the Stabiliser Polytope'' (2018).
arXiv:1807.10296

[22] Israel Nathan Herstein, Jordan Homomorphisms'' Transaction of the American Mathematical Society 81, 331 –341 (1956).
https:/​/​doi.org/​10.2307/​1992920

[23] Mark Howard and Earl Campbell, Application of a Resource Theory for Magic States to Fault-Tolerant Quantum Computing'' Physical Review Letters 118, 090501 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.118.090501

[24] Angela Karanjai, Joel J Wallman, and Stephen D Bartlett, Contextuality bounds the efficiency of classical simulation of quantum processes'' (2018).

[25] Richard Kueng and David Gross, Qubit stabilizer states are complex projective 3-designs'' (2015).
arXiv:1510.02767

[26] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes'' North Holland (1977).

[27] A. Mari and J. Eisert, Positive Wigner Functions Render Classical Simulation of Quantum Computation Efficient'' Physical Review Letters 109, 230503 (2012).
https:/​/​doi.org/​10.1103/​PhysRevLett.109.230503

[28] Gabriele Nebe, Eric M. Rains, and Neil J.A. Sloane, Self-Dual Codes and Invariant Theory'' Springer Science & Business Media (2006).
https:/​/​doi.org/​10.1007/​3-540-30731-1

[29] Maarten Van den M. Van den Nest, Jeroen Dehaene, and Bart De Moor, Graphical description of the action of local Clifford transformations on graph states'' Physical Review A 69 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.69.022316
http:/​/​arxiv.org/​abs/​quant-ph/​0308151

[30] Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition'' Cambridge University Press (2011).
https:/​/​doi.org/​10.1017/​CBO9780511976667

[31] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett, Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities'' Physical Review Letters 115, 070501 (2015).
https:/​/​doi.org/​10.1103/​PhysRevLett.115.070501

[32] Patrick Rall, Fractal Properties of Magic State Distillation'' (2017).
arXiv:1708.09256

[33] Patrick Rall, Signed quantum weight enumerators characterize qubit magic state distillation'' (2017).

[34] Ben W. Reichardt, Quantum universality by state distillation'' (2006).
http:/​/​arxiv.org/​abs/​quant-ph/​0608085

[35] D. Schlingemann, Stabilizer codes can be realized as graph codes'' (2001).
http:/​/​arxiv.org/​abs/​quant-ph/​0111080

[36] Victor Veitch, Christopher Ferrie, David Gross, and Joseph Emerson, Negative quasi-probability as a resource for quantum computation'' New Journal of Physics 14, 113011 (2012).
https:/​/​doi.org/​10.1088/​1367-2630/​14/​11/​113011
http:/​/​stacks.iop.org/​1367-2630/​14/​i=11/​a=113011

[37] Victor Veitch, S. A. Hamed S. A. H. Mousavian, Daniel Gottesman, and Joseph Emerson, The resource theory of stabilizer quantum computation'' New Journal of Physics 16, 013009 (2014).
https:/​/​doi.org/​10.1088/​1367-2630/​16/​1/​013009
http:/​/​stacks.iop.org/​1367-2630/​16/​i=1/​a=013009

[38] GuifrÃ© Vidal and Rolf Tarrach, Robustness of entanglement'' Physical Review A 59, 141–155 (1999).
https:/​/​doi.org/​10.1103/​PhysRevA.59.141

[39] S. Virmani, Susana F. Huelga, and Martin B. Plenio, Classical simulability, entanglement breaking, and quantum computation thresholds'' Physical Review A 71, 042328 (2005).
https:/​/​doi.org/​10.1103/​PhysRevA.71.042328

[40] Zak Webb, The Clifford Group Forms a Unitary 3-design'' Quantum Info. Comput. 16, 1379–1400 (2016).
https:/​/​doi.org/​10.26421/​QIC16.15-16
http:/​/​dl.acm.org/​citation.cfm?id=3179439.3179447

[41] Huangjun Zhu, Multiqubit Clifford groups are unitary 3-designs'' Physical Review A 96, 062336 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.96.062336

[42] Huangjun Zhu, Permutation symmetry determines the discrete Wigner function'' Physical Review Letters 116, 040501 (2016-01-26).
https:/​/​doi.org/​10.1103/​PhysRevLett.116.040501

### Cited by

[1] Zi-Wen Liu, Kaifeng Bu, and Ryuji Takagi, "One-Shot Operational Quantum Resource Theory", Physical Review Letters 123 2, 020401 (2019).

[2] Shigeo Hakkaku and Keisuke Fujii, "Comparative Study of Sampling-Based Simulation Costs of Noisy Quantum Circuits", Physical Review Applied 15 6, 064027 (2021).

[3] James R. Seddon and Earl T. Campbell, "Quantifying magic for multi-qubit operations", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475 2227, 20190251 (2019).

[4] Hammam Qassim, Joel J. Wallman, and Joseph Emerson, "Clifford recompilation for faster classical simulation of quantum circuits", arXiv:1902.02359, Quantum 3, 170 (2019).

[5] Hao Dai, Shuangshuang Fu, and Shunlong Luo, "Detecting Magic States via Characteristic Functions", International Journal of Theoretical Physics 61 2, 35 (2022).

[6] Zi-Wen Liu and Andreas Winter, "Many-Body Quantum Magic", PRX Quantum 3 2, 020333 (2022).

[7] Patrick Rall, Daniel Liang, Jeremy Cook, and William Kretschmer, "Simulation of qubit quantum circuits via Pauli propagation", Physical Review A 99 6, 062337 (2019).

[8] M. Lostaglio and A. Ciani, "Error Mitigation and Quantum-Assisted Simulation in the Error Corrected Regime", Physical Review Letters 127 20, 200506 (2021).

[9] Arne Heimendahl, Felipe Montealegre-Mora, Frank Vallentin, and David Gross, "Stabilizer extent is not multiplicative", Quantum 5, 400 (2021).

[10] Oliver Hahn, Alessandro Ferraro, Lina Hultquist, Giulia Ferrini, and Laura García-Álvarez, "Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding", Physical Review Letters 128 21, 210502 (2022).

[11] James R. Seddon, Bartosz Regula, Hakop Pashayan, Yingkai Ouyang, and Earl T. Campbell, "Quantifying Quantum Speedups: Improved Classical Simulation From Tighter Magic Monotones", PRX Quantum 2 1, 010345 (2021).

[12] Michael Zurel, Cihan Okay, and Robert Raussendorf, "Hidden Variable Model for Universal Quantum Computation with Magic States on Qubits", Physical Review Letters 125 26, 260404 (2020).

[13] Robert Raussendorf, Juani Bermejo-Vega, Emily Tyhurst, Cihan Okay, and Michael Zurel, "Phase-space-simulation method for quantum computation with magic states on qubits", Physical Review A 101 1, 012350 (2020).

[14] Markus Heinrich and David Gross, "Robustness of Magic and Symmetries of the Stabiliser Polytope", Quantum 3, 132 (2019).

[15] Xin Wang, Mark M. Wilde, and Yuan Su, "Efficiently Computable Bounds for Magic State Distillation", arXiv:1812.10145, Physical Review Letters 124 9, 090505 (2020).

[16] S Sarkar, C Mukhopadhyay, and A Bayat, "Characterization of an operational quantum resource in a critical many-body system", New Journal of Physics 22 8, 083077 (2020).

[17] Kanato Goto, Tomoki Nosaka, and Masahiro Nozaki, "Chaos by Magic", arXiv:2112.14593.

The above citations are from Crossref's cited-by service (last updated successfully 2022-05-29 06:07:50) and SAO/NASA ADS (last updated successfully 2022-05-29 06:07:51). The list may be incomplete as not all publishers provide suitable and complete citation data.