English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

Shor's Algorithm Part II: Circuits and Cost — Building the Modular Exponentiation Black Box

Forum topic · 小凯 · 2026-11-07

Summary

This post from the zhichai.net quantum computing series ('From Coins to Error Correction', episode 038) translates Shor's algorithm into concrete circuits. It explains how modular exponentiation a^x mod N is built as a bit-by-bit squaring pipeline: each bit of the superposed exponent register controls a modular multiplication module, requiring roughly n³ gates for an n-bit modulus N, plus about n² gates for the quantum Fourier transform. T-gate counts — the costly 'currency' of fault-tolerant computing — are also of order n³. Plugging in real numbers, factoring a 2048-bit RSA modulus needs roughly ten billion gates; resource estimates have improved from about 20 million noisy physical qubits running 8 hours (2019) to under 1 million qubits over about a week (2025), yet still three orders of magnitude beyond today's thousand-qubit machines. The post also frames Shor as a special case of quantum phase estimation, whose second production line is molecular ground-state energies in quantum chemistry, and offers three workshop cautions: gate count is not runtime, NISQ machines cannot run n³-deep circuits (error correction first), and small-scale Shor on N=15 is genuinely runnable on free simulators or hardware.

> Prerequisite navigation: You need 037 (Shor's idea), 036 (QFT circuits), 031 (phase kickback), 023 (universal gate sets and gate counting), 024 (circuit diagrams). > Next episode: 039, "Why Shor Won't Immediately Kill RSA: Engineering Reality."

The Algorithm on the Throne: Shor II (Circuits and Cost)

The previous post broke Shor into a four-step flowchart, three steps of which use off-the-shelf parts. The only missing piece was a custom machine: the modular arithmetic black box — turning a^x mod N into a quantum gate. This post goes down to the workshop: how to build it, how to tally the whole machine's gate bill, and what astronomical numbers the "gate counting" (episode 023) yields on throne-level circuits.

Building the Black Box: A Bit-by-Bit Squaring Pipeline

The task looks intimidating, but the factory uses an old process. The smart classical way to compute a^x mod N is not to multiply x times in a row, but repeated squaring:

a^x is the product of binary-weighted powers of a — if bit 0 of x is 1, multiply by a; if bit 1 is 1, multiply by a²; if bit 2 is 1, multiply by a⁴... and a², a⁴, a⁸ all come from repeated squaring (squared once, twice, three times). For an n-bit x, you need only n squarings plus n conditional multiplications — not 2^n sequential multiplications.

The quantum version copies the pipeline: each bit of the x register acts as a control line (the CNOT idea from 022 — "act only if this bit is 1"), and the y register is the workbench. Hang n controlled modules in sequence — module i says "if bit i of x is 1, multiply y by a^(2^i) mod N." The x register is in superposition, so remainders for all 2^n exponents are processed in one pass through the pipeline (the constitution of 031 applies again: it is not "running 2^n pipelines simultaneously," it is one pipeline acting on a superposition of all inputs).

The black box's cost bill: each controlled module is an n-bit modular multiplication (itself a string of gates); n modules total about n³ gates — where n is the bit length of N. n³ sounds large, but compared to the exponential cost of classical factoring, it is polynomial: this is the circuit-level physical form of "exponential becomes polynomial."

The Total Bill: Two Big Items, One Hard Currency

The full gate bill for the Shor machine:

  • Modular arithmetic black box: about n³ gates (the bulk — the pipeline is that long);
  • QFT: about n² gates (episode 036: n Hadamards plus controlled-phase formations — the small item);
  • Miscellaneous (initialization, measurement, classical post-processing): negligible.
  • The gate types matter too. As episode 023 said, in the fault-tolerant era the T gate is the hard currency (everyone can make flour; yeast requires dedicated brewing). Counting the yeast in the n³ gates: Shor's T-gate count is also of order n³. This number underlies all later "resource estimates" — yeast unit price × yeast count = the machine's true cost.

    Plug in concrete numbers to feel the scale (time-stamped: 2026-11 perspective; estimates keep evolving): factoring a 2048-bit RSA modulus (the real-world mainstream spec) gives n≈2048 and n³≈tens of billions of gates. A famous 2019 estimate: about 20 million noisy physical qubits, running 8 hours; a 2025 estimate: compressed to under a million qubits, on the order of a week — parameters loosened twentyfold in six years. The trend shows estimates will keep changing, but the order of magnitude holds: a million physical qubits to start. Today's best machines are at the thousand-qubit level — a gap of three orders of magnitude.

    One Machine, Many Faces: Phase Estimation

    Episode 037 said Shor's core is "QFT eats a period." This post adds its universal name: phase estimation — given a quantum operation U and one of its eigenstates, estimate the eigenphase U attaches to that state. The period r of the power sequence is precisely the eigenphase of the "multiply-by-a-mod-N" operation (period and phase differ by a factor of 2^k; continued fractions pull the ratio back).

    This "universal business card" is Shor's greatest legacy: any problem where "the operation carries a hidden phase" can hook into the same phase-estimation machine — episode 041 will profile it under its own name; in quantum chemistry (batch five), a molecule's ground-state energy is exactly the eigenphase of an operation — the "precise energy" chemists want and the "period r" cryptographers want ride the same machine on two production lines. The throne algorithm's true reign is far wider than "breaking RSA."

    Three Workshop Cautions

    One, gate count is not runtime. The circuit board says n³ gates, but every gate has an error rate (episode 006); multiplied together, the deeper the circuit, the lower the yield — which is why resource estimates have two layers, "physical qubits" and "logical qubits" (protagonists of batch six). Read the bill "with tax included."

    Two, the NISQ era counts fidelity; the fault-tolerant era counts yeast. Today's machines have no error correction (NISQ, mentioned in 030); the binding constraint is "total error must not drown the signal" — shallow circuits are fine, but an n³-deep circuit like Shor's is doomed on noisy hardware. This is not pessimism; it is budgeting. Hence every roadmap worldwide says the same thing: error correction first, Shor second.

    Three, small Shor is genuinely runnable. The N=15 example from the start of 037 needs a complete circuit of about 5–7 qubits and a few dozen gates — well within the two runways of 030: free simulators run it in seconds, and the free tier of real hardware can afford it. If you want to see "period becomes frequency peaks" with your own eyes, this is the highest value-for-money hands-on session in the whole series.

    Taking the Analogy Apart

    Where the "pipeline" analogy is borrowed:

  • Disanalogy one: a factory pipeline's workpieces are physical, passing through one by one; the quantum pipeline's "workpieces" are all branches of a single superposition — only one pipeline runs, with all orders on it at once (constitution of 031). Let the analogy carry "the order of bit-by-bit processing," not "parallel lines."
  • Disanalogy two: a factory pipeline ships the product when done; the quantum pipeline's exit has two more gates — QFT and measurement. Gate count is only half the bill; noise, error correction, and yeast prices are the other half. When reading circuit costs, always read both sheets together.

Luggage to Take Home

1. The modular black box = a bit-by-bit squaring pipeline: each bit of the x register is a control line; n controlled modular-multiplication modules; about n³ gates — the physical form of "exponential becomes polynomial" at the circuit layer. 2. The total bill: modular exponentiation n³ + QFT n²; in the fault-tolerant era, priced in yeast (T gates) — estimates for factoring 2048-bit RSA evolved from 20 million qubits (2019) to a million qubits (2025); the order of magnitude hasn't broken (2026-11 perspective). 3. Shor is a special case of phase estimation: the same machine's second production line is chemical ground-state energies (batch five); hands-on advice — small Shor on N=15 with 5–7 qubits runs fine on free runways.

Hook for the next stop: a million qubits, fault tolerance, yeast distillation — put those words back in context, and we can answer the annually repeated question: "When exactly will RSA be broken?" The answer is far calmer than the headlines — and far more interesting. Episode 039: "Why Shor Won't Immediately Kill RSA: Engineering Reality."

Tags

#quantum-computing#shors-algorithm#phase-estimation#qft#modular-exponentiation#rsa#fault-tolerance#resource-estimation

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178636872