  That superpositions of states can be useful for performing tasks in quantum
systems has been known since the early days of quantum information, but only
recently has quantitative theory of quantum coherence been proposed. Here we
apply that theory to an analysis of the Deutsch-Jozsa algorithm, which depends
on quantum coherence for its operation. The Deutsch-Jozsa algorithm solves a
decision problem, and we focus on a probabilistic version of that problem,
comparing probability of being correct for both classical and quantum
procedures. In addition, we study a related decision problem in which the
quantum procedure has one-sided error while the classical procedure has
two-sided error. The role of coherence on the quantum success probabilities in
both of these problems is examined.
