  This paper develops verification methodology for quantum programs, and the
contribution of the paper is two-fold: 1. Sharir, Pnueli and Hart [SIAM J.
Comput. 13(1984)292-314] presented a general method for proving properties of
probabilistic programs, in which a probabilistic program is modeled by a Markov
chain and an assertion on the output distribution is extended into an invariant
assertion on all intermediate distributions. Their method is essentially a
probabilistic generalization of the classical Floyd inductive assertion method.
In this paper, we consider quantum programs modeled by quantum Markov chains
which are defined by super-operators. It is shown that the Sharir-Pnueli-Hart
method can be elegantly generalized to quantum programs by exploiting the
Schr\"odinger-Heisenberg duality between quantum states and observables. In
particular, a completeness theorem for the Sharir-Pnueli-Hart verification
method of quantum programs is established. 2. As indicated by the completeness
theorem, the Sharir-Pnueli-Hart method is in principle effective for verifying
all properties of quantum programs that can be expressed in terms of Hermitian
operators (observables). But it is not feasible for many practical applications
because of the complicated calculation involved in the verification. For the
case of finite-dimensional state spaces, we find a method for verification of
quantum programs much simpler than the Sharir-Pnueli-Hart method by employing
the matrix representation of super-operators and Jordan decomposition of
matrices. In particular, this method enables us to compute easily the average
running time and even to analyze some interesting long-run behaviors of quantum
programs in a finite-dimensional state space.
