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 result that may be useful for other quantum algorithms. A key ingredient was an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. This implementation worked with only black-box access to any quantum circuit for out-of-place modular multiplication, which they believed was a result of potentially broader interest. They also showed that Regev’s classical postprocessing procedure could be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev’s analysis of this classical postprocessing procedure required all runs to be successful. According to the researchers they achieved this using lattice reduction techniques to detect and filter out corrupt samples… read more. Open Access TECHNICAL ARTICLE
This new algorithm requires fewer quantum building blocks… Credit: iStock