Quantum Algorithms and Speedups

Where speedups actually come from

Superposition alone does not make a quantum algorithm powerful. Power comes when a problem has structure that a circuit can expose through interference, phase, and measurement. Superposition is the stage; interference is the actor; the problem's structure is the script.

So the serious question is always the same pair: what structure is being exploited, and what is the best classical baseline? A speedup claim that cannot answer both is not yet a claim — it is a mood.

The shape of a quantum algorithm

Most introductory quantum algorithms follow one pattern:

1. Prepare a simple initial state.
2. Create superposition over candidate inputs.
3. Query an oracle or simulate a structured operation.
4. Use interference to push amplitude toward useful outcomes.
5. Measure.
6. Interpret the result classically.

The circuit is only half the story. The other half is the promise: what you are allowed to assume about the problem. Algorithms that look identical on paper diverge completely once you ask what the oracle costs to build.

Queries are not runtimes

Many textbook results are stated in query complexity — how many times the algorithm calls a black-box oracle. That is a clean way to prove separation between models. It is not the same as time on hardware.

End-to-end runtime also includes:

• state preparation
• oracle construction
• compilation to a native gate set
• circuit depth against coherence time
• error correction overhead
• measurement shots and repetitions
• classical pre- and post-processing
• data loading
• verification of the answer

The rule for builders and investors: a query speedup is not a product until the full workflow beats the best classical alternative. Part V's resource-estimation chapters exist to put numbers on every line of this list.

Phase kickback: the trick underneath

Phase kickback is the first idea that makes quantum algorithms feel genuinely different from classical ones. An oracle computes $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$ — it writes the function value into a target qubit. Prepare that target in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ and something subtle happens:

The target comes out unchanged, and the function value lands in the phase of the input register instead. The information you asked for has been kicked back into a sign — and a sign can interfere, which a classical bit sitting in a register never does. Nearly every algorithm in this guide is phase kickback plus a clever way to read the sign.

Worked example: Bernstein-Vazirani on two bits

The problem: $f_s(x)=s\cdot x\mathrm{mod}2$, where $s$ is a hidden two-bit string and $f_s(x)=s_1{x}_1\oplus s_2{x}_2$. Classically, with black-box access, you need two queries to learn both bits. Quantumly, one suffices:

1. Start with $|00⟩|1⟩$ — two input qubits and a target in $|1⟩$.
2. Apply Hadamard to all three qubits, producing $\frac{1}{2}{\sum }_x|x⟩$ over 00, 01, 10, 11, with the target in $|-⟩$.
3. Apply the oracle. Phase kickback yields $\frac{1}{2}{\sum }_x(-1{)}^{s\cdot x}|x⟩$, with the target still in $|-⟩$.
4. Apply Hadamard to the two input qubits. They decode the phase pattern, concentrating all amplitude on $|s⟩$.
5. Measure and read out $s$.

Why it works: the oracle writes function values into phase, the final Hadamards decode that phase pattern, and the promise — linear structure over bits — is what makes the decoding exact. Change the promise and the algorithm has nothing to grab.

Grover: a quadratic you can trust

Grover's algorithm searches an unstructured space of $N$ items with $M$ marked ones using about $O(\sqrt{N/M})$ oracle queries, against $O(N/M)$ for the best classical worst case. It is one of the most robust results in the field — and it is quadratic, not exponential. It also assumes an oracle that recognizes a marked item efficiently, and building that oracle is often where practical advantage goes to die.

Worked example: Grover on four items

Take $N=4$ on two qubits. Apply $H\otimes H$ to $|00⟩$:

Suppose the marked item is $|11⟩$. The oracle flips its sign:

Now the diffusion operator inverts every amplitude about the mean. The amplitudes are $\frac{1}{2},\frac{1}{2},\frac{1}{2},-\frac{1}{2}$, so the mean is $\frac{1}{4}$, and each amplitude maps to $2\cdot \mathrm{mean}-\mathrm{old}$:

All amplitude lands on $|11⟩$: one Grover iteration solves the four-item case exactly. Notice the two moves — mark with phase, then amplify. Every amplitude-amplification argument in the field is a variation on those two moves.

The quantum Fourier transform

The QFT is the discrete Fourier transform applied to amplitudes rather than to a classical data vector. Its importance is not that it "does Fourier faster" — you cannot read out the coefficients. Its importance is that it exposes periodic structure encoded in a quantum state, converting hidden periodicity into measurable peaks.

It sits at the center of phase estimation, period finding, Shor's factoring algorithm, and the hidden-subgroup family. When a quantum algorithm seems to pull structure out of nowhere, the QFT is usually the mechanism doing the pulling.

Phase estimation

Given a unitary with $U|u⟩=e^{2\pi i\varphi }|u⟩$, phase estimation extracts the eigenphase $\varphi$ as classical bits. It converts phase — the thing measurement normally hides — into output you can keep.

It is a foundation of Shor's algorithm and of most fault-tolerant simulation methods. The caveat is cost: useful phase estimation typically needs deep, coherent circuits, which pushes it firmly toward fault-tolerant hardware rather than today's devices.

Shor is period finding

Shor's algorithm (1994) factors an integer by reducing factoring to finding a period:

1. Choose an integer $a$ with $1<a<N$.
2. Consider the periodic function $f(x)=a^x\mathrm{mod}N$.
3. Use quantum period finding — phase estimation plus the QFT — to estimate the period $r$.
4. Use classical number theory to recover factors from $r$ when conditions are favorable.

The quantum part never tries factors. It extracts periodic structure that no known classical algorithm can extract efficiently. The strategic consequences are real: a large fault-tolerant quantum computer running Shor breaks RSA and elliptic-curve cryptography, which is why post-quantum cryptography migration is already prudent — while the hardware to threaten production keys remains far beyond current general-purpose systems. Both halves of that sentence deserve equal emphasis.

Hamiltonian simulation: the natural application

Hamiltonian simulation asks how a quantum system evolves over time — and since nature is quantum, this is the most native workload a quantum computer can have. The application areas are chemistry, materials, catalysis, superconductivity, magnetic systems, and energy-related materials.

The serious questions are concrete: which Hamiltonian, at what precision, in what encoding, needing how many logical qubits and how many reliable operations — and what classical approximation method is the baseline? That last question is the one most often skipped, because classical simulation methods are formidable competitors.

Variational algorithms: near-term, unproven

Variational algorithms pair a parameterized quantum circuit with a classical optimizer: choose parameters, run the circuit, measure an objective, update, repeat. VQE targets chemistry-style objectives, QAOA targets optimization-style ones, and quantum machine-learning circuits follow the same loop.

The appeal is real: these algorithms tolerate shallow circuits, which makes them the friendliest option for noisy near-term hardware, and they slot naturally into hybrid workflows. The caution is equally real:

• The optimization surface can be hard to train — barren plateaus flatten gradients.
• Noise can dominate the measured objective.
• Classical heuristics are strong and constantly improving.
• Data loading can erase any advantage.
• A good demo does not automatically become product value.

Part IV and Part VIII return to these algorithms with the benchmark discipline they require.

The algorithm evidence checklist

For any algorithm claim, nine questions:

• What is the exact problem statement?
• What promise or structure does it exploit?
• What is the quantum subroutine?
• What is the classical baseline?
• Is the speedup in query complexity or in full runtime?
• What data must be loaded, and at what cost?
• How is the answer verified?
• What hardware assumptions are required?
• How many logical qubits and reliable operations does it need?

A claim that answers all nine is rare — and instantly more credible than a headline.

Misconceptions worth unlearning

"Quantum algorithms speed up everything." Known speedups are problem-specific and structure-specific. For most tasks, the best known algorithm is classical by a wide margin.

"Grover makes brute force easy." Grover gives a quadratic speedup. Searching a space of a trillion items still takes a million steps, and the oracle has to be built and paid for.

"Shor is a near-term application." Cryptographically relevant factoring requires large fault-tolerant systems. The near-term action is cryptographic migration, not panic.

"Quantum ML will automatically beat classical ML." Not without addressing classical baselines, data loading, trainability, and noise — four problems that have ended many papers' practical ambitions.

What this buys you in diligence

A quantum algorithm company must show:

• a problem with clear economic value,
• a plausible quantum advantage mechanism,
• resource estimates, not just asymptotics,
• a credible hardware timeline those estimates depend on,
• integration with existing classical workflows,
• defensible IP or workflow position,
• a non-quantum revenue path if hardware arrives late.

Algorithmic insight is necessary for such a company. It has never been sufficient.

Exercises

1. Explain phase kickback in your own words, without the word "spooky".
2. Derive the Bernstein-Vazirani result for $s=10$.
3. Redo the four-item Grover calculation with marked item $|01⟩$.
4. Explain why Grover is quadratic rather than exponential, in one paragraph.
5. Explain Shor's algorithm as period finding to a colleague who knows RSA but no quantum mechanics.
6. Pick one application paper and identify whether it relies on phase estimation, Hamiltonian simulation, variational circuits, or another primitive.
7. Write a one-page diligence note on a claimed quantum optimization application, using the nine-question checklist.

Check your understanding

You have this guide when you can, without notes:

• identify the structure an algorithm exploits,
• separate query complexity from end-to-end runtime,
• explain phase kickback,
• compute a small Grover example by hand,
• describe why Shor threatens public-key cryptography without being a near-term event,
• evaluate an application claim against a classical baseline.