{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T18:18:06Z","timestamp":1772734686980,"version":"3.50.1"},"reference-count":25,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,2,24]],"date-time":"2021-02-24T00:00:00Z","timestamp":1614124800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DFG","award":["PP1798 CoSIP"],"award-info":[{"award-number":["PP1798 CoSIP"]}]},{"name":"Cluster of ExcellenceMatter and Light for Quantum Computin","award":["EXC2004\/1"],"award-info":[{"award-number":["EXC2004\/1"]}]},{"name":"EuropeanUnion\u2019s Horizon 2020 research and innovation programme under the Marie Sk\u0142odowska-Curie agreemen","award":["764759"],"award-info":[{"award-number":["764759"]}]},{"name":"Symplectic Structures in Geometry, Algebra and Dynamics","award":["SFB\/TRR 191"],"award-info":[{"award-number":["SFB\/TRR 191"]}]},{"name":"Spectral bounds in extremal discrete geometry","award":["414898050"],"award-info":[{"award-number":["414898050"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mtext class=\"MJX-tex-mathit\" mathvariant=\"italic\">stabilizer extent<\/mml:mtext><\/mml:mrow><\/mml:math>, 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.<\/jats:p>","DOI":"10.22331\/q-2021-02-24-400","type":"journal-article","created":{"date-parts":[[2021,2,24]],"date-time":"2021-02-24T10:58:09Z","timestamp":1614164289000},"page":"400","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":30,"title":["Stabilizer extent is not multiplicative"],"prefix":"10.22331","volume":"5","author":[{"given":"Arne","family":"Heimendahl","sequence":"first","affiliation":[{"name":"Department Mathematik\/Informatik, Universit\u00e4t zu K\u00f6ln, Weyertal 86\u201390, 50931 Cologne, Germany"}]},{"given":"Felipe","family":"Montealegre-Mora","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, Universit\u00e4t zu K\u00f6ln, Z\u00fclpicher Str. 77, 50937 Cologne, Germany"}]},{"given":"Frank","family":"Vallentin","sequence":"additional","affiliation":[{"name":"Department Mathematik\/Informatik, Universit\u00e4t zu K\u00f6ln, Weyertal 86\u201390, 50931 Cologne, Germany"}]},{"given":"David","family":"Gross","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, Universit\u00e4t zu K\u00f6ln, Z\u00fclpicher Str. 77, 50937 Cologne, Germany"}]}],"member":"9598","published-online":{"date-parts":[[2021,2,24]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A 70, 052328, 2004. 10.1103\/PhysRevA.70.052328.","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Farid Alizadeh and Donald Goldfarb. Second-order cone programming. Math. Program. 95, no. 1, Ser. B, 2003. 10.1007\/s10107-002-0339-5.","DOI":"10.1007\/s10107-002-0339-5"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.119.120505"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. ISBN 0521833787. 10.1017\/CBO9780511804441.","DOI":"10.1017\/CBO9780511804441"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.116.250501"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Graeme Smith, and John Smolin. Trading classical and quantum computational resources. Phys. Rev. X 6, 021043, 2016. 10.1103\/PhysRevX.6.021043.","DOI":"10.1103\/PhysRevX.6.021043"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2019-09-02-181"},{"key":"8","unstructured":"Earl Campbell. Private communication, 2020."},{"key":"9","unstructured":"Jeffrey Epstein and Daniel Gottesman. Stabilizer quantum mechanics and magic state distillation. http:\/\/jeffreymepstein.com\/PSIEssay.pdf, 2015. Masters Essay, Perimeter Institute."},{"key":"10","doi-asserted-by":"publisher","unstructured":"Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Springer, 2013. 10.1007\/978-0-8176-4948-7.","DOI":"10.1007\/978-0-8176-4948-7"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/1367-2630\/aae3ad"},{"key":"12","unstructured":"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."},{"key":"13","doi-asserted-by":"publisher","unstructured":"David Gross. Hudson's theorem for finite-dimensional quantum systems. J. Math. Phys. 47, 122107, 2006. 10.1063\/1.2393152.","DOI":"10.1063\/1.2393152"},{"key":"14","unstructured":"Arne Heimendahl. The stabilizer polytope and contextuality for qubit systems. Master's thesis, University of Cologne, 2019."},{"key":"15","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2019-04-08-132"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.118.090501"},{"key":"17","unstructured":"Richard Kueng and David Gross. Qubit stabilizer states are complex projective 3-designs. 2015. arXiv:1510.02767 [quant-ph]."},{"key":"18","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2011. 10.1017\/CBO9780511976667.","DOI":"10.1017\/CBO9780511976667"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.115.070501"},{"key":"20","doi-asserted-by":"publisher","unstructured":"G\u00e1bor Pataki. The geometry of semidefinite programming. In Handbook of semidefinite programming, pages 29\u201365. Springer, 2000. 10.1007\/978-1-4615-4381-7_3.","DOI":"10.1007\/978-1-4615-4381-7_3"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.101.012350"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Bartosz Regula. Convex geometry of quantum resource quantification. J. Phys. A: Math. Theor. 51, 045303, 2018. 10.1088\/1751-8121\/aa9100.","DOI":"10.1088\/1751-8121\/aa9100"},{"key":"23","doi-asserted-by":"crossref","unstructured":"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].","DOI":"10.1103\/PRXQuantum.2.010345"},{"key":"24","doi-asserted-by":"publisher","unstructured":"G\u00fcnter M. Ziegler. Lectures on Polytopes. Springer, 1995. 10.1007\/978-1-4613-8431-1.","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-02-24-400\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T04:30:24Z","timestamp":1619411424000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-02-24-400\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,24]]},"references-count":25,"URL":"https:\/\/doi.org\/10.22331\/q-2021-02-24-400","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,24]]},"article-number":"400"}}