The Machinery of Cancellation: The Mathematics Behind the Interference Machine

Physics · Computing · Derivations

The Machinery of Cancellation

The mathematics the companion piece deliberately left out: four postulates, two algorithms, one theorem that caps them, and the arithmetic that turns an algorithm into a machine.

September 2026 · A companion piece to The Interference Machine

This is the technical companion. The Interference Machine: What Quantum Computing Actually Does made the argument in prose: superposition is not parallelism, the resource is interference, and interference only pays where a problem has exploitable structure. Several readers asked to see the actual mathematics. This piece is that. It repeats almost none of the argument and instead derives it — the postulates and what they forbid, Grover and Shor worked through rather than described, the theorem that caps unstructured search, and the resource arithmetic that separates a published algorithm from a machine that could run it. It assumes linear algebra and nothing else. Every claim in the parent piece that was asserted is proved here, or cited to where it is.

The rules, stated once

Quantum mechanics as a computational model is four postulates. Everything downstream — every algorithm, every impossibility — is a consequence of them, and it is worth having them written down in one place because most confusion in this subject is a postulate being quietly violated.

The four rules

1. States. The state of an isolated system is a unit vector in a complex Hilbert space. For n qubits that space is C²ⁿ, with basis |x> indexed by the 2ⁿ bit strings x.

2. Composition. Systems combine by tensor product, not Cartesian product. This is the whole of entanglement: dimensions multiply where classical descriptions would add.

3. Evolution. Closed-system dynamics is unitary: |ψ> → U|ψ> with U†U = I. Unitary means reversible and norm-preserving. There is no quantum operation that erases, copies, or discards.

4. Measurement. Measuring in the computational basis returns outcome x with probability |<x|ψ>|2 and leaves the state at |x>. This is the only non-unitary, non-reversible, information-destroying step in the theory, and it happens exactly once, at the end.

Two consequences are worth extracting immediately, because they bound everything that follows.

The readout ceiling

Postulate 4 says an n-qubit measurement yields n classical bits. Not a summary of the 2ⁿ amplitudes, not a function of them — one basis label, sampled. Holevo's theorem sharpens this into a hard bound: n qubits cannot transmit more than n classical bits of accessible information.[1] The exponential state space is real and it is not a channel. Every quantum algorithm is therefore a scheme for arranging that the single sample you are permitted is the one you wanted.

No-cloning, in four lines

Suppose some unitary U copied arbitrary states: U|ψ>|0> = |ψ>|ψ> for every |ψ>. Take two states and compare inner products before and after. Unitaries preserve inner products, so:

before: <ψ|φ> · <0|0> = <ψ|φ> after: <ψ|φ> · <ψ|φ> = <ψ|φ>² so <ψ|φ> = <ψ|φ>² ⇒ <ψ|φ> ∈ {0, 1}

Any two states a machine can copy are either identical or orthogonal. A universal copier is inconsistent with unitarity.[2] The practical consequence is that you cannot checkpoint a computation, cannot back up a state before measuring it, and cannot use the standard classical trick of running a probabilistic procedure once and keeping a copy. You can re-run the whole circuit, at full cost, which is why every algorithm below cares about its success probability per run.

Interference, formally

The Hadamard gate and its n-fold tensor power do the work in every algorithm here, and the reason is a single identity:

H|x> = (1/√2) Σ_y∈{0,1} (−1)^xy |y> H^⊗n|x> = 2^−n/2 Σ_y∈{0,1}ⁿ (−1)^x·y |y> (x·y = bitwise dot product mod 2)

H⊗n maps a basis state to a uniform superposition carrying a sign pattern determined by x. Since H2 = I, the map is its own inverse: apply it twice and the sign patterns fold back to a single basis state. Every algorithm in this piece is an instance of the same three-beat structure — spread with H⊗n, write information into signs, fold back with H⊗n — and they differ only in how the middle step manages to write.

Grover is a rotation. The oracle and the diffusion step are each reflections, and two reflections compose to a rotation by twice the angle between their axes — here 2θ per iteration, in the plane spanned by the solution and everything else.

Phase kickback

An oracle for a Boolean function f must be reversible, so it takes the standard form Uf|x>|y> = |x>|y ⊕ f(x)>: it XORs the answer into a target register. Prepare that target in |−> = (|0> − |1>)/√2 and note that X|−> = −|−> — the state is an eigenvector of the bit flip with eigenvalue −1. Then:

U_f |x>|−> = |x> · (|f(x)> − |1⊕f(x)>)/√2 = (−1)^f(x) |x>|−>

The target register factors out unchanged and unentangled; the function value survives only as a sign on the input register. This converts a bit oracle into a phase oracle |x> → (−1)f(x)|x> at the cost of one ancilla, and it is the reason the phase oracles used below are not an idealisation. The ancilla emerging unentangled is essential: had it retained a record of f(x), the input register would be in a mixed state and the interference below would be degraded rather than exact.

Bernstein–Vazirani, in one query

Hidden string s ∈ {0,1}n; the oracle computes f(x) = s·x mod 2. Classically, n queries are necessary and sufficient: query ei to read bit i. Quantumly:

|0>^⊗n → H^⊗n → 2^−n/2 Σ_x |x> → phase oracle → 2^−n/2 Σ_x (−1)^s·x |x> = H^⊗n|s> → H^⊗n → |s>

The middle line is the whole proof: the state after the query is H⊗n|s>, by the identity above, so a second Hadamard layer inverts it exactly. One query, n bits, zero error probability.[3] Deutsch–Jozsa is the same circuit against a promise oracle, distinguishing constant from balanced in one query where classical determinism needs 2ⁿ⁻¹+1.[4]

Both are exponential separations in query complexity and neither solves a problem anyone has. They are cited here for the same reason they were invented: to establish that the separation exists at all, cleanly, before anyone argues about applications.

Grover, derived

Search over N = 2ⁿ candidates with a phase oracle marking one solution |ω>. Write |s> = N−1/2 Σx|x> for the uniform state. The algorithm alternates two operators:

U_ω = I − 2|ω><ω| reflection about the hyperplane ⊥ |ω> D = 2|s><s| − I reflection about |s>

Both are reflections, and the composition of two reflections is a rotation — by twice the angle between their axes. That single geometric fact is the entire analysis.

The two-dimensional subspace

Let |ω⊥> be the normalised uniform superposition over the N−1 non-solutions. Every state the algorithm ever visits lies in the plane spanned by {|ω>, |ω⊥>}, because both operators preserve it. Define θ by

sin θ = <ω|s> = 1/√N so |s> = cosθ·|ω^⊥> + sinθ·|ω>

The starting state sits at angle θ from the non-solution axis — a small angle, since sinθ = N^−1/2. Each Grover iteration G = D·Uω rotates the state by 2θ toward |ω>. After k iterations:

G^k|s> = cos((2k+1)θ)·|ω^⊥> + sin((2k+1)θ)·|ω> P(success after k iterations) = sin²((2k+1)θ)

Success probability is sin²((2k+1)θ), so it is periodic in the iteration count. For N = 16 the optimum is three; six iterations rotates the state so far past the solution that the machine performs worse than a single random guess. More effort is not monotonically better — an unclassical property with real consequences.

This is the closed form for the whole algorithm, and every practical fact about Grover reads off it.

How many iterations, and why not more

Success is maximised when (2k+1)θ ≈ π/2, giving

k_opt = round( π/(4θ) − 1/2 ) ≈ (π/4)√N for large N

Note the shape of the failure mode: because the amplitude is sinusoidal in k, running Grover too long rotates the state past the solution and success probability falls again. This is genuinely unlike classical search, where more effort never hurts, and it means the iteration count must be known in advance — which requires knowing the number of solutions. When that count is unknown, the standard fix is the exponential-search wrapper of Boyer, Brassard, Høyer and Tapp, which recovers O(√N) without the promise.[5]

The threshold theorem is the sign of one inequality. Below pₜₕ, adding distance suppresses errors exponentially; above it, the same additional hardware adds noise faster than it removes it. There is no gradual region between the two curves — only which side of the threshold the physical error rate sits on.

For N = 4 the arithmetic closes exactly: sinθ = 1/2, so θ = π/6, and one iteration gives sin(3·π/6) = sin(π/2) = 1. Four is the unique size at which Grover is deterministic, which is why it makes a good worked example and a misleading intuition — the parent piece's padlock succeeds with certainty for a reason that does not generalise.

N	θ = arcsin(1/√N)	kopt	Success probability
4	30°	1	1.000
16	14.48°	3	0.961
128	5.07°	8	0.996
1024	1.79°	25	0.999
106	0.057°	785	1.000

Why √N is a floor, not a record

The lower bound is the part of Grover's story that gets omitted, and it is the more important half. Bennett, Bernstein, Brassard and Vazirani proved that any quantum algorithm making T queries to an unstructured oracle must have T = Ω(√N) to find a marked item with constant probability.[6]

The argument is a hybrid: run the algorithm against the all-zero oracle, which contains no solution, and track how much total amplitude it places on each index across all T queries. That total is fixed at T, spread across N indices, so some index receives at most T/N. Switching the oracle to mark that index perturbs the final state by an amount bounded in terms of T/√N, and for the algorithm to notice the difference reliably that quantity must be Ω(1). Hence T = Ω(√N).

What the bound actually says

It is a statement about oracle access, not about hardware or cleverness. Given a function you can only evaluate, quadratic is the ceiling, permanently. It does not apply the moment the function's internal structure is available for the algorithm to exploit — which is the loophole every genuinely exponential quantum algorithm walks through, Shor included.

Shor, derived

Shor's algorithm is a classical reduction with a single quantum subroutine, and the reduction is the older and less glamorous half.[7]

The classical reduction

To factor N, pick a uniformly from {2, …, N−1}. If gcd(a, N) > 1 you have already won, which never happens for the RSA case. Otherwise let r be the multiplicative order of a modulo N — the least r > 0 with ar ≡ 1 (mod N). If r is even and ar/2 ≠ −1 (mod N), then

a^r − 1 ≡ 0 (mod N) (a^r/2 − 1)(a^r/2 + 1) ≡ 0 (mod N)

So N divides the product but, by the two conditions, divides neither factor. Therefore gcd(ar/2 − 1, N) is a proper divisor. For N odd with at least two distinct prime factors, a random a satisfies both conditions with probability at least 1/2, so a handful of attempts suffices.

Worked on N = 15 with a = 7: the order is r = 4, ar/2 = 72 = 4, and gcd(3, 15) = 3, gcd(5, 15) = 5. With a = 14 the order is 2 and ar/2 = 14 ≡ −1 (mod 15) — the second condition fails, both gcds are trivial, and you resample. That is exactly the failure case, and it is why the algorithm is stated with a retry.

Everything in this subsection is Euclid and modular arithmetic. The only step no classical computer can do at scale is finding r.

The quantum subroutine: order finding

Choose M = 2^m with N² ≤ M < 2N². Prepare two registers, apply H⊗m to the first, and compute modular exponentiation reversibly into the second:

M^−1/2 Σ_x=0^M−1 |x>|a^x mod N>

The second register is now entangled with the first, and its value depends on x only through x mod r. Measuring it (or simply discarding it — the effect is identical) collapses the first register onto an arithmetic progression of spacing r:

∝ Σ_j |x₀ + jr> for some unknown offset x₀

A periodic state, whose period is the thing we want and whose offset is the thing we do not. Apply the quantum Fourier transform,

QFT_M |x> = M^−1/2 Σ_y=0^M−1 e^2πixy/M |y>

and two things happen at once. The offset x₀ becomes a global phase — unobservable, and therefore harmlessly discarded. And the amplitudes concentrate on values of y near integer multiples of M/r: for those, the r-spaced terms arrive in phase and add; for every other y they are spread around the unit circle and cancel. This is the interference step, and it is the only one in the algorithm.

Measure and you get some y ≈ c·M/r. Divide by M and you hold a rational approximation to c/r good to within 1/2M ≤ 1/2N². Continued fractions recover c/r in lowest terms uniquely from an approximation that tight, which yields r when gcd(c, r) = 1 — probable enough that a few repetitions settle it. Verify by checking ar ≡ 1, which is cheap, so the algorithm is a Las Vegas procedure: never wrong, occasionally slow.

Where the exponential actually comes from

Not from evaluating ax mod N at 2^m values of x. That superposition exists in the naive algorithm too and yields nothing on measurement.

It comes from periodicity being a global property. The QFT is a basis change in which period is a coordinate, so a single measurement in that basis returns a fact about the whole function rather than about one input. Bernstein–Vazirani extracts a parity the same way; Shor extracts a period; both spend one measurement on one global fact. The difference is that a period, unlike a parity, is worth something.

Cost

With n = log₂ N, the QFT costs O(n²) gates exactly, or O(n log n) in the standard approximate version whose small rotations are simply dropped.[8] It is not the bottleneck. Reversible modular exponentiation is: O(n³) elementary gates with schoolbook arithmetic, and for n = 2048 this lands at a few billion Toffoli gates in the best current constructions.[9] Everything in the resource estimates further down is downstream of that number.

What the formalism forbids

The parent piece asserts that superposition and entanglement are not, by themselves, the source of any advantage. That is not rhetoric; it is a theorem.

Gottesman–Knill

The Clifford group is generated by H, S = diag(1, i) and CNOT. Circuits built from Clifford gates, applied to computational basis states and followed by measurement, can be simulated on a classical computer in polynomial time — in O(n²) per gate by tracking the stabiliser group rather than the state vector.[10]

These circuits are not trivial. They produce superpositions over all 2ⁿ basis states, generate maximal entanglement, and include the entire family of states used in teleportation, superdense coding and quantum error correction. The state vector has exponentially many nonzero amplitudes throughout. And a laptop simulates them.

Exponential superposition, maximal entanglement, polynomial classical simulation. Whatever the resource is, it is none of those three.

What Clifford circuits lack is a gate outside the group — the T gate, diag(1, e^iπ/4), suffices for universality. The advantage lives in the non-Clifford part, which is also, not coincidentally, the part that is expensive to make fault-tolerant. Everything cheap is classically simulable; the entire cost of a quantum computer is concentrated in the gates that make it more than a classical one.

Where BQP sits

BQP is the class of decision problems solvable by a polynomial-size quantum circuit with error at most 1/3. The known containments are modest:

P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE

Every containment is open. Nobody has proved BQP ≠ P — doing so would prove P ≠ PSPACE and settle a question older than the field. What exists instead is oracle evidence, and it points both ways with useful precision. BBBV shows that relative to a random oracle, NP ⊈ BQP: quantum computers do not solve NP-complete problems by brute force, and no amount of effort will make them.[6] Raz and Tal, in 2019, constructed an oracle relative to which BQP ⊈ PH, so quantum computation is not merely a speedup of classical search but sits outside the polynomial hierarchy in a way nothing classical does.[11]

The honest summary is that BQP is believed to be incomparable with NP: it contains problems (factoring, discrete log) not known to be in P, and it is not believed to contain NP-complete problems. Neither belief is proved. Both are the reason the practical list in the parent piece is five items long.

Error correction, quantitatively

Classical error correction copies bits and takes a majority vote. Postulate 3 forbids the copy, postulate 4 forbids looking, and quantum errors are continuous rather than discrete. All three obstacles are removed by the same manoeuvre.

Syndromes, and the discretisation of errors

Encode a logical qubit across many physical qubits and measure a set of commuting operators — stabilisers — chosen so that their eigenvalues reveal where an error occurred while revealing nothing about the encoded state. Since the measured operators commute with the logical operators, the logical information is untouched by the measurement.

The consequence that makes the whole field possible: a general error is a continuous superposition of Paulis, E = αII + αXX + αYY + αZZ, and measuring the syndrome projects that superposition onto one discrete Pauli. A continuum of possible faults collapses to a finite set the moment you look at the syndrome, and a finite set can be corrected by a lookup. Analogue noise becomes digital noise for free.

The surface code, in three numbers

The surface code arranges physical qubits on a two-dimensional lattice with only nearest-neighbour checks, which is why it dominates: it matches what superconducting hardware can actually wire.[12] Its code distance d is the number of physical errors needed to cause an undetectable logical error, and:

physical qubits per logical ≈ 2d² logical error rate p_L ≈ A · (p/p_th)^{⌊(d+1)/2⌋} error suppression factor Λ = p_L(d) / p_L(d+2)

The middle line is the threshold theorem made concrete.[13] If the physical error rate p is below the threshold p_th — roughly 1% for the surface code under circuit-level noise — the base of that exponential is less than one and increasing d suppresses errors exponentially. If p is above threshold, the base exceeds one and adding qubits makes the machine worse. There is no gradual region. The sign of a single inequality determines whether the entire enterprise is possible.

The shape every algorithm here shares. Hadamards spread the register over all 2ⁿ basis states; the oracle writes its answer into signs by phase kickback, leaving its ancilla unentangled; a second Hadamard layer folds the sign pattern back into a single basis state. Only the middle beat differs between Deutsch–Jozsa, Bernstein–Vazirani, Grover and Shor.

Which is what Google measured. Running d = 3, 5 and 7 on Willow, they found Λ = 2.14 ± 0.02 — each two-step increase in distance halving the logical error rate, sustained across the sequence.[14] That is the below-threshold regime observed rather than argued, and it is why the parent piece calls it the only important result in years.

What the T gates cost

In the surface code, Clifford operations are comparatively cheap. Non-Clifford gates are not: the standard route is magic state distillation, which consumes many noisy copies of a special ancilla to produce one clean one, with the factories occupying a substantial fraction of the chip.[15] In most fault-tolerant resource estimates the T-gate cost dominates everything else, which puts the field in the position of paying almost its entire budget for precisely the gates that Gottesman–Knill says are the ones that matter. The economics and the theory agree, which is reassuring and expensive.

From algorithm to machine

Resource estimation is the arithmetic that turns a published algorithm into a machine specification, and it runs in one direction:

algorithm → Toffoli / T count → distillation factories + routing → required logical error rate → code distance d → physical qubits × runtime

The step that surprises people is the third. The required logical error rate is set by the total gate count: if an algorithm applies 10¹⁰ logical operations and must succeed, each needs an error rate well below 10⁻¹⁰, which fixes d through the exponential above and therefore fixes the physical qubit count through the 2d². Algorithmic improvements that reduce gate count reduce the required distance, which reduces qubits quadratically. Savings compound in a way that is easy to underestimate.

That is why the headline number has moved so far without any hardware changing. Gidney and Ekerå estimated 20 million physical qubits and 8 hours for RSA-2048 in 2019.[9] Gidney's 2025 revision is under a million, in under a week — a twentyfold reduction from better modular arithmetic, cheaper magic states and improved code constructions.[16] No new physics, no new hardware, purely the compilation getting better.

The asymmetry to keep in view

Hardware progress is public, slow and easy to track. Compilation progress is published in venues nobody reports on and has produced larger factor improvements than the hardware has. Anyone timing the cryptographic migration off qubit counts alone is watching the slower of the two variables.

Coda

Everything above descends from the same four lines. Postulate 2 gives the exponential state space; postulate 4 makes it unreadable; postulate 3 forbids the copy that would let you sample it twice. The power and the limitation are not in tension and they are not separate discoveries — they are the same axioms read in two directions.

What remains, once the formalism has taken back everything it appears to offer, is the narrow thing the parent piece describes: a machine that can arrange for wrong answers to cancel, useful exactly where a problem's structure gives the cancellation something to grip, and quadratic or useless everywhere else. That is a smaller claim than the press releases make and a far more interesting one, because it is true and it is provable, and both of those are rarer than they should be.

If you want the full treatment

Nielsen and Chuang remains the standard graduate text and covers every derivation here at proper length.[17] Preskill's lecture notes are the best free alternative. For the complexity theory specifically, Aaronson's Quantum Computing Since Democritus is unmatched and funnier than it needs to be.

References

1. Holevo, A. S. (1973). “Bounds for the quantity of information transmitted by a quantum communication channel.” Problems of Information Transmission 9(3), 177–183.
2. Wootters, W. & Zurek, W. (1982). “A single quantum cannot be cloned.” Nature 299, 802–803. See also Dieks, D. (1982), Physics Letters A 92, 271–272.
3. Bernstein, E. & Vazirani, U. (1997). “Quantum Complexity Theory.” SIAM Journal on Computing 26(5), 1411–1473. Originally STOC 1993.
4. Deutsch, D. & Jozsa, R. (1992). “Rapid solution of problems by quantum computation.” Proceedings of the Royal Society A 439(1907), 553–558.
5. Boyer, M., Brassard, G., Høyer, P. & Tapp, A. (1998). “Tight bounds on quantum searching.” Fortschritte der Physik 46(4–5), 493–505.
6. Bennett, C., Bernstein, E., Brassard, G. & Vazirani, U. (1997). “Strengths and Weaknesses of Quantum Computing.” SIAM Journal on Computing 26(5), 1510–1523.
7. Shor, P. (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.” SIAM Journal on Computing 26(5), 1484–1509. (First presented at FOCS 1994.)
8. Coppersmith, D. (1994). “An approximate Fourier transform useful in quantum factoring.” IBM Research Report RC19642; reissued as arXiv:quant-ph/0201067.
9. Gidney, C. & Ekerå, M. (2021). “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.” Quantum 5, 433. quantum-journal.org
10. Gottesman, D. (1998). “The Heisenberg Representation of Quantum Computers.” arXiv:quant-ph/9807006. Simulation cost improved in Aaronson, S. & Gottesman, D. (2004), Physical Review A 70, 052328.
11. Raz, R. & Tal, A. (2019). “Oracle Separation of BQP and PH.” Proceedings of STOC 2019, 13–23.
12. Fowler, A., Mariantoni, M., Martinis, J. & Cleland, A. (2012). “Surface codes: Towards practical large-scale quantum computation.” Physical Review A 86, 032324.
13. Aharonov, D. & Ben-Or, M. (1997). “Fault-Tolerant Quantum Computation with Constant Error.” Proceedings of STOC '97, 176–188. See also Knill, Laflamme & Zurek (1998), Science 279, 342–345.
14. Google Quantum AI (2025). “Quantum error correction below the surface code threshold.” Nature 638, 920–926. nature.com
15. Bravyi, S. & Kitaev, A. (2005). “Universal quantum computation with ideal Clifford gates and noisy ancillas.” Physical Review A 71, 022316.
16. Gidney, C. (2025). “How to factor 2048 bit RSA integers with less than a million noisy qubits.” arXiv:2505.15917
17. Nielsen, M. & Chuang, I. (2010). Quantum Computation and Quantum Information, 10th Anniversary Edition. Cambridge University Press.

Published September 2026 · Companion to The Interference Machine · Derivations follow Nielsen & Chuang; resource figures from the cited primary literature.