A logarithmic-depth quantum carry-lookahead adder
By Thomas G. Draper, Samuel Kutin, Eric M. Rains, Krysta Marie Svore. Quantum information & computation, 2004
328 citations recorded by the source corpus.
We present an efficient addition circuit, borrowing techniques from classical carry-lookahead arithmetic. Our quantum carry-lookahead (QCLA) adder accepts two n-bitnumbers and adds them in O(log n) depth using O(n) ancillary qubits. We present bothin-place and out-of-place versions, as well as versions that add modulo 2n and modulo2n - 1. Previously, the linear-depth ripple-carry addition circuit has been the methodof choice. Our work reduces the cost of addition dramatically with only a slight increasein the number of required qubits. The QCLA adder can be used within current modularmultiplication circuits to reduce substantially the run-time of Shor's algorithm.
View Paper: https://www.semanticscholar.org/paper/b96e881f8d525bf8b8e62804ae40f2debb53d5cc
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Christopher R. Monroe
- Luming Duan
- A. Ruthven
- Robert Raussendorf
- Peter Maunz
- Jungsang Kim
- K. Brown
- Jakub Marecek
Citations in the corpus
- Quantum Computing for Finance: State-of-the-Art and Future Prospects (2020, background): “, a comparator that takes a fixed value to compare to as a classical input, can be based on adder circuits [53].”
- Large-scale modular quantum-computer architecture with atomic memory and photonic interconnects (2012, methodology): “Under these circumstances, the depth of the n-bit in-place adder circuit is given by [50] blog2 nc+blog2(n−1)c+blog2 n 3 c+blog2 n− 1 3 c+14, (1)”
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2019, methodology): “The major benefit of oblivious carry runways, compared to previous techniques for reducing the depth of addition such as Draper et al’s logarithmic depth carry-lookahead adder [38], is that oblivious carry runways can be introduced gradually without incurring large overheads.”
- Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning (2013, unknown): “9 QCLA-Com7 [11] 24 215 203 73 583 95 73 0.”