Measurement-based uncomputation (MBU) is a technique used to perform probabilistic uncomputation of quantum circuits. We formalize this technique for the case of single-qubit registers, and we show applications to modular arithmetic. Using MBU, we reduce Toffoli count and depth by 10% to 15% for modular adders based on the architecture of [1], and by almost 25% for modular adders based on the architecture of [2]. Our results have the potential to improve other circuits for modular arithmetic, such as modular multiplication and modular exponentiation, and can find applications in quantum cryptanalysis.

Windowed arithmetic is a technique for reducing the cost of quantum arithmetic circuits with space-time trade-offs using memory queries to precomputed tables. It can reduce the asymptotic cost of modular exponentiation from $\mathcal{O}\left(n^{2}\right)$ to $\mathcal{O}\left(n^{2} / \log ^{2} n\right)$ operations, resulting in the current state-of-the-art compilations of quantum attacks against modern cryptography. We introduce several optimizations to windowed arithmetic. Notably, we effect an approximate $50 \%$ reduction in the costs of uncomputing memory lookups in quantum factoring applications. We validate our optimizations by improving the gate count of quantum attacks against public-key cryptography by $1.5 \%$ to $3.4 \%$, depending on the key size. We also enable a $16 \%$ runtime reduction at the cost of a $12 \%$ increase in qubit count. Our techniques can be used to reduce the complexity of not only factoring algorithms but also a wide range of quantum algorithms that rely on windowed arithmetic.