# What exactly is an oracle?

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?

• Microsoft has nice documentation on quantum oracles. Commented Mar 27, 2019 at 22:27

## 2 Answers

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.

• Could you clarify what you meant by strictly in the last sentence? Commented Mar 26, 2019 at 12:36
• @tparker not really - the purpose of such oracle forms is often that it allows a description not only of the algorithm, but for optimality of the algorithm. That is measured simply as a count of the number of uses of the oracle. It doesn’t matter how long the oracle takes to run. So for grover’s, that requires square root of the number of oracle calls that the classical one does. Commented Oct 2, 2019 at 5:28
• You're right; my comment was poorly phrased. What I meant to say is that if you want an oracle result to give any insight into a "real-world" runtime, you need to assume (in addition to the black-box assumption) that whatever subroutine you're running to actually implement the oracle call dominates the algorithm's runtime, so that the number of oracle calls is indeed proportional to the actual runtime. But that's an addition assumption for "real-world" relevance, not a necessary part of the definition of an oracle. Commented Oct 2, 2019 at 11:57
• What are oracles used for? Why?
– skan
Commented Apr 12, 2020 at 11:54
• @skan, think of oracle as an abstraction, like an API call, you do not know how the API is coded, but you know what are its inputs and outputs. By doing this you are abstracting away all the implementation details of the function and hence "the time complexity of the function". By doing this, we will be able to compare the speed of classical algo vs quantum algo. This is the main purpose of oracle. Commented Apr 22, 2021 at 5:00

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:

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