  Quantum programming languages aim to reduce the burden of manipulating
hardware-level logic gates when implementing a quantum algorithm. A hurdle to
this goal is the difficulty of expressing control flow, such as branching and
iteration, that depends on the value of data in quantum superposition. To
implement algorithms for factorization, search, and simulation that contain
control flow, quantum languages often require the use of bit-level logic gates
as opposed to the high-level constructs provided by classical languages.
  The reason for this gap is that whereas a classical computer supports
imperative abstractions for control flow via a program counter that can depend
on data and functional abstractions via terms in the $\lambda$-calculus, the
typical architecture of a quantum computer does not provide a program counter
that can depend on data in superposition, nor a physical representation of
$\lambda$-terms in superposition. In principle, a quantum architecture
supporting such abstractions would simplify the implementation of control flow
in quantum programs.
  However, in this work, we identify a fundamental obstacle to control flow in
quantum programming, which is that a quantum computer cannot correctly support
the conventional conditional jump instruction in superposition, nor the
$\beta$-reduction of $\lambda$-terms in superposition. We formally prove that
programming abstractions with non-injective state transition semantics, such as
the above, produce incorrect results in superposition.
  As a way forward, we present the necessary and sufficient conditions for
control flow in superposition to be correctly realizable in a program. We
introduce the quantum control machine, an instruction set architecture that
satisfies these conditions, and show how it enables the use of control flow to
implement algorithms such as phase estimation, quantum walk, and physical
simulation.
