Halving the cost of quantum addition

Abstract

We improve the number of T gates needed to perform an n-bit adder from 8n + O(1) to 4n + O(1). We do so via a "temporary logical-AND" construction which uses four T gates to store the logical-AND of two qubits into an ancilla and zero T gates to later erase the ancilla. This construction is equivalent to one by Jones, except that our framing makes it clear that the technique is far more widely applicable than previously realized. Temporary logical-ANDs can be applied to integer arithmetic, modular arithmetic, rotation synthesis, the quantum Fourier transform, Shor's algorithm, Grover oracles, and many other circuits. Because T gates dominate the cost of quantum computation based on the surface code, and temporary logical-ANDs are widely applicable, this represents a significant reduction in projected costs of quantum computation. In addition to our n-bit adder, we present an n-bit controlled adder circuit with T-count of 8n + O(1), a temporary adder that can be computed for the same cost as the normal adder but whose result can be kept until it is later uncomputed without using T gates, and discuss some other constructions whose T-count is improved by the temporary logical-AND.

6 pages, 5 figures

References in corpus (8)

• Surface codes: Towards practical large-scale quantum computation
• Fault-tolerant quantum computation with high threshold in two dimensions
• Topological fault-tolerance in cluster state quantum computation
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• A new quantum ripple-carry addition circuit
• Novel constructions for the fault-tolerant Toffoli gate
• T-count Optimized Design of Quantum Integer Multiplication

Cited by in corpus (118)

• Quantum Chemistry in the Age of Quantum Computing
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• A random compiler for fast Hamiltonian simulation
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Building a fault-tolerant quantum computer using concatenated cat codes
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Magic State Distillation: Not as Costly as You Think
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Quantum Algorithms for Simulating the Lattice Schwinger Model
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Lower bounds on the non-Clifford resources for quantum computations
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Black-box quantum state preparation without arithmetic
• Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• A randomized quantum algorithm for statistical phase estimation
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Oracles for Gauss's law on digital quantum computers
• Early fault-tolerant simulations of the Hubbard model
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Quantum Algorithms for Jet Clustering
• Applying quantum algorithms to constraint satisfaction problems
• Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory
• Efficient quantum computation of molecular forces and other energy gradients
• Initial state preparation for quantum chemistry on quantum computers
• Block-encoding structured matrices for data input in quantum computing
• Constrained Optimization via Quantum Zeno Dynamics
• Low cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problem
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• Parallelising the Queries in Bucket Brigade Quantum RAM
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• Quantum Computation for Periodic Solids in Second Quantization
• Shorter quantum circuits via single-qubit gate approximation
• A polynomial time and space heuristic algorithm for T-count
• ZX-calculus for the working quantum computer scientist
• Resource-Optimized Fermionic Local-Hamiltonian Simulation on Quantum Computer for Quantum Chemistry
• Low-Overhead Transversal Fault Tolerance for Universal Quantum Computation
• Quantum circuits design for evaluating transcendental functions based on a function-value binary expansion method
• Fast Black-Box Quantum State Preparation
• Gate-based Quantum Computing for Protein Design
• Systems Architecture for Quantum Random Access Memory
• Exponential improvements in the simulation of lattice gauge theories using near-optimal techniques
• Synthesizing efficient circuits for Hamiltonian simulation
• Quantum Simulations of Chemistry in First Quantization with any Basis Set
• Fault-tolerant quantum computation of molecular observables
• Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
• Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
• Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation
• Rise of conditionally clean ancillae for efficient quantum circuit constructions
• The prospects of Monte Carlo antibody loop modelling on a fault-tolerant quantum computer
• Fast Black-Box Quantum State Preparation Based on Linear Combination of Unitaries
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Quantum Financial Modeling on Noisy Intermediate-Scale Quantum Hardware: Random Walks using Approximate Quantum Counting
• Graphical Fourier Theory and the Cost of Quantum Addition
• Implementing fault-tolerant non-Clifford gates using the [[8,3,2]] color code
• Option pricing under stochastic volatility on a quantum computer
• Leveraging Qubit Loss Detection in Fault Tolerant Quantum Algorithms
• The phase/state duality in reversible circuit design
• Solving reaction dynamics with quantum computing algorithms
• Black-Box Quantum State Preparation with Inverse Coefficients
• TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry
• Code switching revisited: Low-overhead magic state preparation using color codes
• Improved precision scaling for simulating coupled quantum-classical dynamics
• Quantum simulation of fermionic systems using hybrid digital-analog quantum computing approach
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• End-to-end complexity for simulating the Schwinger model on quantum computers
• A Quantum Search Decoder for Natural Language Processing
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• T-count and Qubit Optimized Quantum Circuit Designs of Carry Lookahead Adder
• Cost-optimal single-qubit gate synthesis in the Clifford hierarchy
• Resource-optimized fault-tolerant simulation of the Fermi-Hubbard model and high-temperature superconductor models
• Windowed quantum arithmetic
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• Ladder Operator Block-Encoding
• Trotter simulation of vibrational Hamiltonians on a quantum computer
• CNOT-count optimized quantum circuit of the Shor's algorithm
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Learning from physics experiments, with quantum computers: Applications in muon spectroscopy
• T-count Optimized Quantum Circuits for Bilinear Interpolation
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Approximate encoded permutations and piecewise quantum adders
• Unification of Finite Symmetries in Simulation of Many-body Systems on Quantum Computers
• Optimizing T and CNOT Gates in Quantum Ripple-Carry Adders and Comparators
• Fault-tolerance in qudit circuit design
• Quantum Carry Lookahead Adders for NISQ and Quantum Image Processing
• Phase estimation with partially randomized time evolution
• Quantum state preparation via piecewise QSVT
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit
• Fault-tolerant quantum simulation of generalized Hubbard models
• A CCCZ gate performed with 6 T gates
• Quantum block lookahead adders and the wait for magic states
• Spectral sparsification of matrix inputs as a preprocessing step for quantum algorithms
• Quantum Theory from Principles, Quantum Software from Diagrams
• Role of Riemannian geometry in double-bracket quantum imaginary-time evolution
• Halving the cost of quantum multiplexed rotations
• Symmetric channel verification for purifying noisy quantum channels
• Catalytic $z$-rotations in constant $T$-depth
• Performance Evaluations of Signed and Unsigned Noisy Approximate Quantum Fourier Arithmetic
• Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems
• Transversal architecture for megaquop-scale quantum simulation with neutral atoms
• Quantum phase estimation with optimal confidence interval using three control qubits
• Quantum Arithmetic Algorithms: Implementation, Resource Estimation, and Comparison
• Transversal AND in Quantum Codes
• Formal Verification of Quantum Ancilla Safety
• Benincasa-Dowker-Glaser causal set actions by quantum counting
• Quantum oracles for the finite element method
• Controlling distilleries in fault-tolerant quantum circuits: problem statement and analysis towards a solution
• Quantum Simulation of Nuclear Dynamics in First Quantization