  Quantum computers promise to perform certain computations exponentially
faster than any classical device. Precise control over their physical
implementation and proper shielding from unwanted interactions with the
environment become more difficult as the space/time volume of the computation
grows. Code optimization is thus crucial in order to reduce resource
requirements to the greatest extent possible. Besides manual optimization,
previous work has adapted classical methods such as constant-folding and common
subexpression elimination to the quantum domain. However, such
classically-inspired methods fail to exploit certain optimization opportunities
across subroutine boundaries, limiting the effectiveness of software reuse. To
address this insufficiency, we introduce an optimization methodology which
employs annotations that describe how subsystems are entangled in order to
exploit these optimization opportunities. We formalize our approach, prove its
correctness, and present benchmarks: Without any prior manual optimization, our
methodology is able to reduce, e.g., the qubit requirements of a 64-bit
floating-point subroutine by $34\times$.
