Fetching the paper…
Reading the bibliography…
We show that $n$-bit integers can be factorized by independently running a quantum circuit with $\tilde{O}(n^{3/2})$ gates for $\sqrt{n}+4$ times, and then using polynomial-time classical post-processing.
On the evaluation of powers and monomials
Nicholas Pippenger · 1980
Earlier work this paper cites.
New bounds in some transference theorems in the geometry of numbers
Wojciech Banaszczyk · 1993
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Peter W. Shor · 1999
Earlier work this paper cites.
Fast parallel circuits for the quantum Fourier transform
Richard Cleve and John Watrous · 2000
Earlier work this paper cites.
The expected number of random elements to generate a finite abelian group
Carl Pomerance · 2001
Earlier work this paper cites.
Using fewer qubits in Shor’s factorization algorithm via simultaneous Diophantine approximation
Jean-Pierre Seifert · 2001
Earlier work this paper cites.
An approximate Fourier transform useful in quantum factoring, 2002
Don Coppersmith · 2002
Cited alongside, same era.
Creating superpositions that correspond to efficiently integrable probability distributions, 2002
Lov Grover and Terry Rudolph · 2002
Cited alongside, same era.
Prime numbers
Richard Crandall and Carl Pomerance · 2005
Cited alongside, same era.
Finding short lattice vectors within Mordell’s inequality
Nicolas Gama and Phong Q. Nguyen · 2008
Cited alongside, same era.
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2009
Cited alongside, same era.
Quantum algorithms for computing short discrete logarithms and factoring RSA integers
Martin Ekerå and Johan Håstad · 2017
Cited alongside, same era.
Polynomial time bounded distance decoding near Minkowski’s bound in discrete logarithm lattices
Léo Ducas and Cécile Pierrot · 2019
Later among the works it cites.
On post-processing in the quantum algorithm for computing short discrete logarithms
Martin Ekerå · 2020
Later among the works it cites.
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Craig Gidney and Martin Ekerå · 2021
Later among the works it cites.
Integer multiplication in time O ( n log n ) O(n\log n)
David Harvey and Joris van der Hoeven · 2021
Later among the works it cites.
Extending regev’s factoring algorithm to compute discrete logarithms, 2023
Martin Ekerå and Joel Gärtner · 2023
Closest in time.
Optimizing space in regev’s factoring algorithm, 2023
Seyoon Ragavan and Vinod Vaikuntanathan · 2023
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Closest in time.