Posted in: Cognitive Computing, Quantum Computing

Quantum’s advantage solves black box bit riddle

How IBM Q learns parity with noise

Quantum theory met practice in the Nature Quantum Information paper, “Demonstration of quantum advantage in machine learning” when colleagues at IBM Research and I collaborated with scientists at Raytheon BBN to demonstrate 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 we showed that just a few superconducting qubits can discover the hidden string faster and more efficiently than today’s computers.

In a way, the quantum algorithm wins by simply asking the right questions. It’s as if the conventional (“classical”) computer is working blindfolded, stumbling around in the dark, while the quantum method quickly zeroes in on the right solution.

We discovered that even when the output of the black box is noisy, making it even harder for the classical algorithm to find the hidden string, it still remains easy for the quantum computer. This is surprising even to quantum physicists, because usually the very delicate quantum information stored in a quantum computer is extremely susceptible to noise, while classical computers are quite robust.

What’s in the box?

Oddly enough, the quantum computation needed is fairly simple. Building the black box was the difficult part. Raytheon BBN’s team programmed such a black box that, with the push of a button, produces a string of bits with a hidden a pattern (such at 0010) for both a classical computation and a quantum computation. The gray area in the figure below represents the black box. On the left “classical computation” side, the bits (D) are being examined one-by-one (the meter symbols represent an experimental measurement result). 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.

On the right “quantum computation” side, the quantum gates that make up the black box are shown. The gates are known as “controlled-not” gates. Each wire with a black circle on it corresponds to the bits that are one in the hidden string, while the rest are zero. The string represented in the figure is 101.

The quantum algorithm itself is simply several Hadamard or H gates. This is the quantum trick of measuring the output in a different way than is done classically — it isn’t hard, but you have to know quantum physics to do it! The Hadamard gates 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.

Implementation of a parity function in a superconducting circuit. a) Conceptual diagram of parity learning. The (classical or quantum) oracle f ideally maps the parity of a subset of n data bits (or qubits), defined by the bit string k, into bit A. Repeated queries of the oracle allow the reconstruction of k by reading the output register. b) Gate sequence implementing a quantum parity oracle with k = 11…1. Random examples are generated by preparing the data qubits {D1,…,Dn} in a uniform superposition. Vertical lines indicate CNOT gates between each Di (control) and the ancilla qubit A (target). Quantum learning differs from classical learning only by the addition of single-qubit gates (dashed boxes) applied before measurement.

Implementation of a parity function in a superconducting circuit. a) Conceptual diagram of parity learning. The (classical or quantum) oracle f ideally maps the parity of a subset of n data bits (or qubits), defined by the bit string k, into bit A. Repeated queries of the oracle allow the reconstruction of k by reading the output register. b) Gate sequence implementing a quantum parity oracle with k = 101. Random examples are generated by preparing the data qubits {D1,…,Dn} in a uniform superposition. Vertical lines indicate CNOT gates between each Di (control) and the ancilla qubit A (target). Quantum learning differs from classical learning only by the addition of single-qubit gates (dashed boxes) applied before measurement.

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 our study, at just five qubits (access our five qubit machine, here), 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.

Perhaps the right way to look at this work is not as a computation, but rather as a technique for analyzing noisy data. While it is still speculative, it is hoped that our simple demonstration will lead to new ways of using quantum computers to extract useful information from noise. Imagine quantum sensors that could “see” street signs clearly in a storm, despite the visual “noise” of rain or snow.

You can read “Demonstration of quantum advantage in machine learning” by Raytheon BBN’s Diego Ristè, Marcus da Silva, Colm Ryan, and Blake Johnson, and IBM’s Andrew Cross, Antonio Córcoles, Jay M. Gambetta, Jerry Chow, and me, here. For more about the origins of the idea, read our 2015 APS Physics paper, “Quantum learning robust against noise.”

And explore the algorithm we used for this black box experiment, as well as many other algorithms, on IBM Q. Developers interested in quantum can also try our API on Github.

 

Comments

Add Comment

Your email address will not be published. Required fields are marked *

John Smolin, quantum computation

John Smolin

Quantum Computation Scientist, IBM Research