  Quantum computing has shown tremendous promise in addressing complex
computational problems, yet its practical realization is hindered by the
limited availability of qubits for computation. Recent advancements in quantum
hardware have introduced mid-circuit measurements and resets, enabling the
reuse of measured qubits and significantly reducing the qubit requirements for
executing quantum algorithms. In this work, we present a systematic study of
dynamic quantum circuit compilation, a process that transforms static quantum
circuits into their dynamic equivalents with a reduced qubit count through
qubit-reuse. We establish the first general framework for optimizing the
dynamic circuit compilation via graph manipulation. In particular, we
completely characterize the optimal quantum circuit compilation using binary
integer programming, provide efficient algorithms for determining whether a
given quantum circuit can be reduced to a smaller circuit and present heuristic
algorithms for devising dynamic compilation schemes in general. Furthermore, we
conduct a thorough analysis of quantum circuits with practical relevance,
offering optimal compilations for well-known quantum algorithms in quantum
computation, ansatz circuits utilized in quantum machine learning, and
measurement-based quantum computation crucial for quantum networking. We also
perform a comparative analysis against state-of-the-art approaches,
demonstrating the superior performance of our methods in both structured and
random quantum circuits. Our framework lays a rigorous foundation for
comprehending dynamic quantum circuit compilation via qubit-reuse, bridging the
gap between theoretical quantum algorithms and their physical implementation on
quantum computers with limited resources.
