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

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 $$$$U_f = I - 2\left|x_0\right> \left

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?

• – glS
May 30, 2021 at 20:10

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.