2022/12/29 by Kamil Khadiev, Liliya R. Safina, Khadiev, Kamil +1 · 1 citation
Computer Science · #Algorithms and Data Compression #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2212.14433
openalex publication_date 2022/12/29 · openalex created_date 2023/01/06 · openalex updated_date 2026/07/28
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(√nmlog n), and the running time of the best known deterministic algorithm is O(n+m), where n is the number of vertices, 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.