Researchers from IBM T. J. Watson Research Center, the University of Waterloo, Canada, and the Technical University of Munich, Germany, have proved theoretically that quantum computers can solve certain problems faster than classical computers. The algorithm they devised fits the limitations of current quantum computing processors, and an experimental demonstration may come soon.
Researchers from IBM T. J. Watson Research Center, the University of Waterloo, Canada, and the Technical University of Munich, Germany, have proved theoretically that quantum computers can solve certain problems faster than classical computers. The algorithm they devised fits the limitations of current quantum computing processors, and an experimental demonstration may come soon.
Strictly speaking, the three researchers – Sergey Bravyi, David Gosset, and Robert König – have shown that
parallel quantum algorithms running in a constant time period are strictly more powerful than their classical counterparts; they are provably better at solving certain linear algebra problems associated with binary quadratic forms.
The proof they provided is based on an algorithm to solve a quadratic “hidden linear function” problem that can be implemented in quantum constant-depth. A hidden linear function is a linear function that is not entirely known but is “hidden” inside of another function you can calculate. For example, a linear function could be hidden inside of an oracle that can be queried. The challenge is to fully characterize the hidden linear function based on the results of applying the known function. If this sounds somewhat similar to the problem of inverting a public key to find its private counterpart, it is no surprise, since this is exactly what it is about. In the case of an oracle, the problem is solved by the classical Bernstein-Vazirani algorithm, which minimizes the number of queries to the oracle. Now, according to the three researchers, the fact that the Bernstein-Vazirani algorithm is applied to an oracle limits its practical applicability, so they suggest “hiding” a linear function inside a bidimensional grid graph. After proving that this is indeed possible, they built a quantum constant-depth algorithm to find the hidden function out.
The other half of the proof provided by the researchers is showing that, contrary to a quantum circuit, any classical circuit needs to increase its depth as the number of inputs grows. For example, while the quantum algorithm can solve that problem using at most a quantum circuit of depth 10 no matter how many inputs you have, you need, say, a classical circuit of depth 10 for a 16 inputs problem; a circuit of depth 14 for a 32 inputs problem; a circuit of depth 20 for a 64 inputs problem, and so on. This second part of the proof is philosophically deeply interesting, since it dwells on the idea of quantum nonlocality, which in turn is related to quantum entanglement, one of the most peculiar properties of quantum processors along with superposition. So, quantum advantage would seem to derive from the most intrinsic properties of quantum physics.
At the theortical level, the value of this achievement is not to be underestimated either. As IBM Q Vicepresident Bob Sutor wrote:
The proof is the first demonstration of unconditional separation between quantum and classical algorithms, albeit in the special case of constant-depth computations.
Previously, the idea that quantum computer were more powerful than classical ones was based on factorization problems. Shor showed quantum computers can factor an integer in polynomial time, i.e. more efficiently than any know classical computer algorithms. Albeit an interesting result, this did not rule out the possibility that a more efficient classical factorization algorithm could indeed be found. So unless one conjectured that no efficient solution to the factorization problem could exist, which is equivalent to demonstrate that “ P ≠ NP ”, one could not really say that quantum advantage was proved.
As mentioned, Bravyi, Gosset, and König’s algorithm, relying on a constant number of operations (the depth of a quantum circuit) seems to fit just right with the limitation of current quantum computer processors. Those are basically related to qubits’ error rate and coherence time, which limit the maximal duration of a sequence of operations and their overall number. Therefore, using short-depth circuits is key for any feasible application of current quantum circuits. Thanks to this property of the proposed algorithm, IBM researchers are already at work ot demonstrate quantum advantage using IBM quantum computer, Sutor remarks.
If you are interested in the full details of the proof, do not miss the talk David Gosset gave at the Perimeter Institute for Theoretical Physics along with the presentation slides .
