  Numerous quantum algorithms require the use of quantum error correction to
overcome the intrinsic unreliability of physical qubits. However, error
correction imposes a unique performance bottleneck, known as T-complexity, that
can make an implementation of an algorithm as a quantum program run more slowly
than on idealized hardware. In this work, we identify that programming
abstractions for control flow, such as the quantum if-statement, can introduce
polynomial increases in the T-complexity of a program. If not mitigated, this
slowdown can diminish the computational advantage of a quantum algorithm.
  To enable reasoning about the costs of control flow, we present a cost model,
using which a developer can analyze the T-complexity of a program under quantum
error correction and pinpoint the sources of slowdown. We also present a set of
program-level optimizations, using which a developer can rewrite a program to
reduce its T-complexity, predict the T-complexity of the optimized program
using the cost model, and then compile it to an efficient circuit via a
straightforward strategy.
  We implement the program-level optimizations in Spire, an extension of the
Tower quantum compiler. Using a set of 11 benchmark programs that use control
flow, we show that the cost model is accurate, and that Spire's optimizations
recover programs that are asymptotically efficient, meaning their runtime
T-complexity under error correction is equal to their time complexity on
idealized hardware.
  Our results show that optimizing a program before it is compiled to a circuit
can yield better results than compiling the program to an inefficient circuit
and then invoking a quantum circuit optimizer found in prior work. For our
benchmarks, only 2 of 8 existing circuit optimizers recover circuits with
asymptotically efficient T-complexity. Compared to these 2 optimizers, Spire
uses 54x to 2400x less compile time.
