Proving the advantage of quantum scratch space over classical scratch space
New research mathematically proves that there are functions that the restricted classical computer cannot compute, but that the restricted quantum computer can.
New research mathematically proves that there are functions that the restricted classical computer cannot compute, but that the restricted quantum computer can.
Quantum computers will, we hope, soon offer advantages over today's classical computers when it comes to tackling certain important problems. But quantum computers won't beat their classical counterparts based simply on the fact that their underlying architecture is different. We must find and write theoretical proofs of these advantages, and then demonstrate them experimentally. Here, for the first time that we are aware of, we report a simultaneous proof and experimental verification of a new kind of quantum advantage. Specifically, we show that qubits, even today's noisy qubits, offer more value than bits as a medium of storage during computations.
Our team thinks of computing in terms of circuits. At the start of a circuit, we have a number of classical or quantum bits, like swimmers in swim lanes. We set these bits to an initial value, and then the circuit progresses forward through a userwritten program, consisting of gates. Different gates have different effects on these bits. The output of such a circuit is a set of zeroes and ones in both the classical and quantum case.
In the classical version, these bits are switches that can only take one of two positions—on or off—and can interact inside gates that flip switches based on the inputs to this gate. Quantum bits, however, have access to a larger space of values; they can take on a combination of the two switch positions each with a corresponding amplitude, represented by a complex number. Quantum gates create states incorporating every possible combination of switch positions, and combinations of gates can increase or decrease the amplitudes across a state spanning many qubits. Upon measurement, each qubit returns a single classical bit, with the amplitudes dictating the probability of returning each qubit value.
In our work, “Quantum advantage for computations with limited space,”^{1} published today in Nature Physics, we explored what we call the limited space computations. These are circuits restricted to using twoinput gates, and limited to using one bit of computational/scrap space. This restriction allows us to establish a fair comparison between the power of classical and quantum computational space, and in particular demonstrate a fundamental advantage of computing with qubits over classical bits.
Through our research, we're exploring a very simple question: how does the computational power differ when a computer has access to classical scratch space versus quantum scratch space?
In our paper, we prove mathematically that there are functions that the restricted classical computer cannot compute but that the restricted quantum computer can.
We didn't stop at theoretical proofs for this paper, though—we also pitted a real (albeit noisy) quantum computer against a classical computer. Our demonstration includes the study of the simplest function that cannot be computed classically in the onebit limited space model: finding the majority of three bits (that is, returning zero if more than half of the bits are zero, and returning one if more than half of the bits are one).
We armed the limited classical computer with access to random Boolean gates to further increase its computational capabilities. But even with access to this randomness, the classical computer can only succeed 87.5 percent of the time whereas a perfect, noiseless quantum computer could succeed 100 percent of the time.
Of course, real quantum computers today are noisy, which degrades the success probability. To combat this, we calibrated special entangling gates—fractional The controlledNOT gate, also known as the controlledx (CX) gate, acts on a pair of qubits, with one acting as ‘control’ and the other as ‘target.’ It performs a NOT on the target whenever the control is in state ∣1⟩. If the control qubit is in a superposition, this gate creates entanglement.CNOT gates—in order to perform these circuits more efficiently. Using this technique, our limitedspace quantum computer demonstrated a success rate of 93 percent, still beating the limitedspace classical computer. This result demonstrates that a noisy quantum computer with as few as four qubits (three input qubits to encode the input; one qubit to use as computational or scrap space) can perform calculations inaccessible to a perfect classical computer.
But we didn't stop there. Quantum computers also face the challenge of limited qubit connectivity. In the threeinput, onecomputational qubit case, each input qubit can interact directly with the computational qubit. However, when we expand the problem to more input qubits (four, five, and six inputs), not all inputs can interact directly with the computational qubit due to the topology of our quantum hardware—how the qubits connect to one another. Therefore, in practice we must implement costly The SWAP gate swaps the states of two qubits.SWAP operations in order to execute these circuits.
While our publication shows that the quantum computer can still outperform the classical computer with larger numbers of inputs despite having to implement the SWAP gates, we can leverage a new hardware capability, midcircuit reset, to further improve the performance of circuits. Now, instead of SWAPing qubits to interact them with the computational qubit, we can reset the physical qubits that are adjacent to the computational qubit and reinitialize them to a new qubit state. With high fidelity midcircuit reset, we show an improvement of 3 percent over the SWAP circuits.
This is result has important implication—it shows that quantum computers, even noisy quantum computers, are powerful computational tools. This result seems to “break” a wellknown boundary set by physicist Alexander Holevo—we know from Holevo's work that one qubit can only store one bit of information, but our paper demonstrates that you can store much more than one bit as the intermediate results of a computation.
At an even deeper level, demonstrating that quantum systems do things that classical physics cannot explain has long been a fundamental part of the study of quantum information science. Most famously, physicist John Stewart Bell showed that the classical rules of physics and probability fail to explain the behavior of correlated particles obeying the rules of quantum mechanics, even if the particles are too far away to communicate.
Our team continued the legacy of Bell with similarspirited tests of our own. Prior to this work, we explored what happened if we limited the depth of computation, but not the available bits. We proved that not only do perfect quantum computers give an advantage over classical computers on these “shallow circuits,” but even noisy quantum computers do. Taken together, our work shows how quantum computers compare to classical computers in terms of both computational time and space.
The IBM Quantum team is continuing to develop hardware that we hope will provide speedups for some of today's hardest quantum computing problems, as well as improvements to the variety of operations accessible to quantum computations in order to maximize the performance of that hardware. Amid this development, the theory team will continue to carry out equally important work: investigating and demonstrating the uniqueness of quantum computation, and what kinds of benefits over classical computers such uniqueness may deliver.
Notes
 Note 1: The controlledNOT gate, also known as the controlledx (CX) gate, acts on a pair of qubits, with one acting as ‘control’ and the other as ‘target.’ It performs a NOT on the target whenever the control is in state ∣1⟩. If the control qubit is in a superposition, this gate creates entanglement. ↩︎
 Note 2: The SWAP gate swaps the states of two qubits. ↩︎
References

Maslov, D., Kim, J., Bravyi, S., et. al. Quantum advantage for computations with limited space. Nat. Phys. (2021). ↩