Grover’s Algorithm

Grover’s Algorithm can be oversimplified as a database search algorithm that is quadratically faster than classical computation. While other quantum algorithms may be exponentially faster, a quadratic speedup can still be substantial given large datasets.

What makes Grover’s Algorithm interesting is that it determines, with high probability, the unique input when it is the output that is known. It is, therefore, also described as inverting a function. One potential application is cryptography: reverse-engineering hash functions.

Once again, I used QASM (Quantum Assembly Language). If you use IBM Q Experience, the first four lines of code are provided for you, so don’t worry about the missing two lines at the top.

Lines 3 and 4 initialize the qubits (quantum bits), setting them to a ground state of zero; this is always the first step. Lines 6 and 7 change the quantum states of the qubits to a superposition (0, 1, or infinite probabilities of either). Lines 9 through 11 is the oracle and lines 13 through 33 is the Grover Diffusion Operator. Lines 35 and 36 measure the final states of the qubits; each qubit has to be measured individually.

The oracle is what somehow solves the search. But, remarkably, the oracle and the Grover Diffusion Operator are both referred to as “black boxes.” It somehow doesn’t matter if we don’t know the inner workings, we are supposed to just trust that they somehow work. It’s the most unsatisfying answer I can think of.

This is what the code looks like graphically after it runs. It isn’t formatted the way you might see it elsewhere, because the equivalent of white space is removed. But, I checked the order of all the gates, and it is aligned with the model that I used to write my code.

The final output is supposed to be two ones, which is the rightmost column. I’m still new at this, so I’m not sure why the accuracy is so bad.

One model I saw had 100% accuracy, but when I double-checked it I discovered that it was only run on a simulator, not an actual quantum computer. I ran my code on an actual quantum computer, with which you should expect imperfections in this stage of their development.

Another model had 100% accuracy, but it was fine-tuned to run only 1 cycle. It was also a saved result, not run in real time, so I don’t know how many single-cycles were run to produce a perfect output for a demonstration.

Quantum computing is fun. I’ve never done so little yet felt so thrilled about it. I’m excited about discovering other algorithms and exploring ways, perhaps, to generate more accurate results.