Halving the width of Toffoli-based constant modular addition to n+3 qubits

We present an arithmetic circuit performing constant modular addition having O(n) depth of Toffoli gates and using a total of n+3 qubits. This is an improvement by a factor of two compared to the width of the state-of-the-art Toffoli-based constant modular adder. The advantage of our adder, compared to the ones operating in the Fourier basis, is that it does not require small-angle rotations and their Clifford+T decomposition. Our circuit uses a recursive adder combined with the modular addition scheme proposed by Vedral et al. The circuit is implemented and verified exhaustively with quantify, an open-sourced framework. We also report on the Clifford+T cost of the circuit.