Quantum Search Algorithm
A brief overview of Grover's Algorithm, i.e. Quantum Search Algorithm, which efficiently searches an unsorted database.
This is a shorter article on Grover’s algorithm, originally intended to be a Twitter (X) thread. For the full-length version, see Quantum Search Algorithm (Full).
Introduction
Say you want to search a large unsorted database. With classical computing, you’d have to check half its entries on average (or, worst case, each entry). Isn’t there a more efficient way to search? Thanks to quantum computing, there is!
Grover’s algorithm (i.e. quantum search algorithm) finds m targets within an unsorted database of size $N$. More generally, it inverts function $y = f(x)$ by finding $x = f^{−1}(y)$ with $O(\sqrt{N})$ evaluations. This algorithm requires $n = \lceil \log_{2}N \rceil$ qubits; $N$, $n$, and $m$ are all positive integers, and $N > 1$.
Background
Qubits: The Building Blocks of Quantum Computing
What exactly is a qubit? A quantum bit (i.e. qubit) is a basic unit of quantum information used in quantum computing. It’s analogous to a classical bit, but with key differences. Some of its properties include:
- Superposition: A qubit’s ability to be in multiple states simultaneously. While a bit can only ever be 0 or 1, a qubit can be both. It holds more information than a bit and allows the system to work on many computations at once (i.e. parallelism). Thus, a quantum computer’s processing speed is superior to that of a classical computer.
- Entanglement: Linking a pair of qubits in a system such that they’re dependent on one another (i.e. their values correlate); measuring or changing one will instantly change the other(s) in a predictable way regardless of the distance between them. This dramatically increases how many qubits can be processed.
- Teleportation: The transmission of one entangled qubit to another irrespective of distance, resulting in information transfer that’s impossible to lose or intercept (i.e. secure, unbreakable encryption). This may lead to a quantum internet in the future.
- Tunneling: A qubit’s ability to move through an impenetrable barrier. It seems paradoxical or impossible in the context of classical mechanics, but it’s part of how quantum computers complete tasks that are impossible for classical computers.
- Decoherence: A process where environmental factors (e.g. measurement, radiation, light, sound, heat, vibrations, magnetic fields, etc.) instantaneously and irreversibly alter a qubit’s state, resulting in the decay and loss of [stored] information. It’s why quantum computers have a higher error rate than classical computers.
The Mathematics of Qubits
A single qubit $q$ can be described as state $\ket{q} = \alpha \ket{0} + \beta \ket{1}$, where $\alpha$ and $\beta$ are complex numbers known as probability amplitudes defining the likelihood of $q$ being in a particular state (i.e. $\ket{0}$ or $\ket{1}$) after measurement. Probability of $\ket{0}$ is $\vert \alpha \vert^{2}$, probability of $\ket{1}$ is $\vert \beta \vert^{2}$, and $\vert \alpha \vert^{2} + \vert \beta \vert^{2} = 1$.
States can either be pure (100% certain of system’s state) or mixed (uncertain of system’s state; probability distribution of pure states).
For the sake of simplicity, we’ll only focus on pure states.
Why Quantum Computing Matters
Why are quantum computers special? They’re faster and more powerful than any classical computer (as of right now) by a very large order of magnitude. Increasing a qubit’s speed doubles a quantum computer’s processing power; a calculation that’d take any classical supercomputer millennia could be done by a quantum computer in minutes.
Grover’s algorithm can estimate a numerical set’s mean and median, and speeds up:
- Black-box problems (e.g. collision problem, element distinctness)
- NP-complete problems
- Constraint satisfaction problems
- Brute-force symmetric-key cryptography (e.g. collision attacks, pre-image attacks)
Quantum vs Classical Computing
Grover’s algorithm takes $O(\sqrt{N})$ time, compared to a classical algorithm’s $O(N)$ time.
For example, if $N = 64$, Grover’s algorithm finds the targets in 8 steps or less. On the other hand, a classical algorithm requires 64 steps or less to do the same thing.
This is a quadratic speedup!
Grover’s algorithm requires $O(\log_{2}N)$ storage space, while a classical algorithm (in this case, linear search) uses $O(1)$ storage space.
If N is small, a classical algorithm may be more suitable. However, if $N$ is very large, Grover’s algorithm is the superior choice.
Each database entry is represented as an $n$-qubit state $\ket{x_{i}}$ where:
\[0 \le i \le N - 1\] \[\ket{0}^{n} \le \ket{x_{i}} \le \ket{1}^{n}\]For example, if $N = 8$ and $n = 3$ there are 3 qubits and 8 states $[ \ket{x_{0}}, \ldots, \ket{x_{7}} ]$ where:
\[\ket{000} \le \ket{x_{i}} \le \ket{111}\]If target $w = 4$, it’s encoded as $\ket{100}$.
$w$ is composed of m non-negative integer(s) (e.g. $w = 4$, $m = 1$; $w = [4, 3, 6]$, $m = 3$).
Grover’s algorithm can even be used on $N$ non-numerical objects (e.g. poker cards, sudoku) by encoding each item as a state, then decoding after measurement.
How Grover’s Algorithm Works
Grover’s algorithm is composed of 4 main steps:
- State Preparation (i.e. Initialization)
- Oracle
- Amplitude Amplification (i.e. Diffuser)
- Measurement
State Preparation
State preparation involves initializing all $n$ qubits to $\ket{0}$, then putting each qubit in a uniform superposition via Hadamard gate $H$. As a result, initial state $\ket{s} = H \ket{0}^{n}$.
Note: Uniform superposition refers to a qubit with an equal chance (50% probability) of being $\ket{0}$ or $\ket{1}$.
Oracle
Oracle $O$ marks target states $[ \ket{x_{0}}, \ldots, \ket{x_{m - 1}} ]$ and leaves all other states alone:
\[O \ket{x} = (-1)^{f(x)} \ket{x}\]Where:
IF $\ket{x}$ IN $[ \ket{x_{0}}, \ldots, \ket{x_{i - 1}}]$: $f(x) = 1$
ELSE: $f(x) = 0$
Diffusion
Diffuser $D$ amplifies target states $[ \ket{x_{0}}, \ldots, \ket{x_{m - 1}} ]$ while deamplifying all other states.
\[D \ket{x} = (-1)^{g(x)} \ket{x}\]Where:
IF $\ket{x} = \ket{0}^{n}$: $g(x) = 0$
ELSE: $g(x) = 1$
This increases the chance of getting the correct answer after measurement with near certain (i.e. close to 100%) probability.
Iteration and Measurement
Applying Oracle $O$ and then Diffuser $D$ is known as Grover’s operator. Since quantum algorithms are probabilistic, the probability of correctness can be maximized by repeating Grover’s operator an optimal amount of times $t$. If the iteration number isn’t optimized (i.e. not equal to $t$), we risk getting incorrect results after measurement.
\[t \approx \lfloor \frac{\pi}{4} \sqrt{\frac{N}{m}}\rfloor\]For example, if $N = 32$ and $m = 2$, $t ≈ 3$.
Following $t$ iterations we’re left with final state $\ket{\psi} = (DO)^{t} \ket{s}$.
After measurement, the correct states are found with near certainty.