Welcome to the resource topic for 2023/1501
Title:
Optimizing Space in Regev’s Factoring Algorithm
Authors: Seyoon Ragavan, Vinod Vaikuntanathan
Abstract:We improve the space efficiency of Regev’s quantum factoring algorithm [Reg23] while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using O(n \log n) qubits and O(n^{3/2} \log n) gates. In contrast, Regev’s circuit requires O(n^{3/2}) qubits, while Shor’s circuit requires O(n^2) gates. As with Regev, to factor an n-bit integer N, one runs this circuit independently \approx \sqrt{n} times and apply Regev’s classical post-processing procedure.
Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2.
ePrint: https://eprint.iacr.org/2023/1501
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 .