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 (7)

• 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
• Efficient Networks for Quantum Factoring
• Fast Quantum Modular Exponentiation
• Experimental Realization of an Order-Finding Algorithm with an NMR Quantum Computer
• A Refinement of Shor's Algorithm

Cited by in corpus (10)

• The Variational Quantum Eigensolver: a review of methods and best practices
• Synthesis and Optimization of Reversible Circuits - A Survey
• Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures
• Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Non-Markovian Dynamics of a Single Excitation within Many-Body Dissipative Systems
• Remarks on Quantum Modular Exponentiation and Some Experimental Demonstrations of Shor's Algorithm
• Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks
• Simplified Factoring Algorithms for Validating Small-Scale Quantum Information Processing Technologies
• Quantum Algorithms in Cybernetics