Quantum supremacy
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Quantum Supremacy: How the Quantum Computer Revolution Will Change Everything is a non-fiction book by the American futurist and physicist Michio Kaku. The book, Kaku's eleventh, was initially published on 2 May 2023 by Doubleday.
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. The term was coined by John Preskill in 2011, but the concept dates 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.
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. Examples of proposals to demonstrate quantum supremacy include the boson sampling proposal of Aaronson and Arkhipov, 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.
Criticisms
See also
Gottesman–Knill theorem List of quantum processors Sycamore processor Jiuzhang (quantum computer) Noisy intermediate-scale quantum era
Text derived from https://en.wikipedia.org/w/index.php?oldid=1365153700 under CC BY-SA 4.0; modifications have been made.