Implementing the Quantum Oracle

Question

Suppose I have a simple function $f(x): 1 + x$ and I want to find $x$ such that $f(x) = 5$, for instance, using the Grover search. Am I correct to say that I will need to implement this function $f(x)$ within the oracle itself? For example: def oracle_qc(desired_output): """implement adder quantum circuits?""" return qc such that the oracle circuit will mark out the state that gave the desired output.

So far, the oracles in the examples I have seen are hard-coded such that $|100\rangle$ will return a negative. However, if I were to change the desired output to say $f(x) = 6$, then the oracle needs to be changed again so that $|101\rangle$ will now be marked instead. It doesn't actually implement the function itself.

This is just for a simple function so I cannot imagine the complexity involved for a more complicated function, especially one with floating point, if the function needs to be implemented in the quantum oracle.

Answer 1

Yes, you're exactly right, generally, you do need to implement the function $f(x)$ within the oracle. Typically the oracle would have 3 parts for a search like this:

1. a circuit to compute $f(x)$
2. a comparison circuit to compare whether $f(x)=t$ for some target $t$ (and cause a phase flip if it is)
3. a circuit to uncompute $f(x)$

Let's think about the 2nd step. If you have a register $\vert f(x)\rangle$ (in binary), you can compute $\vert f(x)\oplus t\rangle$ (where $\oplus$ is bit-wise XOR) and this will be $0$ if and only if $f(x)=t$; thus, you only need a circuit that flips a phase only when all bits are $0$ (you can construct this with a tree of Toffoli gates and some ancilla).

How to compute $f(x)\oplus t$? Since you know $t$ classically, you can actually just apply an $X$ gate for every 1 bit in $t$.

In fact, as a precomputation, you generally assume that you do as much pre-computation as possible to "compile" the circuit down as small as it can be. For example, to implement $f(x)=x+1$, you could use a general adder such as

(source), which is fairly complicated, with your input $x$ taking the role of $t$ and setting $i=1$. But since $i=1$ is known, you can replace a lot of the CNOT and AND and Toffoli gates with other, simpler gates.

At the small scales of algorithms people can implement on quantum computers today, this gets really boring, because it's so small that it's easy to compile the circuit down to almost nothing (i.e., a circuit that hard-codes the answer, like you've seen). For large scales, the circuits absolutely get incredibly complex.

To design and describe circuits for complex functions (as a theoretical exercise, since they're decades ahead of what we can implement), people use software tools (Q# is well-designed for this), and the circuits can and do use several hundred thousand gates.