{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T18:15:51Z","timestamp":1780424151619,"version":"3.54.1"},"reference-count":52,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T00:00:00Z","timestamp":1578873600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Investigating the classical simulability of quantum circuits provides a promising avenue towards understanding the computational power of quantum systems. Whether a class of quantum circuits can be efficiently simulated with a probabilistic classical computer, or is provably hard to simulate, depends quite critically on the precise notion of ``classical simulation'' and in particular on the required accuracy. We argue that a notion of classical simulation, which we call EPSILON-simulation (or<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03f5<\/mml:mi><\/mml:math>-simulation for short), captures the essence of possessing ``equivalent computational power'' as the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03f5<\/mml:mi><\/mml:math>-simulator from one possessing the simulated quantum system. We relate<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03f5<\/mml:mi><\/mml:math>-simulation to various alternative notions of simulation predominantly focusing on a simulator we call a<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\">poly-box<\/mml:mtext><\/mml:mrow><\/mml:math>. A poly-box outputs<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>1<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mi>p<\/mml:mi><mml:mi>o<\/mml:mi><mml:mi>l<\/mml:mi><mml:mi>y<\/mml:mi><\/mml:math>precision additive estimates of Born probabilities and marginals. This notion of simulation has gained prominence through a number of recent simulability results. Accepting some plausible computational theoretic assumptions, we show that<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03f5<\/mml:mi><\/mml:math>-simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03f5<\/mml:mi><\/mml:math>-simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution (<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\">poly-sparsity<\/mml:mtext><\/mml:mrow><\/mml:math>).<\/jats:p>","DOI":"10.22331\/q-2020-01-13-223","type":"journal-article","created":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T16:41:57Z","timestamp":1578933717000},"page":"223","source":"Crossref","is-referenced-by-count":30,"title":["From estimation of quantum probabilities to simulation of quantum circuits"],"prefix":"10.22331","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3782-7602","authenticated-orcid":false,"given":"Hakop","family":"Pashayan","sequence":"first","affiliation":[{"name":"Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Sydney, NSW 2006, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4387-670X","authenticated-orcid":false,"given":"Stephen D.","family":"Bartlett","sequence":"additional","affiliation":[{"name":"Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Sydney, NSW 2006, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Gross","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, University of Cologne, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2020,1,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"R. P. Feynman, ``Simulating Physics with Computers,'' Int. J. Theor. Phys., 21, 467-488 (1982).","DOI":"10.1007\/BF02650179"},{"key":"1","doi-asserted-by":"publisher","unstructured":"S. Aaronson and D. Gottesman, ``Improved simulation of stabilizer circuits,'' Phys. Rev. A, 70, 052328 (2004).","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"2","doi-asserted-by":"publisher","unstructured":"L. G. Valiant, ``Quantum circuits that can be simulated classically in polynomial time,'' SIAM Journal on Computing, 31, 1229-1254 (2002).","DOI":"10.1137\/S0097539700377025"},{"key":"3","doi-asserted-by":"publisher","unstructured":"B. M. Terhal and D. P. DiVincenzo, ``Classical simulation of noninteracting-fermion quantum circuits,'' Phys. Rev. A 65, 032325 (2002).","DOI":"10.1103\/PhysRevA.65.032325"},{"key":"4","doi-asserted-by":"publisher","unstructured":"S. D. Bartlett, B. C. Sanders, S. L. Braunstein, and K. Nemoto, ``Efficient classical simulation of continuous variable quantum information processes,'' Phys. Rev. Lett. 88, 097904 (2002).","DOI":"10.1103\/PhysRevLett.88.097904"},{"key":"5","doi-asserted-by":"publisher","unstructured":"L. Gurvits, ``On the complexity of mixed discriminants and related problems,'' in: Jedrzejowicz J., Szepietowski A. (eds) Mathematical Foundations of Computer Science 2005. MFCS 2005. Lecture Notes in Computer Science, vol 3618. Springer, Berlin, Heidelberg (2005).","DOI":"10.1007\/11549345_39"},{"key":"6","doi-asserted-by":"publisher","unstructured":"S. Aaronson and A. Arkhipov, ``The computational complexity of linear optics,'' in Proceedings of the forty-third annual ACM symposium on Theory of computing, 333-342, ACM (2011).","DOI":"10.1145\/1993636.1993682"},{"key":"7","doi-asserted-by":"publisher","unstructured":"M. J. Bremner, R. Jozsa, and D. J. Shepherd, ``Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,'' Proc. R. Soc. A 467, (2010).","DOI":"10.1098\/rspa.2010.0301"},{"key":"8","doi-asserted-by":"publisher","unstructured":"M. J. Bremner, A. Montanaro, and D. J. Shepherd, ``Average-case complexity versus approximate simulation of commuting quantum computations,'' Phys. Rev. Lett. 117, 080501 (2016).","DOI":"10.1103\/PhysRevLett.117.080501"},{"key":"9","doi-asserted-by":"publisher","unstructured":"X. Gao, S.-T. Wang, and L.-M. Duan, ``Quantum supremacy for simulating a translation-invariant Ising spin model,'' Phys. Rev. Lett. 118, 040502 (2017).","DOI":"10.1103\/PhysRevLett.118.040502"},{"key":"10","doi-asserted-by":"publisher","unstructured":"J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, ``Architectures for quantum simulation showing a quantum speedup,'' Phys. Rev. X 8, 021010 (2018).","DOI":"10.1103\/PhysRevX.8.021010"},{"key":"11","unstructured":"B. Fefferman and C. Umans, ``The power of quantum fourier sampling,'' arXiv preprint arXiv:1507.05592, (2015)."},{"key":"12","doi-asserted-by":"publisher","unstructured":"T. Morimae, K. Fujii, and J. F. Fitzsimons, ``Hardness of classically simulating the one-clean-qubit model,'' Phys. Rev. Lett. 112, 130502 (2014).","DOI":"10.1103\/PhysRevLett.112.130502"},{"key":"13","doi-asserted-by":"publisher","unstructured":"T. Morimae, K. Fujii, and H. Nishimura, ``Power of one nonclean qubit,'' Phys. Rev. A 95, 042336 (2017).","DOI":"10.1103\/PhysRevA.95.042336"},{"key":"14","doi-asserted-by":"publisher","unstructured":"S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, ``Characterizing quantum supremacy in near-term devices,'' Nature Phys. 14, 595-600 (2018).","DOI":"10.1038\/s41567-018-0124-x"},{"key":"15","doi-asserted-by":"publisher","unstructured":"A. Bouland, J. F. Fitzsimons, and D. E. Koh, ``Complexity Classification of Conjugated Clifford Circuits,'' in 33rd Computational Complexity Conference (CCC 2018) (R. A. Servedio, ed.), vol. 102 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Germany), pp. 21:1-21:25, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.","DOI":"10.4230\/LIPIcs.CCC.2018.21"},{"key":"16","doi-asserted-by":"publisher","unstructured":"D. J. Brod, ``Efficient classical simulation of matchgate circuits with generalized inputs and measurements,'' Phys. Rev. A 93, 062332 (2016).","DOI":"10.1103\/PhysRevA.93.062332"},{"key":"17","doi-asserted-by":"publisher","unstructured":"R. Jozsa and A. Miyake, ``Matchgates and classical simulation of quantum circuits,'' Proc. R. Soc. A 464, 3089-3106 (2008).","DOI":"10.1098\/rspa.2008.0189"},{"key":"18","doi-asserted-by":"publisher","unstructured":"V. Veitch, C. Ferrie, D. Gross, and J. Emerson, ``Negative quasi-probability as a resource for quantum computation,'' New J. Phys. 14, 113011 (2012).","DOI":"10.1088\/1367-2630\/14\/11\/113011"},{"key":"19","doi-asserted-by":"publisher","unstructured":"V. Veitch, N. Wiebe, C. Ferrie, and J. Emerson, ``Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation,'' New J. Phys. 15, 013037 (2013).","DOI":"10.1088\/1367-2630\/15\/1\/013037"},{"key":"20","doi-asserted-by":"publisher","unstructured":"A. Mari and J. Eisert, ``Positive Wigner functions render classical simulation of quantum computation efficient,'' Phys. Rev. Lett. 109, 230503 (2012).","DOI":"10.1103\/PhysRevLett.109.230503"},{"key":"21","doi-asserted-by":"publisher","unstructured":"S. Bravyi and D. Gosset, ``Improved classical simulation of quantum circuits dominated by Clifford gates,'' Phys. Rev. Lett. 116, 250501 (2016).","DOI":"10.1103\/PhysRevLett.116.250501"},{"key":"22","doi-asserted-by":"publisher","unstructured":"R. S. Bennink, E. M. Ferragut, T. S. Humble, J. A. Laska, J. J. Nutaro, M. G. Pleszkoch, and R. C. Pooser, ``Unbiased simulation of near-Clifford quantum circuits,'' Phys. Rev. A 95, 062337 (2017).","DOI":"10.1103\/PhysRevA.95.062337"},{"key":"23","doi-asserted-by":"publisher","unstructured":"M. J. Bremner, A. Montanaro, and D. J. Shepherd, ``Achieving quantum supremacy with sparse and noisy commuting quantum computations,'' Quantum 1, 8 (2017).","DOI":"10.22331\/q-2017-04-25-8"},{"key":"24","doi-asserted-by":"publisher","unstructured":"M. Oszmaniec and D. J. Brod, ``Classical simulation of photonic linear optics with lost particles,'' New J. Phys. 20, 092002 (2018).","DOI":"10.1088\/1367-2630\/aadfa8"},{"key":"25","doi-asserted-by":"publisher","unstructured":"M. Howard and E. Campbell, ``Application of a resource theory for magic states to fault-tolerant quantum computing,'' Phys. Rev. Lett. 118, 090501 (2017).","DOI":"10.1103\/PhysRevLett.118.090501"},{"key":"26","doi-asserted-by":"publisher","unstructured":"H. Pashayan, J. J. Wallman, and S. D. Bartlett, ``Estimating outcome probabilities of quantum circuits using quasiprobabilities,'' Phys. Rev. Lett. 115, 070501 (2015).","DOI":"10.1103\/PhysRevLett.115.070501"},{"key":"27","doi-asserted-by":"crossref","unstructured":"M. Van Den Nest, ``Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups,'' arXiv preprint arXiv:1201.4867, 2012.","DOI":"10.26421\/QIC13.11-12-7"},{"key":"28","unstructured":"J. Bermejo-Vega and M. Van Den Nest, ``Classical simulations of Abelian-group normalizer circuits with intermediate measurements,'' Quantum Info. Comput. 14, 181-216 (2014)."},{"key":"29","unstructured":"M. Schwarz and M. Van Den Nest, ``Simulating quantum circuits with sparse output distributions,'' arXiv preprint arXiv:1310.6749, 2013."},{"key":"30","doi-asserted-by":"publisher","unstructured":"S. Bravyi, G. Smith, and J. A. Smolin, ``Trading classical and quantum computational resources,'' Phys. Rev. X, 6, 021043 (2016).","DOI":"10.1103\/PhysRevX.6.021043"},{"key":"31","doi-asserted-by":"publisher","unstructured":"K. Temme, S. Bravyi, and J. M. Gambetta, ``Error mitigation for short-depth quantum circuits,'' Phys. Rev. Lett. 119, 180509 (2017).","DOI":"10.1103\/PhysRevLett.119.180509"},{"key":"32","unstructured":"M. Van Den Nest, ``Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond,'' Quantum Info. Comput. 10, 258-271 (2010)."},{"key":"33","doi-asserted-by":"publisher","unstructured":"R. Jozsa and N. Linden, ``On the role of entanglement in quantum-computational speed-up,'' Proc. R. Soc. A 459, 2011-2032 (2003).","DOI":"10.1098\/rspa.2002.1097"},{"key":"34","unstructured":"B. M. Terhal and D. P. DiVincenzo, ``Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games,'' Quantum Info. Comput. 4, 134-145 (2004)."},{"key":"35","doi-asserted-by":"publisher","unstructured":"T. Morimae, ``Hardness of classically sampling the one-clean-qubit model with constant total variation distance error,'' Phys. Rev. A 96, 040302 (2017).","DOI":"10.1103\/PhysRevA.96.040302"},{"key":"36","doi-asserted-by":"publisher","unstructured":"S. Aaronson, ``The equivalence of sampling and searching,'' Theory of Computing Systems, 55, 281-298 (2014).","DOI":"10.1007\/s00224-013-9527-3"},{"key":"37","unstructured":"M. Van Den Nest, ``Simulating quantum computers with probabilistic methods,'' Quantum Info. Comput. 11, 784-812 (2011)."},{"key":"38","unstructured":"D. Shepherd, ``Binary matroids and quantum probability distributions,'' arXiv preprint arXiv:1005.1744, (2010)."},{"key":"39","doi-asserted-by":"publisher","unstructured":"S. Bravyi and A. Kitaev, ``Universal quantum computation with ideal clifford gates and noisy ancillas,'' Phys. Rev. A 71, 022316 (2005).","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"40","unstructured":"R. Jozsa and M. Van Den Nest, ``Classical simulation complexity of extended Clifford circuits,'' Quantum Info. Comput. 14, 633-648 (2014)."},{"key":"41","doi-asserted-by":"publisher","unstructured":"L. A. Goldberg and H. Guo, ``The complexity of approximating complex-valued Ising and Tutte partition functions,'' comput. complex. 26, 765-833 (2017).","DOI":"10.1007\/s00037-017-0162-2"},{"key":"42","doi-asserted-by":"publisher","unstructured":"G. Kuperberg, ``How hard is it to approximate the Jones polynomial?,'' Theory of Computing, 11, 183-219 (2015).","DOI":"10.4086\/toc.2015.v011a006"},{"key":"43","doi-asserted-by":"publisher","unstructured":"K. Fujii and T. Morimae, ``Commuting quantum circuits and complexity of Ising partition functions,'' New J. Phys. 19, 033003 (2017).","DOI":"10.1088\/1367-2630\/aa5fdb"},{"key":"44","doi-asserted-by":"publisher","unstructured":"D. Stahlke, ``Quantum interference as a resource for quantum speedup,'' Phys. Rev. A 90, 022302 (2014).","DOI":"10.1103\/PhysRevA.90.022302"},{"key":"45","doi-asserted-by":"publisher","unstructured":"D. Shepherd and M. J. Bremner, ``Temporally unstructured quantum computation,'' Proc. R. Soc. A 465, 1413-1439 (2009).","DOI":"10.1098\/rspa.2008.0443"},{"key":"46","unstructured":"D. J. Shepherd, ``Quantum complexity: restrictions on algorithms and architectures,'' arXiv preprint arXiv:1005.1425 (2010)."},{"key":"47","doi-asserted-by":"publisher","unstructured":"D. Vertigan, ``Bicycle dimension and special points of the Tutte polynomial,'' J. Combin. Theory Ser. B 74, 378-396 (1998).","DOI":"10.1006\/jctb.1998.1860"},{"key":"48","doi-asserted-by":"publisher","unstructured":"R. Renner and S. Wolf, ``Smooth R\u00e9nyi entropy and applications,'' in International Symposium on Information Theory, 2004. ISIT 2004. Proceedings., pp. 233 (2004).","DOI":"10.1109\/ISIT.2004.1365269"},{"key":"49","doi-asserted-by":"publisher","unstructured":"L. Stockmeyer, ``The complexity of approximate counting,'' in Proceedings of the fifteenth annual ACM symposium on Theory of computing, pp. 118-126, ACM, (1983).","DOI":"10.1145\/800061.808740"},{"key":"50","doi-asserted-by":"publisher","unstructured":"S. Toda, ``PP is as hard as the polynomial-time hierarchy,'' SIAM Journal on Computing 20, 865-877 (1991).","DOI":"10.1137\/0220053"},{"key":"51","unstructured":"S. Aaronson and T. Hance, ``Generalizing and derandomizing Gurvits's approximation algorithm for the permanent,'' Quantum Info. Comput. 14, 541-559 (2014)."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-01-13-223\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T01:04:05Z","timestamp":1665450245000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-01-13-223\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,13]]},"references-count":52,"URL":"https:\/\/doi.org\/10.22331\/q-2020-01-13-223","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,13]]},"article-number":"223"}}