  Compiling high-level quantum programs to machines that are size constrained
(i.e. limited number of quantum bits) and time constrained (i.e. limited number
of quantum operations) is challenging. In this paper, we present SQUARE
(Strategic QUantum Ancilla REuse), a compilation infrastructure that tackles
allocation and reclamation of scratch qubits (called ancilla) in modular
quantum programs. At its core, SQUARE strategically performs uncomputation to
create opportunities for qubit reuse.
  Current Noisy Intermediate-Scale Quantum (NISQ) computers and forward-looking
Fault-Tolerant (FT) quantum computers have fundamentally different constraints
such as data locality, instruction parallelism, and communication overhead. Our
heuristic-based ancilla-reuse algorithm balances these considerations and fits
computations into resource-constrained NISQ or FT quantum machines, throttling
parallelism when necessary. To precisely capture the workload of a program, we
propose an improved metric, the "active quantum volume," and use this metric to
evaluate the effectiveness of our algorithm. Our results show that SQUARE
improves the average success rate of NISQ applications by 1.47X. Surprisingly,
the additional gates for uncomputation create ancilla with better locality, and
result in substantially fewer swap gates and less gate noise overall. SQUARE
also achieves an average reduction of 1.5X (and up to 9.6X) in active quantum
volume for FT machines.
