Quantum computational supremacy
10.1038/nature23458
Crossref journal-article
Springer Science and Business Media LLC
Nature (297)
Bibliography

Harrow, A. W., & Montanaro, A. (2017). Quantum computational supremacy. Nature, 549(7671), 203–209.

Authors 2
  1. Aram W. Harrow (first)
  2. Ashley Montanaro (additional)
References 56 Referenced 579
  1. Preskill, J. Quantum computing and the entanglement frontier. Preprint at http://arXiv.org/abs/1203.5813 (2012)
  2. Papadimitriou, C. Computational Complexity (Addison-Wesley, 1994)
  3. 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–134 (IEEE Computer Society, 1994) (10.1109/SFCS.1994.365700)
  4. Georgescu, I., Ashhab, S. & Nori, F. Quantum simulation. Rev. Mod. Phys. 86, 153 (2014) (10.1103/RevModPhys.86.153) / Rev. Mod. Phys. by I Georgescu (2014)
  5. Cirac, J. I. & Zoller, P. Goals and opportunities in quantum simulation. Nat. Phys. 8, 264–266 (2012) (10.1038/nphys2275) / Nat. Phys. by JI Cirac (2012)
  6. Häaner, T., Roetteler, M. & Svore, K. Factoring using 2n + 2 qubits with Toffoli based modular multiplication. Preprint at http://arXiv.org/abs/1611.07995 (2016) (10.26421/QIC17.7-8-7)
  7. Cheuk, L. W. et al. Observation of spatial charge and spin correlations in the 2D Fermi-Hubbard model. Science 353, 1260–1264 (2016) (10.1126/science.aag3349) / Science by LW Cheuk (2016)
  8. Terhal, B. M. & DiVincenzo, D. P. Adaptive quantum computation, constant-depth quantum circuits and Arthur-Merlin games. Quantum Inf. Comput. 4, 134–145 (2004). This paper gave the first complexity-theoretic argument that a simple class of quantum circuits should be hard to simulate classically / Quantum Inf. Comput. by BM Terhal (2004)
  9. Aaronson, S. & Arkhipov, A. The computational complexity of linear optics. Theory Comput. 9, 143–252 (2013). This seminal paper introduced the boson sampling problem (10.4086/toc.2013.v009a004) / Theory Comput. by S Aaronson (2013)
  10. Shepherd, D. & Bremner, M. J. Temporally unstructured quantum computation. Proc. R. Soc. A 465, 1413–1439 (2009) (10.1098/rspa.2008.0443) / Proc. R. Soc. A by D Shepherd (2009)
  11. 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–472 (2010). This paper gave evidence that instantaneous quantum polynomial-time (IQP) circuits are hard to simulate classically (10.1098/rspa.2010.0301) / Proc. R. Soc. Lond. A by MJ Bremner (2010)
  12. 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
  13. Lund, A., Bremner, M. & Ralph, T. Quantum sampling problems, BosonSampling and quantum supremacy. Preprint at http://arXiv.org/abs/1702.03061 (2017) (10.1038/s41534-017-0018-2)
  14. Impagliazzo, R. & Paturi, R. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 367–375 (2001) (10.1006/jcss.2000.1727) / J. Comput. Syst. Sci. by R Impagliazzo (2001)
  15. Cheeseman, P., Kanefsky, B. & Taylor, W. Where the really hard problems are. In Proc. 12th Int. Joint Conf. on Artificial Intelligence (IJCAI ’91) (eds Mylopoulos, J. & Reiter, R. ) 331–337 (Morgan Kaufmann, 1991)
  16. Mertens, S., Mézard, M. & Zecchina, R. Threshold values of random k-SAT from the cavity method. Random Struct. Algorithms 28, 340–373 (2006) / Threshold values of random k-SAT from the cavity method. Random Struct. Algorithms by S Mertens (2006)
  17. Levin, L. A. Average case complete problems. SIAM J. Comput. 15, 285–286 (1986) (10.1137/0215020) / SIAM J. Comput. by LA Levin (1986)
  18. Bremner, M. J., Montanaro, A. & Shepherd, D. J. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016) (10.1103/PhysRevLett.117.080501) / Phys. Rev. Lett. by MJ Bremner (2016)
  19. Gao, X., Wang, S.-T. & Duan, L.-M. Quantum supremacy for simulating a translation-invariant Ising spin model. Phys. Rev. Lett. 118, 040502 (2017) (10.1103/PhysRevLett.118.040502) / Phys. Rev. Lett. by X Gao (2017)
  20. Aaronson, S. & Chen, L. Complexity-theoretic foundations of quantum supremacy experiments. Preprint at http://arXiv.org/abs/1612.05903 (2016)
  21. Knill, E., Laflamme, R. & Zurek, W. Resilient quantum computation. Science 279, 342–345 (1998) (10.1126/science.279.5349.342) / Science by E Knill (1998)
  22. Knill, E. Quantum computing with realistically noisy devices. Nature 434, 39–44 (2005) (10.1038/nature03350) / Nature by E Knill (2005)
  23. Fowler, A., Mariantoni, M., Martinis, J. & Cleland, A. Surface codes: towards practical large-scale quantum computation. Phys. Rev. A 86, 032324 (2012) (10.1103/PhysRevA.86.032324) / Phys. Rev. A by A Fowler (2012)
  24. Markov, I. L. & Shi, Y. Simulating quantum computation by contracting tensor networks. SIAM J. Comput. 38, 963–981 (2008) (10.1137/050644756) / SIAM J. Comput. by IL Markov (2008)
  25. Bravyi, S. & Gosset, D. Improved classical simulation of quantum circuits dominated by Clifford gates. Phys. Rev. Lett. 116, 250501 (2016) (10.1103/PhysRevLett.116.250501) / Phys. Rev. Lett. by S Bravyi (2016)
  26. Morimae, T., Fujii, K. & Fitzsimons, J. On the hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett. 112, 130502 (2014) (10.1103/PhysRevLett.112.130502) / Phys. Rev. Lett. by T Morimae (2014)
  27. 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 . (10.22331/q-2017-04-25-8) / Quantum by M Bremner (2017)
  28. Fujii, K. & Tamate, S. Computational quantum-classical boundary of noisy commuting quantum circuits. Sci. Rep. 6, 25598 (2016) (10.1038/srep25598) / Sci. Rep. by K Fujii (2016)
  29. Watrous, J. Quantum computational complexity. In Encyclopedia of Complexity and Systems Science 7174–7201 (Springer, 2009) (10.1007/978-0-387-30440-3_428)
  30. Aaronson, S. & Gottesman, D. Improved simulation of stabilizer circuits. Phys. Rev. A 70, 052328 (2004) (10.1103/PhysRevA.70.052328) / Phys. Rev. A by S Aaronson (2004)
  31. Tichy, M., Mayer, K., Buchleitner, A. & Mølmer, K. Stringent and efficient assessment of boson-sampling devices. Phys. Rev. Lett. 113, 020502 (2014) (10.1103/PhysRevLett.113.020502) / Phys. Rev. Lett. by M Tichy (2014)
  32. Aaronson, S. & Arkhipov, A. BosonSampling is far from uniform. Quantum Inf. Comput. 14, 1383–1423 (2014) / Quantum Inf. Comput. by S Aaronson (2014)
  33. Spagnolo, N. et al. General rules for bosonic bunching in multimode interferometers. Phys. Rev. Lett. 111, 130503 (2013) (10.1103/PhysRevLett.111.130503) / Phys. Rev. Lett. by N Spagnolo (2013)
  34. Carolan, J. et al. On the experimental verification of quantum complexity in linear optics. Nat. Photon. 8, 621–626 (2014) (10.1038/nphoton.2014.152) / Nat. Photon. by J Carolan (2014)
  35. 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)
  36. Gosset, D., Terhal, B. & Vershynina, A. Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction. Phys. Rev. Lett. 114, 140501 (2015) (10.1103/PhysRevLett.114.140501) / Phys. Rev. Lett. by D Gosset (2015)
  37. Broadbent, A., Fitzsimons, J. & Kashefi, E. Universal blind quantum computation. In Proc. 50th Annual Symp. Foundations of Computer Science 517–526 (IEEE, 2009) (10.1109/FOCS.2009.36)
  38. Aharonov, D. & Vazirani, U. in Computability: Turing, Gödel, Church, and Beyond (MIT Press, 2013)
  39. Rahimi-Keshari, S., Ralph, T. C. & Caves, C. M. Sufficient conditions for efficient classical simulation of quantum optics. Phys. Rev. X 6, 021039 (2016) / Phys. Rev. X by S Rahimi-Keshari (2016)
  40. Kalai, G. & Kindler, G. Gaussian noise sensitivity and BosonSampling. Preprint at http://arXiv.org/abs/1409.3093 (2014)
  41. Bravyi, S., DiVincenzo, D., Oliveira, R. & Terhal, B. The complexity of stoquastic local Hamiltonian problems. Quant. Inf. Comput. 8, 0361–0385 (2008) / Quant. Inf. Comput. by S Bravyi (2008)
  42. Dickson, N. G. et al. Thermally assisted quantum annealing of a 16-qubit problem. Nat. Commun. 4, 1903 (2013) (10.1038/ncomms2920) / Nat. Commun. by NG Dickson (2013)
  43. 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) (10.1103/PhysRevE.94.032105) / Phys. Rev. E by K Nishimura (2016)
  44. Farhi, E. & Harrow, A. W. Quantum supremacy through the quantum approximate optimization algorithm. Preprint at http://arXiv.org/abs/1602.07674 (2016)
  45. Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M. Quantum Computation by Adiabatic Evolution. Tech. Rep. MIT-CTP-2936 (Massachusetts Institute of Technology, 2000)
  46. Broome, M. A. et al. Photonic boson sampling in a tunable circuit. Science 339, 794–798 (2013) (10.1126/science.1231440) / Science by MA Broome (2013)
  47. Spring, J. B. et al. Boson sampling on a photonic chip. Science 339, 798–801 (2013) (10.1126/science.1231692) / Science by JB Spring (2013)
  48. Tillmann, M. et al. Experimental boson sampling. Nat. Photon. 7, 540–544 (2013) (10.1038/nphoton.2013.102) / Nat. Photon. by M Tillmann (2013)
  49. Crespi, A. et al. Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nat. Photon. 7, 545–549 (2013) (10.1038/nphoton.2013.112) / Nat. Photon. by A Crespi (2013)
  50. Spagnolo, N. et al. Experimental validation of photonic boson sampling. Nat. Photon. 8, 615–620 (2014) (10.1038/nphoton.2014.135) / Nat. Photon. by N Spagnolo (2014)
  51. Carolan, J. et al. Universal linear optics. Science 349, 711–716 (2015) (10.1126/science.aab3642) / Science by J Carolan (2015)
  52. Wang, H. et al. High-efficiency multiphoton boson sampling. Nat. Photon. 11, 361–365 (2017) (10.1038/nphoton.2017.63) / Nat. Photon. by H Wang (2017)
  53. Bentivegna, M. et al. Experimental scattershot boson sampling. Sci. Adv. 1, e1400255 (2015) (10.1126/sciadv.1400255) / Sci. Adv. by M Bentivegna (2015)
  54. Han, Y., Hemaspaandra, L. & Thierauf, T. Threshold computation and cryptographic security. SIAM J. Comput. 26, 59–78 (1997) (10.1137/S0097539792240467) / SIAM J. Comput. by Y Han (1997)
  55. Aaronson, S. Quantum computing, postselection, and probabilistic polynomial-time. Proc. R. Soc. A 461, 3473 (2005) (10.1098/rspa.2005.1546) / Proc. R. Soc. A by S Aaronson (2005)
  56. Toda, S. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20, 865–877 (1991) (10.1137/0220053) / SIAM J. Comput. by S Toda (1991)
Dates
Type When
Created 7 years, 11 months ago (Sept. 12, 2017, 12:12 p.m.)
Deposited 1 month, 4 weeks ago (June 25, 2025, 2:17 p.m.)
Indexed 13 hours, 25 minutes ago (Aug. 23, 2025, 9:55 p.m.)
Issued 7 years, 11 months ago (Sept. 1, 2017)
Published 7 years, 11 months ago (Sept. 1, 2017)
Published Online 7 years, 11 months ago (Sept. 14, 2017)
Published Print 7 years, 11 months ago (Sept. 1, 2017)
Funders 0

None

@article{Harrow_2017, title={Quantum computational supremacy}, volume={549}, ISSN={1476-4687}, url={http://dx.doi.org/10.1038/nature23458}, DOI={10.1038/nature23458}, number={7671}, journal={Nature}, publisher={Springer Science and Business Media LLC}, author={Harrow, Aram W. and Montanaro, Ashley}, year={2017}, month=sep, pages={203–209} }