Theoretical Computer Science
quantum-computing quantum-information oracles search-problem black-box
Updated Sat, 21 May 2022 06:52:50 GMT

Oracle Construction for Grover's Algorithm


In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's algorithm, there seems to be no mention of how Grover's Oracle is constructed, unless we already know which state it is that we are searching for, defeating the purpose of the algorithm. Specifically, my question is this: given some f(x) such that for some x value, f(x)=1, but for all others, f(x)=0, how does one construct an oracle that will get us from our initial, arbitrary state |x>|y> to |x>|y+f(x)>? As much explicit detail as possible (perhaps an example?) would be greatly appreciated. If such a construction for any arbitrary function is possible with Hadamard, Pauli, or other standard quantum gates, a method for construction with these would be appreciated.

Solution

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to.

For example, suppose you have a 3-sat problem:

(x1  x3  x4) 
    (x2  x3  x4) 
    (x1  x2  x4) 
    (x1  x3  x4) 
    (x1  x2  x3)

Or, in table form with each row being a 3-clause, x meaning "this variable false", o meaning "this variable true", and space meaning "not in clause":

1 2 3 4
-------
x   x x
  o o x
o x   o
x o x

Now make a circuit that computes whether the input is a solution, like this:

solution checker

Now, to turn your circuit into an oracle, hit the output bit with a Z gate and uncompute any garbage you made (i.e. run the compute circuit in reverse order):

oracle circuit

That's all there is to it. Compute the predicate, hit the result with a Z, uncompute the predicate. That's an oracle.

Iterate diffusion steps with oracle steps, and you've got yourself a grover search:

grover search

... although you should probably pick an example with fewer solutions, so the progress is gradual (instead of rotating along the start-state-solution-state plane by more than 90 degrees per step as my example is).

Comments (5)

  • +0 – Thanks, this was immensely helpful. Incredibly clear, answered everything I asked (and even used common quantum gates!) Is there any reason you decide to change all of your starting qubits to the |1> state before putting them in superposition with Hadamard gates instead of just putting the |0> state qubits through Hadamards (i.e. is there an advantage to this)? Also, what operation is that for your diffusion steps? Looks like controlled X, but are you using |1>'s or |0>'s as controls? — Jul 06, 2017 at 18:03  
  • +0 – @Will I used a different starting state. You can do that as long as you also change the state negated by the diffusion operator (they have to match). All starting/diffusion states that have equal angle-distance to every computational basis state work equally well. The little circled-plus control in my diagram is an "X-axis control", which is equivalent to a normal control surrounded by Hadamard gates. It looks like a NOT because they're interchangeable. My starting/diffusion state is $(\frac{1}{\sqrt{2}} |0\rangle - \frac{1}{\sqrt{2}} |1\rangle)^{\otimes n}$. — Jul 06, 2017 at 18:43  
  • +0 – Fantastic answer, and thanks for the link to algassert.com/quirk ! — Jul 11, 2017 at 13:17  
  • +0 – In addition to this great answer, you can get rid of the last qubit by directly using a multi-controlled Z gate having as target the last but one qubit link — Sep 15, 2020 at 15:12  
  • +0 – @tigerjack89 You need to conjugate that Z gate with X gates to make it act like an off control instead of an on control. — Sep 15, 2020 at 19:29  

External Links

External links referenced by this document:

References