Quantum Carry-Save Arithmetic

Abstract

This paper shows how to design efficient arithmetic elements out of quantum gates using "carry-save" techniques borrowed from classical computer design. This allows bit-parallel evaluation of all the arithmetic elements required for Shor's algorithm, including modular arithmetic, deferring all carry propagation until the end of the entire computation. This reduces the quantum gate delay from O(N^3) to O(N log N) at a cost of increasing the number of qubits required from O(N) to O(N^2).

arXiv comment12 pages, embedded figures. Corrected typos, added clarifications, improved result

References in corpus (2)

• Elementary gates for quantum computation
• Quantum Networks for Elementary Arithmetic Operations

Cited by in corpus (11)

• Addition on a Quantum Computer
• Fast Quantum Modular Exponentiation
• Requirements for fault-tolerant factoring on an atom-optics quantum computer
• Oracles for Gauss's law on digital quantum computers
• Quantum arithmetic operations based on quantum Fourier transform on signed integers
• High Performance Quantum Modular Multipliers
• Towards Large-Scale Quantum Computation
• Architecture-Dependent Execution Time of Shor's Algorithm
• Optimal Estimation of States in Quantum Image Processing
• Quantum block lookahead adders and the wait for magic states
• A Quantum Performance Simulator based on fidelity and fault-path counting