High Performance Quantum Modular Multipliers

Abstract

We present a novel set of reversible modular multipliers applicable to quantum computing, derived from three classical techniques: 1) traditional integer division, 2) Montgomery residue arithmetic, and 3) Barrett reduction. Each multiplier computes an exact result for all binary input values, while maintaining the asymptotic resource complexity of a single (non-modular) integer multiplier. We additionally conduct an empirical resource analysis of our designs in order to determine the total gate count and circuit depth of each fully constructed circuit, with inputs as large as 2048 bits. Our comparative analysis considers both circuit implementations which allow for arbitrary (controlled) rotation gates, as well as those restricted to a typical fault-tolerant gate set.

References in corpus (7)

• An Open-System Quantum Simulator with Trapped Ions
• Quantum Networks for Elementary Arithmetic Operations
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Fast Quantum Modular Exponentiation
• Adding control to arbitrary unknown quantum operations
• Shor's algorithm on a nearest-neighbor machine
• Quantum Carry-Save Arithmetic

Cited by in corpus (7)

• Quantum circuits design for evaluating transcendental functions based on a function-value binary expansion method
• A quantum circuit simulator and its applications on Sunway TaihuLight supercomputer
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Quantum Control Machine: The Limits of Control Flow in Quantum Programming
• Quasi-Chaotic Oscillators Based on Modular Quantum Circuits
• Halving the width of Toffoli based constant modular addition to n+3 qubits
• Offloading Quantum Computation by Superposition Masking