Quantum supremacy

In quantum computing, quantum supremacy, quantum primacy 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. The term was coined by John Preskill in 2012, but the concept dates back to Yuri Manin's 1980 and Richard Feynman's 1981 proposals of quantum computing. 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. 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. 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. A notable property of quantum supremacy is that it can be feasibly achieved by near-term quantum computers, since it does not require a quantum computer to perform any useful task or use high-quality quantum error correction, both of which are long-term goals. Consequently, researchers view quantum supremacy as primarily a scientific goal, with relatively little immediate bearing on the future commercial viability of quantum computing. Due to unpredictable possible improvements in classical computers and algorithms, quantum supremacy may be temporary or unstable, placing possible achievements under significant scrutiny.