Welcome to the resource topic for 2017/352
Title:
A low-resource quantum factoring algorithm
Authors: Daniel J. Bernstein, Jean-François Biasse, Michele Mosca
Abstract:In this paper, we present a factoring algorithm that, assuming standard heuristics, uses just (\log N)^{2/3+o(1)} qubits to factor an integer N in time L^{q+o(1)} where L = \exp((\log N)^{1/3}(\log\log N)^{2/3}) and q=\sqrt[3]{8/3}\approx 1.387. For comparison, the lowest asymptotic time complexity for known pre-quantum factoring algorithms, assuming standard heuristics, is L^{p+o(1)} where p>1.9. The new time complexity is asymptotically worse than Shor’s algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement it sooner.
ePrint: https://eprint.iacr.org/2017/352
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .