PreprintarXiv licencearXiv
A Sharp Noise Threshold for Shor's Quantum Factoring and Discrete Log Algorithms
Abstract
We study the asymptotic behavior of Shor's quantum factoring and discrete log algorithms when noise affects the precise controlled rotation gates in their quantum Fourier transforms. Improving the results of Cai (2024) and Cai and Young (2025), we identify a sharp and vanishingly small noise threshold. If the noise level lies below this threshold, then the two algorithms succeed in expected polynomial time. If the noise level exceeds this threshold, then the algorithms provably fail to solve their respective problems in expected polynomial time when the underlying primes belong to a set of positive density.
Related
- Fast Quantum Algorithms for Learning Linear Threshold Functions
- Factoring six-digit integers with superconducting quantum circuits
- Streaming Regev's Quantum Factoring Algorithm
- Sharp universal death of entanglement threshold for Pauli Hamiltonians
- Operator Michelson Contrast: Logarithmic Parametrisation, Subadditivity, and a Sharp Noncommutativity Threshold
BibTeX
@misc{cai2026sharp,
title = {{A Sharp Noise Threshold for Shor's Quantum Factoring and Discrete Log Algorithms}},
author = {Jin-Yi Cai and Ben Young},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.24316},
eprint = {2609.24316},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24316},
}
RIS
TY - UNPB
TI - A Sharp Noise Threshold for Shor's Quantum Factoring and Discrete Log Algorithms
AU - Jin-Yi Cai
AU - Ben Young
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.24316
UR - https://arxiv.org/abs/2609.24316
AB - We study the asymptotic behavior of Shor's quantum factoring and discrete log algorithms when noise affects the precise controlled rotation gates in their quantum Fourier transforms. Improving the results of Cai (2024) and Cai and Young (2025), we identify a sharp and vanishingly small noise threshold. If the noise level lies below this threshold, then the two algorithms succeed in expected polynomial time. If the noise level exceeds this threshold, then the algorithms provably fail to solve their respective problems in expected polynomial time when the underlying primes belong to a set of positive density.
ER -