An Efficient Quantum Factoring Algorithm
Oded Regev
Abstract
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. The correctness of the algorithm relies on a certain number-theoretic conjecture. It is currently not clear if the algorithm can lead to improved physical implementations in practice.
Topics & Concepts
CorrectnessFactoringConjectureQuantum computerAlgorithmComputer scienceQuantum algorithmPolynomialImplementationQuantumDiscrete mathematicsMathematicsQuantum mechanicsPhysicsProgramming languageFinanceMathematical analysisEconomicsQuantum Computing Algorithms and ArchitectureQuantum Information and CryptographyCryptography and Data Security