Quantum Algorithms and Programming

Most speedup statements are made in a query model: the algorithm may call a unitary oracle that marks or evaluates items at unit cost. Grover's O(√N) queries is a statement about calls, not about seconds. Building the oracle for a real database requires loading data into a quantum state, which costs at least as much as reading it classically unless the data already exists in quantum form.

This is why serious proposals state the oracle construction explicitly and account for its depth. When an oracle needs a QRAM-style structure, the resource estimate includes that structure's qubits and error budget. Any claim omitting oracle cost should be treated as incomplete rather than merely optimistic.

The QFT maps amplitudes according to ω = e^{2πi/N} and is implemented with Hadamards and controlled phase rotations followed by a bit-reversal swap layer. It is efficient because the transform is a product of two-qubit interactions, not because it stores exponentially many values usefully. Phase estimation applies a controlled unitary U^2^j, writes the eigenphase into evaluation qubits, and reads it out with the inverse QFT.

Precision depends on the number of evaluation qubits: m qubits give roughly m bits of phase, and the success probability concentrates near the true value with a distribution that must be accounted for in iterative variants. Phase estimation is the engine of Shor, of ground-state estimation and of many eigenvalue routines, so understanding its error behaviour is the single highest-value skill in algorithm work.

Amplitude amplification rotates the state in a two-dimensional subspace spanned by the marked and unmarked components. For M marked items among N, the optimal number of iterations is approximately (π/4)√(N/M), and over-rotating past that point reduces success probability. Grover is the special case where the oracle marks bitstrings; quantum counting estimates M by combining amplification with phase estimation.

Beyond search, amplitude estimation gives a quadratic improvement in samples for expectation values, which is the basis of claimed speedups in Monte Carlo pricing and risk. The honest framing: if a classical simulation needs a million samples, the quantum version may need about a thousand coherent evaluations — each of which, today, is far more expensive than a classical sample.

Shor reduces factoring to order finding, and order finding to phase estimation on the modular exponentiation unitary. The consequence is that RSA and finite-field Diffie-Hellman fall, because their security assumes factoring and discrete logarithms are hard. Elliptic-curve cryptography falls for the same reason with far smaller key sizes required by the attacker.

The algorithm needs a fault-tolerant machine with enough logical qubits and runtime to execute modular exponentiation at the target key size; published resource estimates put that far beyond current devices. Grover's effect on symmetric ciphers is different and weaker: it halves the effective security level, which is why AES-256 remains appropriate while AES-128 margins shrink.

Transpilation maps logical gates to a device basis and inserts SWAPs so that two-qubit gates act on connected pairs. The result can be several times deeper than the logical circuit. Choosing an initial layout that respects the interaction graph, and allowing the transpiler to optimise for depth or error rate, materially changes success probability.

Benchmarking requires a baseline and statistics. For search problems, compare against classical brute force at the same instance size; for optimisation, against CP-SAT or MILP; for sampling, against a classical simulator of the reduction. Report median and interquartile range across seeds, total wall-clock including queueing, and the fidelity of the executed circuits.

Quantum algorithms are usually presented as an oracle and a number of calls to it. In practice, defining the oracle is the entire engineering problem. A search problem must be expressed as a predicate on bitstrings; a phase-estimation problem must be expressed as a unitary whose eigenvalues encode the answer; a linear-algebra problem must be embedded so that the input is prepared efficiently. None of these steps are automatic, and each one can destroy the speedup before a single gate is compiled.

The preparation cost is the part most often omitted from comparisons. If loading your data into the quantum state requires a circuit whose depth grows with the problem size, then the advantage claimed for the algorithm may be consumed by the loading step — a limitation that applies to data-heavy problems including many machine-learning formulations. An honest resource estimate includes preparation, the algorithm, and the measurement repetitions needed to read an answer to the required precision.

Read the asymptotic claim and the constant factors together. Big-O notation hides polynomial overhead that is irrelevant at a million qubits and decisive at a few hundred. A quadratic speedup whose circuit requires thousands of logical qubits and error correction is not deployable today, even though the mathematics is correct. The engineering translation of an algorithm paper is a table of qubit counts, gate counts and repetitions at realistic problem sizes.

A resource estimate is a document with a defined problem instance, a circuit specification, and counts at three levels: logical operations, logical qubits including ancillae, and physical qubits after routing and error correction. Producing one forces every assumption into the open, which is why it is the most valuable artefact a junior quantum engineer can build. It is also the artefact most often missing from internal proposals.

Do the estimate at two problem sizes. A single point cannot distinguish a method that scales well from one that does not, and the difference between the two curves is the actual argument for or against the approach. Plot the estimate against the best classical method's measured cost on the same instances; the crossover, if any, is the finding.

Ancilla management is where estimates go wrong. Temporary qubits are needed for arithmetic, comparison and uncomputation, and naive counting omits them. Uncomputation — reversing a computation to return borrowed qubits cleanly — doubles work and is mandatory for coherent reuse. Estimates that skip it are typically optimistic by a factor that grows with the circuit's arithmetic depth.

A claim survives review when four things are true: the task is well defined, the classical baseline is the best available rather than a convenient one, the quantum resource estimate is complete, and the comparison is at matched precision. Most claims fail on the second or fourth. A classical baseline run without tuning, or at lower accuracy than the quantum result, makes a speedup appear that is an artefact of the comparison.

The second common failure is conflating runtime with wall-clock. Quantum algorithms often report gate counts or oracle calls as the cost, while the classical method is measured in seconds including I/O. Converting between the two requires assumptions about gate times and error-correction cycles that must be stated. Reviewer credibility depends on stating them rather than burying them.

The third failure is a demonstration that no classical method has been applied to yet. Historically, several celebrated quantum results were matched by classical algorithms within months. If your claim rests on a task chosen for its classical difficulty, that is a claim about the current state of classical research, not a durable statement about quantum machines.

An experiment log for quantum algorithms has more fields than most teams expect: problem instance, oracle specification, source circuit, transpiled circuit, backend calibration, shot count, seeds, post-processing steps and the classical baseline output. Storing these together is what makes a rerun meaningful and a peer review short. It also makes your own debugging tractable months later.

Structure the log around decisions rather than results. Record why the ancilla budget was set to that value, why that transpilation optimisation level was chosen, and what was rejected. Results without rationale are unreviewable, and the rationale is the part that dissolves on a team change.

Automate the boring parts. A notebook that emits the manifest as a side effect of running the experiment will be used; a manual template will be abandoned in week two. The measurable success criterion is simple: a colleague given only the log should be able to rerun the experiment and obtain the same counts within shot noise.

Build the QFT, invert it, and read a known phase from a controlled unitary.

Implement a three-qubit QFT, verify it on a Fourier basis state, then use phase estimation to recover a phase of π/4 and compare with the analytical distribution.

Measure success probability as a function of iterations and locate the optimum.

Construct a three-qubit Grover search for one and for two marked items, sweeping iterations from 0 to 4 and plotting measured success.

Compare query complexity with wall-clock reality.

Benchmark Grover for small N against a classical scan, including transpilation and queue time, and report the instance size at which classical still wins.

Context: Route search over a large candidate set.

Method: Grover-style search on an encoded subset, benchmarked against exhaustive classical search.

Findings and status: No advantage at reachable problem sizes because oracle construction dominated.

Transferable lesson: Oracle overhead, not iteration count, decides viability.

Context: Transpiled circuits far exceeded logical depth on real hardware.

Method: Layout-aware compilation and depth-optimised transpilation for the target coupling map.

Findings and status: Depth reduced substantially, with measurable fidelity improvement at unchanged logical circuit.

Transferable lesson: Compilation choices change outcomes as much as algorithm design.

Context: Published results were not reproducible across SDK versions.

Method: Version pinning, seeds, calibration snapshots and container images recorded with each experiment.

Findings and status: Reproduction rate improved from unreliable to routine.

Transferable lesson: Provenance is part of the algorithm, not documentation overhead.

Context: Learners could run circuits but could not debug failures.

Method: Prediction-before-execution exercises with analytical histograms required in every submission.

Findings and status: Debugging fluency improved markedly compared with run-only learners.

Transferable lesson: Hand computation is the fastest route to hardware intuition.

Context: The proposal quoted an asymptotic speedup in oracle calls but no estimate of qubits, repetitions or data-loading cost.

Method: Produced a resource estimate at two portfolio sizes including state preparation and readout repetitions, then compared against the firm's tuned classical solver on the same instances.

Findings and status: The crossover point was far beyond any plausible hardware horizon, so the team redirected effort to classical heuristics and a narrow research track.

Transferable lesson: A complete resource estimate is what turns an exciting paper into a defensible decision.

Context: The classical comparison used an untuned baseline at lower solution quality.

Method: Reran the comparison against a tuned solver at matched quality and equal time budget, and published both results.

Findings and status: The advantage disappeared, but the corrected methodology was adopted for subsequent internal claims.

Transferable lesson: Match precision and effort in the baseline, or the comparison measures the analyst, not the machine.

Work through these in order — each builds evidence the capstone requires. Record assumptions, code versions, shots or sample counts, and validation results; the reasoning is assessed, not only the answer.

A research team wants an independent assessment of an algorithmic claim before committing engineering effort.

Problem: Implement one algorithm from this course at a defensible scale, estimate its cost, and determine whether it beats the best classical method on the same instances.

Objectives: Produce a reproducible implementation with analytical validation, transpilation report, resource estimate and a classical baseline measured on identical instances.

Deliverables: Repository, notebook, resource estimate table, benchmark results with confidence intervals and a written verdict.

Assessment: Correctness 30%, resource analysis 25%, benchmark fairness 25%, written verdict 20%.