Grover's Algorithm and the Unstructured Search Problem

The Unstructured Search Problem

For the purposes of this lesson, the unstructured search problem is defined by a function $f$ that maps binary strings of length $n$ to a single bit. We are searching for a solution, which we define as a binary string of length $n$ that causes $f$ to evaluate to one. This is generally a very difficult computational problem; specifically, if the input is a description of a boolean circuit for computing the function $f$, it is an NP-complete problem. We can formalize this as a query problem, which is reasonable within the context of the query model. However, in practice, it is natural to think of $f$ as being computed by a Boolean circuit. As seen in lesson six, we can connect these viewpoints by converting a Boolean circuit into a quantum circuit to implement a query operation.

In this problem, the input is the function $f$, and we seek a solution if one exists. If $f$ is the constant zero function, the correct output is to report that no solutions exist. This is termed an "unstructured" search problem because there is nothing special about $f$ that facilitates finding a solution, unlike searching through ordered data or data structures. An analogy is searching for a phone number in a phone book versus searching for a name; the latter is easier because names are alphabetized. This represents searching for a solution to a complicated equation or a combination for a lock. While oracles and black boxes do not exist in real life, complicated Boolean circuits are essentially black boxes to us. For notation, we let $n$ be the length of the input strings and $N = 2^n$ be the total number of input strings.

Classical and Quantum Search Costs

Classically, the search problem can be solved by iterating through all possible $n$-bit strings and evaluating $f$ on each. If a solution is found, the process stops. In the worst case, this requires $N$ queries. This is the best a deterministic algorithm can do in the query model because if we have queried every string except one and found no solutions, we cannot be sure the final string is not a solution without querying it. Randomness can offer minor improvements, such as reducing the expected number of queries or trading correctness probability for query reduction, but the number of queries remains linear in $N$.

Grover's algorithm is a quantum algorithm for search that requires only $O(\text{square root of } N)$ or $O(\text{square root of } 2^n)$ queries. This represents a quadratic advantage over classical methods. While this advantage may not lead to practical application soon, it is a foundational part of quantum algorithms. The algorithm is often expressed using phase query gates.

Query Gates and Phase Query Operations

To understand Grover's algorithm, we must review query gates. The ordinary query gate $U_f$ for a function $f$ is defined on standard basis states by XORing the output value onto an additional qubit. From a Boolean circuit for $f$, we can build a circuit for $U_f$ at a cost linear in the size of the Boolean circuit. On the other hand, the phase query gate $Z_f$ operates on $n$ qubits instead of $n+1$. It automatically kicks the function value into the phase: $Z_f |x\rangle = (-1)^{f(x)} |x\rangle$. By using phase kickback with a $U_f$ gate and a $|-\rangle$ state, we can implement a $Z_f$ gate at the cost of one evaluation of $U_f$. While a $Z_f$ gate alone cannot recover a $U_f$ gate, a controlled version of $Z_f$ can be used to build a $U_f$ gate.

In addition to the phase query gate for $f$, we require a phase query gate for the $n$-bit OR function ($Z_{OR}$). This function takes the value zero only for the all-zero string and one for all others. The $Z_{OR}$ gate does not depend on $f$ and therefore requires no queries. It can be built using a Boolean circuit that computes the OR function on $n$ bits.

Description of Grover's Algorithm

Grover's algorithm begins by initializing $n$ qubits to the $|+\rangle$ state, creating an equal superposition of all binary strings of length $n$. At this point, every string is equally likely to be a solution. We then repeatedly apply the Grover operation, denoted as $G$, a total of $t$ times, where $t$ is a non-negative integer. Finally, we measure in the standard basis to obtain a candidate solution $x$. While there is no guarantee $x$ is a solution, a good choice of $t$ makes the probability large. We can spend one additional query to check if $x$ is a solution. If it is not, we can try again or report no solutions.

The Grover operation $G$ is an $n$-qubit operation composed of: a $Z_f$ gate, a layer of Hadamard gates ($H^{\text{tensor } n}$), a $Z_{OR}$ gate, and another layer of Hadamard gates. One iteration of $G$ requires exactly one query to $f$ because only the $Z_f$ portion depends on $f$. Thus, the number of iterations $t$ equals the number of queries.

Analysis of the Grover Subspace

To analyze the algorithm, we partition the set of all $n$-bit strings into two sets: $A_0$ containing strings that evaluate to zero (non-solutions) and $A_1$ containing strings that evaluate to one (solutions). We assume both sets are non-empty. Let $|a_0\rangle$ be the uniform superposition over all non-solutions and $|a_1\rangle$ be the uniform superposition over all solutions. The state of the register remains in the two-dimensional subspace spanned by $|a_0\rangle$ and $|a_1\rangle$ throughout the algorithm. The initial state $|u\rangle$ (the uniform superposition of all strings) can be expressed as $\frac{\text{square root of } (N - s)}{\text{square root of } N} |a_0\rangle + \frac{\text{square root of } s}{\text{square root of } N} |a_1\rangle$, where $s$ is the number of solutions.

By examining the action of $G$ on this subspace, we find it behaves as a rotation matrix $M$. The action of $Z_f$ on the subspace reflects the state about the line parallel to $|a_0\rangle$ by putting a minus sign on the component of $|a_1\rangle$. The second part of the operation, $H^{\text{tensor } n} Z_{OR} H^{\text{tensor } n}$, is a reflection about the line parallel to the uniform state $|u\rangle$. In geometry, the composition of two reflections is a rotation. Specifically, the Grover operation rotates the state by an angle of $2\theta$, where $\theta = \text{arcsin}(\frac{\text{square root of } s}{\text{square root of } N})$. After $t$ applications of $G$, the state of the register is $\text{cos}((2t+1)\theta) |a_0\rangle + \text{sin}((2t+1)\theta) |a_1\rangle$.

Choosing the Number of Iterations

The goal is to choose $t$ such that the probability of measuring a solution is large. This probability is given by $\text{sin}^2((2t+1)\theta)$. We want the angle to be as close to $\frac{\text{pi}}{2}$ as possible. Solving for $t$ gives an ideal value of $\frac{\text{pi}}{4\theta} - \frac{1}{2}$. Since $t$ must be an integer, we typically choose $t = \text{floor}(\frac{\text{pi}}{4\theta})$. This choice depends on the number of solutions $s$.

In the case of unique search ($s=1$), which was the version Lov Grover originaly introduced in 1996, the angle $\theta$ is approximately $\frac{1}{\text{square root of } N}$ for large $N$. The number of iterations is then approximately $\text{floor}(\frac{\text{pi}}{4} \times \text{square root of } N)$. For example, if $N=128$, $\theta$ is approximately $0.0885 \text{ radians}$, and $t$ is $8$. In this specific case, the probability of failure is only about $0.5$%. For $N=4$, it requires exactly one query and works perfectly. Generally, the success probability for unique search is at least $1 - \frac{1}{N}$.

If there are multiple solutions and we know $s$, Grover's algorithm works with probability at least $1 - \frac{s}{N}$. For instance, if $N=128$ and $s=4$, the optimal $t=4$, yielding a success probability greater than $99.9$%. Using a target $t$ meant for $s=1$ when $s=4$ would result in a very small probability of success because the state would rotate past the target vector. The query requirement is at most $\frac{\text{pi}}{4} \times \text{square root of } \frac{N}{s}$.

Searching with an Unknown Number of Solutions

If the number of solutions is unknown, we cannot calculate the exact optimal $t$. A simple approach is to choose $t$ uniformly at random between $1$ and $\text{floor}(\frac{\text{pi}}{4} \times \text{square root of } N)$. This gives at least a $40$% chance of finding a solution if one exists. We can boost this probability by repeating the process; for example, $10$ independent runs would provide a $99$% success rate. This requires $O(\text{square root of } N)$ queries.

A more sophisticated approach starts with $t=1$ and repeatedly runs Grover's algorithm with a random number of iterations between $1$ and $t$, increasing $t$ exponentially after each failure. A common rate of increase is replacing $t$ with the ceiling of $\frac{5}{4}t$. Doubling $t$ is too fast to benefit from lighter spins. This method ensures we find a solution in $O(\text{square root of } \frac{N}{s})$ queries without knowing $s$ in advance. If no solutions exist, the process terminates after $O(\text{square root of } N)$ queries.

Optimality and Applications

Within the query model, Grover's algorithm is asymptotically optimal; it is impossible to solve the search problem using fewer than $O(\text{square root of } N)$ queries in the worst case. This fact was known even before Grover discovered his algorithm. The square root speedup is broadly applicable; Grover's algorithm can be used as a subroutine for other tasks, such as finding the minimum of a set of values with a quadratic advantage over classical algorithms. Furthermore, the technique of using two reflections can be generalized as amplitude amplification, which quadratically boosts the success probability of other quantum algorithms. While it may not provide a practical advantage immediately, Grover's algorithm remains a fundamental and versatile component of quantum computation.