Noise breaks Shor's quantum factoring advantage in circuits

Resonance Breaking in Noisy Shor's Algorithm

Computational ComplexityInformation Theory

Summary

Shor's algorithm is a famous quantum method that can factor large numbers much faster than traditional computers. This paper shows that even a tiny amount of noise in the quantum circuit can ruin the special patterns needed for the algorithm to work well, causing its speed advantage to disappear. The authors also present a classical method that can simulate part of the algorithm under noise conditions, meaning the quantum advantage is lost. Their work suggests that noise can fundamentally limit how useful some quantum algorithms are in practice.

What this means in practice

  • For quantum hardware engineers: Design error correction and noise mitigation techniques focused on preventing resonance breaking in quantum circuits running Shor's algorithm.
  • For cryptography system designers: Reassess security assumptions relying on quantum factoring speedups given noise-induced breakdown of Shor's algorithm performance.

A theory result. No direct application yet.

Authors

Zhengwei Liu

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 $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.