# Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs

arXiv: https://arxiv.org/abs/1804.09950 · HTML: https://mlsanity.com/paper/1804.09950/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2018.

## Built on by (most cited first, 2 of 2)

- [Quantum Algorithm for the Shortest Superstring Problem](https://mlsanity.com/paper/2112.13319/) (2021)
- [Quantum Random Forest for the Regression Problem](https://mlsanity.com/paper/2603.22790/) (2026)

## Abstract (arXiv)

In this paper, we present a quantum algorithm for dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is O(√hatnmlog hatn), and the running time of the best known deterministic algorithm is O(n+m), where n is the number of vertices, hatn 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 evaluating. Another two are the single source longest paths search for weighted DAGs and the diameter search problem for unweighted DAGs.