  In this paper, we present a quantum algorithm for the dynamic programming
approach for problems on directed acyclic graphs (DAGs). The running time of
the algorithm is $O(\sqrt{\hat{n}m}\log \hat{n})$, and the running time of the
best known deterministic algorithm is $O(n+m)$, where $n$ is the number of
vertices, $\hat{n}$ is the number of vertices with at least one outgoing edge;
$m$ is the number of edges. We show that we can solve problems that use OR,
AND, NAND, MAX, and MIN functions as the main transition steps. The approach is
useful for a couple of problems. One of them is computing a Boolean formula
that is represented by Zhegalkin polynomial, a Boolean circuit with shared
input and non-constant depth evaluation. Another two are the single source
longest paths search for weighted DAGs and the diameter search problem for
unweighted DAGs.
