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.
In the Nature Physics paper, “Quantum advantage for computations with limited space,” IBM Quantum scientists prove mathematically 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 user-written 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.
