Oracle Construction for Grover's Algorithm

Question

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.

Answer 1

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:

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):

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:

... 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).

Answer 2

You can also get a solution which uses only one ancillary qubit (but relies on NOT gates with multiple controls), by getting your input to algebraic normal form (e.g. with Mathematicas BooleanConvert).

For example let us use the 2x2 "Sudoku" example in the Qiskit book (i.e. a 2x2 grid of 1bit numbers where in each column and row there should be no duplicates). Numbering the entries like

$$ \begin{matrix} x_0 & x_1 \\ x_2 & x_3 \end{matrix} $$

our function is

$$ f(x_0, x_1, x_2, x_3) = (x_0\oplus x_1)\land(x_2\oplus x_3)\land(x_0\oplus x_2)\land(x_1\oplus x_3) $$

Either by hand or with computer help, we arrive at

$$ f(x_0, x_1, x_2, x_3) = (x_0\land x_3)\oplus (x_1\land x_2)\oplus (x_0\land x_1\land x_2)\oplus (x_0\land x_1\land x_3)\oplus (x_0\land x_2\land x_3)\oplus (x_1\land x_2\land x_3) $$

As you are looking for an operation that gives you $|x,y\rangle\to|x,f(x)\oplus y\rangle$, we can just apply the terms one after the other. And as each term is just an AND between multiple variables, this can be written as a controlled not gate, where the not operates on $y$ and has a control for each appearing $x_i$. For our example, this looks as follows (q is $x$ and o is $y$)

Implementing one Grover iteration, we see that it yields the two solutions

$$ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}\quad\text{and}\quad \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} $$

as expected.

Answer 3

For many famous NP-complete problems, the Grover oracle can be constructed with quantum annealing: https://arxiv.org/abs/2304.10488 . The time to realize this oracle scales only polynomially with the memory size, and no change to the leading order scaling for the Grover algorithm.