Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation
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 paper, the authors develop such optimizations in a bottom-up fashion, starting with most convenient C values. When zero-initialized ancilla registers are available, they reduce the search for compact circuits to a shortest-path problem.
Subscribe to the Innovation Insider Newsletter
Catch up on the latest tech innovations that are changing the world, including IoT, 5G, the latest about phones, security, smart cities, AI, robotics, and more. Delivered Tuesdays and Fridays