MIT News  August 23, 2024 Researchers at MIT made two improvements to Regev’s quantum factoring algorithm by addressing its space efficiency and its noise-tolerance. They improved the quantum space efficiency of Regev’s algorithm by constructing a quantum factoring circuit using O(n log n) qubits and O(n3/2log n) gates. achieving the best of Shor and Regev gates. Optimization was achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2. This technique allowed them to perform quantum modular exponentiation that was efficient in both space and size without requiring significant precomputation, a […]