[1][2][3] The term was coined by John Preskill in 2011,[1][4] but the concept dates to Yuri Manin's 1980[5] and Richard Feynman's 1981[6] proposals 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.
In 1980, Paul Benioff used Turing's paper to propose the theoretical feasibility of Quantum Computing.
[25] In 2011, D-Wave Systems of Burnaby, British Columbia, Canada became the first company to sell a quantum computer commercially.
[28] Google had announced plans to demonstrate quantum supremacy before the end of 2017 with an array of 49 superconducting qubits.
[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.
"[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.
[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".
[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.
[3] In October 2021, teams from USTC again reported quantum primacy by building two supercomputers called Jiuzhang 2.0 and Zuchongzhi.
[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".
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.
The task performed was the simulation of the non-equilibrium dynamics of a magnetic spin system quenched through a quantum phase transition.
[59] 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.
[62] The difficulty of proving what cannot be done with classical computing is a common problem in definitively demonstrating quantum supremacy.
[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.
[48] The following are proposals for demonstrating quantum computational supremacy using current technology, often called NISQ devices.
It was the first polynomial-time quantum algorithm proposed for a real-world problem that is believed to be hard for classical computers.
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.
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.
[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.
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.
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.