Quantum supremacy
In quantum computing, quantum supremacy is the goal of demonstrating that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time. By comparison, the weaker quantum advantage is the demonstration that a quantum device can solve a problem merely faster than classical computers. 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. The term was originally popularized by John Preskill but the concept of a quantum computational advantage, specifically for simulating quantum systems, dates back to Yuri Manin's and Richard Feynman's proposals of quantum computing.
Examples of proposals to demonstrate quantum supremacy include the boson sampling proposal of Aaronson and Arkhipov, D-Wave's specialized frustrated cluster loop problems, and sampling the output of random quantum circuits.
Like factoring integers, sampling the output distributions of random quantum circuits is believed to be hard for classical computers based on reasonable complexity assumptions. Google previously announced plans to demonstrate quantum supremacy before the end of 2017 by solving this problem with an array of 49 superconducting qubits. In early January 2018, Intel announced a similar hardware program. In October 2017, IBM demonstrated the simulation of 56 qubits on a conventional supercomputer, increasing the number of qubits needed for quantum supremacy. 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.” Theoretical work published in 2018 suggests that quantum supremacy should be possible with a "two-dimensional lattice of 7x7 qubits and around 40 clock cycles" if error rates can be pushed low enough. On June 18, 2019, Quanta Magazine suggested that quantum supremacy could happen in 2019, according to Neven's law. On September 20, 2019, the Financial Times reported that "Google claims to have reached quantum supremacy with an array of 54 qbits 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". On October 23, Google officially confirmed the claims. IBM responded by suggesting some of the claims are excessive, and suggested that it could take 2.5 days instead of 10,000 years.
Computational complexity
arguments concern how the amount of some resource needed to solve a problem scales with the size of the input. As an extension of classical computational complexity theory, quantum complexity theory considers what a theoretical universal quantum computer could accomplish without necessarily accounting for the difficulty of building a physical quantum computer or dealing with decoherence and noise. Since quantum information is a generalization of classical information, quantum computers can simulate any classical algorithm.The complexity class BQP is the class of decision problems that can be solved in polynomial time by a universal quantum computer. It is related to important classical complexity classes by the hierarchy. Whether any of these containments is proper is still an open question.
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. 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. 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. The arguments used to reach this conclusion have also been extended to IQP Sampling, where only the conjecture that the average- and worst-case complexities of the problem are the same is needed.
Proposed experiments
The following are proposals for demonstrating quantum computational supremacy using current technology, often called NISQ devices. Such proposals include a well-defined computational problem, a quantum algorithm to solve this problem, a comparison best-case classical algorithm to solve the problem, and a complexity-theoretic argument that, under a reasonable assumption, no classical algorithm can perform significantly better than current algorithms.Shor's algorithm for factoring integers
This algorithm finds the prime factorization of an n-bit integer in time whereas the best known classical algorithm requires time and the best upper bound for the complexity of this problem is. 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.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. Namely, it gives a superpolynomial speedup under the reasonable assumption that RSA, today's most common encryption protocol, is secure.
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, so it is not being pursued as a strategy for demonstrating supremacy.
Boson sampling
This computing paradigm based upon identical photons sent through a linear-optical network can solve certain sampling and search problems that, assuming a few complexity-theoretical conjectures are intractable for classical computers. However, it has been shown that boson sampling in a system with large enough loss and noise can be simulated efficiently.The largest experimental implementation of boson sampling to date had 6 modes so could handle up to 6 photons at a time. The best proposed classical algorithm for simulating boson sampling runs in time for a system with n photons and m output modes. is an open-source implementation in R. The algorithm leads to an estimate of 50 photons required to demonstrate quantum supremacy with boson sampling.
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. Google had 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. The largest universal quantum circuit simulator running on classical supercomputers at the time was able to simulate 48 qubits. But for particular kinds of circuits, larger quantum circuit simulations with 56 qubits are possible. This may require increasing the number of qubits to demonstrate quantum supremacy. 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 made 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. IBM disputed this claim, saying that an improved classical algorithm should be able to solve that problem in two and a half days in that same supercomputer.Skepticism
are much more susceptible to errors than classical computers due to decoherence and noise. The threshold theorem states that a noisy quantum computer can use quantum error-correcting codes to simulate a noiseless quantum computer assuming the error introduced in each computer cycle is less than some number. Numerical simulations suggest that that number may be as high as 3%. However, it is not known how the resources needed for error correction will scale with the number of qubits. 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.There have also been algorithmic breakthroughs in classical computing as a result of quantum computing research resulting in comparable performance of classical computers. This implies that at some level quantum supremacy may be trying to prove a negative; that an algorithm doesn't exist that allows classical computers to perform equally well.