Quantum Algorithms

Quantum Algorithm Paradigms

Quantum algorithms achieve speedups over classical algorithms through three main mechanisms:

1. Quantum parallelism — superposition allows evaluating a function on all inputs simultaneously
2. Interference — amplifying correct answers while canceling wrong ones
3. Entanglement — correlating qubits to encode global properties

The most significant speedups come from algorithms using the quantum Fourier transform (QFT) as a subroutine.

Deutsch-Jozsa Algorithm

The Deutsch-Jozsa algorithm determines whether a Boolean function is constant or balanced with a single query, whereas a classical algorithm requires queries in the worst case.

Algorithm Steps

1. Prepare qubits in and one ancilla in
2. Apply Hadamard to all qubits
3. Apply the oracle (phase oracle)
4. Apply Hadamard to the first qubits
5. Measure the first qubits

The output is if is constant, and a non-zero state if is balanced.

Simon's Algorithm

Simon's algorithm finds a hidden period of a function where:

Classically, this requires queries (birthday paradox). Simon's algorithm uses only queries.

Key Insight

The quantum circuit uses the same structure as Shor's algorithm. By measuring the output of in superposition and applying the QFT, we obtain linearly independent equations modulo 2 that determine .

Quantum Speedup Hierarchy

The dequantization results of Tang (2018) showed that some quantum machine learning speedups can be matched classically, highlighting the subtlety of quantum advantage claims.

Quantum Advantage

Quantum advantage (or supremacy) refers to demonstrating a computational task that a quantum computer can solve faster than any classical computer.

In 2019, Google's Sycamore processor performed random circuit sampling in 200 seconds, claiming this would take a classical supercomputer 10,000 years. IBM contested this, estimating 2.5 days with better classical algorithms.

The key criteria for quantum advantage:

1. The task must be well-defined and verifiable
2. The quantum algorithm must be proven or believed to have no efficient classical simulation
3. The quantum computer must actually implement the algorithm correctly

Amplitude Amplification

The amplitude amplification framework generalizes Grover's search. For an algorithm that succeeds with probability , amplitude amplification boosts the success probability to 1 using applications of the Grover operator:

where prepares the initial state and marks the target states.

This provides a quadratic speedup for any algorithm whose success probability is bounded away from zero.

Python: Deutsch-Jozsa Oracle

import numpy as np

def deutsch_jozsa_oracle(n, balanced=True):
    # Create a Deutsch-Jozsa oracle as a unitary matrix.
    N = 2 ** (n + 1)
    oracle = np.zeros((N, N), dtype=complex)

    for x in range(2**n):
        for y in range(2):
            fx = x & 1 if balanced else 0
            out = y ^ fx
            oracle[out * 2**n + x, y * 2**n + x] = 1

    return oracle

# Test with n=2 qubits
n = 2
Uf = deutsch_jozsa_oracle(n, balanced=True)
print(f"Oracle shape: {Uf.shape}")
print(f"Oracle is unitary: {np.allclose(Uf @ Uf.conj().T, np.eye(2**(n+1)))}")

This constructs an oracle for the Deutsch-Jozsa problem and verifies its unitarity.

Quantum Lower Bounds

The quantum query complexity lower bound for unstructured search:

This was proven by Bennett, Bernstein, Brassard, and Vazirani (1997) using the polynomial method and adversary method.

The polynomial method: any quantum algorithm computing with queries produces a polynomial of degree approximating . Since some functions require high-degree polynomial approximation, must be large.

The adversary method: constructs an adversary strategy that forces any quantum algorithm to make many queries.

Algorithm Summary Table