(Medium) A new paper has proven that under the right circumstances, there are situations where even noisy quantum computers prone to unexpected changes in their qubit values can beat a classical computer — on a circuit you can run yourself.
Two years ago, a team of international researchers including IBM’s Sergey Bravyi proved that quantum effects allowed these limited quantum computers to outperform classical computers for a certain selection of problems, so long as the classical computers were constrained to running constant-depth circuits — circuits with an upper bound to the number of discrete steps they could run. Bravyi’s team has now published a proof of an algorithm where quantum computers hampered by noise, like the ones that exist today, can beat a classical computer running constant-depth circuits.
Bravyi explained, “From the complexity theory perspective, this result constitutes the first rigorous separation between the computational power of noisy constant-depth quantum circuits and noiseless constant-depth classical circuits.”
Upcoming generations of quantum computers may actually be able to run this circuit with the help of these error correction strategies, which introduce redundant qubits in order to avoid errors.
These papers do not represent quantum computers utterly crushing classical computers, nor do they represent algorithms with obvious applications. But think of them as foundation building; each place where scientists unequivocally prove a speedup of a quantum computer over some element of classical computation helps us better understand these devices, and could act as signposts toward quantum applications in the future.
Running the magic square problem isn’t outside the realm of an IBM device with Qiskit, either. The article ends with code for readers to try out and modify on their own.
This Proof Demonstrates a Quantum Advantage–Even for Noisy Quantum Computers
