Resonance Breaking in Noisy Shor's Algorithm
Abstract
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 4n 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 λ, for any Hamming weight d, we obtain corresponding measurement rate bounded by 2(1−λ)d for higher frequency terms and by O(nd)/2n/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(nd) to substitute the low frequency contribution.
Related
- Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem
- Beyond Shor's Conjecture: Optimal Quantum Measurements at Fixed Error
- Superselection Rigidity of Topological Calderbank--Shor--Steane Codes: From Koszul-Complex Models to Nonsplit Extensions
- The Capacity of the Noisy Torn Paper Channel and the Noisy Shuffling Channel
- Universal classical and quantum fluctuations in the large deviations of current of noisy quantum systems: Quantum symmetric simple exclusion and inclusion processes
BibTeX
@misc{liu2026resonance,
title = {{Resonance Breaking in Noisy Shor's Algorithm}},
author = {Zhengwei Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37636},
eprint = {2609.37636},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37636},
}
RIS
TY - UNPB
TI - Resonance Breaking in Noisy Shor's Algorithm
AU - Zhengwei Liu
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37636
UR - https://arxiv.org/abs/2609.37636
AB - 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 λ, for any Hamming weight d, we obtain corresponding measurement rate bounded by 2(1−λ)^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.
ER -