Quantum Dynamic Programming Algorithm for DAGs. Applications for AND-OR DAG Evaluation and DAG's Diameter Search
share
In this paper, we present Quantum Dynamic Programming approach for problems on directed acycling graphs (DAGs). The algorithm has time complexity O(√(n̂m)n̂) comparing to a deterministic one that has time complexity O(n+m). Here n is a number of vertexes, n̂ is a number of vertexes with at least one outgoing edge; and m is a number of edges. We show that we can solve problems that have OR, AND, NAND, MAX and MIN functions as the main transition step. The approach is useful for a couple of problems. One of them is computing Boolean formula that represented by DAG with AND and OR boolean operations in vertexes. Another one is DAG's diameter search.
READ FULL TEXT