Scientists from IBM Research and Raytheon BBN have demonstrated one of the first proven examples of a quantum computer’s advantage over a classical computer. By probing a black box containing an unknown string of bits, they showed that just a few superconducting qubits can discover the hidden string faster and more efficiently than today’s computers. Their research was published in the paper, “Demonstration of quantum advantage in machine learning” Nature Quantum Information.
With only a five superconducting quantum bit processor, the quantum algorithm consistently identified the sequence in up to a 100-fold fewer computational steps and was more tolerant of noise than the classical (non-quantum) algorithm. This is much larger than any previous head-to-head comparison between quantum and classical processors.
“In a way, the quantum algorithm wins by simply asking the right questions. It’s as if the classical computer is working blindfolded, stumbling around in the dark, while the quantum method quickly zeroes in on the right solution,” said John Smolin, Quantum Computation Scientist, IBM Research.
Raytheon BBN’s team programmed a black box such that, with the push of a button, it produces a string of bits with a hidden a pattern (such as 0010) for both a classical computation and a quantum computation. The classical computer examines the bits one by one. Each result gives a little information about the hidden string, and the classical computer queries the black box many times until it can determine the full answer.
The quantum computer employs a quantum algorithm to measure the output in a different way than is done classically. The quantum computer is able to extract the information hidden in the quantum phase — information to which a classical algorithm is completely blind. The bits are then measured as usual and, about half the time, the hidden string can be immediately read out.
Information vs. computation
This bit string challenge looks for missing information, and is not a computational horsepower comparison between classical and quantum computers. This is why the quantum processor used for the study, at just five qubits, can find an unknown bit string in fewer queries than a classical computer.
This is a particular type of machine learning, where a computer tries to learn a domain when given indirect or noisy information about it.
As the size of the hidden string grows, not only do the number of queries, but also the amount of computational work the classical computer needs to do to find the hidden string becomes greater. At some point, a quantum computer with 100-200 qubits and large enough quantum volume would be able to find a string so complicated that there would not be enough time left in the universe for the most-powerful (non-quantum) supercomputer to find the answer.