  We study expected runtimes for quantum programs. Inspired by recent work on
probabilistic programs, we first define expected runtime as a generalisation of
quantum weakest precondition. Then, we show that the expected runtime of a
quantum program can be represented as the expectation of an observable (in
physics). A method for computing the expected runtimes of quantum programs in
finite-dimensional state spaces is developed. Several examples are provided as
applications of this method, including computing the expected runtime of
quantum Bernoulli Factory -- a quantum algorithm for generating random numbers.
In particular, using our new method, an open problem of computing the expected
runtime of quantum random walks introduced by Ambainis et al. (STOC 2001) is
solved.

Programming Languages;Quantum Physics