Quantum block lookahead adders and the wait for magic states

Abstract

We improve the Toffoli count of low depth quantum adders, and analyze how their spacetime cost reacts to having a limited number of magic state factories. We present a block lookahead adder that parallelizes across blocks of bits of size $b$, instead of over all bits. The block lookahead adder achieves a Toffoli count of $3n+5n/b$ for out of place addition (vs $4n$ in previous work by Thapliyal et al) and $5n+8n/b$ for in place addition (vs $7n$ in previous work by Thapliyal et al). The tradeoff is that the reaction depth of these circuits depends linearly on $b$, and they use additional workspace. We estimate the spacetime volume of these adders, and adders from previous work, for various register sizes and factory counts under plausible assumptions for a large scale quantum computer based on the surface code and superconducting qubits.

arXiv comment12 pages, 1 table, 5 figures, Q# source code

References in corpus (11)

• Surface codes: Towards practical large-scale quantum computation
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• A new quantum ripple-carry addition circuit
• Halving the cost of quantum addition
• Addition on a Quantum Computer
• Quantum Carry-Save Arithmetic
• Time-optimal quantum computation
• Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
• Flexible layout of surface code computations using AutoCCZ states
• T-count and Qubit Optimized Quantum Circuit Designs of Carry Lookahead Adder
• Approximate encoded permutations and piecewise quantum adders

Cited by in corpus (1)

• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules