Physicists have been talking about the power of quantum computing for more than 30 years, but the questions have always been: Will it ever do something useful, and is it worth investing in? For such large-scale endeavors, it is good engineering practice to formulate decisive short-term goals that demonstrate whether the designs are going in the right direction. So, scientists at Google devised an experiment as an important milestone to help answer these questions. This experiment, referred to as a quantum supremacy experiment, provided direction for the team to overcome the many technical challenges inherent in quantum systems engineering to make a computer that is both programmable and powerful. To test the total system performance, a sensitive computational benchmark was selected that fails if just a single component of the computer is not good enough.
The results of this quantum supremacy experiment have been published in the Nature article “Quantum Supremacy Using a Programmable Superconducting Processor.” A new 54-qubit processor, named “Sycamore,” was developed that is comprised of fast, high-fidelity quantum logic gates in order to perform the benchmark testing. The machine performed the target computation in 200 seconds, and measurements in the experiment revealed that the world’s fastest supercomputer would require 10,000 years to produce a similar output.
The Experiment
To get a sense of how this benchmark works, imagine enthusiastic quantum computing neophytes visiting the laboratory in order to run a quantum algorithm on the new processor. They can compose algorithms from a small dictionary of elementary gate operations. Because each gate has a probability of error, the guests would want to limit themselves to a modest sequence with about a thousand total gates. Assuming these programmers have no prior experience, they might create what essentially looks like a random sequence of gates, which one could think of as the “hello world” program for a quantum computer. Because random circuits have no structure that classical algorithms can exploit, emulating such quantum circuits typically takes an enormous amount of classical supercomputer effort.
Each run of a random quantum circuit on a quantum computer produces a bitstring, for example 0000101. Owing to quantum interference, some bitstrings are much more likely to occur than others when we repeat the experiment many times. However, finding the most likely bitstrings for a random quantum circuit on a classical computer becomes exponentially more difficult as the number of qubits (width) and number of gate cycles (depth) grow.
In the experiment, the scientists first ran random simplified circuits from 12 up to 53 qubits, keeping the circuit depth constant. They checked the performance of the quantum computer using classical simulations and compared with a theoretical model. Once they verified that the system was working, they ran random hard circuits with 53 qubits and increasing depth, until reaching the point where classical simulation became infeasible.
This result is the first experimental challenge against the extended Church-Turing thesis, which states that classical computers can efficiently implement any “reasonable” model of computation. With the first quantum computation that cannot reasonably be emulated on a classical computer, a new realm of computing has been opened up to be explored.