Quantum Oracle Models

In the quantum oracle model, we have an oracle that holds an $N$-bit input string. Our task is to determine the value of some fixed Boolean function of the oracle string, using as few oracle queries as possible. An oracle query is a question of the form: ``What is the $i$th bit of the oracle string?'' The quantum oracle model is a special case of Ambainis' more general quantum adversary model [1], which we describe below.

In the quantum adversary model, we run an algorithm against an oracle that contains a superposition of inputs. Let $S$ be a subset of the possible inputs $\{0,1\}^{N}$. Algorithms in the quantum adversary model will work in the Hilbert space $H = H_{A} \otimes H_{I}$, where $H_{A} = \Complex^{2^{m}}$ is the Hilbert space of our $m$-qubit memory register, and $H_{I} = \Complex^{\vert S\vert}$ is the Hilbert space spanned by basis vectors $\vert x\rangle$ corresponding to the elements of $S$. We think of $H_{A}$ as our algorithm space, and $H_{I}$ as our input space. The tensor product of two vector spaces $A$ and $B$, denoted $A \otimes B$, is a new vector space spanned by all possible pairs $(i,j)$ of basis vectors $i$ from the first space and $j$ from the second space. Thus $H = \Complex^{\vert S\vert 2^{m}}$.

We can represent the basis states of our algorithm space as $\vert i, b, z\rangle$, where $i$ consists of $\lceil\log{N}\rceil$ bits, $b$ is a single bit, $z$ denotes all other bits our quantum algorithm requires. We define the oracle transformation $O$ as the unitary operator that takes any eigenstate $\vert i,b,z\rangle \otimes \vert x\rangle$ to $\vert i, b \oplus x_{i}, z\rangle \otimes \vert x\rangle$. The first $\lceil\log{N}\rceil$ bits of the subspace defined by a particular input $\vert x\rangle$ is the index $i$ to the oracle bit $x_{i}$ that we are querying. $O$ is a permutation matrix.

A quantum algorithm that performs $T$ queries is just a sequence of unitary transformations

$$U_{0}\rightarrow O\rightarrow U_{1} \rightarrow O \ldots \rightarrow U_{T-1} \rightarrow O \rightarrow U_{T},$$

where $U_{i}$ is an arbitrary unitary transformation that does not depend on the oracle, and $O$ is the oracle transformation. (Recall that unitary transformations are reversible and preserve the normalization of the state vector.)

The standard oracle query model is just an instance of the quantum adversary model where the input space is spanned by a single eigenstate $\vert x\rangle$. In this case a quantum algorithm starts with the state $\vert\rangle \otimes \vert x\rangle$, applies $U_{0}, O, U_{1}, \ldots, O, U_{T}$, and then measures the final state. The rightmost bit of the measured state of the algorithm space is the output of the algorithm on $x$. The algorithm computes $f$ in the bounded error setting if for every input $x \in \{0,1\}^{N}$, the output is $f(x)$ with some constant probability.

The measure of complexity in both the quantum oracle model and quantum adversary model is the number of oracle queries. It should be noted that querying the oracle is not always the most time consuming portion of an algorithm. For example, to factor an $N$ bit integer that the oracle holds, we can determine the integer in $N$ queries. However, we must then do $2^{N^{\Omega(1)}}$ additional steps in the classical case, or $N^{2}\log^{O(1)}{N}$ additional steps in the quantum case to factor the number using the best known algorithms [2]. Nonetheless we restrict our attention to the number of oracle queries required, as it is clearly a lower bound on the overall running time of the algorithm. Classical bounds for query complexity are well studied, making comparisons between quantum and classical oracle query complexity possible.