8-1. Oracles
In this section, we treat the search problem in general and introduce oracles, a concept necessary to consider its computational complexity [1].
What is an oracle?
A search problem is generally a problem of finding \(M\) solutions from \(N\) elements. For example, you have a database of names of people, and you want to find only Sato-san from the database. Assuming that \(N\) elements are labeled with \(n\)-digit bit strings \(x=x_1\ldots x_n\), we define the “classical oracle” for this search problem as follows.
In other words, \(f\) is a function that, given the label \(x\) of an element, tells us in two choices whether that element is a solution. For example, if \(Name_0\)=Takahashi and \(Name_1\)=Sato, then \(f(0)=0, f(1)=1\). Oracle means an abstract entity that is a black box inside but tells us the answer anyway, not caring how it is implemented (nor does the implementation actually need to exist). The computational complexity of a classical algorithm for solving a search problem is evaluated by the number of times it asks the classical oracle if \(x\) is a solution. In this way, a uniform evaluation independent of the detail of the problem is possible.
On the other hand, the computational complexity of the quantum algorithm for solving the search problem is evaluated by the number of calls to the following (quantum) oracle \(\mathcal{O}_f\).
where the input state \(|x \rangle\) is the state of the input bit sequence \(x\) in the computational basis, \(|q \rangle\) is the auxiliary bit, and \(\oplus\) is the modulo-2 addition (XOR operation). We can tell if \(x\) is a solution to the search problem by checking if the auxiliary bit \(q\) is inverted：\(|x \rangle |0 \rangle \xrightarrow{\mathcal{O}_f} |x \rangle | f(x) \rangle\). In addition, if the auxiliary bit is \(|- \rangle = (|0 \rangle - |1 \rangle)/\sqrt{2}\) ,
The phase of the state is reversed only when \(x\) is a solution to the search problem.
One of the most significant features of the oracle \(\mathcal{O}_f\) is that it works as is even if the input states are superposed.
For example, if we take the superposition of all states \(N^{-1/2} \sum_x |x\rangle\) as input state and set the auxiliary bit to \(|-\rangle\), then
The Grover’s algorithm, which will be introduced in the next section, makes good use of this property of phase reversal only when \(x\) is a solution to find a solution.
Reference
[1] M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information 10th Anniversary Edition“, University Printing House の 6.1 The quantum search algorithm