Case Study: Truncating the QFT — How Much Precision Do You Actually Need?

Executive Summary

The exact QFT on $n$ qubits contains controlled rotations as small as $\pi/2^{n-1}$. For $n = 2048$ — the register size in a Shor attack on RSA-2048 — that is a rotation by $10^{-616}$ radians: smaller than any physical control system can express, smaller than the gate error by hundreds of orders of magnitude, and requiring more $T$ gates to synthesize than the rest of the algorithm combined.

The resolution, due to Coppersmith, is to simply not apply rotations below a threshold. This case study derives how aggressive the truncation can be, shows the resulting cost reduction, and makes a general point about numerical precision in quantum algorithms that applies well beyond the QFT.

Skills applied

• Analyzing the QFT's rotation hierarchy (§14.7).
• Bounding truncation error and comparing it to hardware error (§14.9).
• Estimating gate-count savings from approximation.
• Reasoning about the cost of synthesizing arbitrary rotations fault-tolerantly.

Phase 1: The rotation hierarchy

The QFT applies $R_k = \begin{pmatrix}1 & 0\\ 0 & e^{2\pi i/2^k}\end{pmatrix}$ controlled from qubit $j$ onto qubit $j+k$.

There are $O(n^2)$ rotations, but their magnitudes decay geometrically, so almost all of them are essentially the identity.

Phase 2: Bound the truncation error

Dropping all rotations with $k > m$ leaves each qubit missing at most $n - m$ rotations, each of magnitude at most $2\pi/2^{m}$. The total error in operator norm is bounded by

$$\|QFT - AQFT_m\| \le 2\pi n \cdot 2^{-m}$$

(Coppersmith's bound; tighter analyses improve the constant.)

Set the target error at $\varepsilon$:

$$m \ge \log_2\!\left(\frac{2\pi n}{\varepsilon}\right)$$

The threshold grows only logarithmically in $n$. Even a 2,048-qubit QFT needs only about 24 levels of rotation for $10^{-3}$ accuracy — not 2,048.

Phase 3: The cost saving

Gate count drops from $O(n^2)$ to $O(nm) = O(n\log(n/\varepsilon))$:

At the scale that matters for cryptanalysis, truncation removes 98% of the rotations.

Phase 4: The deeper reason — fault-tolerant synthesis cost

The gate-count saving understates the benefit considerably, because in a fault-tolerant architecture an arbitrary rotation is not a primitive at all.

Clifford+$T$ is a discrete set. An arbitrary $R_z(\theta)$ must be synthesized to accuracy $\delta$ from that set, at a cost of roughly

$$3\log_2(1/\delta) \ \ T \text{ gates}$$

using modern Ross–Selinger synthesis. So each arbitrary rotation costs on the order of 50–100 $T$ gates, and $T$ gates are the dominant resource in fault-tolerant computing (Chapter 9's magic-state analysis).

For the exact 2,048-qubit QFT:

$$2.1\times10^{6} \text{ rotations} \times \sim75\ T \text{ each} \approx 1.6\times10^{8}\ T \text{ gates}$$

For the truncated version:

$$4.9\times10^{4} \times 75 \approx 3.7\times10^{6}\ T \text{ gates}$$

A saving of $1.5\times10^{8}$ $T$ gates — which at 225 raw magic states per distilled $T$ (Chapter 9) is tens of billions of magic states not needed.

Finding. Truncation is not a minor optimization. In fault-tolerant resource estimates it is the difference between the QFT being a rounding error in the total cost and being a substantial fraction of it.

Phase 5: The general principle

Why can a rotation by $10^{-12}$ radians be dropped without consequence? Because the algorithm's precision requirement is set by what it must distinguish, not by the mathematical exactness of the transform.

In Shor's algorithm the QFT output is post-processed by continued fractions, which tolerate substantial error — the algorithm only needs the measured $y$ to be close enough to $j2^t/r$ that the correct rational approximation is recovered. Errors far below the sampling resolution cannot change the outcome.

This generalizes. Three related instances:

• Phase estimation (Chapter 16) is run to $t$ bits of precision, so rotations below $2^{-t}$ are irrelevant by construction.
• Hamiltonian simulation (Chapter 17) truncates Trotter expansions once the error falls below the target accuracy.
• Variational algorithms (Chapter 19) need gate precision no better than the shot noise on the energy estimate — typically $10^{-3}$, making high-precision synthesis pointless.

The principle. Determine the algorithm's error budget first, then implement to that budget. Implementing a subroutine to precision far beyond what the surrounding algorithm can use is pure waste — and in fault-tolerant computing, the waste is measured in magic-state factories.

Phase 6: Practical guidance

• Set $m \approx \log_2(2\pi n/\varepsilon)$ where $\varepsilon$ is the algorithm's error budget, not machine epsilon.
• On NISQ hardware, truncate aggressively. Hardware gate error ($10^{-3}$) exceeds the truncation error for $m \gtrsim 15$ at any realistic $n$, so any further rotations add error rather than accuracy.
• Verify empirically. Run the algorithm at $m = 5, 10, 15, 20$ and plot success probability; the curve typically saturates far earlier than the bound suggests, because the bound is worst-case.

Discussion Questions

1. The truncation threshold grows as $\log n$ while the exact rotation count grows as $n^2$. Explain why the QFT is therefore "almost linear" in practice.
2. Fault-tolerant synthesis costs $\sim3\log_2(1/\delta)$ $T$ gates per rotation. Why does that make truncation more valuable under error correction than on NISQ hardware?
3. A colleague implements the exact QFT "to be safe." What is the actual effect on accuracy on a device with $10^{-3}$ gate error?
4. State the general precision principle and apply it to a variational algorithm with 1% shot noise.

Your Turn: Extensions

• Implement the AQFT with a tunable $m$ and measure fidelity against the exact QFT for $n = 8, 12, 16$.
• Run Shor's period-finding on $N=15$ with $m = 1, 2, 3$ and find the smallest $m$ that still recovers the period.
• Compute the $T$-count for exact and truncated QFTs at $n = 512$ using $3\log_2(1/\delta)$.
• Simulate with a noise model and find the $m$ beyond which added rotations reduce fidelity.

Key Takeaways

• The QFT's rotations decay geometrically; almost all are numerically indistinguishable from the identity.
• Truncating below $m \approx \log_2(2\pi n/\varepsilon)$ bounds the error at $\varepsilon$ and reduces cost from $O(n^2)$ to $O(n\log n)$ — a 43× saving at $n = 2048$.
• Fault-tolerantly, each arbitrary rotation costs ~75 $T$ gates to synthesize, so truncation saves hundreds of millions of $T$ gates in a cryptanalytic-scale QFT.
• Precision should be set by the algorithm's error budget, not by mathematical exactness — a principle that recurs in phase estimation, Hamiltonian simulation, and variational methods.
• On noisy hardware, rotations smaller than the gate error actively hurt: they add error without adding accuracy.