5.1.2 Bit oracles

This idea works not only for the logical $\operatorname{AND}$ function but in fact for any function

that takes $n$ bits as an input and returns a single bit. For any such function $f$ we can define a reversible operation on $(n+1)$ bits:

for all $x_{1},\dotsc,x_{n},y\in\{0,1\}$. Just like Eq. 5.3, this operation is its own inverse, i.e., applying it twice is equivalent to doing nothing.

It is reassuring that we can implement any function $f:\{0,1\}^{n}\to\{0,1\}$ reversibly as in Eq. 5.4. First of all, it means that any computation on a classical computer can be done in such a way that we can recover the original input. Second, once the computation is made reversible, we can run it also on a quantum computer. This implies that quantum computers can compute everything that classical computers can! Third, this means that we can implement any function $f$ as an oracle on a quantum computer.

Let’s see how this actually works. The quantum version of the operation in Eq. 5.4 is defined as follows:

for all $x_{1},\dotsc,x_{n},y\in\{0,1\}$. Eq. 5.5 defines how $U_{f}$ acts on all basis states of $n+1$ qubits. As usual, we extend this definition to an arbitrary state on $n+1$ qubits by linearity. Since $U_{f}$ simply permutes the basis states, you can check as in 4.4 that it defines a valid quantum operation.

We call the quantum operation $U_{f}$ defined in Eq. 5.5 the bit oracle for $f$ (we could also call the function in Eq. 5.4 a classical bit oracle, but we will not need this name). The term ‘oracle’ simply means that applying this operation is like asking an all-powerful oracle to tell us the value of the function on any given input. We do not know how the oracle is implemented precisely nor where it gets its answer from, we will just count how many questions we need to ask the oracle to learn some property of the function $f$. Many interesting algorithmic problems can be modeled in this fashion, as we will see in the remainder of this quest.

The concept of an oracle is a bit like playing the ‘guess my number’ game. Your friend (the oracle) comes up with some number and you ask them questions of the form “is your number x”? Your friend answers each of these questions with either “yes” or “no”. In other words, your friend is hiding a function that evaluates to “no” on all inputs, except on one (the number they have in mind). With every question you ask, you gain more information about which number it could possibly be. You may wonder how many questions you need to ask to determine the number. Moreover, what if you could ask your questions to a quantum oracle such as $U_{f}$ instead of your friend? Could you figure out the answer with less questions? In this week’s quest, we will see several interesting examples where this indeed is the case!

Let us discuss some examples of bit oracles. Assume $f$ is the AND function. According to Eq. 5.1, we can interpret AND as multiplication modulo 2 since $\operatorname{AND}(x_{1},x_{2})=x_{1}x_{2}$. The corresponding bit oracle

is nothing but the Toffoli gate from 4.4. Even for $n=1$ and the function $f(x)=x$ that simply returns its input, we get an interesting result: for all $a,b\in\{0,1\}$,

This is just the familiar controlled-NOT gate $\mathrm{CNOT}_{1\to 2}$ from Eq. 3.64 in Section 3.2.4! Thus, the bit oracle construction reproduces several interesting quantum operations that we had previously defined by hand. In the following exercise you can try to implement all other bit oracles for functions of a single bit.