Quantum supremacy

Quantum supremacy or "quantum advantage" is the potential ability of quantum computing devices to solve problems that classical computers practically cannot. In computational complexity-theoretic terms, this generally means providing a superpolynomial speedup over the best known or possible classical algorithm. 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 (1980) and Richard Feynman's (1981) proposals of quantum computing.

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. Although it is yet to be proved, factoring is generally believed to be hard using classical resources. The difficulty of proving what cannot be done with classical computing is a common problem in definitively demonstrating quantum supremacy. It also affects 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. However, as of early January 2018, only Intel has announced such hardware. In October 2017, IBM demonstrated the simulation of 56 qubits on a conventional supercomputer, increasing the number of qubits needed for quantum supremacy.

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. Since quantum information is a generalization of classical information, it is clear that a quantum computer can efficiently simulate any classical algorithm.

...
Wikipedia