Grover’s Quantum Algorithm

04 Feb 2022

Introduction

With the 1996 paper “A fast quantum mechanical algorithm for database search”, the Indian-American computer scientist Lov K. Grover helped highlight the non-negligible impact of quantum computing on the cryptographic systems currently in use.

Grover’s work concerns the problem of searching an unstructured database, i.e., a database lacking any ordering that could facilitate the search operation.

To understand the contribution of Grover’s algorithm, let us consider a simple example. Take a standard telephone directory in which names are listed in alphabetical order, each associated with a corresponding phone number.

Suppose, however, that one needs to perform a reverse lookup and therefore has a given phone number whose owner must be identified.

A classical approach to solving this problem consists of scanning the directory and checking the phone numbers one by one until the desired one is found, thereby identifying the associated name. Consequently, in the worst case, identifying the owner requires checking all the numbers in the directory except the last one.

By contrast, using Grover’s algorithm, a quantum computer would solve the same instance with a much smaller number of “quantum checks” compared to the classical case. In particular, one speaks of a quadratic speed-up with respect to the classical approach. This means that, given a search problem requiring $N$ checks in the classical case, the quantum case using Grover’s algorithm requires only about $\sqrt{N}$ quantum checks.

Returning to the previous example, if the telephone directory consisted of 10000 entries, the classical approach would require 9999 checks in the worst case, whereas the quantum approach would require fewer than 100.

If a quantum computer with adequate characteristics were to be realized, the most relevant security implications of Grover’s result would arise in the context of symmetric cryptography currently in use.

For example, consider the AES (Advanced Encryption Standard) encryption scheme with a cryptographic key $k$ of length 128 bits, and assume that an attacker knows some plaintext–ciphertext pairs and aims to find the key such that, for each known pair, the corresponding ciphertext can be obtained from the plaintext and vice versa.

At the state of the art, no attack is known that performs significantly better than exhaustive search for key recovery^[1].
In the classical case, exhaustive search would require approximately $2^{128}$ calls to the oracle^[2] $O$ to determine $k$ , whereas in the quantum case Grover’s algorithm would invoke the oracle $U$ approximately $2^{64}$ times, with a success probability very close to 1.

It is often stated in common narratives that Grover’s search algorithm “halves” the security of modern symmetric cryptography. This halving refers to the bit length of the key involved. For instance, breaking AES with a $128$ -bit key using Grover’s algorithm requires a number of quantum oracle invocations comparable to the number of classical oracle invocations needed to break AES with a $64$ -bit key via exhaustive search.

As a consequence, it is reasonable to expect that, in order to restore the security of symmetric schemes in light of developments in quantum computing, it would suffice to double the cryptographic key size in bits. However, this would be a particularly conservative choice in practice, since the effective halving of security can only be considered partial, for at least two reasons.

The first reason is the difficulty of precisely determining the computational cost of executing $U$ , which is generally believed to be higher than that of $O$ ^[3].
The second aspect to consider is the impossibility of efficiently parallelizing the quantum search algorithm, which would therefore typically be executed on a single quantum processor, whereas the computational burden of exhaustive search can be distributed across multiple devices operating in parallel.

The following sections are devoted to a technical description of Grover’s algorithm and the corresponding quantum circuit. To fully understand the discussion, the reader is advised to review the concepts introduced in the previous article.

Qubits as Vectors

In order to interpret the rationale underlying Grover’s work, it is useful to review the definition of qubits in vectorial terms.

Let $\mathbb{C}^n$ be the $n$ -dimensional complex vector space equipped with the usual inner product. Each $n$ -qubit is associated with a unit-norm vector in this space.

In particular, vectors corresponding to qubits of the form $|x_0\cdots x_{n-1}\rangle$ are called basis vectors.

As illustrative examples, consider the cases $n=1$ and $n=2$ . For $n=1$ :

$\begin{aligned} \text{1-qubit basis states: } | & 0\rangle \longleftrightarrow \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \qquad |1\rangle \longleftrightarrow \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \\ \text{Generic 1-qubit: } | & \psi\rangle = \alpha |0\rangle + \beta |1\rangle \longleftrightarrow \begin{pmatrix} \alpha \\ \beta \end{pmatrix}. \end{aligned}$

For $n=2$ :

$\begin{aligned} \text{2-qubit basis states: }| & 00\rangle \longleftrightarrow \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \qquad |01\rangle \longleftrightarrow \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \qquad |10\rangle \longleftrightarrow \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \qquad |11\rangle \longleftrightarrow \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}, \\ \text{Generic 2-qubit: }| & \psi\rangle = \alpha |00\rangle + \beta |01\rangle +\gamma |10\rangle + \delta |11\rangle\longleftrightarrow \begin{pmatrix} \alpha \\ \beta \\ \gamma \\ \delta \end{pmatrix}. \end{aligned}\end{tiny}$

Grover Circuit

In a numerical formulation of Grover’s search algorithm, without loss of generality, one may consider searching over the set of the first $N$ natural numbers, with $N=2^n$ , whose binary representations are:

$\begin{aligned} 0 & \leftrightarrow 0\dots 000 \\ 1 & \leftrightarrow 0\dots 001 \\ 2 & \leftrightarrow 0\dots 010 \\ \vdots & \\ N-1 & \leftrightarrow \underbrace{1\dots 111}_{n} \end{aligned}$

The fact that only a particular $a\in{0,1}^n$ satisfies a given condition can be captured by defining the following function $f$ , which outputs $1$ if the input is $a$ , and 0 otherwise.

$\begin{aligned} f\colon {0,1}^n & \longrightarrow {0,1} \\ a & \longmapsto 1 \\ x (\neq a) & \longmapsto 0 \end{aligned}$

It is assumed that access to the function is provided through the oracle $O_f$ , meaning that $f$ is not known explicitly, but given $x\in{0,1}^n$ , the value $f(x)$ can be obtained.

In the absence of additional information about the distribution of the integers between $0$ and $N-1$ with respect to $f$ , a classical computer can only proceed via exhaustive search, applying the oracle to different elements of ${0,1}^n$ until $a$ is found.

To achieve a success probability of $\frac{m}{N}$ , the oracle must be queried on $m$ distinct integers. In particular, a probability greater than $\frac{1}{2}$ of identifying $a$ is achieved by performing at least $\frac{N}{2}$ oracle calls, while in the worst case, for a deterministic answer, the number of oracle invocations is $N-1$ .
Since this number grows linearly with $N$ , the oracle complexity is denoted asymptotically as $O(N)$ .

Under the same assumptions on the database, Grover’s 1996 work proposes a quantum algorithm capable of solving the search problem with probability very close to $1$ , using approximately $\frac{\pi}{4}\sqrt{N}$ calls to the quantum oracle $U_f$ for large $N$ , asymptotically $O(\sqrt{N})$ . Since the number of oracle calls scales linearly with $\sqrt{N}$ , this constitutes a quadratic speed-up over the classical exhaustive search algorithm.

More precisely, recall the action of $U_f$ on a register of $n+1$ qubits.

$U_f(|x_0\cdots x_{n-1}\rangle |y\rangle) = |x_0\cdots x_{n-1}\rangle |y\oplus f(x_0\cdots x_{n-1})\rangle$

Given the function $f$ defined above, consider the application of $U_f$ to the $n+1$ -qubit state $|x\rangle H |1\rangle$ ^[4], where $x=x_0\cdots x_{n-1}$ .

$U_f(|x\rangle H|1\rangle)=|x\rangle(-1)^{f(x)}H|1\rangle = (-1)^{f(x)}|x\rangle H |1\rangle$

In this form, $U_f$ can be interpreted as a gate $V_f$ acting only on the first $n$ qubits as

$V_f|x\rangle = (-1)^{f(x)}|x\rangle = \begin{cases} |x\rangle \text{ if } x\neq a,\ -|a\rangle \text{ if } x = a. \end{cases}$

Given a generic $n$ -qubit state, $V_f$ flips the sign of the component along $|a\rangle$ while leaving unchanged the component orthogonal to $|a\rangle$ .

Given the uniform superposition^[5]

$|\phi\rangle = \underbrace{H|0\rangle \cdots H|0\rangle}{n}= \frac{1}{2^{\frac{n}{2}}}\sum{x=0}^{2^n-1}|x\rangle,$

one defines, analogously to $V_f$ , the transformation $W$ , which acts on a generic $n$ -qubit by fixing the component along $|\phi\rangle$ and flipping the sign of the component orthogonal to $|\phi\rangle$ .

The repeated successive application of the transformations $V_f$ and $W$ to the state $|\phi\rangle$ enables Grover’s algorithm to determine $|a\rangle$ in $O(\sqrt{N})$ steps. Below, the corresponding circuit and the proof of correctness are presented.

The first step consists in applying the Hadamard gate $H$ to the state $|0\cdots01\rangle$ . This places the first $n$ qubits into the uniform superposition $|\phi\rangle$ , allowing the last qubit to be subsequently ignored and regarded as an ancillary qubit, in light of the previous observation regarding $V_f$ .

Next, since the action of $V_f$ and $W$ on the states $|\phi\rangle$ and $|a\rangle$ yields linear combinations of these two states with real coefficients

$\begin{aligned} & V_f|a\rangle=-|a\rangle, & & V_f|\phi\rangle=|\phi\rangle-\frac{2}{2^{\frac{n}{2}}}|a\rangle, \\\ & W|a\rangle = \frac{2}{2^{\frac{n}{2}}}|\phi\rangle-|a\rangle, & & W|\phi\rangle=|\phi\rangle, \end{aligned}$

the analysis can be restricted to the real plane spanned by $|\phi\rangle$ and $|a\rangle$ .

In this plane, $V_f$ reduces to a reflection about $|a_{\bot}\rangle$ , where $|a_{\bot}\rangle$ denotes the vector orthogonal to $|a\rangle$ that is “close” to $|\phi\rangle$ , while $W$ reduces to a reflection about $|\phi\rangle$ . For sufficiently large $N$ , the angle $\theta$ between $|a_{\bot}\rangle$ and $|\phi\rangle$ can be approximated using $\sin\theta$ , since^[6]

$\sin\theta=\cos\Big(\frac{\pi}{2}-\theta\Big)=\langle a|\phi \rangle = \frac{1}{2^{\frac{n}{2}}}=\frac{1}{\sqrt{N}}\implies \theta\approx\frac{1}{\sqrt{N}}.$

The combination of the reflections $V_f$ and $W$ results in a counterclockwise rotation of all qubits in the described plane by an angle $2\theta$ . In particular, the figure illustrates the action on the state $|\phi\rangle$ .

By repeating this operation $k$ times, so as to traverse the entire arc from $|\phi\rangle$ to $|a\rangle$ , one obtains a quantum state which, upon measurement, collapses to $|a\rangle$ with probability very close to $1$ . For completeness, $k$ is obtained by solving the equation

$\frac{2\pi}{2\theta}=2k+1,$

from which $k$ is the integer closest to the real number $\frac{\pi}{4}\sqrt{N}$ .

^[1] The best known attack against AES is the biclique attack, which provides a speed-up of approximately a factor $4$ compared to exhaustive search.

^[2] The oracle of a function $f$ is a mechanism that allows one to obtain the evaluation of $f$ on a given input without explicitly knowing the definition of $f$ . In this case, the oracle returns a positive answer if and only if the key is the correct one. The classical oracle is denoted by $O$ , while the quantum oracle is denoted by $U$ .

^[3] Note that the actual total cost is given by the product of the number of oracle executions and the cost of a single oracle execution.

^[4] Recall that
$H|0\rangle=\big(\frac{1}{\sqrt{2}} |0\rangle +\frac{1}{\sqrt{2}}|1\rangle\big), \quad H|1\rangle=\big(\frac{1}{\sqrt{2}} |0\rangle -\frac{1}{\sqrt{2}}|1\rangle\big)$

^[5] Superposition of all the considered basis states with the same real coefficient and, therefore, with the same probability.

^[6] Note that the expression $\langle a|\phi \rangle$ denotes the inner product between $|a\rangle$ and $|\phi\rangle$ .

This article is part of a series of contributions by the Telsy Cryptography Research Group dedicated to quantum computing and its implications for cryptography. For other articles, please refer to the index of the section.

For other articles related to quantum and cryptography, please refer to the relevant categories in the blog.

The authors

Veronica Cristiano, a bachelor’s degree in Mathematics from the University of Pisa and a master’s degree in Mathematics with a specialization in Cryptography at the University of Trento, joined the Telsy Cryptography research group in mid-2021.

Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at end of 2020 focusing in particular on issues related to quantum technologies.