Using Grover's Algorithm

Using the qubit phase

Machine learning can be thought of as a search problem. Given only observations of inputs and related outputs, we can characterize the learning problem as searching for a mapping of inputs to the correct outputs. A good mapping, the solution to the search problem, allows predicting the output for any given input.

Logically, the mapping is a function, such as $y=f(x)$ with $x$ as the input and $y$ as the output. The problem is that we don’t know anything about the function $f$. If we did, we wouldn’t need to learn it from the data. We would specify it directly.

If we can’t specify the function, the next best thing we can do is find an approximation of the function $f$. Since we don’t know anything about the mapping function $f$, we can’t tell how good an approximation would look. It could be a mathematical function. It could be a Bayesian system. It could even be an artificial neural network. There are infinitely many possible approximations, and we don’t know which kind of approximation would work best.

We can think of all possible approximations of the mapping function as a huge search space. The learning task is to search this space for a good enough approximation. In general, searches involve trial and error. We can try a possible solution, see how it performs, and adjust the solution accordingly.

How Grover’s algorithm works

In many situations, we need to find one particular item in a set of many items. Unsurprisingly, searching algorithms are among the most prominent and useful algorithms in computer science.

Imagine that you need to call a famous quantum computing pioneer, Mr. Grover. You search a phone book for his number because you don’t have it yet. You open up the book in the middle, and see names with the starting letter L. Since G is before L, you take the book’s first half and open it up in the middle again. There you see names with an E. Since G is after E, you open up the book in the middle between E and L. There, you’ll see Mr. Grover’s number.

Binary search

The name of this search algorithm is a binary search. This algorithm repeatedly divides the search interval in half. If the searched item is lower than the item in the middle of the interval, it narrows the interval to the lower half. Otherwise, it narrows it to the upper half. It repeats until the value is found or the interval is empty. The binary search algorithm narrows down the search space quicklyt and converges to a solution. The only problem is that the algorithm relies on the data we search to be sorted. The algorithm doesn’t work if the data isn’t sorted.

This is a big problem because binary search relies on sorted data, but almost all search algorithms do.

If the data is not sorted or structured in any other way, the only valid search algorithm is a linear search. In linear search, we have to evaluate every single item to verify whether it is the searched one or not. While this approach works for small data, it becomes inappropriate for large data sets.

Grover’s algorithm

This is where Grover’s algorithm comes into play. In the lesson How to Solve a Problem with Quantum Computing, we learned about Deutsch’s algorithm, which can evaluate a function for two input parameters while only running it once. Grover’s algorithm teaches us how to search for an item in an unsorted list without looking at each item one by one but by looking at them all at once. It accomplishes that using two techniques. First, it uses a quantum oracle to mark the searched state. Second, it uses a diffuser that amplifies the amplitude of the marked state to increase its measurement probability.

We can describe quantum systems in terms of their states, amplitudes, and measurement probabilities. These are internal descriptions that we can’t observe directly. Whenever we measure a quantum system, we get a single value, which is the one state that this specific system is in.

If we measure two similar systems, we might measure different values. Then, we’ll know that this particular system can be in different states. We might measure the system in some states more often than in other states if we have many similar systems. How often we measure a quantum system in a certain state depends on probability. Each state of a quantum system has a certain measurement probability. The higher it is, the more likely it is that we’ll measure the system ...