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.

12 pages, 1 table, 5 figures, Q# source code

References in corpus (6)

• Surface codes: Towards practical large-scale quantum computation
• A new quantum ripple-carry addition circuit
• Time-optimal quantum computation
• 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