Grover’s algorithm

Description

Grover’s algorithm [1] is a probabilistic quantum algorithm for performing an unstructured search on an input of size \(N\) in a time (query) complexity of \(\BigO(\sqrt{N})\). In other words, Grover’s algorithm finds (with high probability) a marked (or target) value contained within an input domain (which is usually taken to be some given dataset). This is achieved by first encoding the input domain as a quantum state (i.e., a quantum superposition of all possible values), following which the target state’s probability amplitude in the superposition is amplified via Grover iterations—a sequence of oracles and Grover diffusion operators. Classically, an unstructured search would require, on average, exactly \(N/2\) evaluations (queries) of the input to find the correct value, which corresponds to a query complexity of \(\BigO(N)\). Grover’s algorithm therefore presents a quadratic speedup compared to the best classical algorithm.

Algorithm

In Grover’s algorithm, we have two inputs: the input size \(N \geq 1\) and marked value \(\tilde{x} \geq 0\), both decimal integers with \(\tilde{x} < N\). The task is to, given the set of inputs,

(426)\[\Integers_N = \{ x \in \Integers \, : \, 0 \leq x \leq N - 1 \},\]

find the marked value \(\tilde{x} \in \Integers_N\). Note however that, as at least \(n = \lceil \log_{2}(N) \rceil\) qubits are required to encode the entire input set, then the search will necessarily be conducted on the (larger) domain

(427)\[\Integers_{2^n} = \{ x \in \Integers \, : \, 0 \leq x \leq 2^n - 1 \}.\]

The quantum circuit representation of Grover’s algorithm appears in Figure 30. Here, the circuit’s register is initialized in the state

(428)\[\ket{\Psi_0} = \ket{0}^{\otimes n}.\]

Figure 30 Grover’s algorithm.

We first apply a Hadamard gate to each system, which yields

(429)\[\begin{split}\begin{aligned} \ket{\Psi_1} &= \Hadamard^{\otimes n}\ket{\Psi_0} \\ &= \Hadamard^{\otimes n} \ket{0}^{\otimes n} \\ &= \ket{+}^{\otimes n} \\ &= \ket{\phi}, \end{aligned}\end{split}\]

where defined the equiprobabilistic or uniform superposition state \(\ket{\phi}\) as

(430)\[\ket{\phi} \equiv \frac{1}{\sqrt{N}} \sum_{x=0}^{N - 1} \ket{x},\]

with \(N \equiv 2^n\). This state describes the (equal) superposition of all possible values in the input domain \(\Integers_{2^n}\).

Next, we perform the Grover iterations. Each iteration involves first applying the oracle \(\Oracle_{\tilde{x}}\), which has the action

(431)\[\Oracle_{\tilde{x}} = \Identity - 2 \ket{\tilde{x}}\bra{\tilde{x}},\]

where \(\tilde{x}\) is the marked value. The role of the oracle is to flip the phase of the marked state: this is manifestly evident when we characterize the oracle by its action on a basis state \(\ket{x}\),

(432)\[\Oracle_{\tilde{x}} \ket{x} = (-1)^{f(x)} \ket{x},\]

where

(433)\[\begin{split}f(x) = \begin{cases} 1, & \text{if } x = \tilde{x}; \\ 0, & \text{if } x \neq \tilde{x}. \end{cases}\end{split}\]

The second part of each Grover iteration is the transformation of the state under the Grover diffusion operator,

(434)\[\begin{split}\begin{aligned} \Diffusion &= 2 \ket{\phi}\bra{\phi} - \Identity^{\otimes n} \\ &= \Hadamard^{\otimes n} \cdot (2 \ket{0}\bra{0}^{\otimes n} - \Identity^{\otimes n}) \cdot \Hadamard^{\dagger \otimes n}. \end{aligned}\end{split}\]

Applying this operator to any given state effectively performs an inversion of its amplitudes about the average. For the state in the algorithm immediately after transformation by the oracle, this results in the phase-flipped marked value’s amplitude being inverted (phase-flipped) and subsequently amplified more than that of any of the other values.

After \(r\) such iterations, arrive at the output state

(435)\[\ket{\Psi_2} = (\Diffusion \Oracle_{\tilde{x}})^r \ket{\Psi_1}.\]

Measuring this in the computational basis, we find that, for the most optimal number of iterations (which can be shown analytically to be approximately \(r \approx \pi\sqrt{N}/4\)), the most probable state is \(\ket{\tilde{x}}\).

Implementation

Code Block 34 /text/examples/algorithms/grover.py

from qhronology.quantum.gates import GateStack, Hadamard, QuantumGate
from qhronology.quantum.circuits import QuantumCircuit
from qhronology.mechanics.matrices import ket, bra, encode, decode
from qhronology.mechanics.operations import densify

import math
import sympy as sp
import numpy as np

N = 10  # The size of the input space (domain)
marked = 4  # The value to find (should be smaller than N)

n = int(math.ceil(math.log(N, 2)))  # Encoding depth
iterations = int(math.pi * math.sqrt(2**n) / 4)

# Gates
H = GateStack(*[Hadamard()] * n)

# Construct the oracle from its definition
oracle = QuantumGate(
    spec=sp.eye(2**n) - 2 * densify(encode(marked, num_systems=n)),
    targets=list(range(0, n)),
    num_systems=n,
    label="O",
)

# Construct the Grover diffusion gate from its definition
diffusion = QuantumCircuit(
    gates=[H]
    + [
        QuantumGate(
            spec=2 * ket([0] * n) * bra([0] * n) - sp.eye(2**n),
            targets=list(range(0, n)),
        )
    ]
    + [H]
).gate(label="D")

# Construct the gate sequence of the Grover iterations
grover_iterations = [oracle, diffusion] * iterations

# Circuit
grover = QuantumCircuit(
    gates=[H] + grover_iterations,
    numerical=True,
    array=True,
)
grover.diagram(pad=(1, 0), sep=(1, 2), force_separation=True)

# Measurement
basis = [encode(k, n) for k in range(0, 2**n)]
probabilities = grover.measure(
    operators=basis,
    observable=False,
    statistics=True,
)
probabilities = [np.real(probability) for probability in probabilities]

# Results
print(f"Input size: {N}")
print(f"Marked value: {marked}")
expectation = 0
threshold = 0.001
for k, probability in enumerate(probabilities):
    value = decode(basis[k])
    bitstring = encode(value, n, return_type=str)
    expectation += probability * value

    suffix = ""
    if probability == max(probabilities):
        suffix = " (most probable)"

    if probability >= threshold or probability == max(probabilities):
        probability = sp.N(probability).round(3)
        print(
            f"Bitstring={bitstring}, "
            + f"Probability={probability}, "
            + f"Value={value}"
            + f"{suffix}"
        )

expectation = sp.N(expectation).round(3)
print(f"Expectation (weighted average): {expectation}")

Output

Diagram

>>> grover.diagram(pad=(1, 0), sep=(1, 2), force_separation=True)

Results

Cumulative output from the various print statements:

Input size: 10
Marked value: 4
Bitstring=0000, Probability=0.003, Value=0
Bitstring=0001, Probability=0.003, Value=1
Bitstring=0010, Probability=0.003, Value=2
Bitstring=0011, Probability=0.003, Value=3
Bitstring=0100, Probability=0.961, Value=4 (most probable)
Bitstring=0101, Probability=0.003, Value=5
Bitstring=0110, Probability=0.003, Value=6
Bitstring=0111, Probability=0.003, Value=7
Bitstring=1000, Probability=0.003, Value=8
Bitstring=1001, Probability=0.003, Value=9
Bitstring=1010, Probability=0.003, Value=10
Bitstring=1011, Probability=0.003, Value=11
Bitstring=1100, Probability=0.003, Value=12
Bitstring=1101, Probability=0.003, Value=13
Bitstring=1110, Probability=0.003, Value=14
Bitstring=1111, Probability=0.003, Value=15
Expectation (weighted average): 4.144

References

[1]

L. K. Grover, “A fast quantum mechanical algorithm for database search”, Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing - STOC '96, pages 212–219, Philadelphia, Pennsylvania, United States, 1996, ACM Press. DOI: 10.1145/237814.237866