Ask anyone what Shor's algorithm does and you will hear about the quantum Fourier transform, phase estimation, interference peaks. All true — and almost none of it is where the machine's effort goes. Profile an actual implementation of Shor's algorithm and the picture is comically lopsided: the QFT is a sliver, and nearly every qubit and nearly every gate is spent on modular exponentiation — a^x \bmod N, computed by reversible adders, reversible multipliers, reversible comparators. In other words: the payoff of a quantum computer is delivered by classical reversible arithmetic, the very circuits of the synthesis module, now running on qubits. This is the lesson where your two skill sets fuse: the reversible-synthesis toolbox is the quantum compiler backend.

The arithmetic tower

Shor needs the unitary |x\rangle|1\rangle \mapsto |x\rangle|a^x \bmod N\rangle for an n-bit modulus N. Nobody builds that in one piece; it is compiled down a tower, and every storey of the tower is a construction you already know:

• Exponentiation → multiplications. Classical square-and-multiply: write x in binary and, for each of its \approx 2n bits, conditionally multiply the accumulator by a precomputed constant a^{2^i} \bmod N. Each conditional multiply is a controlled modular multiplier — controlled on one qubit of |x\rangle.
• Multiplications → additions. A modular multiply by a constant is a shift-and-add loop: about n modular additions, each a plain reversible adder followed by a compare-and-conditionally-subtract-N (itself an adder run in reverse plus a comparator — which is an adder too).
• Additions → Toffolis. Each adder is exactly the VBE or Cuccaro ripple-carry circuit from the synthesis module — carries computed by Toffolis, sums by CNOTs, carries uncomputed by the mirror-image Toffolis. On qubits, gate for gate, unchanged.

Multiply it out: 2n multipliers \times\; n additions \times\; O(n) Toffolis — an O(n^3)-Toffoli engine of pure classical reversible logic, wrapped around a whisper-thin layer of Hadamards, a QFT and a measurement. For N of cryptographic size, that is billions of Toffolis of grade-school arithmetic done without ever forgetting a carry.

Uncomputation, wall to wall

The tower would collapse without the discipline of the previous lesson. Every storey manufactures intermediates — carry chains, partial products, the "did we overflow N?" comparison bit — and every one of them is entangled with |x\rangle. Left in place, they are which-path records that would erase the periodic interference pattern the final QFT exists to read. So every block is a compute–copy–uncompute sandwich: the Cuccaro adder uncomputes its own carries as it goes; the modular multiplier computes b \cdot a^{2^i} \bmod N into a fresh register, then uncomputes the old accumulator by running the inverse multiplication (the swap-and-unmultiply trick); the comparison ancilla is returned to |0\rangle by re-running the comparison backwards. Roughly half the gates in a real Shor circuit are there purely to unhappen the other half — Bennett's bargain, paid at industrial scale.

What it costs, in the currency that matters

On fault-tolerant hardware, gates are not created equal. Clifford gates (CNOT, H, S) are cheap under error correction; the expensive resource is the T gate, manufactured offline by magic-state distillation — and a Toffoli costs a small constant number of T gates (a standard decomposition uses seven, or four with tricks). So quantum engineers budget circuits in Toffoli count or T-count, and mostly ignore everything else. That convention quietly concedes this lesson's thesis: the fault-tolerant cost of Shor is the cost of its classical reversible arithmetic, because that is where all the Toffolis are. The same synthesis skills you practised — trade ancillas against depth, shave a Toffoli here, uncompute earlier there — are precisely what shrinks a factoring machine.

There is one genuinely quantum-native alternative worth knowing as contrast: Draper's QFT adder. It adds a constant not with carry chains but in phase space: Fourier-transform the register, apply single-qubit phase rotations R_k (addition becomes phase accumulation — no carries, no ancillas at all), and transform back. Elegant, qubit-frugal — and made of many small rotations, each of which must be synthesised from T gates on fault-tolerant hardware, so it usually loses the T-count contest to the humble Toffoli ripple adder. The trade-off table every implementer keeps in their head: