Quantum supremacy
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.
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.
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.
Background
Quantum supremacy in the 20th century
In 1936, Alan Turing published his paper, "On Computable Numbers", in response to the 1900 Hilbert Problems. Turing's paper described what he called a "universal computing machine", which later became known as a Turing machine. In 1980, Paul Benioff used Turing's paper to propose the theoretical feasibility of Quantum Computing. His paper, "The Computer as a Physical System: A Microscopic Quantum Mechanical Hamiltonian Model of Computers as Represented by Turing Machines", was the first to demonstrate that it is possible to show the reversible nature of quantum computing as long as the energy dissipated is arbitrarily small. In 1981, Richard Feynman showed that quantum mechanics could not be efficiently simulated on classical devices. During a lecture, he delivered the famous quote, "Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy." Soon after this, David Deutsch produced a description for a quantum Turing machine and designed an algorithm created to run on a quantum computer.In 1994, further progress toward quantum supremacy was made when Peter Shor formulated Shor's algorithm, streamlining a method for factoring integers in polynomial time. In 1995, Christopher Monroe and David Wineland published their paper, "Demonstration of a Fundamental Quantum Logic Gate", marking the first demonstration of a quantum logic gate, specifically the two-bit "controlled-NOT". In 1996, Lov Grover put into motion an interest in fabricating a quantum computer after publishing his algorithm, Grover's Algorithm, in his paper, "A fast quantum mechanical algorithm for database search". In 1998, Jonathan A. Jones and Michele Mosca published "Implementation of a Quantum Algorithm to Solve Deutsch's Problem on a Nuclear Magnetic Resonance Quantum Computer", marking the first demonstration of a quantum algorithm.
Progress in the 21st century
Vast progress toward quantum supremacy was made in the 2000s from the first 5-qubit nuclear magnetic resonance computer, the demonstration of Shor's theorem, and the implementation of Deutsch's algorithm in a clustered quantum computer. In 2011, D-Wave Systems of Burnaby, British Columbia, Canada became the first company to sell a quantum computer commercially. In 2012, physicist Nanyang Xu landed a milestone accomplishment by using an improved adiabatic factoring algorithm to factor 143. However, the methods used by Xu were met with objections. Not long after this accomplishment, Google purchased its first quantum computer.Google had announced plans to demonstrate quantum supremacy before the end of 2017 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 classical supercomputer, thereby increasing the computational power needed to establish 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 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. The scheme discussed was a variant of a quantum random sampling scheme in which qubits undergo random quantum circuits featuring quantum gates drawn from a universal gate set, followed by measurements in the computational basis.
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 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".
This announcement was met with a rebuttal from Google's direct competitor, IBM. IBM contended that the calculation Google claimed would take 10,000 years could be performed in just 2.5 days on its own Summit supercomputer if its architecture were optimized, sparking a debate over the precise threshold for "quantum supremacy"
However, separate from this debate, the demonstration that Google's Sycamore processor could perform a specific calculation significantly faster than the most powerful existing supercomputer is considered a major scientific achievement. The research was published in the peer-reviewed scientific journal Nature. In 2024, the Google team estimated that, thanks to improvements in classical tensor network algorithms, simulating 53 qubits would take only six seconds on the Frontier supercomputer.
In December 2020, a group based in the University of Science and Technology of China led by Pan Jianwei reached quantum supremacy by implementing gaussian boson sampling on 76 photons with their photonic quantum computer Jiuzhang. The paper states that to generate the number of samples the quantum computer generates in 200 seconds, a classical supercomputer would require 2.5 billion years of computation.
In October 2021, teams from USTC again reported quantum primacy by building two supercomputers called Jiuzhang 2.0 and Zuchongzhi. The light-based Jiuzhang 2.0 implemented gaussian boson sampling to detect 113 photons from a 144-mode optical interferometer and a sampling rate speed up of – a difference of 37 photons and 10 orders of magnitude over the previous Jiuzhang. 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. 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".
In June 2022, Xanadu reported a boson sampling experiment summing to those of Google and USTC. 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. They detected a mean of 125 up to 219 photons from 216 squeezed modes and claim to have obtained a speedup 50 million times more than previous experiments.
In March of 2024, D-Wave Systems reported on an experiment using a quantum annealing based processor that out-performed classical methods including tensor networks and neural networks. They argued that no known classical approach could yield the same results as the quantum simulation within a reasonable time-frame and claimed quantum supremacy. The task performed was the simulation of the non-equilibrium dynamics of a magnetic spin system quenched through a quantum phase transition.
A later tensor network-based study, however, questioned this advantage, demonstrating that a number of the D-Wave supremacy experiments can be simulated with comparable or superior accuracy on classical hardware using efficient, optimized tensor network techniques.
Achievements in quantum error correction
Google is also considered a leader in the field of quantum error correction, one of the biggest challenges in quantum computing. In research also published in Nature, the company was the first to demonstrate that it was possible to build a logical qubit with a lower error rate than the physical qubits that constitute it.This is seen as a crucial step toward fault-tolerant quantum computers, which are necessary for practical applications. Whereas the "quantum supremacy" experiment demonstrated the potential 'speed' of quantum computers, this research demonstrated their potential for 'stability' and 'reliability'.
Furthermore, Google contributes to the open-source research ecosystem by providing software frameworks such as Cirq and TensorFlow Quantum, which allow researchers to develop and test new quantum algorithms.