The Pattern Behind Every Quantum Algorithm

  1. Prepare a superposition over many inputs (Hadamard gates).
  2. Compute something that marks the answer you want, usually by flipping a phase.
  3. Interfere so amplitude flows toward the right answers and away from the wrong ones.
  4. Measure and verify classically. Most algorithms succeed with high probability, not certainty, so you check the result and rerun if needed.

The code below uses Qiskit and the Aer simulator (install with pip install qiskit qiskit-aer). If bitstrings look reversed, remember that Qiskit prints qubit 0 on the right, as explained in the gates article.

Deutsch–Jozsa: The Smallest Honest Speed-Up

You are given a black-box function f on n bits that is either constant (always 0 or always 1) or balanced (0 for exactly half the inputs). Classically you may need 2ⁿ⁻¹ + 1 calls to be sure. A quantum circuit decides with one call. The problem is artificial and a randomised classical algorithm solves it with high probability in a few calls, so this is a teaching example, not a product. It is still the clearest demonstration of phase interference doing real work.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

def dj(oracle, n=3):
    qc = QuantumCircuit(n + 1)
    qc.x(n); qc.h(range(n + 1))          # ancilla in |->, inputs in superposition
    oracle(qc, n)                        # ONE call to the black box
    qc.h(range(n))
    probs = Statevector.from_instruction(qc).probabilities_dict(qargs=list(range(n)))
    return {str(k): round(float(v), 3) for k, v in probs.items() if v > 1e-9}   # drop numerical noise

constant = lambda qc, n: None                               # f(x) = 0
balanced = lambda qc, n: [qc.cx(i, n) for i in range(n)]    # f(x) = x0 xor x1 xor x2
print("constant ->", dj(constant))   # {'000': 1.0}
print("balanced ->", dj(balanced))   # {'111': 1.0}, never '000'

Reading the input register after the single oracle call tells you the answer: all zeros means constant, anything else means balanced.

Grover's Algorithm: Quadratic Search Speed-Up

Grover's algorithm finds a marked item among N unsorted items in about (π/4)·√N oracle calls instead of the ~N/2 a classical scan needs on average. Each iteration does two things: the oracle flips the sign of the marked state's amplitude, then the diffuser reflects all amplitudes about their average, which boosts the marked one a little each round.

import math
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

def grover_circuit(n, marked, iterations):
    qc = QuantumCircuit(n, n)
    qc.h(range(n))                                   # uniform superposition
    for _ in range(iterations):
        # Oracle: flip the phase of |marked>
        for i, bit in enumerate(reversed(marked)):   # qubit 0 is the rightmost bit
            if bit == "0": qc.x(i)
        qc.h(n - 1); qc.mcx(list(range(n - 1)), n - 1); qc.h(n - 1)   # multi-controlled Z
        for i, bit in enumerate(reversed(marked)):
            if bit == "0": qc.x(i)
        # Diffuser: reflect about the average amplitude
        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(range(n), range(n))
    return qc

n, marked = 3, "101"
N = 2 ** n
k = math.floor(math.pi / 4 * math.sqrt(N))           # optimal iterations for one marked item
print("N =", N, "optimal iterations =", k)
sim = AerSimulator()
for it in (0, 1, k, 3):
    qc = grover_circuit(n, marked, it)
    counts = sim.run(transpile(qc, sim), shots=2000, seed_simulator=11).result().get_counts()
    print("iterations", it, "P(101) ~", round(counts.get(marked, 0) / 2000, 3))

Expected output from our run:

N = 8 optimal iterations = 2
iterations 0 P(101) ~ 0.133
iterations 1 P(101) ~ 0.784
iterations 2 P(101) ~ 0.948
iterations 3 P(101) ~ 0.33

Two lessons are visible. First, zero iterations gives 1/8 ≈ 0.125, which is just guessing. Two iterations give about 95% success. Second, a third iteration makes things worse (0.33). Grover rotates the state toward the answer and overshoots if you keep going, so you must know roughly how many solutions exist. With the wrong count you can miss the answer entirely.

What the Quadratic Speed-Up Does and Does Not Give You

  • Real but modest: √N is a big win for huge N, but each quantum operation is slower and noisier than a classical one today. For realistic problem sizes a classical machine with indexes or hashing usually wins.
  • Not a database accelerator: loading N classical records into quantum memory costs at least N operations, which erases the gain. Grover helps when the oracle is a computable function (check a candidate key, test a constraint), not a lookup table.
  • Cryptography impact: Grover roughly halves the effective bit-strength of symmetric keys, so AES-128 gives ~64-bit quantum search cost while AES-256 stays comfortable. Doubling key sizes is the standard mitigation.

Shor's Algorithm: The One That Breaks RSA

Factoring N reduces to finding the period r of f(x) = aˣ mod N for a random a. Classically finding r is as hard as factoring. A quantum computer finds it efficiently by building a superposition over x, computing f, then using the quantum Fourier transform to make the period show up as a measurable peak. Everything else is ordinary arithmetic.

This snippet runs the classical half on the textbook example N = 15, with brute force standing in for the quantum period-finding step:

from math import gcd

def find_period(a, N):           # <- the ONLY step a quantum computer accelerates
    x, r = a % N, 1
    while x != 1:
        x = (x * a) % N; r += 1
    return r

N, a = 15, 7
r = find_period(a, N)
print("period r =", r)                                   # period r = 4
assert r % 2 == 0 and pow(a, r // 2, N) != N - 1         # conditions for success
p, q = gcd(pow(a, r // 2) - 1, N), gcd(pow(a, r // 2) + 1, N)
print("factors:", p, q)                                  # factors: 3 5

For a 2048-bit RSA modulus the brute-force loop would never finish, but a fault-tolerant quantum computer would do that single step in polynomial time. That is the entire threat: one subroutine, applied to the maths behind RSA, Diffie–Hellman and elliptic-curve cryptography.

Beware "quantum factored 15" headlines

Factoring 15 or 21 on hardware has been demonstrated, but small cases can be made easy by compiling in knowledge of the answer. Real progress is measured in error-corrected logical qubits, not in the size of the number factored by a noisy experiment. See Quantum Hardware and Error Correction.

What Is Realistic Today

AlgorithmSpeed-upPractical status
Deutsch–JozsaExponential vs deterministic classical, none vs randomisedTeaching tool only
GroverQuadraticNeeds large fault-tolerant machines to beat classical for real workloads
ShorExponential (super-polynomial)Needs a large fault-tolerant machine; drives post-quantum migration now
Quantum simulationPotentially exponential for some chemistry and materials problemsMost credible early application; active research
Optimisation / MLUnclear, mostly heuristicNo broadly accepted practical advantage yet

What to Do With This as a Developer

  • Run the three snippets above and change the marked item, the number of iterations and the oracle until the behaviour feels predictable.
  • Treat vendor "quantum advantage" claims as claims about specific benchmarks, not general speed.
  • Act on the part that is already urgent: start the post-quantum cryptography migration, because Shor's threat to encryption is a data-lifetime problem you can address today.

Frequently Asked Questions

Does Grover's algorithm make brute-forcing AES practical?

No. It reduces the work from 2^n to roughly 2^(n/2) operations, so AES-128 behaves like a 64-bit search and AES-256 like a 128-bit search. The operations also have to run sequentially on error-corrected hardware, so AES-256 remains considered safe.

Can a quantum computer break RSA today?

No. Breaking RSA-2048 with Shor's algorithm needs a large error-corrected quantum computer that does not exist yet. The concern is data that must stay secret for many years, which can be recorded now and decrypted later.

Why does adding more Grover iterations reduce the success rate?

Each iteration rotates the state toward the marked answer by a fixed angle. Past the optimal count of about (π/4)·√N iterations the state rotates beyond the target, so the success probability falls again.

What part of Shor's algorithm is quantum?

Only the period-finding step, which uses superposition and the quantum Fourier transform. Choosing a, checking conditions and computing greatest common divisors to extract the factors are ordinary classical computation.

Is the Deutsch–Jozsa speed-up useful in practice?

Not directly. A randomised classical algorithm solves the problem with high probability in a few queries. It matters as the cleanest example of how phase interference lets one query reveal a global property.