A noise threshold for Shor's Fourier transform

Shor's algorithm, in the 1997 paper, is a polynomial-time algorithm on an ideal quantum gate array. The factoring bound counts gates, and the practicality section already names precision and decoherence as the obstacle to running them. Cai and Young (arXiv:2609.24316, 21 Sep 2026) prove a threshold for one concrete way those gates can be imprecise. The note below follows Theorems 3.3 and 4.3 and the noise model in their section 2. It does not add a second model.

The rotations they perturb

The body of the n-qubit quantum Fourier transform is Hadamard gates and controlled rotations about Z. The rotation indexed by k is through angle 2π/2^k. Cai and Young keep every such rotation exact for k below a cutoff b, and they take b on the order of log n. For every k at least b, they replace the rotation by a noisy one through angle 2π(1 + εr)/2^k. The parameter ε is a single noise magnitude. Each gate has its own standard Gaussian random variable r, the variables are independent, and the same draw of r multiplies every amplitude that gate touches. They call the noise relative because it scales with the intended angle. Large angles stay exact. The small ones do not.

This is not a model of depolarizing noise on every qubit, and it is not a model of a surface-code cycle. The only gates they corrupt are those controlled rotations inside the Fourier transform.

The threshold

Let n be the bit length of the integer to be factored, or of the prime modulus in the discrete-logarithm problem. Theorems 3.3 and 4.3 use the same cutoff on the noise.

If ε/2^b is bounded by a constant times the square root of (log n)/n, then the expectation, over the random noise, of the probability of measuring a useful Fourier outcome is at least an inverse polynomial in n. For factoring, that outcome is a sample from which a prime factor is recovered by the usual classical post-processing, and the algorithm runs in expected time polynomial in n. For discrete logarithms, the same lower bound holds for any generator and any target, and the algorithm finds the discrete logarithm in expected time polynomial in n.

If, instead, the ratio of ε/2^b to that square root tends to infinity with n, the expectation of the success probability is exponentially small in n. For factoring, this is for both prime factors drawn from a set of primes of positive density. For discrete logarithms, it is for a positive-density set of prime moduli, every generator, and all but an exponentially small fraction of targets. The introduction records that the two directions match, so the threshold is asymptotically tight, and that any fixed b and ε eventually fall on the failing side once n is large enough. A noise level that does not shrink with n is above the threshold for all sufficiently large inputs in those sets.

Where the claim stops

The paper's own emphasis is the sentence a resource estimate has to keep: if the algorithms are to work for arbitrarily large inputs under this model, the Fourier transform has to use arbitrarily precise controlled rotations. That is a statement about the ideal gate array once those rotations are allowed to be relatively noisy. It is not a laboratory measurement, and it is not a revision of the 1997 gate count for a perfect circuit.

Remark 4.1 discusses fault tolerance. The authors say the threshold can be read as a necessary tolerance that error correction would have to meet for this noise. They note that the threshold theorem supplies a constant physical error rate, under a tensor-product model of many qubits, below which independent noise of the kind in the paper can be corrected by encoding. The first author then states a belief: that the tensor-product model is not infinitely accurate, and that the threshold theorem therefore does not dispose of the difficulty. That belief is not Theorem 3.3 or Theorem 4.3. This library does not adopt it as a result. The proved claim stops at the noise model, the positive-density set of primes, and the expected polynomial runtime on the other side of the cutoff.