Quantum search from scratch
Welcome to Introduction to Quantum Computing. I am your guide, Associate Professor Chris Ferrie, a researcher in the UTS Centre for Quantum Software and Information. This is Lecture 9.
It would probably be a good idea to have read the previous Lectures before continuing.
What did you learn last week?
Last week you learned about the high-level structure of quantum algorithms, especially those with oracles. You’ve also seen the detailed implementation of the Deutsch-Jozsa algorithm and how it makes use of the quantum primitives: superposition, quantum logic, phase logic, and uncomputation.What will you learn this week?
This week you will be introduced to the most famous oracle-based quantum algorithm: Grover. Grover’s algorithm is also known as “quantum search” and it provides a quadratic speed-up over classical search.What will you be able to do at the end of the week?
At the end of this module, you should be able to answer these questions:
What is quantum database searching?
What is Grover’s algorithm and what does its circuit look like?
How many queries are needed in quantum search?
Finding a needle in a very small haystack
Remember that an oracle is a “black box” meaning we aren’t supposed to know what it does. In Deutsch’s problem, the task was to find out if the unknown function was constant or balanced. Here, the problem will be more difficult. The task is to find exactly which function it is! We’ll assume that the function is 1 for a single bit string and 0 for all others. Think of it as a completely unstructured database with a single marked item, and the task is to find the item.
Since the database is unstructured, the number of queries needed to find the marked bit string might very well be all of them! In general, for a database with N items, it would take N queries to find a marked item in the worse case. If you were lucky, you might find it on the first go. On average, it would take (N+1)/2 queries (exercise!).
Let’s consider an example. Consider the function f(x) = 0 for all x except f(11) = 1. How many queries of f would it take to find the 1? Well, you could get lucky on the first go and try the input 11. Or, you could be unlucky and try the other three inputs first. In any case, the worst case is cleary 4 queries.
Can we do better with quantum queries?
More quantum magic
We need to recall the oracles from Lecture 8. The phase oracle applied a phase to the computational basis state |x⟩ if the function f(x) evaluated to 1.
This seems useful. Clearly the oracle function for this problem is neither constant nor balanced. So, Deutsch’s superposition trick from Lecture 7 is not going to work. But, hey, you only live one quantum life, so let’s try it anyway.
Let’s call the two input bits of the marked string w, so that f(w)=1. In the AND function example above w = 11. The oracle applied in superposition takes the state |00⟩+|01⟩+|10⟩+|11⟩ to |00⟩+|01⟩+|10⟩−|11⟩. Some magic foresight would have us write that as |00⟩+|01⟩+|10⟩+|11⟩−2|11⟩. Now, we can see that for a general marked string w, the phase oracle produces the superposition |00⟩+|01⟩+|10⟩+|11⟩−2|w⟩ no matter which function was applied.
The state which is a superposition of all computational basis states is usually denoted |s⟩. So the state after the phase oracle is |s⟩−|w⟩. A measurement at this point would reveal randomness due to |s⟩, so let’s try to get rid of it with some more Hadamard gates. Let’s call w=xy to separate out the two bits.
Okay, that doesn’t look better. But we could have something a little more symmetric if got rid of the negative sign in front of |00⟩. Curiously, this can be done with another phase “oracle” — except we know this time exactly what state is marked. The circuit which does this is not hard to derive.
You can check that this acts as advertised on the other computational states. Now apply this to the state.
Ah, much better. Now we simply apply a couple more Hadamard and the state ends up in −|w⟩. The minus sign is irrelevant when we measure, which will reveal the marked string in a single oracle query!
Circuits for your viewing pleasure
That was a long of math. Eww, am I right? No. Math is awesome. Anyway, let’s look at some pictures now. First, what did we just do? We created a quantum circuit that implements an oracle that requires only one use to determine. This is Grover’s algorithm.
Anticipating the generalisation to more qubits, we’ve abstracted it into some primitives. We can also use a quantum simulator such as Quirk to verify and play around with the algorithm.
Grover’s algorithm implemented our AND oracle. Play with this circuit on Quirk. You can cycle through the possibilities by placing X gates around the CZ gate where you want to mark your string.
Awesome. So quantum computers can solve all problems by checking through all possible solutions simultaneously, right? Hold up…
Trial by threes
Let’s try to replace the ⊗2 in the above circuit with ⊗n, for n qubits. Since we have a nice simulator handy, let’s avoid doing the calculation by hand.
Uh oh. That doesn’t look right. But it looks like the circuit did something. It kind of worked. So… let’s try it again.
Wow! OK. Now we are getting somewhere. Let’s do it one more time to eek out that last 5.5%.
Ah, shit. Well, now we are stuck. We better do some math.
Dirac is back
Those calculations above look daunting enough with two qubits. How the heck are we going to do it for n qubits? The magic of Dirac notation of course! First, let’s simplify some things. The oracles we use can be written succinctly with just two terms, independent of n.
Now we can examine Grover’s circuit with ease!
At this point, we can stick in n=2 to find out, as expected, the first term cancels out and we are left with only |w⟩. Similarly, stick in n=3 and we find out exactly why the circuit “doesn’t work” for more than two qubits.
It’s up to you to apply the oracle and D again. This time you will end up in an intermediate calculation with 8 terms that you have to group to find the coefficients of |w⟩ and |s⟩. You should expect to find that the coefficient of |w⟩ has grown. In fact, you can find a general formula for how fast it grows. And, this is what would demonstrate that a quadratic number of rounds is required to achieve the maximum value for the amplitude of |w⟩.
Additional Resources
Many people seem to like the “geometric proof” of Grover’s algorithm. The Wikipedia entry on Grover’s algorithm does a nice job of explaining it.
The Qiskit textbook has a lengthy chapter on Grover’s algorithm and demonstrates how to run the algorithm on hardware.
