Classical Quantum Algorithms

1 History & Context: The Birth of Quantum Algorithms

Before the 1990s, quantum mechanics and computer science were largely separate intellectual territories. Physicists studied how quantum systems behaved; computer scientists proved theorems about Turing machines and Boolean circuits. The synthesis of the two — the idea that quantum mechanics could be exploited to solve computational problems faster than any classical machine — began not with a grand theory, but with a tiny toy problem.

David Deutsch's 1985 paper “Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer” was the founding document. Deutsch noticed that a quantum computer could, in principle, evaluate a function on a superposition of all inputs simultaneously — what he called quantum parallelism. But parallelism alone doesn't give speedup; the hard part is extracting a useful global property from the interference of all those parallel computations. In 1992, Deutsch and Richard Jozsa found the first concrete demonstration that this could be done.

The period 1992–1996 produced a burst of landmark algorithms, each exploiting the same core toolkit — superposition, oracle queries, phase kickback, and interference — in increasingly sophisticated ways.

1.1 Algorithm Timeline

1.2 Computational Complexity Classes

To understand what quantum algorithms achieve, we need the language of complexity classes — sets of problems grouped by the resources needed to solve them.

2 The Query / Oracle Model

All of this week's algorithms are studied in the query complexity (or oracle complexity) model. Rather than measuring the total running time on some computational model, we count only the number of times the algorithm needs to evaluate a black-box function $f$. This isolates the quantum speedup cleanly from any implementation details.

2.1 The Standard Oracle — The Starting Point

In a classical setting, calling an oracle on input $x$ simply returns $f(x)$. In a quantum setting, we use an operation $U_f$ on two registers: the input register $\ket{x}$ and an ancilla (helper) register $\ket{y}$.

This is called a standard oracle or bit oracle. It performs an XOR addition ($\oplus$) on the target register.

2.2 Setting up the Trick: The $|-\rangle$ State

To achieve phase kickback, we do not feed a basic $\ket{0}$ or $\ket{1}$ into the ancilla register. Instead, we prepare it in the minus state, which is a specific superposition: $$\ket{-} = \frac{\ket{0} - \ket{1}}{\sqrt{2}}$$

2.3 The Proof: Stepping Through the Phase Kickback

2.4 Quantum Parallelism: The Engine at Work

The math above shows how a single input $\ket{x}$ gets a phase flip if $f(x)=1$. The real power is applied when our input is a massive superposition of all possible inputs: $$\ket{\psi} = \sum_x \alpha_x \ket{x}$$

When we apply the phase oracle, the math distributes perfectly across every single term:

When the input is a superposition, the phase oracle acts as a "filter" that marks certain states with a negative sign: $$U_f \left(\sum_x \alpha_x \ket{x}\right)\ket{-} = \left(\sum_x (-1)^{f(x)}\alpha_x \ket{x}\right)\ket{-}$$ This is the fundamental engine behind all this week's algorithms.

3 The Deutsch–Jozsa Algorithm

3.1 The Problem

3.2 Full Circuit Derivation

The circuit uses $n$ data qubits and 1 ancilla qubit.

Let us track the state at each step rigorously.

3.3 Why It Works: The Key Insight

The crucial insight is that $H^{\otimes n}$ is its own inverse ($(H^{\otimes n})^2 = I$). If $f$ is constant, $(-1)^{f(x)}$ is a global phase on all states — applying $H^{\otimes n}$ a second time undoes the first $H^{\otimes n}$ and sends every state back to $\ket{0^n}$. If $f$ is balanced, the phases are not all the same; there's a non-trivial pattern across $x$, and the final Hadamard performs a kind of Fourier transform that sends the amplitude of $\ket{0^n}$ to zero — exactly the pattern that a balanced function creates.

Let's verify with a concrete $n=2$ example to build intuition:

3.4 Interactive Oracle Demo

3.5 Qiskit Implementation

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.primitives import StatevectorSampler
import numpy as np

def deutsch_jozsa_circuit(oracle_type: str, n: int = 3) -> QuantumCircuit:
    """
    Build n-qubit Deutsch-Jozsa circuit.
    oracle_type: 'constant_0', 'constant_1', or 'balanced'
    """
    qr = QuantumRegister(n + 1, 'q')   # n data + 1 ancilla
    cr = ClassicalRegister(n, 'c')
    qc = QuantumCircuit(qr, cr)

    # Step 1: Initialise ancilla to |1⟩
    qc.x(qr[n])                   # ancilla = qubit n

    # Step 2: Apply H to all qubits
    qc.h(qr)                       # creates |+⟩^n |−⟩ on data, ancilla

    qc.barrier()

    # Step 3: Apply oracle
    if oracle_type == 'constant_0':
        pass                       # f(x)=0 for all x: do nothing

    elif oracle_type == 'constant_1':
        qc.x(qr[n])                # f(x)=1: flip ancilla unconditionally
                                   # (global phase of -1 on all states)

    elif oracle_type == 'balanced':
        # Example balanced oracle: f(x) = x_0  (XOR with first qubit)
        # Implement as CNOT from data qubit 0 to ancilla
        for i in range(n):
            qc.cx(qr[i], qr[n])   # phase kickback from each data qubit

    qc.barrier()

    # Step 4: Apply H again to data qubits
    qc.h(qr[:n])

    # Step 5: Measure data qubits
    qc.measure(qr[:n], cr)

    return qc

# Run with exact statevector sampler (no noise)
qc = deutsch_jozsa_circuit('balanced', n=3)
sampler = StatevectorSampler()
job = sampler.run([qc], shots=1024)
result = job.result()[0]
counts = result.data.c.get_counts()

# Interpret result
total = sum(counts.values())
zero_count = counts.get('000', 0)
if zero_count / total > 0.95:
    print("Function is CONSTANT (measured all-zeros)")
else:
    print("Function is BALANCED (measured non-zero string)")
    print(f"Measured: {counts}")

4 The Bernstein–Vazirani Algorithm

4.1 The Problem

4.2 Full Derivation

Remarkably, the circuit is identical to the Deutsch–Jozsa circuit. What changes is the oracle and the interpretation of the measurement.

4.3 Interactive Demo — Recover the Secret String

Qiskit code for BV:

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister

def bernstein_vazirani(s: str) -> QuantumCircuit:
    """
    s: secret bit-string (e.g. '10110')
    Returns circuit that recovers s in one query.
    """
    n = len(s)
    qr = QuantumRegister(n + 1, 'q')
    cr = ClassicalRegister(n, 'c')
    qc = QuantumCircuit(qr, cr)

    # Prepare ancilla |−⟩
    qc.x(qr[n])
    qc.h(qr)          # H on all: data→|+⟩^n, ancilla→|−⟩
    qc.barrier()

    # Oracle: implement f(x) = s·x mod 2
    # = CNOT from each data qubit i to ancilla where s[i]='1'
    for i, bit in enumerate(reversed(s)):   # LSB first
        if bit == '1':
            qc.cx(qr[i], qr[n])

    qc.barrier()
    qc.h(qr[:n])       # Second Hadamard layer
    qc.measure(qr[:n], cr)
    return qc

# Test
s = '10110'
qc = bernstein_vazirani(s)
print(f"Hidden string: {s}")
print(f"Circuit depth: {qc.depth()}")

5 Simon's Algorithm

5.1 The Problem

If $s = 0^n$, then $f$ is one-to-one (injective). Otherwise, every output value is hit exactly twice, by $x$ and $x \oplus s$. This is like a "hidden XOR symmetry" — and the technique used to solve it is the prototype for Shor's algorithm.

5.2 Step-by-Step Evolution

6 Grover's Search Algorithm

6.1 The Search Problem

Given $N = 2^n$ items (indexed $0, 1, \ldots, N-1$), of which $M$ are "marked" (satisfy some criterion), find one. In the oracle model, we can ask "is item $x$ marked?" — a single yes/no query.

For $n=30$ qubits ($N = 10^9$ items), Grover uses about $\pi/4 \cdot \sqrt{10^9} \approx 24{,}868$ queries; a classical search averages $500{,}000{,}000$. The speedup is quadratic — modest compared to Shor's exponential, but the setting is completely generic (no structure assumed on $f$).

6.2 The Phase Oracle

Grover's oracle marks the target state $\ket{t}$ with a phase flip: $$\mathcal{O}\ket{x} = \begin{cases} -\ket{x} & \text{if } x = t \\ +\ket{x} & \text{otherwise} \end{cases} \equiv (-1)^{f(x)}\ket{x}$$ where $f(x) = 1$ iff $x$ is a marked item. In matrix form, $\mathcal{O} = I - 2\ket{t}\bra{t}$. This is a reflection about the hyperplane orthogonal to $\ket{t}$ — the oracle simply flips the phase of the marked state.

6.3 The Diffusion Operator (The Mirror about the Mean)

The second component is the diffusion operator. While the oracle "marks" our target with a minus sign, the diffuser is what actually amplifies its probability.

The formal definition is $D = 2\ket{s}\bra{s} - I$, where $\ket{s}$ is the uniform superposition. In a circuit, this is implemented by wrapping a 0-state phase flip between two Hadamard layers ($H^{\otimes n}$).

6.4 Grover Iterator Circuit

6.5 Geometric Picture — Rotation in 2D

Grover's algorithm has an elegant geometric interpretation. Consider the 2D plane spanned by:

• $\ket{\alpha}$ = uniform superposition over unmarked states (normalised)
• $\ket{\beta}$ = uniform superposition over marked states (normalised)

Any state in this plane can be written $\cos\theta\,\ket{\alpha} + \sin\theta\,\ket{\beta}$. The initial uniform superposition $\ket{s} = \sqrt{1-M/N}\,\ket{\alpha} + \sqrt{M/N}\,\ket{\beta}$, so the initial angle is $\sin\theta_0 = \sqrt{M/N}$.

We want $(2k+1)\theta_0 \approx \pi/2$, i.e., $k \approx \frac{\pi}{4\theta_0} - \frac{1}{2}$. For $M=1$: $\theta_0 = \arcsin(1/\sqrt{N}) \approx 1/\sqrt{N}$ (for large $N$), giving: $$k_{\text{opt}} \approx \frac{\pi}{4}\sqrt{N}$$

6.5 Iteration Count and Success Probability

6.6 Interactive Grover Visualizer

The visualization below shows the geometric rotation in the $(\ket{\alpha}, \ket{\beta})$ plane. The blue arrow shows the current state; the gold arrow shows the target direction. Adjust $N$ and watch how many iterations are needed.

6.7 Amplitude Evolution Visualizer — The Full Picture

The geometric view shows why Grover works; the amplitude bar chart shows how it feels from inside. Watch every basis state's amplitude bar evolve with each iteration — the marked element's bar shoots up while all others are suppressed. The gold dashed line is the mean amplitude (the pivot for the diffusion operator).

Algorithm GROVER(oracle O_f, n qubits, N = 2^n):
  T_opt ← ⌊(π/4)·√N⌋         // optimal number of iterations
  |ψ⟩ ← H^⊗n |0⟩^n           // uniform superposition

  for t = 1 to T_opt:
    |ψ⟩ ← O_f |ψ⟩              // Phase oracle: flip sign of |x*⟩
    |ψ⟩ ← D |ψ⟩                // Diffusion: invert about mean
    // D = H^⊗n · (2|0^n⟩⟨0^n| − I) · H^⊗n

  result ← MEASURE(|ψ⟩)        // Success with prob ≥ 1 − 1/N
  return result

6.8 Generalisations and Applications

Grover's algorithm (or amplitude amplification) is used as a subroutine in:

• Collision finding: Find two inputs with the same output in $O(N^{1/3})$ time (quantum birthday problem)
• Element distinctness: Determine if a list has duplicates in $O(N^{2/3})$ queries
• Triangle finding: Quantum speedup for graph problems
• Constraint satisfaction / SAT: Quadratic speedup over classical exhaustive search
• Quantum minimum finding: Find the minimum of $N$ values in $O(\sqrt{N})$ queries
• Cryptographic applications: Grover halves the effective key length of symmetric ciphers — AES-128 becomes equivalent to AES-64 against a quantum adversary, motivating post-quantum cryptography

from qiskit import QuantumCircuit
from qiskit.circuit.library import GroverOperator
from qiskit.primitives import StatevectorSampler
import math

def grover_circuit(n: int, target: int) -> QuantumCircuit:
    """
    Build Grover's circuit to find 'target' in {0,...,2^n - 1}.
    """
    N = 2 ** n
    # Optimal number of iterations
    k_opt = round((math.pi / 4) * math.sqrt(N))

    qc = QuantumCircuit(n)
    qc.h(range(n))          # Initial uniform superposition

    for _ in range(k_opt):
        # Phase oracle: flip phase of |target⟩
        # Implement as X on 0-bits, multi-controlled-Z, X back
        target_bits = format(target, f'0{n}b')
        for i, bit in enumerate(reversed(target_bits)):
            if bit == '0':
                qc.x(i)
        qc.h(n-1)
        qc.mcx(list(range(n-1)), n-1)   # multi-controlled Toffoli
        qc.h(n-1)
        for i, bit in enumerate(reversed(target_bits)):
            if bit == '0':
                qc.x(i)

        # Diffusion operator: 2|s⟩⟨s| - I
        qc.h(range(n))
        qc.x(range(n))
        qc.h(n-1)
        qc.mcx(list(range(n-1)), n-1)
        qc.h(n-1)
        qc.x(range(n))
        qc.h(range(n))

    qc.measure_all()
    return qc

# Example: find |101⟩ = item 5 in N=8
qc = grover_circuit(n=3, target=5)
sampler = StatevectorSampler()
result = sampler.run([qc], shots=1000).result()[0]
print(result.data.meas.get_counts())