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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.