Robustness of Magic and Symmetries of the Stabiliser Polytope

Markus Heinrich; David Gross

doi:10.22331/q-2019-04-08-132

Robustness of Magic and Symmetries of the Stabiliser Polytope

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

Published:	2019-04-08, volume 3, page 132
Eprint:	arXiv:1807.10296v3
Doi:	https://doi.org/10.22331/q-2019-04-08-132
Citation:	Quantum 3, 132 (2019).

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

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.

Featured image: Illustration of the usage of symmetries in the computation of the Robustness of Magic for the single-qubit magic state H.

► BibTeX data

@article{Heinrich2019robustnessofmagic,
  doi = {10.22331/q-2019-04-08-132},
  url = {https://doi.org/10.22331/q-2019-04-08-132},
  title = {Robustness of {M}agic and {S}ymmetries of the {S}tabiliser {P}olytope},
  author = {Heinrich, Markus and Gross, David},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {3},
  pages = {132},
  month = apr,
  year = {2019}
}

► 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
https://books.google.de/books?id=KKMtDAAAQBAJ

[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] Shigeo Hakkaku and Keisuke Fujii, "Comparative Study of Sampling-Based Simulation Costs of Noisy Quantum Circuits", Physical Review Applied 15 6, 064027 (2021).

[2] 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).

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

[4] Xiaohui Li and Shunlong Luo, "Optimal diagonal qutrit gates for creating Wigner negativity", Physics Letters A 460, 128620 (2023).

[5] Xiaohui Li and Shunlong Luo, "Optimality of T-gate for generating magic resource", Communications in Theoretical Physics 75 4, 045101 (2023).

[6] Лин-Сюань Фэн, Lingxuan Feng, Шунь Лун Ло, and Shunlong Luo, "От стабилизирующих состояний к фидуциальным состояниям, задающим симметричную информационно-полную положительную операторнозначную меру", Теоретическая и математическая физика 213 3, 505 (2022).

[7] Fu Shuangshuang, Li Xiaohui, and Luo Shunlong, "Dynamics of atomic magic in the Jaynes–Cummings model", Quantum Information Processing 22 1, 7 (2022).

[8] Nikolaos Koukoulekidis, Hyukjoon Kwon, Hyejung H. Jee, David Jennings, and M. S. Kim, "Faster Born probability estimation via gate merging and frame optimisation", Quantum 6, 838 (2022).

[9] Kanato Goto, Tomoki Nosaka, and Masahiro Nozaki, "Probing chaos by magic monotones", Physical Review D 106 12, 126009 (2022).

[10] 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).

[11] 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).

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

[13] 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).

[14] Shuangshuang Fu, Xiaohui Li, and Shunlong Luo, "Detecting quantum phase transition via magic resource in the XY spin model", Physical Review A 106 6, 062405 (2022).

[15] Tobias Haug and M.S. Kim, "Scalable Measures of Magic Resource for Quantum Computers", PRX Quantum 4 1, 010301 (2023).

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

[17] Jiayu He and Shuangshuang Fu, "Renormalization of magic and quantum phase transition in spin models", Quantum Information Processing 22 3, 161 (2023).

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

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

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

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

[22] Gokul Subramanian Ravi, Pranav Gokhale, Yi Ding, William Kirby, Kaitlin Smith, Jonathan M. Baker, Peter J. Love, Henry Hoffmann, Kenneth R. Brown, and Frederic T. Chong, Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1 15 (2022) ISBN:9781450399159.

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

[24] 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).

[25] Gaurav Saxena and Gilad Gour, "Quantifying multiqubit magic channels with completely stabilizer-preserving operations", Physical Review A 106 4, 042422 (2022).

[26] J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, and I. Roth, "Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates", Communications in Mathematical Physics 397 3, 995 (2023).

[27] 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).

[28] Lingxuan Feng and Shunlong Luo, "From stabilizer states to SIC-POVM fiducial states", Theoretical and Mathematical Physics 213 3, 1747 (2022).

[29] Arne Heimendahl, Markus Heinrich, and David Gross, "The axiomatic and the operational approaches to resource theories of magic do not coincide", Journal of Mathematical Physics 63 11, 112201 (2022).

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

[31] Christophe Piveteau and David Sutter, "Circuit knitting with classical communication", arXiv:2205.00016, (2022).

[32] Lukas Brenner, Christophe Piveteau, and David Sutter, "Optimal wire cutting with classical communication", arXiv:2302.03366, (2023).

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

[34] Kanato Goto, Tomoki Nosaka, and Masahiro Nozaki, "Chaos by Magic", arXiv:2112.14593, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-05 13:21:45) and SAO/NASA ADS (last updated successfully 2023-06-05 13:21:46). 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.