What exactly is an oracle?

Question

What exactly is an "oracle"? Wikipedia says that an oracle is a "blackbox", but I'm not sure what that means.

For example, in the Deutsch–Jozsa algorithm,
$\hspace{85px}$,
is the oracle just the box labeled $`` U_f " ,$ or is it everything between the measurement and the inputs (including the Hadamard gates)?

And to give the oracle, do I need to write $U_f$ in matrix form or the condensed form: $U_f$ gives $y \rightarrow y \oplus f(x)$ and $x \rightarrow x$ is enough with respect to the definition of an oracle?

Answer 1

An oracle (at least in this context) is simply an operation that has some property that you don't know, and are trying to find out. The term "black box" is used equivalently, to convey the idea that it's just a box that you can't see inside, and hence you don't know what it's doing. All you know is that you can supply inputs and receive outputs. In the circuit diagram you depict, it is just the $U_f$ box. Everything else is stuff that you are adding in order order to help interrogate the oracle and discover its properties.

To give the oracle, you can write it in any valid form that defines a map from all possible inputs to outputs. This could be a matrix (presumably with an unknown parameter), or it could be the map $U:(x,y)\mapsto (x,y\oplus f(x))$ (strictly, $\forall x,y\in\{0,1\}$), because given either description, you can work out the other.

Answer 2

What exactly is an oracle

That's a great question, and even after studying 2 courses on quantum algorithms, this concept wasn't clear enough for me.

Mathematically, this is just as written above. For every classical function $f:\{0,1\}^n \rightarrow \{0,1\}$ a quantum oracle is defined as the unitary $U_f |x\rangle_n |y\rangle_1 = |x\rangle_n |y \oplus f(x)\rangle_1 $. So at the end 'it is just' the unitary that implements some function on a quantum computer.

However, some key questions that are usually swept under the rug:

1. Why do we need these oracles?
2. How to implement an oracle?
3. A concrete example for an oracle?

So,

1. Why do we need these oracles?

This is a mathematical concept (or a mathematical tool) that is useful when we design and analyze quantum algorithms. When analyzing algorithms it is common to analyze them in terms of how many times a specific building block is used. Often this building block is the oracle or black box function. Also when designing quantum algorithms, it is sometimes useful to have building blocks where we assume they implement some function, i.e. an oracle.

E.g. the following is an oracle written in Classiq's Qmod language (disclaimer - I’m a Classiq employee):

qfunc oracle_function(target: qbit, x: qnum) {
  target ^= x == 0;
}

this oracle functions applies the oracle for the function $x==0$.

2.How to implement an oracle?

Using high-level functional design tools like Classiq it's quite easy. You design the function you want, and then the compiler synthesizes an underlying implementation. For the above example, this is the underlying circuit implementation for the oracle:

3. A concrete example

A good example for the use of oracles in advanced algorithms is the discrete quantum walk. You can find a good resource for the theory of this in Andrew's Childs lecture notes chapter 17 and a concrete example in the Classiq git repo.

It's also worth noting the phase-kickback is a common primitive that is often used in the context of quantum oracles (see more here).