  Quantum programming languages enable developers to implement algorithms for
quantum computers that promise computational breakthroughs in classically
intractable tasks. Programming quantum computers requires awareness of
entanglement, the phenomenon in which measurement outcomes of qubits are
correlated. Entanglement can determine the correctness of algorithms and
suitability of programming patterns.
  In this work, we formalize purity as a central tool for automating reasoning
about entanglement in quantum programs. A pure expression is one whose
evaluation is unaffected by the measurement outcomes of qubits that it does not
own, implying freedom from entanglement with any other expression in the
computation.
  We present Twist, the first language that features a type system for sound
reasoning about purity. The type system enables the developer to identify pure
expressions using type annotations. Twist also features purity assertion
operators that state the absence of entanglement in the output of quantum
gates. To soundly check these assertions, Twist uses a combination of static
analysis and runtime verification.
  We evaluate Twist's type system and analyses on a benchmark suite of quantum
programs in simulation, demonstrating that Twist can express quantum
algorithms, catch programming errors in them, and support programs that several
languages disallow, while incurring runtime verification overhead of less than
3.5%.
