A four-author study, co-authored with Guangqi Gao, Jerry Xia, and Yiqun Zhao, quantifying the true resource cost of Shor’s factoring algorithm. Shor’s celebrated exponential speedup is usually stated in an idealized gate model that hides the real cost of its “oracle,” modular exponentiation; the study makes that cost explicit under a realistic hardware-native gate set {RZ, SX, X, CX} (RZ rotations applied virtually, at zero gate time) with an approximate QFT. The group established the logical-circuit resource scalings; my own contribution was the fault-tolerant layer, deriving the physical-qubit overhead of that circuit under a surface-code model.
Working as a group, we decomposed the dominant subroutine, modular exponentiation, bottom-up: a Fourier adder (O(n) gates), a modular adder (n+4 qubits), and a controlled modular multiplier (2n+O(1) qubits), assembled into the controlled modular exponential that drives the algorithm’s cost.
Compiling each block to the hardware-native set and swapping the exact QFT for the approximate QFT, keeping only rotations with k ≤ kmax = Θ(log(n/ε)), cuts each qubit to O(log n) phase gates at Coppersmith error O(ε).
The co-authors’ logical-level result: with kmax = O(log n), the full algorithm needs only O(n) logical qubits, with O(n log n) gates for the QFT, O(n² log n) gates for modular multiplication, and O(n³ log n) gates at O(n³) circuit depth for the dominant modular-exponentiation step. Qiskit transpilation confirmed the CNOT and RZ counts grow quadratically with qubit count, matching the QFT’s O(n²) scaling. The study also applies oblivious runway adders to parallelize the arithmetic, trading space for a factor-NL reduction in circuit depth.
My personal contribution was translating that logical circuit into a physical-qubit budget under a coarse surface-code fault-tolerant model with magic-state distillation. Mapping the circuit onto a surface code with lattice surgery for the CX gate gives data qubits Qd = NL(2d+1)² and total physical qubits Qt = 2NL(2d²+2d+1).
Setting the code distance to suppress logical error across the full run, and realizing the non-Clifford RZ rotations through magic-state distillation (T-factories at ~50% of chip area, T-count per rotation ≈ log₂(1/ε)), I found the physical-qubit overhead scales as O(NL · log(NL)²) in the logical-qubit count NL.