Quantum block lookahead adders and the wait for magic states

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.