Quantum Carry-Save Arithmetic

1998/08/27 by Phil Gossett, Gossett, Phil · 1 citation
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/9808061

12 pages, embedded figures. Corrected typos, added clarifications, improved result

arxiv created 1998/08/30 · arxiv updated 2009/12/01

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³) to O(N log N) at a cost of increasing the number of qubits required from O(N) to O(N²).

Cited by

• Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions

Related

• Halving the cost of quantum addition
• Architecture of a Quantum Multicomputer Optimized for Shor's Factoring Algorithm
• Fast quantum modular exponentiation
• High Performance Quantum Modular Multipliers
• The PPKN Gate: An Optimal 1-Toffoli Input-Preserving Full Adder for Quantum Arithmetic