{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T09:39:03Z","timestamp":1784367543769,"version":"3.55.0"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"7671","license":[{"start":{"date-parts":[[2017,9,1]],"date-time":"2017-09-01T00:00:00Z","timestamp":1504224000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nature"],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1038\/nature23458","type":"journal-article","created":{"date-parts":[[2017,9,12]],"date-time":"2017-09-12T16:12:17Z","timestamp":1505232737000},"page":"203-209","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":669,"title":["Quantum computational supremacy"],"prefix":"10.1038","volume":"549","author":[{"given":"Aram W.","family":"Harrow","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashley","family":"Montanaro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,9,14]]},"reference":[{"key":"BFnature23458_CR1","unstructured":"Preskill, J. Quantum computing and the entanglement frontier. Preprint at http:\/\/arXiv.org\/abs\/1203.5813 (2012)"},{"key":"BFnature23458_CR2","unstructured":"Papadimitriou, C. Computational Complexity (Addison-Wesley, 1994)"},{"key":"BFnature23458_CR3","doi-asserted-by":"crossref","unstructured":"Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In Proc. 35th Ann. Symp. on the Foundations of Computer Science (ed. Goldwasser, S. ) 124\u2013134 (IEEE Computer Society, 1994)","DOI":"10.1109\/SFCS.1994.365700"},{"key":"BFnature23458_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1103\/RevModPhys.86.153","volume":"86","author":"I Georgescu","year":"2014","unstructured":"Georgescu, I., Ashhab, S. & Nori, F. Quantum simulation. Rev. Mod. Phys. 86, 153 (2014)","journal-title":"Rev. Mod. Phys."},{"key":"BFnature23458_CR5","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1038\/nphys2275","volume":"8","author":"JI Cirac","year":"2012","unstructured":"Cirac, J. I. & Zoller, P. Goals and opportunities in quantum simulation. Nat. Phys. 8, 264\u2013266 (2012)","journal-title":"Nat. Phys."},{"key":"BFnature23458_CR6","doi-asserted-by":"crossref","unstructured":"H\u00e4aner, T., Roetteler, M. & Svore, K. Factoring using 2n + 2 qubits with Toffoli based modular multiplication. Preprint at http:\/\/arXiv.org\/abs\/1611.07995 (2016)","DOI":"10.26421\/QIC17.7-8-7"},{"key":"BFnature23458_CR7","doi-asserted-by":"publisher","first-page":"1260","DOI":"10.1126\/science.aag3349","volume":"353","author":"LW Cheuk","year":"2016","unstructured":"Cheuk, L. W. et al. Observation of spatial charge and spin correlations in the 2D Fermi-Hubbard model. Science 353, 1260\u20131264 (2016)","journal-title":"Science"},{"key":"BFnature23458_CR8","first-page":"134","volume":"4","author":"BM Terhal","year":"2004","unstructured":"Terhal, B. M. & DiVincenzo, D. P. Adaptive quantum computation, constant-depth quantum circuits and Arthur-Merlin games. Quantum Inf. Comput. 4, 134\u2013145 (2004). This paper gave the first complexity-theoretic argument that a simple class of quantum circuits should be hard to simulate classically","journal-title":"Quantum Inf. Comput."},{"key":"BFnature23458_CR9","doi-asserted-by":"publisher","first-page":"143","DOI":"10.4086\/toc.2013.v009a004","volume":"9","author":"S Aaronson","year":"2013","unstructured":"Aaronson, S. & Arkhipov, A. The computational complexity of linear optics. Theory Comput. 9, 143\u2013252 (2013). This seminal paper introduced the boson sampling problem","journal-title":"Theory Comput."},{"key":"BFnature23458_CR10","doi-asserted-by":"publisher","first-page":"1413","DOI":"10.1098\/rspa.2008.0443","volume":"465","author":"D Shepherd","year":"2009","unstructured":"Shepherd, D. & Bremner, M. J. Temporally unstructured quantum computation. Proc. R. Soc. A 465, 1413\u20131439 (2009)","journal-title":"Proc. R. Soc. A"},{"key":"BFnature23458_CR11","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1098\/rspa.2010.0301","volume":"467","author":"MJ Bremner","year":"2010","unstructured":"Bremner, M. J ., Jozsa, R. & Shepherd, D. J. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. Lond. A 467, 459\u2013472 (2010). This paper gave evidence that instantaneous quantum polynomial-time (IQP) circuits are hard to simulate classically","journal-title":"Proc. R. Soc. Lond. A"},{"key":"BFnature23458_CR12","unstructured":"Boixo, S. et al. Characterizing quantum supremacy in near-term devices. Preprint at http:\/\/arXiv.org\/abs\/1608.00263 (2016). This paper described a proposal for a near-term quantum-supremacy experiment"},{"key":"BFnature23458_CR13","doi-asserted-by":"crossref","unstructured":"Lund, A., Bremner, M. & Ralph, T. Quantum sampling problems, BosonSampling and quantum supremacy. Preprint at http:\/\/arXiv.org\/abs\/1702.03061 (2017)","DOI":"10.1038\/s41534-017-0018-2"},{"key":"BFnature23458_CR14","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R. & Paturi, R. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"BFnature23458_CR15","unstructured":"Cheeseman, P., Kanefsky, B. & Taylor, W. Where the really hard problems are. In Proc. 12th Int. Joint Conf. on Artificial Intelligence (IJCAI \u201991) (eds Mylopoulos, J. & Reiter, R. ) 331\u2013337 (Morgan Kaufmann, 1991)"},{"key":"BFnature23458_CR16","first-page":"340","volume":"28","author":"S Mertens","year":"2006","unstructured":"Mertens, S., M\u00e9zard, M. & Zecchina, R. Threshold values of random k-SAT from the cavity method. Random Struct. Algorithms 28, 340\u2013373 (2006)","journal-title":"Threshold values of random k-SAT from the cavity method. Random Struct. Algorithms"},{"key":"BFnature23458_CR17","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"LA Levin","year":"1986","unstructured":"Levin, L. A. Average case complete problems. SIAM J. Comput. 15, 285\u2013286 (1986)","journal-title":"SIAM J. Comput."},{"key":"BFnature23458_CR18","doi-asserted-by":"publisher","first-page":"080501","DOI":"10.1103\/PhysRevLett.117.080501","volume":"117","author":"MJ Bremner","year":"2016","unstructured":"Bremner, M. J., Montanaro, A. & Shepherd, D. J. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature23458_CR19","doi-asserted-by":"publisher","first-page":"040502","DOI":"10.1103\/PhysRevLett.118.040502","volume":"118","author":"X Gao","year":"2017","unstructured":"Gao, X., Wang, S.-T. & Duan, L.-M. Quantum supremacy for simulating a translation-invariant Ising spin model. Phys. Rev. Lett. 118, 040502 (2017)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature23458_CR20","unstructured":"Aaronson, S. & Chen, L. Complexity-theoretic foundations of quantum supremacy experiments. Preprint at http:\/\/arXiv.org\/abs\/1612.05903 (2016)"},{"key":"BFnature23458_CR21","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1126\/science.279.5349.342","volume":"279","author":"E Knill","year":"1998","unstructured":"Knill, E., Laflamme, R. & Zurek, W. Resilient quantum computation. Science 279, 342\u2013345 (1998)","journal-title":"Science"},{"key":"BFnature23458_CR22","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1038\/nature03350","volume":"434","author":"E Knill","year":"2005","unstructured":"Knill, E. Quantum computing with realistically noisy devices. Nature 434, 39\u201344 (2005)","journal-title":"Nature"},{"key":"BFnature23458_CR23","doi-asserted-by":"publisher","first-page":"032324","DOI":"10.1103\/PhysRevA.86.032324","volume":"86","author":"A Fowler","year":"2012","unstructured":"Fowler, A., Mariantoni, M., Martinis, J. & Cleland, A. Surface codes: towards practical large-scale quantum computation. Phys. Rev. A 86, 032324 (2012)","journal-title":"Phys. Rev. A"},{"key":"BFnature23458_CR24","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1137\/050644756","volume":"38","author":"IL Markov","year":"2008","unstructured":"Markov, I. L. & Shi, Y. Simulating quantum computation by contracting tensor networks. SIAM J. Comput. 38, 963\u2013981 (2008)","journal-title":"SIAM J. Comput."},{"key":"BFnature23458_CR25","doi-asserted-by":"publisher","first-page":"250501","DOI":"10.1103\/PhysRevLett.116.250501","volume":"116","author":"S Bravyi","year":"2016","unstructured":"Bravyi, S. & Gosset, D. Improved classical simulation of quantum circuits dominated by Clifford gates. Phys. Rev. Lett. 116, 250501 (2016)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature23458_CR26","doi-asserted-by":"publisher","first-page":"130502","DOI":"10.1103\/PhysRevLett.112.130502","volume":"112","author":"T Morimae","year":"2014","unstructured":"Morimae, T., Fujii, K. & Fitzsimons, J. On the hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett. 112, 130502 (2014)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature23458_CR27","doi-asserted-by":"publisher","first-page":"8","DOI":"10.22331\/q-2017-04-25-8","volume":"1","author":"M Bremner","year":"2017","unstructured":"Bremner, M., Montanaro, A. & Shepherd, D. Achieving quantum supremacy with sparse and noisy commuting quantum circuits. Quantum 1, 8 (2017); available at https:\/\/doi.org\/10.22331\/q-2017-04-25-8 .","journal-title":"Quantum"},{"key":"BFnature23458_CR28","doi-asserted-by":"publisher","first-page":"25598","DOI":"10.1038\/srep25598","volume":"6","author":"K Fujii","year":"2016","unstructured":"Fujii, K. & Tamate, S. Computational quantum-classical boundary of noisy commuting quantum circuits. Sci. Rep. 6, 25598 (2016)","journal-title":"Sci. Rep."},{"key":"BFnature23458_CR29","doi-asserted-by":"crossref","unstructured":"Watrous, J. Quantum computational complexity. In Encyclopedia of Complexity and Systems Science 7174\u20137201 (Springer, 2009)","DOI":"10.1007\/978-0-387-30440-3_428"},{"key":"BFnature23458_CR30","doi-asserted-by":"publisher","first-page":"052328","DOI":"10.1103\/PhysRevA.70.052328","volume":"70","author":"S Aaronson","year":"2004","unstructured":"Aaronson, S. & Gottesman, D. Improved simulation of stabilizer circuits. Phys. Rev. A 70, 052328 (2004)","journal-title":"Phys. Rev. A"},{"key":"BFnature23458_CR31","doi-asserted-by":"publisher","first-page":"020502","DOI":"10.1103\/PhysRevLett.113.020502","volume":"113","author":"M Tichy","year":"2014","unstructured":"Tichy, M., Mayer, K., Buchleitner, A. & M\u00f8lmer, K. Stringent and efficient assessment of boson-sampling devices. Phys. Rev. Lett. 113, 020502 (2014)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature23458_CR32","first-page":"1383","volume":"14","author":"S Aaronson","year":"2014","unstructured":"Aaronson, S. & Arkhipov, A. BosonSampling is far from uniform. Quantum Inf. Comput. 14, 1383\u20131423 (2014)","journal-title":"Quantum Inf. Comput."},{"key":"BFnature23458_CR33","doi-asserted-by":"publisher","first-page":"130503","DOI":"10.1103\/PhysRevLett.111.130503","volume":"111","author":"N Spagnolo","year":"2013","unstructured":"Spagnolo, N. et al. General rules for bosonic bunching in multimode interferometers. Phys. Rev. Lett. 111, 130503 (2013)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature23458_CR34","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1038\/nphoton.2014.152","volume":"8","author":"J Carolan","year":"2014","unstructured":"Carolan, J. et al. On the experimental verification of quantum complexity in linear optics. Nat. Photon. 8, 621\u2013626 (2014)","journal-title":"Nat. Photon."},{"key":"BFnature23458_CR35","unstructured":"Hangleiter, D., Kliesch, M., Schwarz, M. & Eisert, J. Direct certification of a class of quantum simulations. Preprint at http:\/\/arXiv.org\/abs\/1602.00703 (2016)"},{"key":"BFnature23458_CR36","doi-asserted-by":"publisher","first-page":"140501","DOI":"10.1103\/PhysRevLett.114.140501","volume":"114","author":"D Gosset","year":"2015","unstructured":"Gosset, D., Terhal, B. & Vershynina, A. Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction. Phys. Rev. Lett. 114, 140501 (2015)","journal-title":"Phys. Rev. Lett."},{"key":"BFnature23458_CR37","doi-asserted-by":"crossref","unstructured":"Broadbent, A., Fitzsimons, J. & Kashefi, E. Universal blind quantum computation. In Proc. 50th Annual Symp. Foundations of Computer Science 517\u2013526 (IEEE, 2009)","DOI":"10.1109\/FOCS.2009.36"},{"key":"BFnature23458_CR38","unstructured":"Aharonov, D. & Vazirani, U. in Computability: Turing, G\u00f6del, Church, and Beyond (MIT Press, 2013)"},{"key":"BFnature23458_CR39","first-page":"021039","volume":"6","author":"S Rahimi-Keshari","year":"2016","unstructured":"Rahimi-Keshari, S., Ralph, T. C. & Caves, C. M. Sufficient conditions for efficient classical simulation of quantum optics. Phys. Rev. X 6, 021039 (2016)","journal-title":"Phys. Rev. X"},{"key":"BFnature23458_CR40","unstructured":"Kalai, G. & Kindler, G. Gaussian noise sensitivity and BosonSampling. Preprint at http:\/\/arXiv.org\/abs\/1409.3093 (2014)"},{"key":"BFnature23458_CR41","first-page":"0361","volume":"8","author":"S Bravyi","year":"2008","unstructured":"Bravyi, S., DiVincenzo, D., Oliveira, R. & Terhal, B. The complexity of stoquastic local Hamiltonian problems. Quant. Inf. Comput. 8, 0361\u20130385 (2008)","journal-title":"Quant. Inf. Comput."},{"key":"BFnature23458_CR42","doi-asserted-by":"publisher","first-page":"1903","DOI":"10.1038\/ncomms2920","volume":"4","author":"NG Dickson","year":"2013","unstructured":"Dickson, N. G. et al. Thermally assisted quantum annealing of a 16-qubit problem. Nat. Commun. 4, 1903 (2013)","journal-title":"Nat. Commun."},{"key":"BFnature23458_CR43","doi-asserted-by":"publisher","first-page":"032105","DOI":"10.1103\/PhysRevE.94.032105","volume":"94","author":"K Nishimura","year":"2016","unstructured":"Nishimura, K., Nishimori, H., Ochoa, A. J. & Katzgraber, H. G. Retrieving the ground state of spin glasses using thermal noise: performance of quantum annealing at finite temperatures. Phys. Rev. E 94, 032105 (2016)","journal-title":"Phys. Rev. E"},{"key":"BFnature23458_CR44","unstructured":"Farhi, E. & Harrow, A. W. Quantum supremacy through the quantum approximate optimization algorithm. Preprint at http:\/\/arXiv.org\/abs\/1602.07674 (2016)"},{"key":"BFnature23458_CR45","unstructured":"Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M. Quantum Computation by Adiabatic Evolution. Tech. Rep. MIT-CTP-2936 (Massachusetts Institute of Technology, 2000)"},{"key":"BFnature23458_CR46","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1126\/science.1231440","volume":"339","author":"MA Broome","year":"2013","unstructured":"Broome, M. A. et al. Photonic boson sampling in a tunable circuit. Science 339, 794\u2013798 (2013)","journal-title":"Science"},{"key":"BFnature23458_CR47","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1126\/science.1231692","volume":"339","author":"JB Spring","year":"2013","unstructured":"Spring, J. B. et al. Boson sampling on a photonic chip. Science 339, 798\u2013801 (2013)","journal-title":"Science"},{"key":"BFnature23458_CR48","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1038\/nphoton.2013.102","volume":"7","author":"M Tillmann","year":"2013","unstructured":"Tillmann, M. et al. Experimental boson sampling. Nat. Photon. 7, 540\u2013544 (2013)","journal-title":"Nat. Photon."},{"key":"BFnature23458_CR49","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1038\/nphoton.2013.112","volume":"7","author":"A Crespi","year":"2013","unstructured":"Crespi, A. et al. Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nat. Photon. 7, 545\u2013549 (2013)","journal-title":"Nat. Photon."},{"key":"BFnature23458_CR50","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1038\/nphoton.2014.135","volume":"8","author":"N Spagnolo","year":"2014","unstructured":"Spagnolo, N. et al. Experimental validation of photonic boson sampling. Nat. Photon. 8, 615\u2013620 (2014)","journal-title":"Nat. Photon."},{"key":"BFnature23458_CR51","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1126\/science.aab3642","volume":"349","author":"J Carolan","year":"2015","unstructured":"Carolan, J. et al. Universal linear optics. Science 349, 711\u2013716 (2015)","journal-title":"Science"},{"key":"BFnature23458_CR52","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1038\/nphoton.2017.63","volume":"11","author":"H Wang","year":"2017","unstructured":"Wang, H. et al. High-efficiency multiphoton boson sampling. Nat. Photon. 11, 361\u2013365 (2017)","journal-title":"Nat. Photon."},{"key":"BFnature23458_CR53","doi-asserted-by":"publisher","first-page":"e1400255","DOI":"10.1126\/sciadv.1400255","volume":"1","author":"M Bentivegna","year":"2015","unstructured":"Bentivegna, M. et al. Experimental scattershot boson sampling. Sci. Adv. 1, e1400255 (2015)","journal-title":"Sci. Adv."},{"key":"BFnature23458_CR54","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/S0097539792240467","volume":"26","author":"Y Han","year":"1997","unstructured":"Han, Y., Hemaspaandra, L. & Thierauf, T. Threshold computation and cryptographic security. SIAM J. Comput. 26, 59\u201378 (1997)","journal-title":"SIAM J. Comput."},{"key":"BFnature23458_CR55","doi-asserted-by":"publisher","first-page":"3473","DOI":"10.1098\/rspa.2005.1546","volume":"461","author":"S Aaronson","year":"2005","unstructured":"Aaronson, S. Quantum computing, postselection, and probabilistic polynomial-time. Proc. R. Soc. A 461, 3473 (2005)","journal-title":"Proc. R. Soc. A"},{"key":"BFnature23458_CR56","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20, 865\u2013877 (1991)","journal-title":"SIAM J. Comput."}],"container-title":["Nature"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.nature.com\/articles\/nature23458.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/www.nature.com\/articles\/nature23458","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/www.nature.com\/doifinder\/10.1038\/nature23458","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/www.nature.com\/articles\/nature23458.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T18:17:42Z","timestamp":1750875462000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/nature23458"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9]]},"references-count":56,"journal-issue":{"issue":"7671","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["BFnature23458"],"URL":"https:\/\/doi.org\/10.1038\/nature23458","relation":{},"ISSN":["0028-0836","1476-4687"],"issn-type":[{"value":"0028-0836","type":"print"},{"value":"1476-4687","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9]]},"assertion":[{"value":"28 February 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing financial interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}