HackerPapers

arXiv:2306.10072quant-ph

Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise

Jin-Yi Cai

Abstract

We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form $pq$ when the noise exceeds a vanishingly small level in terms of $n$ -- the number of bits of the integer to be factored, where $p$ and $q$ are from a well-defined set of primes of positive density. We further prove that with probability $1 - o(1)$ over random prime pairs $(p,q)$, Shor's factoring algorithm does not factor numbers of the form $pq$, with the same level of random noise present.

arXiv comments
Journal reference
SCIENCE CHINA Information Sciences 2024
DOI
doi:10.1007/s11432-023-3961-3
Subjects
quant-phQuantum Physics cs.DMDiscrete Mathematics

On Hacker News

Linked by 4 identifiable commenters in 5 comments across 4 threads, from Apr 2024 to Jul 2025.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. Conceptual synaesthesia as cognitive literacy 1 comment

    • Lemonnier only cites pp22 A first approach to programming with quantum effects is the quantum λ-calculus [SV09]. Nevertheless, that language does not handle quantum programming as an algebraic effect, since it requires measurement into classical data to control the flow of…

      gsf_emergency_2View on HNParent context

  2. The case against Google's claims of "quantum supremacy" 1 comment

    • There's a specific view (as I understand it) that QFT's don't scale https://arxiv.org/abs/2306.10072 but some folks seem to dismiss this for reasons I just don't grok at all.

      sgt101View on HNParent context

  3. What You Shouldn't Know About Quantum Computers 1 comment

    • I have forgotten the source where I stumbled on the requirement for a qubit error rate to run the Shor algorithm. I would greatly value it if someone could put a key reference here. A recent result considers a generic error model and a subclass for particular kinds of prime…

      JanisErdmanisView on HNParent context

  4. Quantum Algorithms for Lattice Problems 2 comments

    • Yeah, for Shor's algorithm to factor an integer of order 2^k you need controlled phase gates with phases roughly order 2^{-k} (very roughly, with some caveats, but lets just say you need some small ones) these very small phase gates are susceptible to even very small errors.…

      eigenketView on HNParent context

    • I'm not sure that you are correct. I've tried to read https://arxiv.org/abs/2306.10072 in the last day and if my reading is right (I am very stretched by this stuff so I am very happy to be corrected) then no amount of error correction will rescue Shor's - only zero error phase…

      sgt101View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.