Quantum supremacy

Last updated

In quantum computing, quantum supremacy or quantum advantage is the goal of demonstrating that a programmable quantum computer can solve a problem that no classical computer can solve in any feasible amount of time, irrespective of the usefulness of the problem. [1] [2] [3] The term was coined by John Preskill in 2012, [1] [4] but the concept dates to Yuri Manin's 1980 [5] and Richard Feynman's 1981 [6] proposals of quantum computing.

Contents

Conceptually, quantum supremacy involves both the engineering task of building a powerful quantum computer and the computational-complexity-theoretic task of finding a problem that can be solved by that quantum computer and has a superpolynomial speedup over the best known or possible classical algorithm for that task. [7] [8]

Examples of proposals to demonstrate quantum supremacy include the boson sampling proposal of Aaronson and Arkhipov, [9] and sampling the output of random quantum circuits. [10] [11] The output distributions that are obtained by making measurements in boson sampling or quantum random circuit sampling are flat, but structured in a way so that one cannot classically efficiently sample from a distribution that is close to the distribution generated by the quantum experiment. For this conclusion to be valid, only very mild assumptions in the theory of computational complexity have to be invoked. In this sense, quantum random sampling schemes can have the potential to show quantum supremacy. [12]

A notable property of quantum supremacy is that it can be feasibly achieved by near-term quantum computers, [4] since it does not require a quantum computer to perform any useful task [13] or use high-quality quantum error correction, [14] both of which are long-term goals. [2] Consequently, researchers view quantum supremacy as primarily a scientific goal, with relatively little immediate bearing on the future commercial viability of quantum computing. [2] Due to unpredictable possible improvements in classical computers and algorithms, quantum supremacy may be temporary or unstable, placing possible achievements under significant scrutiny. [15] [16]

Background

Quantum advantage in the 20th century

In 1936, Alan Turing published his paper, “On Computable Numbers”, [17] in response to the 1900 Hilbert Problems. Turing's paper described what he called a “universal computing machine”, which later became known as a Turing machine. In 1980, Paul Benioff used Turing's paper to propose the theoretical feasibility of Quantum Computing. His paper, “The Computer as a Physical System: A Microscopic Quantum Mechanical Hamiltonian Model of Computers as Represented by Turing Machines“, [18] was the first to demonstrate that it is possible to show the reversible nature of quantum computing as long as the energy dissipated is arbitrarily small. In 1981, Richard Feynman showed that quantum mechanics could not be efficiently simulated on classical devices. [19] During a lecture, he delivered the famous quote, “Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy.” [19] Soon after this, David Deutsch produced a description for a quantum Turing machine and designed an algorithm created to run on a quantum computer. [20]

In 1994, further progress toward quantum supremacy was made when Peter Shor formulated Shor's algorithm, streamlining a method for factoring integers in polynomial time. [21] In 1995, Christopher Monroe and David Wineland published their paper, “Demonstration of a Fundamental Quantum Logic Gate”, [22] marking the first demonstration of a quantum logic gate, specifically the two-bit "controlled-NOT". In 1996, Lov Grover put into motion an interest in fabricating a quantum computer after publishing his algorithm, Grover's Algorithm, in his paper, “A fast quantum mechanical algorithm for database search”. [23] In 1998, Jonathan A. Jones and Michele Mosca published “Implementation of a Quantum Algorithm to Solve Deutsch's Problem on a Nuclear Magnetic Resonance Quantum Computer”, [24] marking the first demonstration of a quantum algorithm.

Progress in the 21st century

Vast progress toward quantum supremacy was made in the 2000s from the first 5-qubit nuclear magnetic resonance computer (2000), the demonstration of Shor's theorem (2001), and the implementation of Deutsch's algorithm in a clustered quantum computer (2007). [25] In 2011, D-Wave Systems of Burnaby, British Columbia, Canada became the first company to sell a quantum computer commercially. [26] In 2012, physicist Nanyang Xu landed a milestone accomplishment by using an improved adiabatic factoring algorithm to factor 143. However, the methods used by Xu were met with objections. [27] Not long after this accomplishment, Google purchased its first quantum computer. [28]

Google had announced plans to demonstrate quantum supremacy before the end of 2017 with an array of 49 superconducting qubits. [29] In early January 2018, Intel announced a similar hardware program. [30] In October 2017, IBM demonstrated the simulation of 56 qubits on a classical supercomputer, thereby increasing the computational power needed to establish quantum supremacy. [31] In November 2018, Google announced a partnership with NASA that would "analyze results from quantum circuits run on Google quantum processors, and ... provide comparisons with classical simulation to both support Google in validating its hardware and establish a baseline for quantum supremacy." [32] Theoretical work published in 2018 suggested that quantum supremacy should be possible with a "two-dimensional lattice of 7×7 qubits and around 40 clock cycles" if error rates can be pushed low enough. [33] The scheme discussed was a variant of a quantum random sampling scheme in which qubits undergo random quantum circuits featuring quantum gates drawn from a universal gate set, followed by measurements in the computational basis.

On June 18, 2019, Quanta Magazine suggested that quantum supremacy could happen in 2019, according to Neven's law. [34] On September 20, 2019, the Financial Times reported that "Google claims to have reached quantum supremacy with an array of 54 qubits out of which 53 were functional, which were used to perform a series of operations in 200 seconds that would take a supercomputer about 10,000 years to complete". [35] [36] On October 23, Google officially confirmed the claims. [37] [38] [39] IBM responded by suggesting some of the claims were excessive and suggested that it could take 2.5 days instead of 10,000 years, listing techniques that a classical supercomputer may use to maximize computing speed. IBM's response is relevant as the most powerful supercomputer at the time, Summit, was made by IBM. [40] [15] [41] Researchers have since developed better algorithms for the sampling problem used to claim quantum supremacy, giving substantial reductions to the gap between Google's Sycamore processor and classical supercomputers [42] [43] [44] and even beating it. [45] [46] [47]

In December 2020, a group based in the University of Science and Technology of China (USTC) led by Jian-Wei Pan reached quantum supremacy by implementing gaussian boson sampling on 76 photons with their photonic quantum computer Jiuzhang. [48] [49] [50] The paper states that to generate the number of samples the quantum computer generates in 200 seconds, a classical supercomputer would require 2.5 billion years of computation. [3]

In October 2021, teams from USTC again reported quantum primacy by building two supercomputers called Jiuzhang 2.0 and Zuchongzhi. The light-based Jiuzhang 2.0 implemented gaussian boson sampling to detect 113 photons from a 144-mode optical interferometer and a sampling rate speed up of 1024 – a difference of 37 photons and 10 orders of magnitude over the previous Jiuzhang. [51] [52] Zuchongzhi is a programmable superconducting quantum computer that needs to be kept at extremely low temperatures to work efficiently and uses random circuit sampling to obtain 56 qubits from a tunable coupling architecture of 66 transmons — an improvement over Google's Sycamore 2019 achievement by 3 qubits, meaning a greater computational cost of classical simulation of 2 to 3 orders of magnitude. [53] [54] [55] A third study reported that Zuchongzhi 2.1 completed a sampling task that "is about 6 orders of magnitude more difficult than that of Sycamore" "in the classic simulation". [56]

In June 2022 Xanadu has reported on a boson sampling experiment summing to those of Google and USTC. Their setup used loops of optical fiber and multiplexing to replace the network of beam splitters by a single one which made it also more easily reconfigurable. They detected a mean of 125 up to 219 photon from 216 squeezed modes (squeezed light follows a photon number distribution so they can contain more than one photon per mode) and claim to have obtained a speedup 50 million times bigger than previous experiments. [57] [58]

Computational complexity

Complexity arguments concern how the amount of some resource needed to solve a problem (generally time or memory) scales with the size of the input. In this setting, a problem consists of an inputted problem instance (a binary string) and returned solution (corresponding output string), while resources refers to designated elementary operations, memory usage, or communication. A collection of local operations allows for the computer to generate the output string. A circuit model and its corresponding operations are useful in describing both classical and quantum problems; the classical circuit model consists of basic operations such as AND gates, OR gates, and NOT gates while the quantum model consists of classical circuits and the application of unitary operations. Unlike the finite set of classical gates, there are an infinite amount of quantum gates due to the continuous nature of unitary operations. In both classical and quantum cases, complexity swells with increasing problem size. [59] As an extension of classical computational complexity theory, quantum complexity theory considers what a theoretical universal quantum computer could accomplish without accounting for the difficulty of building a physical quantum computer or dealing with decoherence and noise. [60] Since quantum information is a generalization of classical information, quantum computers can simulate any classical algorithm. [60]

Quantum complexity classes are sets of problems that share a common quantum computational model, with each model containing specified resource constraints. Circuit models are useful in describing quantum complexity classes. [61] The most useful quantum complexity class is BQP (bounded-error quantum polynomial time), the class of decision problems that can be solved in polynomial time by a universal quantum computer. [62] Questions about BQP still remain, such as the connection between BQP and the polynomial-time hierarchy, whether or not BQP contains NP-complete problems, and the exact lower and upper bounds of the BQP class. Not only would answers to these questions reveal the nature of BQP, but they would also answer difficult classical complexity theory questions. One strategy for better understanding BQP is by defining related classes, ordering them into a conventional class hierarchy, and then looking for properties that are revealed by their relation to BQP. [63] There are several other quantum complexity classes, such as QMA (quantum Merlin Arthur) and QIP (quantum interactive polynomial time). [61]

The difficulty of proving what cannot be done with classical computing is a common problem in definitively demonstrating quantum supremacy. Contrary to decision problems that require yes or no answers, sampling problems ask for samples from probability distributions. [64] 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 generally considered to be very unlikely. [10] [11] Boson sampling 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. [65] The arguments used to reach this conclusion have been extended to IQP Sampling, [66] where only the conjecture that the average- and worst-case complexities of the problem are the same is needed, [64] as well as to Random Circuit Sampling, [11] which is the task replicated by the Google [38] and USTC research groups. [48]

Proposed experiments

The following are proposals for demonstrating quantum computational supremacy using current technology, often called NISQ devices. [2] Such proposals include (1) a well-defined computational problem, (2) a quantum algorithm to solve this problem, (3) a comparison best-case classical algorithm to solve the problem, and (4) a complexity-theoretic argument that, under a reasonable assumption, no classical algorithm can perform significantly better than current algorithms (so the quantum algorithm still provides a superpolynomial speedup). [7] [67]

Shor's algorithm for factoring integers

This algorithm finds the prime factorization of an n-bit integer in time [68] whereas the best known classical algorithm requires time and the best upper bound for the complexity of this problem is . [69] 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. [70]

This algorithm is important both practically and historically for quantum computing. It was the first polynomial-time quantum algorithm proposed for a real-world problem that is believed to be hard for classical computers. [68] Namely, it gives a superpolynomial speedup under the reasonable assumption that RSA, a well-established cryptosystem, is secure. [71]

Factoring has some benefit over other supremacy proposals because factoring can be checked quickly with a classical computer just by multiplying integers, even for large instances where factoring algorithms are intractably slow. However, implementing Shor's algorithm for large numbers is infeasible with current technology, [72] [73] so it is not being pursued as a strategy for demonstrating supremacy.

Boson sampling

This computing paradigm based upon sending identical photons through a linear-optical network can solve certain sampling and search problems that, assuming a few complexity-theoretical conjectures (that calculating the permanent of Gaussian matrices is #P-Hard and that the polynomial hierarchy does not collapse) are intractable for classical computers. [9] However, it has been shown that boson sampling in a system with large enough loss and noise can be simulated efficiently. [74]

The largest experimental implementation of boson sampling to date had 6 modes so could handle up to 6 photons at a time. [75] The best proposed classical algorithm for simulating boson sampling runs in time for a system with n photons and m output modes. [76] [77] BosonSampling is an open-source implementation in the R programming language. The algorithm leads to an estimate of 50 photons required to demonstrate quantum supremacy with boson sampling. [76] [77]

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. [33] Bouland, Fefferman, Nirkhe and Vazirani [11] gave, in 2018, theoretical evidence that efficiently simulating a random quantum circuit would require a collapse of the computational polynomial hierarchy. Google had announced its intention to demonstrate quantum supremacy by the end of 2017 by constructing and running a 49-qubit chip that would be able to sample distributions inaccessible to any current classical computers in a reasonable amount of time. [29] The largest universal quantum circuit simulator running on classical supercomputers at the time was able to simulate 48 qubits. [78] But for particular kinds of circuits, larger quantum circuit simulations with 56 qubits are possible. [79] This may require increasing the number of qubits to demonstrate quantum supremacy. [31] On October 23, 2019, Google published the results of this quantum supremacy experiment in the Nature article, “Quantum Supremacy Using a Programmable Superconducting Processor” in which they developed a new 53-qubit processor, named “Sycamore”, that is capable of fast, high-fidelity quantum logic gates, in order to perform the benchmark testing. Google claims that their machine performed the target computation in 200 seconds, and estimated that their classical algorithm would take 10,000 years in the world's fastest supercomputer to solve the same problem. [80] IBM disputed this claim, saying that an improved classical algorithm should be able to solve that problem in two and a half days on that same supercomputer. [81] [82] [83]

Criticisms

Susceptibility to error

Quantum computers are much more susceptible to errors than classical computers due to decoherence and noise. [84] The threshold theorem states that a noisy quantum computer can use quantum error-correcting codes [85] [86] to simulate a noiseless quantum computer, assuming the error introduced in each computer cycle is less than some number. [87] Numerical simulations suggest that that number may be as high as 3%. [88] However, it is not yet definitively known how the resources needed for error correction will scale with the number of qubits. [89] Skeptics point to the unknown behavior of noise in scaled-up quantum systems as a potential roadblock for successfully implementing quantum computing and demonstrating quantum supremacy. [84] [90]

Criticism of the name

Some researchers have suggested that the term "quantum supremacy" should not be used, arguing that the word "supremacy" evokes distasteful comparisons to the racist belief of white supremacy. A controversial [91] [92] commentary article in the journal Nature signed by thirteen researchers asserts that the alternative phrase "quantum advantage" should be used instead. [93] [94] John Preskill, the professor of theoretical physics at the California Institute of Technology who coined the term, has since clarified that the term was proposed to explicitly describe the moment that a quantum computer gains the ability to perform a task that a classical computer never could. He further explained that he specifically rejected the term "quantum advantage" as it did not fully encapsulate the meaning of his new term: the word "advantage" would imply that a computer with quantum supremacy would have a slight edge over a classical computer while the word "supremacy" better conveys complete ascendancy over any classical computer.

"Quantum primacy" was coined in February 2021, in a Scientific American opinion piece as a more suitable replacement. [4] Nature's Philip Ball wrote in December 2020 that the term "quantum advantage" has "largely replaced" the term "quantum supremacy". [95]

See also

Related Research Articles

<span class="mw-page-title-main">Quantum computing</span> Technology that uses quantum mechanics

A quantum computer is a computer that takes advantage of quantum mechanical phenomena.

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.

This is a timeline of quantum computing.

In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model.

In quantum computing, the Gottesman–Knill theorem is a theoretical result by Daniel Gottesman and Emanuel Knill that states that stabilizer circuits, circuits that only consist of gates from the normalizer of the qubit Pauli group, also called Clifford group, can be perfectly simulated in polynomial time on a probabilistic classical computer. The Clifford group can be generated solely by using CNOT, Hadamard, and phase gate S; and therefore stabilizer circuits can be constructed using only these gates.

Adiabatic quantum computation (AQC) is a form of quantum computing which relies on the adiabatic theorem to perform calculations and is closely related to quantum annealing.

In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the set of languages for which, when a string is in the language, there is a polynomial-size quantum proof that convinces a polynomial time quantum verifier of this fact with high probability. Moreover, when the string is not in the language, every polynomial-size quantum state is rejected by the verifier with high probability.

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

Linear optical quantum computing or linear optics quantum computation (LOQC), also photonic quantum computing (PQC), is a paradigm of quantum computation, allowing (under certain conditions, described below) universal quantum computation. LOQC uses photons as information carriers, mainly uses linear optical elements, or optical instruments (including reciprocal mirrors and waveplates) to process quantum information, and uses photon detectors and quantum memories to detect and store quantum information.

<span class="mw-page-title-main">Quantum machine learning</span> Interdisciplinary research area at the intersection of quantum physics and machine learning

Quantum machine learning is the integration of quantum algorithms within machine learning programs.

Boson sampling is a restricted model of non-universal quantum computation introduced by Scott Aaronson and Alex Arkhipov after the original work of Lidror Troyansky and Naftali Tishby, that explored possible usage of boson scattering to evaluate expectation values of permanents of matrices. The model consists of sampling from the probability distribution of identical bosons scattered by a linear interferometer. Although the problem is well defined for any bosonic particles, its photonic version is currently considered as the most promising platform for a scalable implementation of a boson sampling device, which makes it a non-universal approach to linear optical quantum computing. Moreover, while not universal, the boson sampling scheme is strongly believed to implement computing tasks which are hard to implement with classical computers by using far fewer physical resources than a full linear-optical quantum computing setup. This advantage makes it an ideal candidate for demonstrating the power of quantum computation in the near term.

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. Quantum computing may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.

Continuous-variable (CV) quantum information is the area of quantum information science that makes use of physical observables, like the strength of an electromagnetic field, whose numerical values belong to continuous intervals. One primary application is quantum computing. In a sense, continuous-variable quantum computation is "analog", while quantum computation using qubits is "digital." In more technical terms, the former makes use of Hilbert spaces that are infinite-dimensional, while the Hilbert spaces for systems comprising collections of qubits are finite-dimensional. One motivation for studying continuous-variable quantum computation is to understand what resources are necessary to make quantum computers more powerful than classical ones.

In quantum computing, a qubit is a unit of information analogous to a bit in classical computing, but it is affected by quantum mechanical properties such as superposition and entanglement which allow qubits to be in some ways more powerful than classical bits for some tasks. Qubits are used in quantum circuits and quantum algorithms composed of quantum logic gates to solve computational problems, where they are used for input/output and intermediate computations.

The One Clean Qubit model of computation is performed an qubit system with one pure state and maximally mixed states. This model was motivated by highly mixed states that are prevalent in Nuclear magnetic resonance quantum computers. It's described by the density matrix , where I is the identity matrix. In computational complexity theory, DQC1; also known as the Deterministic quantum computation with one clean qubit is the class of decision problems solvable by a one clean qubit machine in polynomial time, upon measuring the first qubit, with an error probability of at most 1/poly(n) for all instances.

Cross-entropy benchmarking is a quantum benchmarking protocol which can be used to demonstrate quantum supremacy. In XEB, a random quantum circuit is executed on a quantum computer multiple times in order to collect a set of samples in the form of bitstrings . The bitstrings are then used to calculate the cross-entropy benchmark fidelity via a classical computer, given by

This glossary of quantum computing is a list of definitions of terms and concepts used in quantum computing, its sub-disciplines, and related fields.

Quantum random circuits (QRC) is a concept of incorporating an element of randomness into the local unitary operations and measurements of a quantum circuit. The idea is similar to that of random matrix theory which is to use the QRC to obtain almost exact results of non-integrable, hard-to-solve problems by averaging over an ensemble of outcomes. This incorporation of randomness into the circuits has many possible advantages, some of which are (i) the validation of quantum computers, which is the method that Google used when they claimed quantum supremacy in 2019., and (ii) understanding the universal structure of non-equilibrium and thermalization processes in quantum many-body dynamics.

References

  1. 1 2 Preskill, John (2012-03-26). "Quantum computing and the entanglement frontier". arXiv: 1203.5813 [quant-ph].
  2. 1 2 3 4 Preskill, John (2018-08-06). "Quantum Computing in the NISQ era and beyond". Quantum. 2: 79. arXiv: 1801.00862 . Bibcode:2018Quant...2...79P. doi: 10.22331/q-2018-08-06-79 .
  3. 1 2 Zhong, Han-Sen; Wang, Hui; Deng, Yu-Hao; Chen, Ming-Cheng; Peng, Li-Chao; Luo, Yi-Han; Qin, Jian; Wu, Dian; Ding, Xing; Hu, Yi; Hu, Peng (2020-12-03). "Quantum computational advantage using photons". Science. 370 (6523): 1460–1463. arXiv: 2012.01625 . Bibcode:2020Sci...370.1460Z. doi:10.1126/science.abe8770. ISSN   0036-8075. PMID   33273064. S2CID   227254333.
  4. 1 2 3 "John Preskill Explains 'Quantum Supremacy'". Quanta Magazine. 2 October 2019. Retrieved 2020-04-21.
  5. ↑ Manin, Yu. I. (1980). Vychislimoe i nevychislimoe [Computable and Noncomputable] (in Russian). Sov.Radio. pp. 13–15. Archived from the original on 2013-05-10. Retrieved 2013-03-04.
  6. ↑ Feynman, Richard P. (1982-06-01). "Simulating Physics with Computers". International Journal of Theoretical Physics. 21 (6–7): 467–488. Bibcode:1982IJTP...21..467F. CiteSeerX   10.1.1.45.9310 . doi:10.1007/BF02650179. ISSN   0020-7748. S2CID   124545445.
  7. 1 2 Harrow, Aram W.; Montanaro, Ashley (September 2017). "Quantum computational supremacy". Nature. 549 (7671): 203–209. arXiv: 1809.07442 . Bibcode:2017Natur.549..203H. doi:10.1038/nature23458. ISSN   1476-4687. PMID   28905912. S2CID   2514901.
  8. ↑ Papageorgiou, Anargyros; Traub, Joseph F. (2013-08-12). "Measures of quantum computing speedup". Physical Review A. 88 (2): 022316. arXiv: 1307.7488 . Bibcode:2013PhRvA..88b2316P. doi:10.1103/PhysRevA.88.022316. ISSN   1050-2947. S2CID   41867048.
  9. 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, New York, United States: Association for Computing Machinery. pp. 333–342. arXiv: 1011.3245 . doi:10.1145/1993636.1993682. ISBN   9781450306911. S2CID   681637.
  10. 1 2 Aaronson, Scott; Chen, Lijie (2016-12-18). "Complexity-Theoretic Foundations of Quantum Supremacy Experiments". arXiv: 1612.05903 [quant-ph].
  11. 1 2 3 4 Bouland, Adam; Fefferman, Bill; Nirkhe, Chinmay; Vazirani, Umesh (2018-10-29). "On the complexity and verification of quantum random circuit sampling". Nature Physics. 15 (2): 159–163. arXiv: 1803.04402 . doi:10.1038/s41567-018-0318-2. ISSN   1745-2473. S2CID   125264133.
  12. ↑ Hangleiter, Dominik; Eisert, Jens (2023-07-20). "Computational advantage of quantum random sampling". Reviews of Modern Physics. 95 (3): 035001. arXiv: 2206.04079 . Bibcode:2023RvMP...95c5001H. doi:10.1103/RevModPhys.95.035001. S2CID   249538723.
  13. ↑ Metz, Cade (2019-10-23). "Google Claims a Quantum Breakthrough That Could Change Computing (Published 2019)". The New York Times. ISSN   0362-4331 . Retrieved 2020-12-07.
  14. ↑ Aaronson, Scott (2019-10-30). "Opinion | Why Google's Quantum Supremacy Milestone Matters (Published 2019)". The New York Times. ISSN   0362-4331 . Retrieved 2020-12-07.
  15. 1 2 "On "Quantum Supremacy"". IBM Research Blog. 2019-10-22. Retrieved 2019-10-24.
  16. ↑ Crane, Leah. "IBM says Google may not have reached quantum supremacy after all". New Scientist. Retrieved 2020-12-07.
  17. ↑ Turing, Alan (1936). On Computable Numbers, With An Application To The Entscheidungsproblem.
  18. ↑ Benioff, Paul (1980-05-01). "The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines". Journal of Statistical Physics. 22 (5): 563–591. Bibcode:1980JSP....22..563B. doi:10.1007/BF01011339. ISSN   1572-9613. S2CID   122949592.
  19. 1 2 Feynman, Richard P. (1982-06-01). "Simulating physics with computers". International Journal of Theoretical Physics. 21 (6): 467–488. Bibcode:1982IJTP...21..467F. doi:10.1007/BF02650179. ISSN   1572-9575. S2CID   124545445.
  20. ↑ "Quantum Computing". Stanford Encyclopedia of Philosophy. September 30, 2019.
  21. ↑ Shor, Peter (1996). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.
  22. ↑ Monroe, C.; Meekhof, D. M.; King, B. E.; Itano, W. M.; Wineland, D. J. (1995-12-18). "Demonstration of a Fundamental Quantum Logic Gate". Physical Review Letters. 75 (25): 4714–4717. Bibcode:1995PhRvL..75.4714M. doi: 10.1103/PhysRevLett.75.4714 . ISSN   0031-9007. PMID   10059979.
  23. ↑ Grover, Lov K. (1996-11-19). "A fast quantum mechanical algorithm for database search". arXiv: quant-ph/9605043 .
  24. ↑ Jones, J. A.; Mosca, M. (August 1998). "Implementation of a Quantum Algorithm to Solve Deutsch's Problem on a Nuclear Magnetic Resonance Quantum Computer". The Journal of Chemical Physics. 109 (5): 1648–1653. arXiv: quant-ph/9801027 . doi:10.1063/1.476739. ISSN   0021-9606. S2CID   19348964.
  25. ↑ Balaganur, Sameer (2019-11-20). "Man's Race To Quantum Supremacy: The Complete Timeline". Analytics India Magazine. Retrieved 2020-11-16.
  26. ↑ Merali, Zeeya (June 2011). "First sale for quantum computing". Nature. 474 (7349): 18. Bibcode:2011Natur.474...18M. doi: 10.1038/474018a . ISSN   0028-0836. PMID   21637232. S2CID   4425833.
  27. ↑ Battersby, Stephen (13 April 2012). "Controversial quantum computer beats factoring record". New Scientist. Retrieved 2020-11-16.
  28. ↑ Hardy, Quentin (2013-05-16). "Google Buys a Quantum Computer". Bits Blog. Retrieved 2020-11-16.
  29. 1 2 Courtland, Rachel (24 May 2017). "Google Plans to Demonstrate the Supremacy of Quantum Computing". IEEE Spectrum. Retrieved 2018-01-11.
  30. ↑ Hsu, Jeremy (8 January 2018). "CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy". IEEE Spectrum. Retrieved 2017-07-22.
  31. 1 2 Kim, Mark (October 20, 2017). "Google's quantum computing plans threatened by IBM curveball". New Scientist. Retrieved October 22, 2017.
  32. ↑ Harris, Mark (November 5, 2018). "Google has enlisted NASA to help it prove quantum supremacy within months". MIT Technology Review. Retrieved 2018-11-30.
  33. 1 2 Boixo, Sergio; Isakov, Sergei V.; Smelyanskiy, Vadim N.; Babbush, Ryan; Ding, Nan; Jiang, Zhang; Bremner, Michael J.; Martinis, John M.; Neven, Hartmut (23 April 2018). "Characterizing quantum supremacy in near-term devices". Nature Physics. 14 (6): 595–600. arXiv: 1608.00263 . Bibcode:2018NatPh..14..595B. doi:10.1038/s41567-018-0124-x. S2CID   4167494.
  34. ↑ Hartnett, Kevin (June 18, 2019). "A New Law to Describe Quantum Computing's Rise?". Quanta Magazine .
  35. ↑ , Quantum Computing Jobs: Unlocking the Future of Technology, January 2024
  36. ↑ "why is quantum computing useful for optimization problems?". Nowizine. Associated Press.
  37. ↑ "Demonstrating Quantum Supremacy" – via www.youtube.com.
  38. 1 2 "Quantum Supremacy Using a Programmable Superconducting Processor".
  39. ↑ Arute, Frank; et al. (23 October 2019). "Quantum supremacy using a programmable superconducting processor". Nature . 574 (7779): 505–510. arXiv: 1910.11333 . Bibcode:2019Natur.574..505A. doi: 10.1038/s41586-019-1666-5 . PMID   31645734.
  40. ↑ "What the Google vs. IBM debate over quantum supremacy means | ZDNet". www.zdnet.com.
  41. ↑ Zialcita, Paolo (23 October 2019). "Google Claims To Achieve Quantum Supremacy — IBM Pushes Back". NPR. Retrieved 2019-10-24.
  42. ↑ Liu, Yong (Alexander); Liu, Xin (Lucy); Li, Fang (Nancy); Fu, Haohuan; Yang, Yuling; Song, Jiawei; Zhao, Pengpeng; Wang, Zhen; Peng, Dajia; Chen, Huarong; Guo, Chu (2021-11-14). "Closing the "quantum supremacy" gap". Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. SC '21. New York, New York, United States: Association for Computing Machinery. pp. 1–12. arXiv: 2110.14502 . doi:10.1145/3458817.3487399. ISBN   978-1-4503-8442-1. S2CID   239036985.
  43. ↑ Bulmer, Jacob F. F.; Bell, Bryn A.; Chadwick, Rachel S.; Jones, Alex E.; Moise, Diana; Rigazzi, Alessandro; Thorbecke, Jan; Haus, Utz-Uwe; Van Vaerenbergh, Thomas; Patel, Raj B.; Walmsley, Ian A. (2022-01-28). "The boundary for quantum advantage in Gaussian boson sampling". Science Advances. 8 (4): eabl9236. arXiv: 2108.01622 . Bibcode:2022SciA....8.9236B. doi:10.1126/sciadv.abl9236. ISSN   2375-2548. PMC   8791606 . PMID   35080972.
  44. ↑ McCormick, Katie (2022-02-10). "Race Not Over Between Classical and Quantum Computers". Physics. 15: 19. Bibcode:2022PhyOJ..15...19M. doi: 10.1103/Physics.15.19 . S2CID   246910085.
  45. ↑ Pan, Feng; Chen, Keyang; Zhang, Pan (2022). "Solving the Sampling Problem of the Sycamore Quantum Circuits". Physical Review Letters. 129 (9): 090502. arXiv: 2111.03011 . Bibcode:2022PhRvL.129i0502P. doi:10.1103/PhysRevLett.129.090502. PMID   36083655. S2CID   251755796.
  46. ↑ "Ordinary computers can beat Google's quantum computer after all". 2022-08-02. doi:10.1126/science.ade2364.{{cite journal}}: Cite journal requires |journal= (help)
  47. ↑ "Google's 'quantum supremacy' usurped by researchers using ordinary supercomputer". TechCrunch. Retrieved 2022-08-07.
  48. 1 2 Ball, Philip (2020-12-03). "Physicists in China challenge Google's 'quantum advantage'". Nature. 588 (7838): 380. Bibcode:2020Natur.588..380B. doi:10.1038/d41586-020-03434-7. PMID   33273711.
  49. ↑ Garisto, Daniel (December 3, 2020). "Light-based Quantum Computer Exceeds Fastest Classical Supercomputers". Scientific American. Retrieved 2020-12-07.
  50. ↑ Conover, Emily (2020-12-03). "The new light-based quantum computer Jiuzhang has achieved quantum supremacy". Science News. Retrieved 2020-12-07.
  51. ↑ Zhong, Han-Sen; Deng, Yu-Hao; Qin, Jian; Wang, Hui; Chen, Ming-Cheng; Peng, Li-Chao; Luo, Yi-Han; Wu, Dian; Gong, Si-Qiu; Su, Hao; Hu, Yi (2021-10-25). "Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light". Physical Review Letters. 127 (18): 180502. arXiv: 2106.15534 . Bibcode:2021PhRvL.127r0502Z. doi:10.1103/PhysRevLett.127.180502. PMID   34767431. S2CID   235669908.
  52. ↑ Johnston, Hamish (26 October 2021). "Quantum advantage takes a giant leap in optical and superconducting systems". Physics World. Retrieved 2021-10-27.
  53. ↑ Wu, Yulin; Bao, Wan-Su; Cao, Sirui; Chen, Fusheng; Chen, Ming-Cheng; Chen, Xiawei; Chung, Tung-Hsun; Deng, Hui; Du, Yajie; Fan, Daojin; Gong, Ming (2021-10-25). "Strong Quantum Computational Advantage Using a Superconducting Quantum Processor". Physical Review Letters. 127 (18): 180501. arXiv: 2106.14734 . Bibcode:2021PhRvL.127r0501W. doi:10.1103/PhysRevLett.127.180501. PMID   34767433. S2CID   235658633.
  54. ↑ Zhong, Han-Sen; Deng, Yu-Hao; Qin, Jian; Wang, Hui; Chen, Ming-Cheng; Peng, Li-Chao; Luo, Yi-Han; Wu, Dian; Gong, Si-Qiu; Su, Hao; Hu, Yi; Hu, Peng; Yang, Xiao-Yan; Zhang, Wei-Jun; Li, Hao; Li, Yuxuan; Jiang, Xiao; Gan, Lin; Yang, Guangwen; You, Lixing; Wang, Zhen; Li, Li; Liu, Nai-Le; Renema, Jelmer J.; Lu, Chao-Yang; Pan, Jian-Wei (25 October 2021). "Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light". Physical Review Letters. 127 (18): 180502. arXiv: 2106.15534 . Bibcode:2021PhRvL.127r0502Z. doi:10.1103/PhysRevLett.127.180502. PMID   34767431. S2CID   235669908.
  55. ↑ Sanders, Barry C. (2021-10-25). "Quantum Leap for Quantum Primacy". Physics. 14: 147. Bibcode:2021PhyOJ..14..147S. doi: 10.1103/Physics.14.147 . S2CID   244826882.
  56. ↑ Qingling Zhu, Sirui Cao; et al. (25 October 2021). "Quantum computational advantage via 60-qubit 24-cycle random circuit sampling". Science Bulletin. 67 (3): 240–245. arXiv: 2109.03494 . doi:10.1016/j.scib.2021.10.017. ISSN   2095-9273. PMID   36546072. S2CID   237442167.
  57. ↑ Brod, Daniel Jost (1 June 2022). "Loops simplify a set-up to boost quantum computational advantage". Nature. 606 (7912): 31–32. Bibcode:2022Natur.606...31B. doi:10.1038/d41586-022-01402-x. PMID   35650360. S2CID   249277681.
  58. ↑ Madsen, Lars S.; Laudenbach, Fabian; Askarani, Mohsen Falamarzi; Rortais, Fabien; Vincent, Trevor; Bulmer, Jacob F. F.; Miatto, Filippo M.; Neuhaus, Leonhard; Helt, Lukas G.; Collins, Matthew J.; Lita, Adriana E. (1 June 2022). "Quantum computational advantage with a programmable photonic processor". Nature. 606 (7912): 75–81. Bibcode:2022Natur.606...75M. doi:10.1038/s41586-022-04725-x. ISSN   1476-4687. PMC   9159949 . PMID   35650354.
  59. ↑ Cleve, Richard (2000). "An Introduction to Quantum Complexity Theory" (PDF). CERN. Bibcode:2000qcqi.book..103C.
  60. 1 2 Watrous, John (2009). "Quantum Computational Complexity". In Meyers, Robert A. (ed.). Encyclopedia of Complexity and Systems Science . Springer New York. pp.  7174–7201. doi:10.1007/978-0-387-30440-3_428. ISBN   9780387758886. S2CID   1380135.
  61. 1 2 Watrous, John (April 21, 2018). "Quantum Computational Complexity". arXiv: 0804.3401 [quant-ph].
  62. ↑ Tereza, Tusarova (2004-09-26). "Quantum Complexity Classes". arXiv: cs/0409051 .
  63. ↑ Tuˇsarov´a, Tereza (2004). "Quantum complexity classes". arXiv: cs/0409051 .
  64. 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): 15. arXiv: 1702.03061 . Bibcode:2017npjQI...3...15L. doi:10.1038/s41534-017-0018-2. ISSN   2056-6387. S2CID   54628108.
  65. ↑ Gard, Bryan T.; Motes, Keith R.; Olson, Jonathan P.; Rohde, Peter P.; Dowling, Jonathan P. (August 2015). "An introduction to boson-sampling". From Atomic to Mesoscale: the Role of Quantum Coherence in Systems of Various Complexities. World Scientific. pp. 167–192. arXiv: 1406.6767 . doi:10.1142/9789814678704_0008. ISBN   978-981-4678-70-4. S2CID   55999387.
  66. ↑ 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): 080501. arXiv: 1504.07999 . Bibcode:2016PhRvL.117h0501B. doi:10.1103/PhysRevLett.117.080501. ISSN   0031-9007. PMID   27588839. S2CID   8590553.
  67. ↑ Jordan, Stephen. "Quantum Algorithm Zoo". math.nist.gov. Archived from the original on 2018-04-29. Retrieved 2017-07-29.
  68. 1 2 Shor, P. (1999-01-01). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Review. 41 (2): 303–332. arXiv: quant-ph/9508027 . Bibcode:1999SIAMR..41..303S. doi:10.1137/S0036144598347011. ISSN   0036-1445.
  69. ↑ Rubinstein, Michael (2006-10-19). "The distribution of solutions to xy = N mod a with an application to factoring integers". arXiv: math/0610612 .
  70. ↑ 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, New York, United States: Association for Computing Machinery. pp. 55–64. CiteSeerX   10.1.1.674.9429 . doi:10.1145/1536414.1536425. ISBN   9781605585062. S2CID   9052772.
  71. ↑ 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. CiteSeerX   10.1.1.607.2677 . doi:10.1145/359340.359342. ISSN   0001-0782. S2CID   2873616.
  72. ↑ Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (November 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. 6 (11): 773–776. arXiv: 1111.4147 . Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. ISSN   1749-4893. S2CID   46546101.
  73. ↑ Fowler, Austin G.; Mariantoni, Matteo; Martinis, John M.; Cleland, Andrew N. (2012-09-18). "Surface codes: Towards practical large-scale quantum computation". Physical Review A. 86 (3): 032324. arXiv: 1208.0928 . Bibcode:2012PhRvA..86c2324F. doi:10.1103/PhysRevA.86.032324. S2CID   119277773.
  74. ↑ 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. arXiv: 1511.06526 . Bibcode:2016PhRvX...6b1039R. doi:10.1103/PhysRevX.6.021039. S2CID   23490704.
  75. ↑ 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. arXiv: 1505.01182 . doi:10.1126/science.aab3642. ISSN   0036-8075. PMID   26160375. S2CID   19067232.
  76. 1 2 Clifford, Peter; Clifford, Raphaël (2017-06-05). "The Classical Complexity of Boson Sampling". arXiv: 1706.01260 [cs.DS].
  77. 1 2 Neville, Alex; Sparrow, Chris; Clifford, Raphaël; Johnston, Eric; Birchall, Patrick M.; Montanaro, Ashley; Laing, Anthony (2017-10-02). "No imminent quantum supremacy by boson sampling". Nature Physics. 13 (12): 1153–1157. arXiv: 1705.00686 . Bibcode:2017arXiv170500686N. doi:10.1038/nphys4270. ISSN   1745-2473. S2CID   73635825.
  78. ↑ Hans De Raedt; Fengping Jin; Dennis Willsch; Madita Willsch; Naoki Yoshioka; Nobuyasu Ito; Shengjun Yuan; Kristel Michielsen (November 2018). "Massively parallel quantum computer simulator, eleven years later". Computer Physics Communications. 237: 47–61. arXiv: 1805.04708 . doi: 10.1016/j.cpc.2018.11.005 .
  79. ↑ Edwin Pednault; John A. Gunnels; Giacomo Nannicini; Lior Horesh; Thomas Magerlein; Edgar Solomonik; Robert Wisnieff (October 2017). "Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits". arXiv: 1710.05867 [quant-ph].
  80. ↑ "Quantum Supremacy Using a Programmable Superconducting Processor". Google AI Blog. Retrieved 2019-11-02.
  81. ↑ Metz, Cade (23 October 2019). "Google Claims a Quantum Breakthrough That Could Change Computing". The New York Times. Retrieved 14 January 2020.
  82. ↑ Edwin Pednault; John Gunnels; Giacomo Nannicini; Lior Horesh; Robert Wisnieff (October 2019). "Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits". arXiv: 1910.09534 [quant-ph].
  83. ↑ "Google and IBM Clash Over Quantum Supremacy Claim". Quanta Magazine. 23 October 2019. Retrieved 2020-10-29.
  84. 1 2 Kalai, Gil (2011-06-02). "How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation". arXiv: 1106.0485 [quant-ph].
  85. ↑ Shor, Peter W. (1995-10-01). "Scheme for reducing decoherence in quantum computer memory". Physical Review A. 52 (4): R2493–R2496. Bibcode:1995PhRvA..52.2493S. doi:10.1103/PhysRevA.52.R2493. PMID   9912632.
  86. ↑ Steane, A. M. (1996-07-29). "Error Correcting Codes in Quantum Theory". Physical Review Letters. 77 (5): 793–797. Bibcode:1996PhRvL..77..793S. doi:10.1103/PhysRevLett.77.793. PMID   10062908.
  87. ↑ Aharonov, Dorit; Ben-Or, Michael (1999-06-30). "Fault-Tolerant Quantum Computation With Constant Error Rate". arXiv: quant-ph/9906129 .
  88. ↑ Knill, E. (2005-03-03). "Quantum computing with realistically noisy devices". Nature. 434 (7029): 39–44. arXiv: quant-ph/0410199 . Bibcode:2005Natur.434...39K. doi:10.1038/nature03350. ISSN   0028-0836. PMID   15744292. S2CID   4420858.
  89. ↑ Kalai, Gil (2016-05-03). "The Quantum Computer Puzzle (Expanded Version)". arXiv: 1605.00992 [quant-ph].
  90. ↑ Dyakonov, M. I. (2007). "Is Fault-Tolerant Quantum Computation Really Possible?". In Luryi, S.; Xu, J.; Zaslavsky, A. (eds.). Future Trends in Microelectronics. Up the Nano Creek. Wiley. pp. 4–18. arXiv: quant-ph/0610117 . Bibcode:2006quant.ph.10117D.
  91. ↑ Board, The Editorial (17 December 2019). "Opinion | Achieving Quantum Wokeness". Wall Street Journal. Retrieved 2019-12-21.
  92. ↑ Knapton, Sarah (2019-12-17). "Academics derided for claiming 'quantum supremacy' is a racist and colonialist term". The Telegraph. ISSN   0307-1235 . Retrieved 2019-12-21.
  93. ↑ Palacios-Berraquero, Carmen; Mueck, Leonie; Persaud, Divya M. (2019-12-10). "Instead of 'supremacy' use 'quantum advantage'". Nature. 576 (7786): 213. doi: 10.1038/d41586-019-03781-0 . PMID   31822842.
  94. ↑ "Open Letter – Responsibility in Quantum Science".
  95. ↑ Ball, Philip (17 December 2020). "Physicists in China challenge Google's 'quantum advantage'". Nature. 588 (7838): 380. Bibcode:2020Natur.588..380B. doi:10.1038/d41586-020-03434-7. PMID   33273711. S2CID   227282052 . Retrieved 16 December 2020.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.