  We present a quantum Viterbi algorithm (QVA) with better than classical
performance under certain conditions. In this paper the proposed algorithm is
applied to decoding classical convolutional codes, for instance; large
constraint length $Q$ and short decode frames $N$. Other applications of the
classical Viterbi algorithm where $Q$ is large (e.g. speech processing) could
experience significant speedup with the QVA. The QVA exploits the fact that the
decoding trellis is similar to the butterfly diagram of the fast Fourier
transform, with its corresponding fast quantum algorithm. The tensor-product
structure of the butterfly diagram corresponds to a quantum superposition that
we show can be efficiently prepared. The quantum speedup is possible because
the performance of the QVA depends on the fanout (number of possible
transitions from any given state in the hidden Markov model) which is in
general much less than $Q$. The QVA constructs a superposition of states which
correspond to all legal paths through the decoding lattice, with phase a
function of the probability of the path being taken given received data. A
specialized amplitude amplification procedure is applied one or more times to
recover a superposition where the most probable path has a high probability of
being measured.
