Fast quantum integer multiplication with zero ancillas

Understand

The multiplication of superpositions of numbers is a core operation in many quantum algorithms.

• The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs.
• Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits.
• In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits -- the only qubits involved are the input and output registers themselves.