Quantum Algorithms: Anatomy and the Classical-to-Quantum Pipeline

This document collects the structural facts about quantum algorithms: how a classical problem turns into a quantum circuit, where the problem-specific work actually lives, what the generic "wrapper" routines do, and how the major algorithm families differ in their use (or avoidance) of the oracle model. It is intended as a companion to:

• misc/deutsch-jozsa.md — a worked example in the query / oracle model,
• misc/quantum-complexity-theory.md — the complexity classes ($\mathsf{BQP}$, $\mathsf{QMA}$, …) and cost models,
• math/complexity-theory.md — classical complexity background.

For broader quantum-computing background and runnable code see the qcfront project.

1. The Two Things You Have to Build

For an oracle-style quantum algorithm (Deutsch–Jozsa, Bernstein–Vazirani, Simon, Grover, Shor's period-finding, phase estimation against a unitary, …), the input has two distinct pieces:

1. A classical specification of the problem — typically a Boolean function $f:\{0,1{\}}^n\to \{0,1{\}}^m$, given as a classical program, circuit, or mathematical description.

   Algorithm	Classical specification
   Deutsch–Jozsa	$f:\{0,1{\}}^n\to \{0,1\}$, promised constant or balanced
   Bernstein–Vazirani	$f(x)=s\cdot x\mathrm{mod}2$ for hidden $s$
   Simon	$f(x)=f(x\oplus s)$ for hidden period $s$
   Grover for SAT	$f(x)=1$ iff assignment $x$ satisfies $\phi$
   Grover for unstructured search	$f(x)=1$ iff $x$ is a marked element
   Shor (factoring)	$f_a(x)=a^x\mathrm{mod}N$ for fixed $a,N$
   Phase estimation	a unitary $U$ given via implementations of $U,U^2,U^4,\dots$

2. A quantum implementation of the oracle unitary $$\boxed{U_f:|x⟩|y⟩⟼|x⟩|y\oplus f(x)⟩}$$ (or, for Shor, $U_{f_a}:|x⟩|y⟩\mapsto |x⟩|y\oplus a^x\mathrm{mod}N⟩$, etc.). This is what the algorithm actually queries.

The algorithm proper — Hadamards, Grover diffusion, inverse QFT, amplitude amplification — is generic and oracle-blind. Essentially all problem-specific engineering lives in building $U_f$.

This separation is exactly the quantum analogue of using a classical decision-tree algorithm with a comparison oracle: the algorithm doesn't know what the elements are, only how to query them.

2. The Classical-to-Quantum Compilation Pipeline

The canonical recipe for turning a classical program / circuit for $f$ into a quantum oracle unitary $U_f$:

classical algorithm for f
   │
   │   (Step A: Bennett / Toffoli compilation)
   ▼
reversible classical circuit on (x, anc, y)
   │
   │   (Step B: promote Toffoli/CNOT to quantum gates)
   ▼
quantum unitary on basis states
   │
   │   (Step C: uncompute the ancilla)
   ▼
oracle unitary U_f, clean on (x, y) with anc returned to |0⟩

2.1 Step A — Classical reversible circuit

A reversible circuit uses only gates whose truth tables are permutations: NOT, CNOT (controlled-NOT), Toffoli = $\mathrm{CCNOT}$ (controlled-controlled-NOT). Toffoli alone is universal for classical reversible computation: any irreversible Boolean function $f$ can be embedded as a reversible map

$$\tilde{f}:(x,a,y)⟼(x,g(x,a),y\oplus f(x)),$$

where $a$ is an ancilla register that holds the intermediate scratch values of the underlying classical computation.

The cost of going from an irreversible circuit to a reversible one is given by Bennett's theorem (1973):

• Naive time-only conversion: $O(s)$ gates and $O(s)$ ancilla bits, where $s$ is the size of the original irreversible circuit.
• Time-space tradeoffs: $O(s^{1+\epsilon })$ time using $O(s^{1-\epsilon }\log s)$ space (Bennett 1989), via pebbling games on the computation DAG.

In practice tooling (e.g. open-source frameworks for quantum gate-level synthesis) does this compilation automatically.

2.2 Step B — Lift to quantum gates

A reversible classical gate is a unitary on the corresponding computational basis: $\mathrm{CNOT}$, $\mathrm{Toffoli}$ are unitary matrices acting on $({\mathbb{C}}^2{)}^{\otimes k}$ that happen to permute basis vectors. Promoting the reversible circuit to a quantum circuit therefore changes nothing about the action on basis states — it just additionally extends, by linearity, to superpositions:

$$\tilde{f}(\sum _x{\alpha }_x|x⟩)|0{⟩}^{\text{anc}}|0{⟩}^{\text{out}}=\sum _x{\alpha }_x|x⟩|g(x,0)⟩|f(x)⟩.$$

This is quantum parallelism: one application of $\tilde{f}$ evaluates $f$ on every $x$ in the input superposition, but the answers are tangled with the inputs and ancillas.

2.3 Step C — Uncomputation

The ancilla register $g(x,0)$ now depends on $x$ — the input and the scratch are entangled. If this entanglement is left in place, subsequent steps (Hadamards in Deutsch–Jozsa, the diffusion operator in Grover, inverse QFT in Shor) will not interfere correctly, because the "other half" of the state (the ancilla) carries which-path information that destroys the needed superposition.

The fix is Bennett uncomputation:

1. Run $\tilde{f}$ forward, producing $|x⟩|g(x,0)⟩|f(x)⟩$.
2. Use a CNOT chain to copy $f(x)$ onto a fresh answer register $|y⟩$, producing $|x⟩|g(x,0)⟩|f(x)⟩|y\oplus f(x)⟩$.
3. Run ${\tilde{f}}^{-1}$ backward (i.e. the reversible circuit in reverse), resetting the ancilla to $|0⟩$ and the intermediate output register to $|0⟩$.

Final state: $|x⟩|0{⟩}^{\text{anc}}|0{⟩}^{\text{out}}|y\oplus f(x)⟩$. Drop the (now-disentangled) ancilla and output registers, and you have the clean oracle

$$U_f:|x⟩|y⟩⟼|x⟩|y\oplus f(x)⟩.$$

Uncomputation roughly doubles the gate count and is what makes the ancillas reusable across queries. The pattern "compute → copy → uncompute" is ubiquitous in quantum algorithm design.

2.4 Cost summary

If the classical irreversible circuit for $f$ has size $s_C$, the quantum oracle $U_f$ costs:

• $O(s_C)$ Toffoli/CNOT gates (with the same $O(s_C)$ ancillas, after Bennett),
• doubled by uncomputation,
• multiplied by a polylogarithmic factor if the universal gate set does not include Toffoli natively (Solovay–Kitaev, see misc/quantum-complexity-theory.md § 2.3).

End-to-end: the quantum circuit for the oracle is, up to constants and a $\mathrm{polylog}$ overhead, the same size as the classical circuit for $f$. Quantum speedup comes from the outer wrapper — the number of oracle calls — not from the cost-per-call.

3. Worked Examples of the Pipeline

3.1 Grover for SAT

Problem: given a 3-CNF formula $\phi$ on $n$ variables and $m$ clauses, find a satisfying assignment (or decide that none exists).

1. Classical predicate: $f(x)=1$ iff $x\in \{0,1{\}}^n$ satisfies $\phi$. As a classical circuit:
   • For each clause ${\ell }_1\vee {\ell }_2\vee {\ell }_3$, write a tiny sub-circuit computing the clause value into a clause-output bit.
   • AND together all $m$ clause-output bits into the final answer.
   • Size $O(m)$ gates, $O(m)$ scratch bits.
2. Reversible compile: each clause becomes 1–3 Toffolis (using De Morgan to express OR as $\neg (\neg {\ell }_1\wedge \neg {\ell }_2\wedge \neg {\ell }_3)$ and writing to an ancilla). The big $m$-input AND becomes a balanced tree of Toffolis with intermediate ancillas. Total: $O(m)$ Toffolis on $O(m)$ ancillas.
3. Quantum oracle: promote to quantum gates, apply uncomputation. Result: $U_{\phi }$ implementable with $O(m)$ Toffolis + CNOTs + $O(m)$ ancillas, all of which return to $|0⟩$ after each oracle call.
4. Plug into Grover. The Grover iteration is $O(\sqrt{2^n})$ applications of (oracle + diffusion operator), each using one $U_{\phi }$ call and $O(n)$ extra gates.

Total gate count: $\tilde{O}(\sqrt{2^n}\cdot m)$. The structure of $\phi$ shows up only inside $U_{\phi }$; the Grover wrapper is generic and oracle-blind. This is the famous Grover quadratic speedup over classical brute-force SAT.

The matching lower bound — Grover cannot be improved generically — is BBBV (Bennett–Bernstein–Brassard–Vazirani 1997): any quantum algorithm for unstructured search on $N$ items needs $\Omega (\sqrt{N})$ queries. So if SAT has a sub-exponential quantum algorithm, it must exploit the structure of the formula — opening the black box, not querying it.

3.2 Shor's algorithm — modular exponentiation

Problem: factor an $n$-bit integer $N$.

The quantum heart of Shor is period-finding for the function $f_a(x)=a^x\mathrm{mod}N$, where $a$ is a random integer coprime to $N$. The period $r$ of $f_a$ (smallest $r>0$ with $a^r\equiv 1(\mathrm{mod}N)$) leaks the factorization of $N$ via $\gcd (a^{r/2}\pm 1,N)$.

1. Classical algorithm for $f_a$: square-and-multiply modular exponentiation — $O(\log x)$ modular multiplications of $\log N$-bit numbers. Total classical circuit size $O(n^3)$ with schoolbook multiplication, or $\tilde{O}(n^2)$ with fast algorithms.
2. Reversible compile: modular addition, multiplication, and exponentiation each have textbook reversible constructions; Beauregard (2002) and Häner–Roetteler–Svore (2017) give $O(n^3)$ Toffoli circuits using $2n+O(\log n)$ qubits. This is the workhorse of practical Shor implementations.
3. Quantum oracle $U_{f_a}$: $\tilde{O}(n^3)$ gates total after uncomputation.
4. Plug into period-finding:
   • Prepare ${\sum }_x|x⟩|0⟩$ via Hadamards on the input register.
   • Apply $U_{f_a}$ once: ${\sum }_x|x⟩|f_a(x)⟩$.
   • Apply inverse QFT to the input register.
   • Measure and post-process the result (continued fractions) classically to extract $r$.

The QFT and the period-finding wrapper are short, generic, and entirely independent of the specific number being factored. All Shor-specific engineering is in step 2. A large fraction of physical-qubit budgets and fault-tolerant overhead estimates for factoring 2048-bit RSA reduces to "how big is the modular exponentiation circuit?".

3.3 Simon's algorithm

Problem: given $f:\{0,1{\}}^n\to \{0,1{\}}^n$ promised to satisfy $f(x)=f(y)⟺y=x\oplus s$ for some hidden $s\in \{0,1{\}}^n\setminus \{0\}$, find $s$.

1. Classical specification: $f$ is supplied as an oracle or as a classical circuit.
2. Reversible compile + lift to quantum: standard. $U_f$ uses $O(\text{circuit size of }f)$ Toffolis.
3. Plug into Simon:
   • Prepare ${\sum }_x|x⟩|0⟩$.
   • Apply $U_f$: ${\sum }_x|x⟩|f(x)⟩$.
   • Hadamard the input register and measure: yields a uniformly random $y\in \{0,1{\}}^n$ orthogonal to $s$ ($y\cdot s=0\mathrm{mod}2$).
   • Repeat $O(n)$ times to collect $n-1$ linearly independent constraints; solve a linear system over ${\mathbb{F}}_2$ classically to recover $s$.

The classical post-processing here is non-trivial (Gaussian elimination over ${\mathbb{F}}_2$) but polynomial. The quantum oracle is again the only problem-specific quantum work.

4. Generic Compilation: Any Classical Function as a Quantum Oracle

The pipeline of § 2 was illustrated on hand-crafted examples (SAT, modular exponentiation, Simon's promise). It is in fact fully generic and automatable: any classical function $f:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ computable by a Turing machine can be compiled into a quantum oracle $U_f$ by a mechanical procedure, with no "quantum compilation gap" in the same sense there is between classical TMs and assembly. This subsection states the theorem and lists the four important caveats.

4.1 The cost-preservation theorem

Combining the steps of § 2 with the standard classical results below gives:

Theorem (folklore, "no-overhead theorem for classical-to-quantum compilation"). A classical Turing machine running in time $T(n)$ and space $S(n)$ admits a quantum oracle unitary $$U_f:|x⟩|y⟩|0{⟩}^{\text{anc}}⟼|x⟩|y\oplus f(x)⟩|0{⟩}^{\text{anc}}$$ implementable by a circuit of size $O(T(n))$ on $O(S(n)+T(n))$ qubits, over any fixed universal gate set; the circuit is itself computable from the TM description in classical polynomial time.

The two classical-side inputs:

• Pippenger–Fischer (1979). Any TM running in time $T(n)$ is simulable by a Boolean circuit family of size $O(T(n)\log T(n))$, uniformly constructible.
• Bennett reversibilization (1973, 1989). Any irreversible Boolean circuit of size $s$ has a reversible Toffoli/CNOT implementation, with several time–space tradeoffs:

The pebbling tradeoff is essentially tight: there exist explicit functions that cannot be reversibly computed in $O(s)$ time and $o(s)$ space.

This is why $\mathsf{P}\subseteq \mathsf{BQP}$ is trivial: every polynomial-time classical computation lifts to a polynomial-size quantum circuit by this pipeline. The same lift, with extra space-management bookkeeping, underlies $\mathsf{L}\subseteq \mathsf{BQP}$ and the $\mathsf{BQP}\subseteq \mathsf{PSPACE}$ upper bound from misc/quantum-complexity-theory.md § 3.2.

4.2 The four caveats

Genericity is real but not free. Four sharp points worth internalizing:

Ancilla blow-up vs. depth

Naive Bennett reversibilization uses $\Theta (s)$ ancillas — one per non-trivial intermediate value. For modular exponentiation in Shor on a 2048-bit RSA modulus the underlying classical computation has $T\gtrsim 10^{10}$ logical steps; the naive circuit would need $\gtrsim 10^{10}$ ancilla qubits, well beyond any conceivable hardware. The pebbling tradeoff is what makes the problem tractable: trade $T\leftrightarrow S$ to land near the space-optimal end of the curve.

Practical Shor implementations (Beauregard 2002; Häner–Roetteler–Svore 2017) use $2n+O(\log n)$ qubits with $O(n^3)$ gates — the qubit count is dominated by modular-arithmetic ancillas, not by the $n$ bits of the number being factored. This is the dominant cost driver in fault-tolerant resource estimates.

No quantum advantage from compilation alone

Compiling a classical algorithm to a quantum circuit gives you a circuit of the same asymptotic size. There is no automatic speedup. If you have a polynomial-time classical solver for $f$, the lifted quantum circuit is also polynomial — still polynomial, no better, no worse.

Quantum advantage comes from a wrapper (Grover, Shor's QFT, phase estimation, amplitude estimation) that calls the compiled oracle $U_f$ a small number of times. The compilation pipeline produces the oracle; the wrapper produces the speedup. Conflating these is a common source of bogus "polynomial-time quantum SAT" claims.

Input encoding is non-trivial

The pipeline assumes inputs are classical bit strings already in the data register. Some algorithms expect inputs of a different type:

• HHL (linear systems $A\vec{x}=\vec{b}$): expects $|\vec{b}⟩={\sum }_i{b}_i|i⟩$, a quantum state encoding the $2^n$-entry vector $\vec{b}$. Loading this requires either a QRAM (quantum random-access memory; Giovannetti–Lloyd–Maccone 2008) — itself a non-trivial hardware primitive — or a structured $\vec{b}$ admitting an efficient state-preparation circuit.
• Quantum machine learning kernels: input “data” are likewise expected as amplitude-encoded states, with all the same access-model caveats (Aaronson 2015, “Read the fine print”).

When comparing “exponential speedup” claims to classical baselines, the access model matters: an exponential algorithmic gain can hide an exponential cost in state preparation or readout, leaving no net advantage end-to-end.

Continuous / real-number functions

The pipeline is for $f:\{0,1{\}}^n\to \{0,1{\}}^m$. Real-valued computations (numerical analysis, optimization, ML) first need quantization: fix a $b$-bit fixed-point or floating-point format, then compile the integer / bit-level arithmetic reversibly. Precision $\epsilon$ on a real-valued output costs $O(\log (1/\epsilon ))$ bits per number, multiplied through the circuit. There is no "native" quantum real-number arithmetic.

4.3 Tools that implement the pipeline

Modern quantum-programming frameworks ship the entire pipeline as an end-to-end compile step, including automatic uncomputation and gate-set translation:

The state of the art on the synthesis side is silq (Bichsel–Baader–Gehr–Vechev 2020): the first language whose type system automatically inserts the compute–copy–uncompute pattern, so the programmer writes $f$ once as if it were ordinary classical code.

4.4 Summary table

5. Beyond the Generic Pipeline: Oracle, Wrapper, and Compiler Optimizations

The generic compilation of § 4 is the -O0 baseline: it works for everything but is wildly suboptimal for almost any specific problem. Real quantum algorithm design improves on it at three orthogonal levels — oracle, wrapper, and compiler — with cumulative gains of $10^2$–$10^3\times$ in qubit and gate budgets for problems like Shor and Grover-on-SAT.

This section traces the SAT example of § 3.1 through all three layers.

5.1 Oracle-level optimizations

Even within the "build a reversible circuit for $f$" framing, the generic pipeline is far from tight.

Phase oracle vs. bit oracle

Many Grover-style algorithms only need the phase oracle

$$O_{\phi }:|x⟩⟼(-1{)}^{\phi (x)}|x⟩$$

rather than the bit oracle $U_{\phi }:|x⟩|y⟩\mapsto |x⟩|y\oplus \phi (x)⟩$. A single multi-controlled-$Z$ at the end replaces the final AND-tree + CNOT-onto-$y$ + uncomputation, roughly halving the gate count for SAT-style oracles.

Custom Boolean-function synthesis

For a 3-CNF formula $\phi$ with $m$ clauses on $n$ variables, instead of a naive clause-by-clause Toffoli tree:

• ESOP (Exclusive-Sum-of-Products) synthesis exploits algebraic identities to merge clauses — the same tricks used in classical reversible-logic design (RevKit, Tweedledum).
• AND-of-OR decomposition with shared sub-clauses: if two clauses share literals, the corresponding Toffolis share sub-computations. Common-subexpression elimination cuts both gate and ancilla count.

Toffoli decomposition tricks

The textbook Nielsen–Chuang decomposition of one Toffoli into Clifford+T uses 7 $T$ gates. Better:

• Measurement-assisted Toffoli (Jones 2013): 4 $T$ gates + 1 ancilla + 1 measurement, using deferred measurement and adaptive Clifford correction.
• Multi-controlled Toffolis (${\mathrm{C}}^n\mathrm{NOT}$): naive nesting gives $O(n)$ Toffolis; Barenco et al. (1995) achieves $O(n)$ Toffolis using $O(\log n)$ "dirty" ancillas (ancillas not in $|0⟩$).
• Relative-phase Toffolis (Maslov 2016): if the Toffoli is going to be uncomputed later, implement it with just 3 $T$ gates by allowing a phase error that the uncomputation cancels. This roughly halves the $T$-count of any compute–copy–uncompute pattern.

$T$-count is the dominant fault-tolerant cost driver because the $T$ gate requires expensive magic-state distillation; halving $T$-count halves the physical-qubit-second budget.

Ancilla recycling and hand-tuned pebbling

The generic Bennett pipeline uses naive $O(s)$ ancillas (§ 4.1). For specific functions, hand-crafted pebbling strategies are dramatically tighter:

• Modular exponentiation for Shor: Beauregard's $2n+3$ qubits versus the naive $O(n^3)$ ancillas — three orders of magnitude reduction.
• Karatsuba / Toom–Cook multiplication, quantized: Gidney (2019) gives reversible Karatsuba in $O(n^{{\log }_{2}3})$ Toffolis using only $O(n)$ ancillas, versus $O(n^2)$ schoolbook.
• In-place arithmetic: addition and multiplication can be done in place (output overwrites input), saving an entire register.

5.2 Wrapper-level: smarter than Grover for structured problems

For SAT specifically, several quantum algorithms beat Grover's $O(\sqrt{2^n})$ by exploiting structure that the black-box wrapper can't see.

Quantum backtracking (Montanaro 2018)

Classical SAT solvers (DPLL, CDCL) use backtracking with unit propagation, conflict-driven clause learning, etc. Montanaro showed:

A classical backtracking algorithm exploring $T$ nodes of a search tree can be quantumly simulated in $\tilde{O}(\sqrt{T\cdot n})$ time using a quantum walk on the tree.

For 3-SAT this becomes roughly $O(1.153^n)$ versus the classical $O(1.308^n)$ (Schöning) — a non-trivial improvement in the exponent on top of the generic ​ speedup. The key: the wrapper inspects the recursion-tree structure, not just an opaque oracle.

Schöning-style amplitude amplification (Ambainis 2004)

Classical Schöning solves $k$-SAT in $O((2-2/k{)}^n)$ randomized time. Ambainis lifts this to quantum:

$$O((2-2/k{)}^{n/2})\text{for }k\text{-SAT}.$$

For 3-SAT: $O(1.155^n)$ instead of $O(1.334^n)$ classical. The gain over generic Grover-on-Schöning composition comes from careful interference between the random-walk and amplification steps.

Quantum walks on structured graphs

The constraint graph or implication graph of a SAT instance has structure that MNRS quantum walks (Magniez–Nayak–Roland–Santha 2011) can exploit. For element distinctness and triangle finding, walk-based algorithms beat Grover by polynomial factors; for SAT-specific walks the savings are problem-dependent.

QAOA / variational approaches for MAX-SAT

For MAX-SAT and other optimization variants, QAOA with $p$ layers (see § 6.3) gives a Hamiltonian whose low-energy states encode good approximate answers. For $p=1$ on MAX-CUT, QAOA achieves a $0.6924$ approximation ratio (Farhi–Goldstone–Gutmann 2014). The "circuit" is not a reversible compilation of a classical algorithm — it's a problem-Hamiltonian encoding $H_C$ alternated with a mixer, parameters tuned classically. Entirely different architecture from oracle + wrapper.

5.3 Compiler-level optimizations

Even after fixing the algorithm and the oracle decomposition, the gate-level circuit admits one more pass of optimization.

$T$-count and $T$-depth minimization

The dominant fault-tolerant cost metric. State-of-the-art tools:

• feynman (Amy 2018): polynomial-time $T$-count optimization for Clifford+T circuits via phase-polynomial analysis. Typically cuts $T$-count by 30–70% on textbook circuits.
• pyzx (Kissinger–van de Wetering 2020): ZX-calculus-based rewriting; often finds even tighter $T$-counts.
• Catalytic computations: reuse leftover ancilla state to avoid redundant $T$ gates entirely.

Gidney–Ekerå (2021) applied this whole optimization stack to RSA-2048 factoring with Shor's algorithm and concluded $\sim 20$ million physical qubits and $\sim 8$ hours on a surface-code fault-tolerant architecture — compared to early-2010s estimates of $\gtrsim 10^9$ physical qubits. Three orders of magnitude of cumulative oracle + compiler optimization on a single algorithm.

Qubit routing and SWAP minimization

Real hardware (heavy-hex on IBM, square grid on Google) does not have all-to-all connectivity, so 2-qubit gates between non-adjacent qubits require SWAP chains. SWAP routing is NP-hard in general, but heuristics (Qiskit's SABRE, tket's routing pass) typically come within 2–3$\times$ of optimal. Hand-crafted layouts for specific algorithms (QFT in a 1D chain, Shor's modular exponentiation on a grid) can save another factor of 2–5.

Pulse-level and gate-cancellation optimization

Below the gate level: $T\cdot T=S$, $H\cdot H=1$, CNOT-chains commute past single-qubit gates with phase corrections — all exploited by Qiskit / tket transpilers. Pulse-level compilation (collapse a gate sequence into a single optimal-control pulse) gives another 10–30% on real hardware.

5.4 End-to-end speedup over the generic baseline

For SAT specifically, the cumulative gap between the generic pipeline and the best-known hand-crafted quantum solver:

The biggest single lever is choosing the right wrapper for the problem structure. Grover over a generic SAT oracle is a poor fit; quantum backtracking over a structured DPLL recursion is a much better one. Compiler-level optimization buys factors of 2–10; oracle-level synthesis buys another 2–10; but moving from black-box search to structure-exploiting walks/backtracking changes the exponent, which dominates everything else at scale.

Rule of thumb. For a known problem, never deploy the generic pipeline naively. Treat it as the upper bound, then look for: (i) a phase-oracle reformulation, (ii) an algorithm-specific wrapper that opens the black box, (iii) hand-crafted ancilla management for any classical sub-algorithm, and (iv) a $T$-count optimizer on the final circuit.

6. The Generic "Wrappers"

Across most oracle algorithms the same handful of subroutines appear as the outer wrapper. Knowing these by name is most of what's needed to read modern quantum-algorithms papers.

Algorithm design at the wrapper level reduces to picking which of these to combine, against an oracle that you are responsible for engineering. The strongest oracle-model quantum speedups so far — Simon, Shor, phase estimation — come from the QFT-based wrappers; Grover-flavored algorithms give at most quadratic gains.

7. Non-Oracle Algorithms

Not every quantum algorithm fits the "classical predicate + oracle + wrapper" mold. The major families that bypass it:

7.1 The QFT itself

The Quantum Fourier Transform is just a fixed unitary — no classical function as input, no oracle. It admits an $O(n^2)$-gate (or $O(n\log n)$-gate with approximation) circuit (Coppersmith 1994). It is the foundational primitive, not an algorithm parameterized by a problem.

7.2 Hamiltonian simulation

Given a Hamiltonian $H$ (typically supplied as a sum $H={\sum }_j{H}_j$ of local terms — not a Boolean function), produce a circuit implementing $e^{-iHt}$ on a quantum state. The input is physics data, not a classical predicate.

Approaches:

• Trotter–Suzuki (Lloyd 1996): $e^{-iHt}\approx ({\prod }_j{e}^{-i{H}_{j}t/r}{)}^r$ for large $r$. Easy to implement, polynomial overhead, dimension-dependent error.
• Qubitization / quantum signal processing (Low–Chuang 2017–19): optimal asymptotic $O(t+\log (1/\epsilon ))$ scaling.
• Linear combinations of unitaries (LCU) (Childs–Wiebe 2012): randomized compilation.

Hamiltonian simulation is what physicists actually want from a quantum computer, and the reason quantum supremacy is plausible — classical simulation of $e^{-iHt}$ takes time exponential in the system size.

7.3 Variational and hybrid algorithms

For NISQ-era hardware:

• VQE (variational quantum eigensolver, Peruzzo et al. 2014): parameterize a shallow circuit $|\psi (\theta )⟩$, classically minimize $⟨\psi (\theta )|H|\psi (\theta )⟩$ over $\theta$.
• QAOA (quantum approximate optimization algorithm, Farhi–Goldstone–Gutmann 2014): a layered ansatz alternating problem-Hamiltonian and mixer-Hamiltonian evolutions; classically tune the angles.

Here the "specification" is again a Hamiltonian (often encoding a classical combinatorial problem via, e.g., $H_C={\sum }_{\text{clauses}}(1-\text{clause-satisfied})$). The classical-to-quantum step is Hamiltonian encoding, not reversible-circuit compilation. There is no oracle and no Grover-style amplification.

7.4 Sampling algorithms

For supremacy-style tasks:

• Random Circuit Sampling (Google 2019): just apply a random sequence of two-qubit gates and sample the output distribution. No problem, no oracle, no answer to verify — only the distribution is the output.
• Boson Sampling (Aaronson–Arkhipov 2011): sample photon detection patterns at the output of a linear-optical interferometer. Hardness rests on $\#\mathsf{P}$-hardness of computing permanents.
• IQP (Bremner–Jozsa–Shepherd 2010): commuting-gate quantum circuits.

These exist to demonstrate quantum supremacy with the smallest possible quantum-circuit complexity, by giving up on solving a useful problem.

7.5 Adiabatic algorithms

Encode the answer as the ground state of a target Hamiltonian $H_1$; adiabatically interpolate from an easy $H_0$ to $H_1$ slowly enough that the spectral gap is preserved. No oracle, no circuit per se — the "program" is the choice of $H_0,H_1$ and the interpolation schedule. Polynomially equivalent to the circuit model.

8. Where the Quantum Advantage Actually Lives

A useful frame for evaluating any "speedup" claim:

• The size of the oracle / Hamiltonian circuit is comparable to the classical computation for $f$ — up to constants, ancilla doubling for uncomputation, and Solovay–Kitaev polylog factors. There is no quantum advantage per call.
• The number of calls can drop super-polynomially (Shor, Simon, phase estimation) or polynomially (Grover, amplitude amplification, walk-based algorithms). This is the speedup.
• For total Boolean functions (no promise) the speedup is at most polynomial: $R(f)=O(Q(f{)}^6)$ (Aaronson et al. 2021, see misc/quantum-complexity-theory.md § 4.3). Super-polynomial speedups require problem structure — a promise (Deutsch–Jozsa, Simon), algebraic structure (Shor's hidden-subgroup setting), or a continuous-input flavor (phase estimation).
• Constants matter for practice. Even Shor's $\tilde{O}(n^3)$ becomes $\gtrsim 10^9$ gates for 2048-bit RSA, and Grover's quadratic speedup over a classical SAT solver with billions of decisions per second is easily eaten by quantum gate times and error-correction overhead. The complexity-theoretic separation is the prerequisite for practical advantage, not the certificate of it.

The big-picture summary is:

What you do once classically — the oracle — you have to do reversibly and uncomputed on the quantum side. What you do many times classically — the search — can sometimes be replaced by a much smaller number of quantum calls. That replacement is the quantum advantage.

References

• C. Bennett, Logical reversibility of computation, IBM J. Res. Dev. 17, 525 (1973).
• C. Bennett, Time/space trade-offs for reversible computation, SIAM J. Comput. 18, 766 (1989).
• N. Pippenger and M. J. Fischer, Relations among complexity measures, J. ACM 26, 361 (1979) — TM-to-circuit simulation with $O(T\log T)$ overhead.
• K.-J. Lange, P. McKenzie, A. Tapp, Reversible space equals deterministic space, J. Comput. Syst. Sci. 60, 354 (2000) — near-space-optimal reversibilization.
• D. Beauregard, Circuit for Shor's algorithm using $2n+3$ qubits, Quant. Inf. Comput. 3, 175 (2003); arXiv:quant-ph/0205095.
• T. Häner, M. Roetteler, K. Svore, Factoring using $2n+2$ qubits with Toffoli based modular multiplication, Quant. Inf. Comput. 17, 673 (2017); arXiv:1611.07995.
• V. Giovannetti, S. Lloyd, L. Maccone, Quantum random access memory, Phys. Rev. Lett. 100, 160501 (2008) — QRAM definition and limits.
• S. Aaronson, Read the fine print, Nature Physics 11, 291 (2015) — HHL input/output-access caveats.
• B. Bichsel, M. Baader, T. Gehr, M. Vechev, Silq: A high-level quantum language with safe uncomputation and intuitive semantics, PLDI 2020 — type-checked automatic uncomputation.
• A. Barenco et al., Elementary gates for quantum computation, Phys. Rev. A 52, 3457 (1995) — multi-controlled gate decompositions and dirty-ancilla tricks.
• C. Jones, Low-overhead constructions for the fault-tolerant Toffoli gate, Phys. Rev. A 87, 022328 (2013) — measurement-assisted 4-$T$ Toffoli.
• D. Maslov, Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization, Phys. Rev. A 93, 022311 (2016) — 3-$T$ relative-phase Toffolis for compute-uncompute patterns.
• A. Montanaro, Quantum speedup of branch-and-bound algorithms, Phys. Rev. Research 2, 013056 (2020); Quantum-walk speedup of backtracking algorithms, Theory of Computing 14, 1 (2018).
• A. Ambainis, Quantum search algorithms, SIGACT News 35, 22 (2004) — quantum Schöning for $k$-SAT.
• F. Magniez, A. Nayak, J. Roland, M. Santha, Search via quantum walk, SIAM J. Comput. 40, 142 (2011) — MNRS quantum walks.
• M. Amy, Towards large-scale functional verification of universal quantum circuits, EPTCS 287 (2018) — the feynman $T$-count optimizer.
• A. Kissinger, J. van de Wetering, Reducing the number of non-Clifford gates in quantum circuits, Phys. Rev. A 102, 022406 (2020) — pyzx and ZX-calculus rewriting.
• C. Gidney, Asymptotically efficient quantum Karatsuba multiplication, arXiv:1904.07356 (2019).
• C. Gidney, M. Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, Quantum 5, 433 (2021) — end-to-end fault-tolerant Shor resource estimates.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge, 2010), §3.2.5 (reversible computation) and §6 (quantum search).
• A. Childs, Lecture Notes on Quantum Algorithms (https://www.cs.umd.edu/~amchilds/qa/) — the modern standard reference, with detailed coverage of Hamiltonian simulation, QSP/qubitization, and walk-based algorithms.