Stabilizer extent is not multiplicative

Arne Heimendahl; Felipe Montealegre-Mora; Frank Vallentin; David Gross

doi:10.22331/q-2021-02-24-400

Stabilizer extent is not multiplicative

Arne Heimendahl¹, Felipe Montealegre-Mora², Frank Vallentin¹, and David Gross²

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

Published:	2021-02-24, volume 5, page 400
Eprint:	arXiv:2007.04363v3
Doi:	https://doi.org/10.22331/q-2021-02-24-400
Citation:	Quantum 5, 400 (2021).

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

Abstract

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

@article{Heimendahl2021stabilizerextentis,
  doi = {10.22331/q-2021-02-24-400},
  url = {https://doi.org/10.22331/q-2021-02-24-400},
  title = {Stabilizer extent is not multiplicative},
  author = {Heimendahl, Arne and Montealegre-Mora, Felipe and Vallentin, Frank and Gross, David},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {400},
  month = feb,
  year = {2021}
}

► References

[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A 70, 052328, 2004. 10.1103/PhysRevA.70.052328.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1103/PhysRevLett.119.120505

[4] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. ISBN 0521833787. 10.1017/CBO9780511804441.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://jeffreymepstein.com/PSIEssay.pdf, 2015. Masters Essay, Perimeter Institute.
http://jeffreymepstein.com/PSIEssay.pdf

[11] Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Springer, 2013. 10.1007/978-0-8176-4948-7.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/quant-ph/9807006.
arXiv:quant-ph/9807006

[14] David Gross. Hudson's theorem for finite-dimensional quantum systems. J. Math. Phys. 47, 122107, 2006. 10.1063/1.2393152.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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].
arXiv:1510.02767

[19] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2011. 10.1017/CBO9780511976667.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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].
arXiv:2002.06181

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

Cited by

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

[2] Poetri Sonya Tarabunga, Emanuele Tirrito, Mari Carmen Bañuls, and Marcello Dalmonte, "Nonstabilizerness via Matrix Product States in the Pauli Basis", Physical Review Letters 133 1, 010601 (2024).

[3] M. Frau, P. S. Tarabunga, M. Collura, M. Dalmonte, and E. Tirrito, "Nonstabilizerness versus entanglement in matrix product states", Physical Review B 110 4, 045101 (2024).

[4] Saeid Ansari, Alireza Akbari, and R. Jafari, "Dynamics of steered quantum coherence and magic resource under sudden quench", Quantum Information Processing 23 6, 212 (2024).

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

[8] Emanuele Tirrito, Poetri Sonya Tarabunga, Gugliemo Lami, Titas Chanda, Lorenzo Leone, Salvatore F. E. Oliviero, Marcello Dalmonte, Mario Collura, and Alioscia Hamma, "Quantifying nonstabilizerness through entanglement spectrum flatness", Physical Review A 109 4, L040401 (2024).

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

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

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

[12] Nadish de Silva, Ming Yin, and Sergii Strelchuk, "Bases for optimising stabiliser decompositions of quantum states", Quantum Science and Technology 9 4, 045004 (2024).

[13] Beatriz Dias and Robert Koenig, "Classical simulation of non-Gaussian fermionic circuits", Quantum 8, 1350 (2024).

[14] 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, (2020).

The above citations are from Crossref's cited-by service (last updated successfully 2024-08-14 12:59:35) and SAO/NASA ADS (last updated successfully 2024-08-14 12:59:36). 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.