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

By Stéphane Beauregard. Quantum information & computation, 2002

305 citations recorded by the source corpus.

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 0(n3lg(n)) elementary quantum gates in a depth of 0(n3) 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/43e6b93fb0cc0819908d3ceabf70d642a1dd1252

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Toward the first quantum simulation with quantum speedup (2017, background): “led-Zgate; the former needs two Tgates and the latter needs none, so the total number of Tgates is approximately 16 3 n 3. Note that it is possible to factor an n-bit number using only about 2nqubits [8, 33], but at the expense of a signiﬁcantly higher gate count. Similarly, gate counts for quantum ”
Shor's discrete logarithm quantum algorithm for elliptic curves (2003, methodology): “Proposals have been made [4, 5] for optimised implementations of the quantum factoring algorithm, in particular for minimising the number of qubits needed.”
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2019, methodology): “2 ≈ 217n2 140 550 1200 62 260 710 Beauregard 2002 [6] 2n+ 3 144n3 lgn+O(n2 lgn) 576n3 lg2 n+O(n3 lgn) 62000 600000 2200000 32000 380000 1700000 Fowler et al.”
ProjectQ: An Open Source Software Framework for Quantum Computing (2016, methodology): “Thus, at a lower level, (double- or single-) controlled constant-adders are performed.”
Guide to Elliptic Curve Cryptography (2004, background): “In contrast, Beauregard [31] showed that k-bit integers can be efficiently factored on a K -qubit quantum computer where K ≈ 2k.”
Post-quantum cryptography (2008, unknown): “For example, a variant of Shor’s algorithm by Beauregard [3] uses O ( n 3 log n ) operations on 2 n + 3 qubits if N = pq ﬁts into n bits.”
An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures (2017, background): “6 Besides that, benchmarks that are relevant for existing quantum algorithms such as quantum ripple-carry adders (based on the realization proposed in [37] and denoted adder ) and small versions of Shor’s algorithm (based on the realization proposed in [38] and denoted shor ) have been considered.”