Resonance Breaking in Noisy Shor's Algorithm

Zhengwei Liu

Source-linked AI summary

Resonance Breaking in Noisy Shor's Algorithm

Zhengwei Liu

arXiv:2609.37636v1Sep 29, 2026quant-phcs.CCcs.ITmath-phmath.ITmath.MPmath.OA

TL;DR

The paper examines how noise at the boundary between composed circuit types can degrade their exponential quantum advantage. The authors express measurement probabilities through a Pauli path integral and analyze independent depolarizing noise on the control register between modular exponentiation and the inverse Fourier transform. For λ > 0, high-frequency terms h(u, v) ≥ d diminish in proportion to (1 − λ)^d, low-frequency terms are bounded by O(n^d)/2^(n/2), and the successful measurement rate is no longer guaranteed as n and d increase.

Problem
The paper examines how noise at the boundary between composed circuit types can degrade their exponential quantum advantage.
Source: §1 · p. 1
Method
The authors express measurement probabilities through a Pauli path integral and analyze independent depolarizing noise on the control register between modular exponentiation and the inverse Fourier transform.
Source: §3 · p. 4
Results
For λ > 0, high-frequency terms h(u, v) ≥ d diminish in proportion to (1 − λ)^d, low-frequency terms are bounded by O(n^d)/2^(n/2), and the successful measurement rate is no longer guaranteed as n and d increase.
Source: §1 · p. 2
Takeaways & Limitations
The authors conclude resonance is essential to a reasonable measurement rate, and a polynomial-time classical algorithm can substitute for the low-frequency contribution.
Source: §1 · p. 2
The result concerns the near-resonant event under the stated single-layer noise model; it does not establish efficient classical simulation of the full noisy circuit or rule out fault-tolerant quantum advantage.
Source: §3 · p. 6

Abstract

from arXiv · show

We argue that the exponential quantum advantage in Shor's algorithm is broken under one-layer depolarizing noise of arbitrary small error rate, by analyzing a resonance breaking phenomenon in noisy quantum circuits. First, we express the distribution of measurements on $n$-qubit strings as the superposition of the $4^n$ wave functions in the Pauli path integral. In the noiseless case, the bit-strings achieving resonant peaks guaranteed a constant rate of successful measurements to factor a large number. Secondly, when the middle layer of the quantum circuit has independent depolarizing noise of rate $\lambda$, for any Hamming weight $d$, we obtain corresponding measurement rate bounded by $2(1-\lambda)^d$ for higher frequency terms and by $O(n^d)/2^{n/2}$ for low frequency terms. The rate approaches to zero as $n$ and $d$ approaches to infinity. Resonance breaking destroys the exponential quantum advantage. Furthermore, we design a classical factoring algorithm in polynomial time $O(n^d)$ to substitute the low frequency contribution.

1 Introduction

The paper studies whether Shor’s resonance-based order finding retains its advantage under noise, focusing on a single depolarizing-noise layer between modular exponentiation and the inverse Fourier transform. It argues that noise suppresses resonant contributions, while a classical algorithm can substitute for the low-frequency contribution.

1 Introduction

The analysis places independent single-qubit depolarizing noise on the control register between modular exponentiation and the inverse Fourier transform, and represents measurement probabilities using a Pauli path integral.The circuit’s other operations are ideal.Source: §1 · p. 1
In the noiseless case, resonant measurement outcomes allow continued-fraction recovery of the order and a nontrivial factor, with a guaranteed successful measurement rate.The resonance arises from constructive addition of the phase terms.Source: §1 · pp. 1–2
With positive depolarizing-noise rate, high-frequency terms are suppressed in proportion to (1−λ)^d, while low-frequency terms are bounded by O(n^d)/2^(n/2).The bounds are stated for terms classified by Hamming weight d.Source: §1 · p. 2
As n and d increase, the measurement rate approaches zero and the authors conclude that resonance breaking destroys the exponential quantum advantage.The paper frames this conclusion for the analyzed noisy Shor circuit.Source: §1 · p. 2
For fixed n, a classical algorithm with running time O(n^d) substitutes for the low-frequency contribution, although decreasing λ while preserving the same exponential factor requires increasing d.The introduction also notes that the polynomial degree may become too high for classical computation and that reducing noise through quantum error correction remains challenging in practice.Source: §1 · p. 2

2 Shor’s algorithm

Shor’s algorithm finds the multiplicative order of a modulo N, then uses classical post-processing to obtain factors. Resonant measurement peaks provide a constant rate of effective measurements, supporting constant overall success with repeated sampling and polynomial-time processing.

2 Shor’s algorithm

Continued fractions produce order candidates from measurements, which are tested or combined by least common multiples; a good even order yields non-trivial factors of N.Repeated independent choices of a yield a good order with high probability when N is odd and has at least two distinct prime factors.Source: §2 · pp. 2–3
As a measurement deviates from a resonant peak, its probability decreases from 1/r to 4/(π²r), up to a small error.The peak bounds are then summed to obtain the constant effective-measurement bound.Source: §2 · p. 3
Summing the peak bounds gives a constant lower bound for effective measurements; repeated sampling and classical post-processing yield constant overall success in polynomial time.The post-processing includes random choices of a.Source: §2 · p. 3
The quantum circuit’s task is to find the multiplicative order r of a through measurements, followed by classical continued-fraction processing.The circuit applies controlled multiplication by powers of a modulo N.Source: §2 · pp. 2–3

3 Resonance breaking under one layer noise

The analysis decomposes noisy Shor measurement probabilities into Hamming-weight sectors and bounds the near-resonant outcomes. For any fixed positive depolarizing rate, the noiseless constant success-rate guarantee disappears, while fixed-d low-weight relations remain classically enumerable.

The probability bound separates low Hamming-distance terms counted by L(d) from higher-weight terms attenuated by depolarizing noise.Each path is contracted once for every non-identity Pauli factor.Source: §3 · p. 5
For every fixed positive noise rate, the constant lower bound on successful measurements is destroyed as N grows and d increases.For fixed d, the first bound term vanishes as N grows; increasing d can then make (1−λ)^d arbitrarily small.Source: §3 · p. 6
For fixed d, low-weight representatives can be listed in O(n^d), and their differences yield multiples of r for a gcd-based order estimate.The gcd argument is heuristic and does not guarantee that the gcd equals the exact order.Source: §3 · p. 6
The conclusion is confined to near-resonant outcomes under the stated one-layer model; it does not establish efficient simulation of the full circuit or exclude fault-tolerant advantage.Source: §3 · p. 6