#### Quantum Computing

# Quantum’s advantage solves black box bit riddle

April 21, 2017 | Written by: IBM Research Editorial Staff

Categorized: Cognitive Computing | Quantum Computing

Share this post:

*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.

**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.

### Archaeologists Seek to Unearth Mysterious Geoglyphs in Peru Using IBM AI and Geospatial Data

After uncovering a new Nasca Line formation with IBM Watson Machine Learning Accelerator on IBM Power Systems, Yamagata University will deploy IBM PAIRS in the hopes of further discoveries with AI.

### IBM’s African Scientists Look to Tackle the Continent’s Pressing Healthcare Challenges with AI

A majority of African countries still have fewer than one doctor for every one thousand people, and with the African population expected reach 1.6 billion by 2030, up from 1 billion in 2010, this is not just problematic, but catastrophic. Just as alarming is that the World Health Organization projects that by 2020 the burden […]

### Progress in IBM & Hartree Collaboration Reduces Physical Prototype Testing, Protects Crops from Pests and Improves Mobile Phone Coverage

More than 24 months ago, IBM and the Science and Technology Facilities Council (STFC) Hartree Centre set an ambitious goal for themselves — enable UK businesses to use modelling, simulation and Big Data Analytics on real problems to develop better products and services that will boost productivity, drive growth, increase UK competitiveness and create jobs. […]