A logarithmic-depth quantum carry-lookahead adder
read the original abstract
We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.
This paper has not been read by Pith yet.
Forward citations
Cited by 11 Pith papers
-
Cultivating logical catalysts for fault-tolerant dyadic phase rotations
A new cultivation protocol prepares reusable logical catalysts as eigenstates of high-period Clifford circuits to implement exact Z^{2^{-b}} phase gates with constant online depth in surface codes.
-
Explicit Block Encoding of Difference-of-Gaussian Operators on a Periodic Grid
Explicit block encoding of the DoG operator achieves constant subnormalization factor λ=2 and a closed-form success probability that scales as O(h^4) on fine grids.
-
Explicit Block Encodings of Discrete Laplacians with Mixed Boundary Conditions
A modular block-encoding framework for finite-difference Laplacians supporting arbitrary combinations of Dirichlet, periodic, and Neumann boundary conditions across dimensions.
-
Magic state cultivation: growing T states as cheap as CNOT gates
Magic state cultivation prepares high-fidelity T states with an order of magnitude fewer qubit-rounds than prior distillation methods by gradually growing them within a surface code under depolarizing noise.
-
A Dual Metastable-State Encoding Architecture for Quantum Processing with $^{171}\mathrm{Yb}$ Atom Arrays
Proposes dual ³P₀/³P₂ metastable encoding in ¹⁷¹Yb atoms to separate storage and fast-operation qubits with coherent shelving for single-species fault-tolerant neutral-atom quantum computing.
-
Fault-Tolerant Quantum Computing with Trapped Ions: The Walking Cat Architecture
A trapped-ion architecture based on LDPC codes and cat-state factories achieves 110 logical qubits and one million T gates per day using 2514 physical qubits, with estimates for Heisenberg model simulation on 100 site...
-
An Oracle-Free Quantum Algorithm for Nonadiabatic Quantum Molecular Dynamics
An oracle-free Trotter-based quantum algorithm for nonadiabatic molecular dynamics achieves circuit depth advantages over QROM architectures and retains T-gate scalability compared to quantum signal processing.
-
A Polylogarithmic-Depth Quantum Multiplier
Quantum integer multiplier with O(log^2 n) circuit depth and T-depth via parallel partial products and binary adder tree in the Clifford+T model.
-
Simulating high-accuracy nuclear motion Hamiltonians using discrete variable representation and Walsh-Hadamard QROM on fault-tolerant quantum computers
A quantum algorithm for rovibrational Hamiltonian simulation on fault-tolerant quantum computers using hybrid DVR and Walsh-Hadamard QROM, claiming exponential resource savings over prior quantum and classical methods.
-
Analog photonic simulator for large-scale transport
Continuous-variable photonic platform with 20,000-mode cluster state simulates advection transport equation, achieving relative errors of 0.8% and 0.92% on first- and second-order moments via homodyne readout.
-
Efficient Gaussian State Preparation in Quantum Circuits
A quantum circuit prepares approximate Gaussian states via single-qubit rotations followed by QFT, achieving high fidelity with optional angle pruning for O(n) gate cost.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.