HackerPapers

arXiv:1301.7007quant-ph

Pretending to factor large numbers on a quantum computer

John A. Smolin, Graeme Smith, Alex Vargo

Abstract

Shor's algorithm for factoring in polynomial time on a quantum computer\cite{Shor} gives an enormous advantage over all known classical factoring algorithm. We demonstrate how to factor products of large prime numbers using a compiled version of Shor's quantum factoring algorithm. Our technique can factor all products of $p,q$ such that $p,q$ are unequal primes greater than two, runs in constant time, and requires only two coherent qubits. This illustrates that the correct measure of difficulty when implementing Shor's algorithm is not the size of number factored, but the length of the period found.

arXiv comments
15 pages including 3 figures and supplementary material
Journal reference
Nature 499, 163-165 (2013)
DOI
doi:10.1038/nature12290
Subjects
quant-phQuantum Physics

On Hacker News

Linked by 5 identifiable commenters in 7 comments across 7 threads, from Apr 2013 to Jan 2026.

Comments linking this paper, per year.

Discussed in comments7 threads

  1. 2026 Predictions Scorecard 1 comment

    • > By late 2024 the biggest numbers that had been factored by an actual digital quantum computer had 35 bits (citing https://arxiv.org/pdf/2410.14397v1 ) This is incorrect. The cited reference says "N <= 35". That N is the number being factored, not the number of bits in the…

      StrilancView on HNParent context

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

    • They were illegitimate instances of Shor according to [1]: > Of course this should not be considered a serious demonstration of Shor’s algorithm. It does, however, illustrate the danger in “compiled” demonstrations of Shor’s algorithm. To varying degrees, all previous…

      trompView on HNParent context

  3. Ask HN: What has quantum computing achieved so far? 1 comment

    • Factoring 15 with quantum computers happened nearly 22 years ago[1]. The current record for factoring, with just Shor's and no minimization, is 21. Like you said, a lot of the hyped ones aren't practical. It's not that hard to pretend to factor large numbers on a quantum…

      iamawackoView on HNParent context

  4. Quantum Computer Datasheet [pdf] 1 comment

    • It depends how much circuit optimization you consider to be cheating. The hard part of Shor's algorithm is computing `pow(g, e, modulus=N)` where g is a uniformly random number, e is a uniformly superposed number, and N is the number you want to factor. But note that 15 is one…

      StrilancView on HNParent context

  5. IBM will soon launch a 53-qubit quantum computer 1 comment

    • For those who are interested in the papers about this topic: https://arxiv.org/abs/1301.7007 "Pretending to factor large numbers on a quantum computer (2013)" "Of course this should not be considered a serious demonstration of Shor’s algorithm. It does, however, illustrate the…

      acqqView on HNParent context

  6. Design of a silicon quantum computer chip 1 comment

    • Two excellent questions. Regarding claims of factoring small numbers: First note that error correction becomes exponentially more important for longer computations. Second, see this https://arxiv.org/abs/1301.7007 Regarding building a tower of ever less noisy qubits: it turns…

      jessriedelView on HNParent context

  7. Lockheed Martin pays $10M for D-Wave's Quantum Computer 1 comment

    • > For the record, this is also true for every quantum computer in existence. Yes, I'm well aware. The difference from D-wave is that the labs at IBM, UCSB, and Yale haven't claimed they've built a quantum computer (mostly). > What is clear though, is that quantum computers have…

      jessriedelView on HNParent context

Submitted to Hacker News

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