Stabilizer extent is not multiplicative

Arne Heimendahl1, Felipe Montealegre-Mora2, Frank Vallentin1, and David Gross2

1Department Mathematik/Informatik, Universität zu Köln, Weyertal 86–90, 50931 Cologne, Germany
2Institute for Theoretical Physics, Universität zu Köln, Zülpicher Str. 77, 50937 Cologne, Germany

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


The Gottesman-Knill theorem states that a Clifford circuit acting on stabilizer states can be simulated efficiently on a classical computer. Recently, this result has been generalized to cover inputs that are close to a coherent superposition of logarithmically many stabilizer states. The runtime of the classical simulation is governed by the $\textit{stabilizer extent}$, which roughly measures how many stabilizer states are needed to approximate the state. An important open problem is to decide whether the extent is multiplicative under tensor products. An affirmative answer would yield an efficient algorithm for computing the extent of product inputs, while a negative result implies the existence of more efficient classical algorithms for simulating largescale quantum circuits. Here, we answer this question in the negative. Our result follows from very general properties of the set of stabilizer states, such as having a size that scales subexponentially in the dimension, and can thus be readily adapted to similar constructions for other resource theories.

► BibTeX data

► References

[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A 70, 052328, 2004. 10.1103/​PhysRevA.70.052328.

[2] Farid Alizadeh and Donald Goldfarb. Second-order cone programming. Math. Program. 95, no. 1, Ser. B, 2003. 10.1007/​s10107-002-0339-5.

[3] Juani Bermejo-Vega, Nicolas Delfosse, Dan E. Browne, Cihan Okay, and Robert Raussendorf. Contextuality as a resource for models of quantum computation on qubits. Phys. Rev. Lett. 119, 120505, 2017. 10.1103/​PhysRevLett.119.120505.

[4] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. ISBN 0521833787. 10.1017/​CBO9780511804441.

[5] Sergei Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A 71, 022316, 2005. 10.1103/​PhysRevA.71.022316.

[6] Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by Clifford gates. Phys. Rev. Lett. 116, 250501, 2016. 10.1103/​PhysRevLett.116.250501.

[7] Sergey Bravyi, Graeme Smith, and John Smolin. Trading classical and quantum computational resources. Phys. Rev. X 6, 021043, 2016. 10.1103/​PhysRevX.6.021043.

[8] 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. 10.22331/​q-2019-09-02-181.

[9] Earl Campbell. Private communication, 2020.

[10] Jeffrey Epstein and Daniel Gottesman. Stabilizer quantum mechanics and magic state distillation. http:/​/​​PSIEssay.pdf, 2015. Masters Essay, Perimeter Institute.

[11] Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Springer, 2013. 10.1007/​978-0-8176-4948-7.

[12] Markus Frembs, Sam Roberts, and Stephen D. Bartlett. Contextuality as a resource for measurement-based quantum computation beyond qubits. New J. Phys. 20, 103011, 2018. 10.1088/​1367-2630/​aae3ad.

[13] Daniel Gottesman. The Heisenberg representation of quantum computers. Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics, eds. S. P. Corney, R. Delbourgo, and P. D. Jarvis, pp. 32-43 (Cambridge, MA, International Press), 1999. https:/​/​​abs/​quant-ph/​9807006.

[14] David Gross. Hudson's theorem for finite-dimensional quantum systems. J. Math. Phys. 47, 122107, 2006. 10.1063/​1.2393152.

[15] Arne Heimendahl. The stabilizer polytope and contextuality for qubit systems. Master's thesis, University of Cologne, 2019.

[16] Markus Heinrich and David Gross. Robustness of magic and symmetries of the stabiliser polytope. Quantum 3, 132, 2019. 10.22331/​q-2019-04-08-132.

[17] Mark Howard and Earl Campbell. Application of a resource theory for magic states to fault-tolerant quantum computing. Phys. Rev. Lett. 118, 090501, 2017. 10.1103/​PhysRevLett.118.090501.

[18] Richard Kueng and David Gross. Qubit stabilizer states are complex projective 3-designs. 2015. arXiv:1510.02767 [quant-ph].

[19] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2011. 10.1017/​CBO9780511976667.

[20] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. Estimating outcome probabilities of quantum circuits using quasiprobabilities. Phys. Rev. Lett. 115, 070501, 2015. 10.1103/​PhysRevLett.115.070501.

[21] Gábor Pataki. The geometry of semidefinite programming. In Handbook of semidefinite programming, pages 29–65. Springer, 2000. 10.1007/​978-1-4615-4381-7_3.

[22] Robert Raussendorf, Juani Bermejo-Vega, Emily Tyhurst, Cihan Okay, and Michael Zurel. Phase space simulation method for quantum computation with magic states on qubits. Phys. Rev. A 101, 012350 (2020), 2020. 10.1103/​PhysRevA.101.012350.

[23] Bartosz Regula. Convex geometry of quantum resource quantification. J. Phys. A: Math. Theor. 51, 045303, 2018. 10.1088/​1751-8121/​aa9100.

[24] James R. Seddon, Bartosz Regula, Hakop Pashayan, Yingkai Ouyang, and Earl T. Campbell. Quantifying quantum speedups: improved classical simulation from tighter magic monotones. 2020. arXiv:2002.06181 [quant-ph].

[25] Günter M. Ziegler. Lectures on Polytopes. Springer, 1995. 10.1007/​978-1-4613-8431-1.

Cited by

[1] James R. Seddon, Bartosz Regula, Hakop Pashayan, Yingkai Ouyang, and Earl T. Campbell, "Quantifying quantum speedups: improved classical simulation from tighter magic monotones", arXiv:2002.06181.

[2] Arne Heimendahl, Markus Heinrich, and David Gross, "The axiomatic and the operational approaches to resource theories of magic do not coincide", arXiv:2011.11651.

The above citations are from SAO/NASA ADS (last updated successfully 2021-04-23 07:32:26). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2021-04-23 07:32:25).