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

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

Resource Details

Provided by:
Cornell University
Topic:
Hardware
Format:
PDF