HackerPapers

arXiv:quant-ph/0205095quant-ph

Circuit for Shor's algorithm using 2n+3 qubits

Stephane Beauregard

Abstract

We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored. Keywords: Factorization, quantum circuits, modular arithmetics

arXiv comments
14 pages, 10 figures, revised January 24, 2003
Journal reference
Quantum Information and Computation, Vol. 3, No. 2 (2003) pp. 175-185
DOI
Subjects
quant-phQuantum Physics

On Hacker News

Linked by 4 identifiable commenters in 4 comments across 4 threads, from Dec 2017 to Apr 2025.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. Fujitsu and RIKEN develop world-leading 256-qubit sup quantum computer 1 comment

    • > Is there some minimum number of qubits at which some minimum viable quantum-supreme task can theoretically be achieved? That is a very broad range of possibilities, so allow me to narrow it to cryptography. I am by no means an expert on this, but I spent the weekend reading…

      ryaoView on HNParent context

  2. Google's threat model for post-quantum cryptography 1 comment

    • From [1]: > We implemented the algorithm on IBM quantum processors using only 5 qubits Last December, a team based out of Harvard demonstrated the ability to scale up to 48 logical qubits: https://arxiv.org/abs/2312.03982 It has been shown that, to factor an integer with n bits…

      smburdickView on HNParent context

  3. Shor, I’ll do it (2007) 1 comment

    • > and how many are needed According to this paper, one can use 2n+3 qubits to factor an integer with n bits: https://arxiv.org/abs/quant-ph/0205095 Those would be perfect qubits, if you use noisy qubits you'd need many more (maybe a factor of 1000x more), since quantum error…

      FartyMcFarterView on HNParent context

  4. Getting the World Quantum Ready 1 comment

    • According to this paper: https://arxiv.org/abs/quant-ph/0205095 You can implement Shor's algorithm to factor an N-bit number with just 2n+3 qubits. So the 20 qubit processor would be able to factor any 8 bit number (not necessarily faster than a classical computer could, or even…

      archgoonView on HNParent context

Submitted to Hacker News

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