How can one evaluation of $U_f$ in Grover's algorithm use only one query of $f$?

Question

I am very much new to quantum computation and do not have a background in quantum mechanics, which I believe is at the root of my confusion around Grover's algorithm.

Suppose that we have a search range of $N = 2^n$ elements and a black box function $f$ where for $N-1$ elements we have that $f(x) = 0$ and for one marked element, $x_0$, we have that $f(x_0) = 1$.

I understand that we take $n$-qubits initally in the $\left|0\right>^{\otimes n}$ state and the apply the Hadamard gate to put them in the $\left|+\right>^{\otimes n}$ state, an equal linear combination of all the possible bit-strings. Then we apply $U_f$ which essentially flips the phase of our marked element and leaves the rest alone, and thus can be written as \begin{equation} U_f = I - 2\left|x_0\right> \left<x_0\right|. \end{equation}

However, I am confused at how one evaluation of $U_f$ on $\left|+\right>^{\otimes n}$ only requires one query of our black box $f$ for this to be quadratic speedup over classical algorithms. Is this due to the some quantum physical property of the "superposition?

Answer 1

how one evaluation of $U_f$ on $\left|+^n\right>$ only requires one query of our black box $f$

It doesn't. There are two black boxes. The quantum black box $U_f$ is the quantum counterpart of the classical black box $f$. In analyzing the query complexity of the classical search algorithm we count the number of times the algorithm invokes the classical black box $f$. Similarly, in analyzing the query complexity of the quantum search algorithm we count the number of times the algorithm invokes the quantum black box $U_f$.

In other words, we assume that we have a means of applying $U_f$ to quantum states. The details of how this is accomplished depend on the application and are not part of the Grover algorithm. Generally speaking, since $U_f$ is a quantum operation its execution does not rely on the invocation of classical predicates such as $f$. However, in practice, the construction of $U_f$ often mimics the construction of the corresponding classical predicate $f$, albeit with quantum gates in place of classical ones.

For a simple example, suppose that our classical predicate $f$ is defined as

$$ f(x) = x_0 \wedge \neg x_1\tag1 $$

where $x$ is a two-bit bitstring and $x_k$ denotes the $k$th bit of $x$. The quantum counterpart $U_f$ of the classical predicate $f$ is a unitary with the property that

$$ U_f|x_0\rangle|x_1\rangle|y\rangle = |x_0\rangle|x_1\rangle|y \oplus f(x)\rangle\tag2 $$

where $\oplus$ denotes addition modulo two (c.f. equation $(6.1)$ on page 249 in Nielsen & Chuang). In the case of the classical predicate defined in $(1)$, $U_f$ may be implemented as

$$ U_f = (I\otimes X \otimes I) \circ \text{TOFFOLI} \circ (I\otimes X \otimes I).\tag3 $$

Intuitively, the rightmost $X$ gate on qubit $x_1$ corresponds to the logical negation $\neg$, the Toffoli gate accomplishes the conjunction $\wedge$ and the final $X$ gate restores $x_1$ to its original state. For a more rigorous analysis, consider the action of $(3)$ on all eight computational basis states and compare with $(2)$.

---

The above situation is of course a major caveat to keep in mind when comparing the classical and quantum search algorithms. I suppose one could protest that any analysis that compares the number of invocations of $U_f$ and $f$ is unfair because $U_f$ is more powerful than $f$. However, one can also regard the quantum computational model's support for operations such as $U_f$, that simultaneously act on an exponentially large number of elements in superposition, as its important feature.