Researchers Finally Proved Quantum Computers are More Powerful Than Classical Computers
Until this week, there was no conclusive proof that quantum computers have an advantage over classical computers.
Oct 19 2018, 1:00pm
For the first time, an international team of researchers has proven that quantum computers offer a computational advantage over classical computers.
As detailed in a paper published Thursday in Science, the researchers designed a quantum circuit that was able to solve a math problem that would be impossible for a classical computer to solve when subject to the same constraints.
“Our work shows that quantum circuits are computationally more powerful than classical ones of the same structure,” Robert König, a complexity theorist at the Technical University of Munich and lead author of the paper, told me in an email. “We are not saying that the problem cannot be solved classically. It can, though this requires more resources.”
The team was able to achieve quantum advantage due to “nonlocality,” a feature of spatially isolated quantum systems that allows them to be considered a single system: a change in one system instantaneously results in a change in another.
Qubits are the quantum analog of bits in a classical computer, except rather being either a one or a zero, qubits can be in a “superposition” of both states at the same time.
When designing quantum circuits, there’s a tradeoff between the number of qubits interacting in the circuit and the number of operations that can be performed on those qubits, also known as the “depth” of the circuit. Increasing the number of qubits or the “depth” of a quantum circuit will increase its information-processing abilities.
But increasing one of these parameters demands a corresponding decrease in the other. A circuit with a large number of qubits that would be difficult to simulate with a classical computer is limited to a small number of operations (it has a “shallow” depth), which makes its advantage over classical computers difficult to prove.
This is because a quantum circuit that doesn’t incorporate error correction is limited in the number of operations that can be performed on the qubits before they succumb to noise and decohere, losing their information content. As more qubits are thrown into the mix, there’s more room for error, resulting in a drop in the number of operations that can be performed before they decohere.
In this case, König and his colleagues designed a quantum circuit in which several shallow circuits operate in parallel, yet can still be considered to be a single system due to nonlocality. These shallow circuits were able to solve an algebra problem using a fixed number of operations (that is, they had a “constant depth”) which is mathematically impossible for a classical circuit with a constant depth.
Large-scale quantum computers are expected to dramatically outperform even the most powerful classical supercomputers by leveraging properties of quantum mechanics such as superposition and nonlocality.
These advantages will, in theory, allow future quantum computers to perform certain types of calculations far faster than a classical computer. Shor’s algorithm, for instance, allows quantum computers to efficiently find the prime factors for a given number and may eventually allow quantum computers with a large number of qubits to crack most modern forms of encryption. Classical computers, on the other hand, wouldn’t be able to crack that encryption before the heat death of the universe, even with all the computing power on Earth.
Read More: Countdown to the Crypto Apocalypse
Interestingly, one of the most vexing problems for scientists studying quantum computing is the ability to say when a quantum computer has definitively outstripped the abilities of a classical computer. For example, Shor’s algorithm is able to factor primes more efficiently than a classical computer, whichdoesn’t necessarily mean the same level efficiency is impossible to achieve with a classical computer. It could be the case that the right method simply hasn’t been discovered yet.
This brings us to the realm of complexity theory, which is inhabited by researchers probing the boundary between classical and quantum computers. Although complexity theory has plenty of conjectures as to why various quantum algorithms are beyond the reach of classical computers, these conjectures haven’t been proved—until now.
König and his colleagues see their work as laying the mathematical foundations for practical, experimental applications in the near future. Unlike many quantum algorithms that are so complex that they can only be implemented on a large-scale quantum computer, these shallow quantum computing circuits were designed to be within the grasp of experimental quantum computers in the near future.
“Experimental realization of such circuits will require additional considerations, including a study of the effects of noise and an optimization of the number of qubits required,” König told me. “Our work is a proof-of-principle showing that quantum computers can indeed be better at solving a certain problem. This is good to know, but in practice, we'd like to address less contrived problems that appear in other areas of science.”