Grover Searches in the Soup

Published by strangeworks (01/22/2021)

Finding a needle in a haystack can be hard. But once you find it, you know it is a needle. This problem is formally known as unstructured search. Grover's algorithm allows us to do this faster than any classical way. It is like using the a magnet to find it.

Introduction

Why are lost things always in the last place you look? Because you didn't look with a quantum computer. 

Instead of looking one place at a time, a quantum computer can create a superposition of all the places, and then increase the probability of the place where it is. This way, you are more likely to start looking in the right place. And that makes searching faster. That is what makes Grover so groovy.

Algorithm

The purpose of Grover Search Algorithm is to find a specific item among a disordered list. The classic example is trying to do a reverse look-up in a phonebook: you know a phone number, and need to use it to find the matching name. 

A (classical) search algorithm to do this NN​ items on a list is simple: start at the top of the list, reading each item, to see if it is the one you want. On average, it takes N/2N/2​ reads to find, but the worst case scenario is if the item is the last one on the list, which means it takes NN​ reads. Grover Algorithm is quite stunning in that it only takes N\sqrt{N}​  reads.

The algorithm has several steps to achieve this. First, the whole list is put into a superposition, all items have equal probability. No surprise here, this is how most quantum algorithms start.

Then we apply an Oracle. An Oracle is a fancy way to say "having the capability to recognize the item we are searching for", in the case of the reverse phonebook look-up, is to know the phone number we are interesting in. So an Oracle could be you if you have the phone number written in a piece of paper, and can compare it to each item in the phonebook, or in the needle and a haystack is simply knowing the difference between hay and a needle. I often think that using the term Oracle makes things sounds more mysterious than they need to be. It is essentially the elephant test: describing an elephant might be hard, but once seen, it is immediately recognizable.

Then a process called Amplitude Amplification is carried out. It transforms the whole state of the list in a way that it increases the probability of the wanted item, while decreasing the others. This procedure is repeated many times so the probability of the desired item is so high we can be confident we have found the item. Then a quantum measurement is performed to read out the item, in the phone book example this corresponds to knowing the name attached to the phone number.

Although this algorithm is iterative, in the example we include here we only do it once, to keep things simple. So at the end, we just have increased the probability a bit of the desired item. Let's go step-by-step into how it works, with more specific details.

Quantum Circuit

We now explain the same algorithm by focusing on the most important lines of the code. Remember, although this algorithm is iterative, in the example we include here we only do things once to keep them simple.

Step 1

First, initialize qubits, bits and the circuit, as usual.

qr = qiskit.QuantumRegister(4)
cr = qiskit.ClassicalRegister(4)
qc = qiskit.QuantumCircuit(qr, cr) 

 In this case, the list to be searched is encoded as the register of four qubits, one of them will be the needle, the rest are the haystack.

 Then create a superposition of the whole list of items.

qc.h(qr[0]) 
qc.h(qr[1]) 
qc.h(qr[2]) 
qc.h(qr[3])

Step 2

 Now comes the action of the Oracle, a quantum circuit that can recognize the right item, and then marks it. In this case the oracle can detect qubit 0010. After it detects 0010, it marks it by rotating all other qubits into a superposition, leaving the desired one the same.

qc.x(qr[0]) 
qc.x(qr[2]) 
qc.x(qr[3]) 

qc.cu1(pi/4, qr[0], qr[3]) 
qc.cx(qr[0], qr[1]) 
qc.cu1(-pi/4, qr[1], qr[3])
qc.cx(qr[0], qr[1]) 
qc.cu1(pi/4, qr[1], qr[3]) 
qc.cx(qr[1], qr[2])
qc.cu1(-pi/4, qr[2], qr[3]) 
qc.cx(qr[0], qr[2]) 
qc.cu1(pi/4, qr[2], qr[3])
qc.cx(qr[1], qr[2]) 
qc.cu1(-pi/4, qr[2], qr[3]) 
qc.cx(qr[0], qr[2]) 
qc.cu1(pi/4, qr[2], qr[3])

qc.x(qr[0]) 
qc.x(qr[2]) 
qc.x(qr[3])

Step 3

Now that the Oracle has marked the desired item, by changing all others, the following routine amplifies the amplitude of the possible solution.

First, do some more rotations to all the qubits, the usual suspects.

qc.h(qr[0]) 
qc.h(qr[1]) 
qc.h(qr[2]) 
qc.h(qr[3])

qc.x(qr[0]) 
qc.x(qr[1]) 
qc.x(qr[2]) 
qc.x(qr[3])

Then apply a conditional phase-shift to all the states except the marked one.

qc.cu1(pi/4, qr[0], qr[3]) 
qc.cx(qr[0], qr[1]) 
qc.cu1(-pi/4, qr[1], qr[3])
qc.cx(qr[0], qr[1]) 
qc.cu1(pi/4, qr[1], qr[3]) 
qc.cx(qr[1], qr[2])
qc.cu1(-pi/4, qr[2], qr[3]) 
qc.cx(qr[0], qr[2]) 
qc.cu1(pi/4, qr[2], qr[3]) 
qc.cx(qr[1], qr[2])
qc.cu1(-pi/4, qr[2], qr[3]) 
qc.cx(qr[0], qr[2]) 
qc.cu1(pi/4, qr[2], qr[3])

This phase-shit essentially pivots the probabilities, lowering the probability of the "hay" and increasing the probability of the "needle". 

To finish things up, undo the rotations from the beginning.

qc.x(qr[0]) 
qc.x(qr[1]) 
qc.x(qr[2]) 
qc.x(qr[3])

qc.h(qr[0]) 
qc.h(qr[1]) 
qc.h(qr[2]) 
qc.h(qr[3])
qc.barrier(qr) 

This completes the amplitude amplification. After this, when a measurement is carried out, the probability of the finding the "needle" is much higher than that of the "hay". This procedure can be done many times in sequence to increase the probabilities of finding the desired item further, to the limit where it is essentially a sure thing. However, in this example we do it only once. Since there are only four items, it is enough.

Step 4

Now to finish things, we carry out measurements.

qc.measure(qr[0], cr[0]) 
qc.measure(qr[1], cr[1]) 
qc.measure(qr[2], cr[2]) 
qc.measure(qr[3], cr[3])

The desired item will appear with higher probability.

And you know what they say: If it looks like a duck, swims like a duck, and quacks like a duck, then it probably is a duck.