Grover Search Algorithm

In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just $O(\sqrt)$ evaluations of the function, where $N$ is the size of the function's domain. It was devised by Lov Grover in 1996.

The analogous problem in classical computation cannot be solved in fewer than $O(N)$ evaluations (because, on average, one has to check half of the domain to get a 50% chance of finding the right input). Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani proved that any quantum solution to the problem needs to evaluate the function $\Omega(\sqrt)$ times, so Grover's algorithm is asymptotically optimal. Since classical algorithms for NP-complete problems require exponentially many steps, and Grover's algorithm provides at most a quadratic speedup over the classical solution for unstructured search, this suggests that Grover's algorithm by itself will not provide polynomial-time solutions for NP-complete problems (as the square root of an exponential function is an exponential, not polynomial, function).

Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover's algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when $N$ is large, and Grover's algorithm can be applied to speed up broad classes of algorithms. Grover's algorithm could brute-force a 128-bit symmetric cryptographic key in roughly 2⁶⁴ iterations, or a 256-bit key in roughly 2¹²⁸ iterations. As a result, it is sometimes suggested that symmetric key lengths be doubled to protect against future quantum attacks.

Applications and limitations

Grover's algorithm, along with variants like amplitude amplification, can be used to speed up a broad range of algorithms. In particular, algorithms for NP-complete problems generally contain exhaustive search as a subroutine, which can be sped up by Grover's algorithm. The current best algorithm for 3SAT is one such example. Generic constraint satisfaction problems also see quadratic speedups with Grover. These algorithms do not require that the input be given in the form of an oracle, since Grover's algorithm is being applied with an explicit function, e.g. the function checking that a set of bits satisfies a 3SAT instance.

Grover's algorithm can also give provable speedups for black-box problems in quantum query complexity, including element distinctness and the collision problem (solved with the Brassard–Høyer–Tapp algorithm). In these types of problems, one treats the oracle function ''f'' as a database, and the goal is to use the quantum query to this function as few times as possible.

Cryptography

Grover's algorithm essentially solves the task of ''function inversion''. Roughly speaking, if we have a function $y = f(x)$ that can be evaluated on a quantum computer, Grover's algorithm allows us to calculate $x$ when given $y$. Consequently, Grover's algorithm gives broad asymptotic speed-ups to many kinds of brute-force attacks on symmetric-key cryptography, including collision attacks and pre-image attacks. However, this may not necessarily be the most efficient algorithm since, for example, the parallel rho algorithm is able to find a collision in SHA2 more efficiently than Grover's algorithm.

Limitations

Grover's original paper described the algorithm as a database search algorithm, and this description is still common. The database in this analogy is a table of all of the function's outputs, indexed by the corresponding input. However, this database is not represented explicitly. Instead, an oracle is invoked to evaluate an item by its index. Reading a full database item by item and converting it into such a representation may take a lot longer than Grover's search. To account for such effects, Grover's algorithm can be viewed as solving an equation or satisfying a constraint. In such applications, the oracle is a way to check the constraint and is not related to the search algorithm. This separation usually prevents algorithmic optimizations, whereas conventional search algorithms often rely on such optimizations and avoid exhaustive search.

The major barrier to instantiating a speedup from Grover's algorithm is that the quadratic speedup achieved is too modest to overcome the large overhead of near-term quantum computers. However, later generations of fault-tolerant quantum computers with better hardware performance may be able to realize these speedups for practical instances of data.

Problem description

As input for Grover's algorithm, suppose we have a function $f\colon \ \to \$. In the "unstructured database" analogy, the domain represent indices to a database, and if and only if the data that ''x'' points to satisfies the search criterion. We additionally assume that only one index satisfies , and we call this index ''ω''. Our goal is to identify ''ω''.

We can access ''f'' with a subroutine (sometimes called an oracle) in the form of a unitary operator ''U_ω'' that acts as follows:
:$\begin U_\omega , x\rang = -, x\rang & \text x = \omega \text f(x) = 1, \\ U_\omega , x\rang = , x\rang & \text x \ne \omega \text f(x) = 0. \end$
This uses the $N$-dimensional state space $\mathcal$, which is supplied by a register with $n = \lceil \log_ N \rceil$ qubits.
This is often written as
:$U_\omega, x\rang = (-1)^, x\rang.$

Grover's algorithm outputs ''ω'' with probability at least ''1/2'' using $O(\sqrt)$ applications of ''U_ω''. This probability can be made arbitrarily large by running Grover's algorithm multiple times. If one runs Grover's algorithm until ''ω'' is found, the expected number of applications is still $O(\sqrt)$, since it will only be run twice on average.

Alternative oracle definition

This section compares the above oracle $U_\omega$ with an oracle $U_f$.

''U_ω'' is different from the standard quantum oracle for a function ''f''. This standard oracle, denoted here as ''U_f'', uses an ancillary qubit system. The operation then represents an inversion ( NOT gate) on the main system conditioned by the value of ''f''(''x'') from the ancillary system:
:$\begin U_f , x\rang , y\rang = , x\rang , \neg y\rang & \text x = \omega \text f(x) = 1, \\ U_f , x\rang , y\rang = , x\rang , y\rang & \text x \ne \omega \text f(x) = 0, \end$
or briefly,
:$U_f , x\rang , y\rang = , x\rang , y \oplus f(x)\rang.$
These oracles are typically realized using uncomputation.

If we are given ''U_f'' as our oracle, then we can also implement ''U_ω'', since ''U_ω'' is ''U_f'' when the ancillary qubit is in the state $, -\rang = \frac1\big(, 0\rang - , 1\rang\big) = H, 1\rang$:
:$\begin U_f \big( , x\rang \otimes , -\rang \big) &= \frac1 \left( U_f , x\rang , 0\rang - U_f , x\rang , 1\rang \right)\\ &= \frac1 \left(, x\rang , f(x)\rang - , x\rang , 1 \oplus f(x)\rang \right)\\ &= \begin \frac1 \left(-, x\rang , 0\rang + , x\rang , 1\rang\right) & \text f(x) = 1, \\ \frac1 \left( , x\rang , 0\rang - , x\rang , 1\rang \right) & \text f(x) = 0 \end \\ &= (U_\omega , x\rang) \otimes , -\rang \end$

So, Grover's algorithm can be run regardless of which oracle is given. If ''U_f'' is given, then we must maintain an additional qubit in the state $, -\rang$ and apply ''U_f'' in place of ''U_ω''.

Algorithm

The steps of Grover's algorithm are given as follows:
# Initialize the system to the uniform superposition over all states
$, s\rangle = \frac \sum_^ , x\rangle.$
# Perform the following "Grover iteration" $r(N)$ times:
## Apply the operator $U_\omega$
## Apply the ''Grover diffusion'' operator $U_s = 2 \left, s\right\rangle \left\langle s\ - I$
# Measure the resulting quantum state in the computational basis.

For the correctly chosen value of $r$, the output will be $, \omega\rang$ with probability approaching 1 for ''N'' ≫ 1. Analysis shows that this eventual value for $r(N)$ satisfies $r(N) \leq \Big\lceil\frac\sqrt\Big\rceil$.

Implementing the steps for this algorithm can be done using a number of gates linear in the number of qubits. Thus, the gate complexity of this algorithm is $O(\log(N)r(N))$, or $O(\log(N))$ per iteration.

Geometric proof of correctness

There is a geometric interpretation of Grover's algorithm, following from the observation that the quantum state of Grover's algorithm stays in a two-dimensional subspace after each step. Consider the plane spanned by $, s\rang$ and $, \omega\rang$; equivalently, the plane spanned by $, \omega\rang$ and the perpendicular ket $\textstyle , s'\rang = \frac\sum_ , x\rang$.

Grover's algorithm begins with the initial ket $, s\rang$, which lies in the subspace. The operator $U_$ is a reflection at the hyperplane orthogonal to $, \omega\rang$ for vectors in the plane spanned by $, s'\rang$ and $, \omega\rang$, i.e. it acts as a reflection across $, s'\rang$. This can be seen by writing $U_\omega$ in the form of a Householder reflection:

:$U_\omega = I - 2, \omega\rangle\langle \omega, .$

The operator $U_s = 2 , s\rangle \langle s, - I$ is a reflection through $, s\rang$. Both operators $U_s$ and $U_$ take states in the plane spanned by $, s'\rang$ and $, \omega\rang$ to states in the plane. Therefore, Grover's algorithm stays in this plane for the entire algorithm.

It is straightforward to check that the operator $U_s U_$ of each Grover iteration step rotates the state vector by an angle of $\theta = 2\arcsin\tfrac$.
So, with enough iterations, one can rotate from the initial state $, s\rang$ to the desired output state $, \omega\rang$. The initial ket is close to the state orthogonal to $, \omega\rang$:

:$\lang s', s\rang = \sqrt.$

In geometric terms, the angle $\theta/2$ between $, s\rang$ and $, s'\rang$ is given by

:$\sin \frac = \frac.$

We need to stop when the state vector passes close to $, \omega\rang$; after this, subsequent iterations rotate the state vector ''away'' from $, \omega\rang$, reducing the probability of obtaining the correct answer. The exact probability of measuring the correct answer is
:$\sin^2\left( \Big( r + \frac \Big)\theta\right),$
where ''r'' is the (integer) number of Grover iterations. The earliest time that we get a near-optimal measurement is therefore $r \approx \pi \sqrt / 4$.

Algebraic proof of correctness

To complete the algebraic analysis, we need to find out what happens when we repeatedly apply $U_s U_\omega$. A natural way to do this is by eigenvalue analysis of a matrix. Notice that during the entire computation, the state of the algorithm is a linear combination of $s$ and $\omega$. We can write the action of $U_s$ and $U_\omega$ in the space spanned by $\$ as:
: U_s : a , \omega \rang + b , s \rang \mapsto \omega_\rang_\,_, _s_\rang\begin
-1_&_-2/\sqrt_\\
0_&_1_\end\begina\\b\end.

So_in_the_basis_$\$_(which_is_neither_orthogonal_nor_a_basis_of_the_whole_space)_the_action_$U_sU_\omega$_of_applying_$U_\omega$_followed_by_$U_s$_is_given_by_the_matrix

:$_U_sU_\omega_=_\begin_-1_&_0_\\_2/\sqrt_&_1_\end \begin -1_&_-2/\sqrt_\\ 0_&_1_\end _=_ \begin 1_&_2/\sqrt_\\ -2/\sqrt_&_1-4/N_\end.$

This_matrix_happens_to_have_a_very_convenient_Jordan_form._If_we_define_$t_=_\arcsin(1/\sqrt)$,_it_is
:$_U_sU_\omega_=_M_\begin_e^_&_0_\\_0_&_e^\end_M^$_where_$M_=_\begin-i_&_i_\\_e^_&_e^_\end.$

It_follows_that_''r''-th_power_of_the_matrix_(corresponding_to_''r''_iterations)_is_
:$_(U_sU_\omega)^r_=_M_\begin_e^_&_0_\\_0_&_e^\end_M^.$
Using_this_form,_we_can_use_trigonometric_identities_to_compute_the_probability_of_observing_''ω''_after_''r''_iterations_mentioned_in_the_previous_section,_
:$\left, \begin\lang\omega, \omega\rang_&_\lang\omega, s\rang\end(U_sU_\omega)^r_\begin0_\\_1\end_\^2_=_\sin^2\left(_(2r+1)t\right).$
Alternatively,_one_might_reasonably_imagine_that_a_near-optimal_time_to_distinguish_would_be_when_the_angles_2''rt''_and_−2''rt''_are_as_far_apart_as_possible,_which_corresponds_to_$2rt_\approx_\pi/2$,_or_$r_=_\pi/4t_=_\pi/4\arcsin(1/\sqrt)_\approx_\pi\sqrt/4$._Then_the_system_is_in_state
:_ \omega_\rang_\,_, _s_\rang(U_sU_\omega)^r_\begin0\\1\end_\approx_ \omega_\rang_\,_, _s_\rangM_\begin_i_&_0_\\_0_&_-i\end_M^_\begin0\\1\end_=_, _\omega_\rang_\frac_-_, s_\rang_\frac.
A_short_calculation_now_shows_that_the_observation_yields_the_correct_answer_''ω''_with_error_$O\left_(\frac_\right)$.

__Extensions_and_variants_

__Multiple_matching_entries_

If,_instead_of_1_matching_entry,_there_are_''k''_matching_entries,_the_same_algorithm_works,_but_the_number_of_iterations_must_be__\frac_instead_of__\frac.

There_are_several_ways_to_handle_the_case_if_''k''_is_unknown._A_simple_solution_performs_optimally_up_to_a_constant_factor:_run_Grover's_algorithm_repeatedly_for_increasingly_small_values_of_''k'',_e.g.,_taking_''k''_=_''N'',_''N''/2,_''N''/4,_...,_and_so_on,_taking_$k_=_N/2^t$_for_iteration_''t''_until_a_matching_entry_is_found.

With_sufficiently_high_probability,_a_marked_entry_will_be_found_by_iteration_$t_=_\log_2(N/k)_+_c$_for_some_constant_''c''._Thus,_the_total_number_of_iterations_taken_is_at_most

:$_\frac_\Big(1_+_\sqrt_+_\sqrt_+_\cdots_+_\sqrt\Big)_=_O\big(\sqrt\big)._$

A_version_of_this_algorithm_is_used_in_order_to_solve_the_collision_problem_
The_r-to-1_collision_problem_is_an_important_theoretical_problem_in__complexity_theory,__quantum_computing,_and__computational_mathematics._The_collision_problem_most_often_refers_to_the_2-to-1_version:_given_n_even_and_a_function_f:\,\\rightarrow\_...