Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation

Understand

Reversible circuits for modular multiplication $Cx$%$M$ with $x<M$ arise as components of modular exponentiation in Shor's quantum number-factoring algorithm.

• However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific $C$ and $M$ values.
• In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient $C$ values.
• When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem.