Faster Quantum Number Factoring via Circuit Synthesis

Abstract

A major obstacle to implementing Shor's quantum number-factoring algorithm is the large size of modular-exponentiation circuits. We reduce this bottleneck by customizing reversible circuits for modular multiplication to individual runs of Shor's algorithm. Our circuit-synthesis procedure exploits spectral properties of multiplication operators and constructs optimized circuits from the traces of the execution of an appropriate GCD algorithm. Empirically, gate counts are reduced by 4-5 times, and circuit latency is reduced by larger factors.

4 pages, 2 figures, 1 table

References in corpus (4)

• Shor's quantum factoring algorithm on a photonic chip
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Fast Quantum Modular Exponentiation