# Robustness of Magic and Symmetries of the Stabiliser Polytope

Markus Heinrich and David Gross

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

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] C. Bachoc, D. C. Gijswijt, A. Schrijver, and F. Vallentin, Invariant semidefinite programs'' Springer US (2012).
https:/​/​doi.org/​10.1007/​978-1-4614-0769-0

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

[4] S. Bravyi and D. 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] S. Bravyi and A. 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] S. Bravyi, G. Smith, and J. A. Smolin, Trading Classical and Quantum Computational Resources'' Physical Review X 6, 021043 (2016).
https:/​/​doi.org/​10.1103/​PhysRevX.6.021043

[7] S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, Simulation of quantum circuits by low-rank stabilizer decompositions'' (2018).
arXiv:1808.00128
http:/​/​arxiv.org/​abs/​1808.00128

[8] E. T. Campbell, B. M. Terhal, and C. Vuillot, Roads towards fault-tolerant universal quantum computation'' Nature 549, 172-179 (2017).
https:/​/​doi.org/​10.1038/​nature23460

[9] C. Cormick, E. F. Galvão, D. Gottesman, J. P. Paz, and A. O. Pittenger, Classicality in discrete Wigner functions'' Physical Review A 73, 012301 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.73.012301

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

[11] L. E. Danielsen and M. G. Parker, On the classification of all self-dual additive codes over GF'' Journal of Combinatorial Theory, Series A 113, 1351-1367 (2006).
https:/​/​doi.org/​10.1016/​j.jcta.2005.12.004

[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

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

[14] M. B. Elliott, B. Eastin, and C. 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] D. Gross, S. Nezami, and M. Walter, Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations'' (2017).
arXiv:1712.08628
http:/​/​arxiv.org/​abs/​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] M. 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 Nest, and H.-J. Briegel, Entanglement in Graph States and its Applications'' (2006).
arXiv:quant-ph/0602096
http:/​/​arxiv.org/​abs/​quant-ph/​0602096

[21] M. Heinrich and D. Gross, Robustness of Magic and Symmetries of the Stabiliser Polytope'' (2018).
arXiv:1807.10296
http:/​/​arxiv.org/​abs/​1807.10296

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

[23] M. Howard and E. 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] A. Karanjai, J. J. Wallman, and S. D. Bartlett, Contextuality bounds the efficiency of classical simulation of quantum processes'' (2018).
arXiv:arXiv:1802.07744

[25] R. Kueng and D. Gross, Qubit stabilizer states are complex projective 3-designs'' (2015).
arXiv:1510.02767
http:/​/​arxiv.org/​abs/​1510.02767

[26] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes'' North Holland (1977).
https:/​/​doi.org/​0.1137/​1022103

[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] G. Nebe, E. M. Rains, and N. J. A. Sloane, Self-Dual Codes and Invariant Theory'' Springer Science & Business Media (2006).
https:/​/​doi.org/​10.1007/​3-540-30731-1

[29] M. Van den Nest, J. Dehaene, and B. 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

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

[31] H. Pashayan, J. J. Wallman, and S. 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] P. Rall, Fractal Properties of Magic State Distillation'' (2017).
arXiv:1708.09256
http:/​/​arxiv.org/​abs/​1708.09256

[33] P. Rall, Signed quantum weight enumerators characterize qubit magic state distillation'' (2017).
arXiv:arXiv:1702.06990

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

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

[36] V. Veitch, C. Ferrie, D. Gross, and J. 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

[37] V. Veitch, S. A. H. Mousavian, D. Gottesman, and J. 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

[38] G. Vidal and R. Tarrach, Robustness of entanglement'' Physical Review A 59, 141-155 (1999).
https:/​/​doi.org/​10.1103/​PhysRevA.59.141

[39] S. Virmani, S. F. Huelga, and M. 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] Z. Webb, The Clifford Group Forms a Unitary 3-design'' Quantum Info. Comput. 16, 1379-1400 (2016).
https:/​/​doi.org/​10.26421/​QIC16.15-16

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

[42] H. 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] James R. Seddon and Earl T. Campbell, "Quantifying magic for multi-qubit operations", arXiv:1901.03322, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475 2227, 20190251 (2019).

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

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

[5] Xin Wang, Mark M. Wilde, and Yuan Su, "Efficiently computable bounds for magic state distillation", arXiv:1812.10145.

[6] Robert Raussendorf, Juani Bermejo-Vega, Emily Tyhurst, Cihan Okay, and Michael Zurel, "Phase space simulation method for quantum computation with magic states on qubits", arXiv:1905.05374.

The above citations are from Crossref's cited-by service (last updated 2019-08-18 11:16:08) and SAO/NASA ADS (last updated 2019-08-18 11:16:09). The list may be incomplete as not all publishers provide suitable and complete citation data.