On the realistic worst case analysis of quantum arithmetic circuits

We provide evidence that commonly held intuitions when designing quantum circuits can be misleading. In particular, we show that 1) reducing the T-count can increase the total depth; 2) it may be beneficial to trade controlled NOTs for measurements in noisy intermediate-scale quantum (NISQ) circuits; 2) measurement-based uncomputation of relative phase Toffoli ancillae can make up to 30% of a circuit's depth; and 4) area and volume cost metrics can misreport the resource analysis. Our findings assume that qubits are and will remain a very scarce resource. The results are applicable for both NISQ and quantum error-corrected protected circuits. Our method uses multiple ways of decomposing Toffoli gates into Clifford+T gates. We illustrate our method on addition and multiplication circuits using ripple-carry. As a byproduct result, we show systematically that for a practically significant range of circuit widths, ripple-carry addition circuits are more resource-efficient than the carry-lookahead addition ones. The methods and circuits were implemented in the open-source QUANTIFY software.