Quantum supremacy

Quantum supremacy is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.[1] In complexity-theoretic terms, this generally means providing a superpolynomial speedup over the best known or possible classical algorithm.[2] The term was originally popularized by John Preskill[1] but the concept of a quantum computational advantage, specifically for simulating quantum systems, dates back to Richard Feynman's 1981 proposal of quantum computing.[3]

Shor's algorithm for factoring integers, which runs in polynomial time on a quantum computer, provides such a superpolynomial speedup over the best known classical algorithm.[4] Factoring is generally believed to be hard using classical resources but there is currently no proof of this fact. The difficulty of proving what cannot be done with classical computing is a common problem in definitively demonstrating quantum supremacy. It also affects the BosonSampling proposal of Aaronson and Arkhipov,[5] D-Wave's specialized frustrated cluster loop problems,[6] and sampling the output of random quantum circuits.[7]

Like factoring integers, sampling the output distributions of random quantum circuits is believed to be hard for classical computers based on reasonable complexity assumptions.[7] Google plans on demonstrating quantum supremacy before the end of 2017 by solving this problem with an array of 49 superconducting qubits.[8]

Computational complexity

Complexity arguments concern how the amount of some resource needed to solve a problem scales with the size of the input to that problem. As an extension of classical computational complexity theory, quantum complexity theory is about what a working, universal quantum computer could accomplish without necessarily accounting for the difficulty of building one or dealing with decoherence and noise.[9] Since quantum information is a generalization of classical information, it is clear that a quantum computer can efficiently simulate any classical algorithm.[9]

Bounded quantum polynomial (BQP) is the class of decision problems that can be solved in polynomial time by a universal quantum computer.[10] It is related to important classical complexity classes by the hierarchy.[11] Whether any of these containments is proper is still an open question.[11]

Contrary to decision problems that require yes or no answers, sampling problems ask for samples from probability distributions.[12] If there is a classical algorithm that can efficiently sample from the output of an arbitrary quantum circuit, the polynomial hierarchy would collapse to the third level, which is considered very unlikely.[7] BosonSampling is a more specific proposal, the classical hardness of which depends upon the intractability of calculating the permanent of a large matrix with complex entries, which is a P#-complete problem.[13] The arguments used to reach this conclusion have also been extended to IQP Sampling,[14] where only the conjecture that the average- and worst-case complexities of the problem are the same is needed.[12]

Superpolynomial speedups

The following algorithms provide superpolynomial speedups over the best known classical algorithms:[15]

Shor's algorithm for factoring integers

This algorithm finds the prime factorization of an n-bit integer in time[4] whereas the best known classical algorithm requires time and the best upper bound for the complexity of this problem is .[16] It can also provide a speedup for any problem that reduces to integer factoring, including the membership problem for matrix groups over fields of odd order.[17]

This algorithm is important both practically and historically for quantum computing. It was the first polynomial-time quantum algorithm proposed for a problem that is believed to be hard for classical computers.[4] This hardness belief is so strong that the security of today's most common encryption protocol, RSA, is based upon it.[18] A quantum computer successfully and repeatably running this algorithm has the potential to break this encryption system.[19]

BosonSampling

This computing paradigm based upon identical photons sent through a linear-optical network can solve certain sampling and search problems that, assuming a few conjectures, are intractable for classical computers.[5] However, it has been shown that BosonSampling in a system with large enough loss and noise can be simulated efficiently.[20]

The largest experimental implementation of BosonSampling to date had 6 modes so could handle up to 6 photons at a time.[21] The best proposed classical algorithm for simulating BosonSampling runs in time for a system with n photons and m output modes.[22] This leads to an estimate of 50 photons required to demonstrate quantum supremacy with BosonSampling.[22]

Sampling the output distribution of random quantum circuits

The best known algorithm for simulating an arbitrary random quantum circuit requires an amount of time that scales exponentially with the number of qubits, leading one group to estimate that around 50 qubits could be enough to demonstrate quantum supremacy.[23] The largest quantum circuit simulation completed successfully on a supercomputer contained only 45 qubits.[24] Google has announced its intention to demonstrate quantum supremacy by the end of 2017 by constructing and running a 49-qubit chip that will be able to sample distributions inaccessible to any current classical computers in a reasonable amount of time.[8]

Skepticism

Quantum computers are much more susceptible to errors than classical computers due to decoherence and noise.[25] The threshold theorem states that a noisy quantum computer can use quantum error-correcting codes[26][27] to simulate a noiseless quantum computer assuming the error introduced in each computer cycle is less than some number.[28] Numerical simulations suggest that that number may be as high as 3%.[29]

However, it is not known how the resources needed for error correction will scale with the number of qubits.[30] Skeptics point to the unknown behavior of noise in scaled-up quantum systems as potential roadblocks for successfully implementing quantum computing and demonstrating quantum supremacy.[31][32]

References

  1. 1 2 Preskill, John (2012-03-26). "Quantum computing and the entanglement frontier". arXiv:1203.5813 [cond-mat, physics:quant-ph].
  2. ↑ Papageorgiou, Anargyros; Traub, Joseph F. (2013-08-12). "Measures of quantum computing speedup". Physical Review A. 88 (2). ISSN 1050-2947. doi:10.1103/PhysRevA.88.022316.
  3. ↑ Feynman, Richard P. (1982-06-01). "Simulating Physics with Computers". International Journal of Theoretical Physics. 21: 467–488. ISSN 0020-7748. doi:10.1007/BF02650179.
  4. 1 2 3 Shor, P. (1999-01-01). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Review. 41 (2): 303–332. ISSN 0036-1445. doi:10.1137/S0036144598347011.
  5. 1 2 Aaronson, Scott; Arkhipov, Alex (2011). "The Computational Complexity of Linear Optics". Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing. STOC '11. New York, NY, USA: ACM: 333–342. ISBN 9781450306911. doi:10.1145/1993636.1993682.
  6. ↑ King, James; Yarkoni, Sheir; Raymond, Jack; Ozfidan, Isil; King, Andrew D.; Nevisi, Mayssam Mohammadi; Hilton, Jeremy P.; McGeoch, Catherine C. (2017-01-17). "Quantum Annealing amid Local Ruggedness and Global Frustration". arXiv:1701.04579 [quant-ph].
  7. 1 2 3 Aaronson, Scott; Chen, Lijie (2016-12-18). "Complexity-Theoretic Foundations of Quantum Supremacy Experiments". arXiv:1612.05903 [quant-ph].
  8. 1 2 "Google Plans to Demonstrate the Supremacy of Quantum Computing". IEEE Spectrum: Technology, Engineering, and Science News. Retrieved 2017-07-22.
  9. 1 2 Watrous, John (2009). Ph. D, Robert A. Meyers, ed. Encyclopedia of Complexity and Systems Science. Springer New York. pp. 7174–7201. ISBN 9780387758886. doi:10.1007/978-0-387-30440-3_428.
  10. ↑ Tereza, Tusarova, (2004-09-26). "Quantum Complexity Classes".
  11. 1 2 Vazirani, Umesh. "A Survey of Quantum Complexity Theory" (PDF). Proceedings of Symposia in Applied Mathematics.
  12. 1 2 Lund, A. P.; Bremner, Michael J.; Ralph, T. C. (2017-04-13). "Quantum sampling problems, BosonSampling and quantum supremacy". npj Quantum Information. 3 (1). ISSN 2056-6387. doi:10.1038/s41534-017-0018-2.
  13. ↑ Gard, Bryan T.; Motes, Keith R.; Olson, Jonathan P.; Rohde, Peter P.; Dowling, Jonathan P. (August 2015). "An introduction to boson-sampling". arXiv:1406.6767 [quant-ph]: 167–192. doi:10.1142/9789814678704_0008.
  14. ↑ Bremner, Michael J.; Montanaro, Ashley; Shepherd, Dan J. (2016-08-18). "Average-case complexity versus approximate simulation of commuting quantum computations". Physical Review Letters. 117 (8). ISSN 0031-9007. doi:10.1103/PhysRevLett.117.080501.
  15. ↑ Jordan, Stephen. "Quantum Algorithm Zoo". math.nist.gov. Retrieved 2017-07-29.
  16. ↑ Rubinstein, Michael (2006-10-19). "The distribution of solutions to xy = N mod a with an application to factoring integers". arXiv:math/0610612.
  17. ↑ Babai, László; Beals, Robert; Seress, Ákos (2009). "Polynomial-time Theory of Matrix Groups". Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing. STOC '09. New York, NY, USA: ACM: 55–64. ISBN 9781605585062. doi:10.1145/1536414.1536425.
  18. ↑ Rivest, R. L.; Shamir, A.; Adleman, L. (February 1978). "A Method for Obtaining Digital Signatures and Public-key Cryptosystems". Commun. ACM. 21 (2): 120–126. ISSN 0001-0782. doi:10.1145/359340.359342.
  19. ↑ Bernstein, Daniel. Post-Quantum Cryptography. Springer.
  20. ↑ Rahimi-Keshari, Saleh; Ralph, Timothy C.; Caves, Carlton M. (2016-06-20). "Sufficient Conditions for Efficient Classical Simulation of Quantum Optics". Physical Review X. 6 (2): 021039. doi:10.1103/PhysRevX.6.021039.
  21. ↑ Carolan, Jacques; Harrold, Christopher; Sparrow, Chris; Martín-López, Enrique; Russell, Nicholas J.; Silverstone, Joshua W.; Shadbolt, Peter J.; Matsuda, Nobuyuki; Oguma, Manabu (2015-08-14). "Universal linear optics". Science. 349 (6249): 711–716. ISSN 0036-8075. PMID 26160375. doi:10.1126/science.aab3642.
  22. 1 2 Clifford, Peter; Clifford, Raphaël (2017-06-05). "The Classical Complexity of Boson Sampling". arXiv:1706.01260 [quant-ph, stat].
  23. ↑ Boixo, Sergio; Isakov, Sergei V.; Smelyanskiy, Vadim N.; Babbush, Ryan; Ding, Nan; Jiang, Zhang; Bremner, Michael J.; Martinis, John M.; Neven, Hartmut (2016-07-31). "Characterizing Quantum Supremacy in Near-Term Devices". arXiv:1608.00263 [quant-ph].
  24. ↑ Häner, Thomas; Steiger, Damian S. (2017-04-04). "0.5 Petabyte Simulation of a 45-Qubit Quantum Circuit". arXiv:1704.01127 [quant-ph].
  25. ↑ Kalai, Gil (2011-06-02). "How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation". arXiv:1106.0485 [quant-ph].
  26. ↑ Shor, Peter W. (1995-10-01). "Scheme for reducing decoherence in quantum computer memory". Physical Review A. 52 (4): R2493–R2496. doi:10.1103/PhysRevA.52.R2493.
  27. ↑ Steane, A. M. (1996-07-29). "Error Correcting Codes in Quantum Theory". Physical Review Letters. 77 (5): 793–797. doi:10.1103/PhysRevLett.77.793.
  28. ↑ Aharonov, Dorit; Ben-Or, Michael (1999-06-30). "Fault-Tolerant Quantum Computation With Constant Error Rate". arXiv:quant-ph/9906129.
  29. ↑ Knill, E. (2005-03-03). "Quantum computing with realistically noisy devices". Nature. 434 (7029): 39–44. ISSN 0028-0836. doi:10.1038/nature03350.
  30. ↑ Kalai, Gil (2016-05-03). "The Quantum Computer Puzzle (Expanded Version)". arXiv:1605.00992 [quant-ph].
  31. ↑ Dyakonov, M. I. (2006-10-14). "Is Fault-Tolerant Quantum Computation Really Possible?". arXiv:quant-ph/0610117.
  32. ↑ Kalai, Gil (2011-06-02). "How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation". arXiv:1106.0485 [quant-ph].
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.