论文标题
用于DAG和应用的动态编程方法的量子算法
Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications
论文作者
论文摘要
在本文中，我们提出了一种针对有向无环图（DAGS）问题的动态编程方法的量子算法。该算法的运行时间为$ O（\ sqrt {\ hat {n} m} \ log \ hat {n}）$，以及最著名的确定性算法的运行时间为$ o（n+m）$，其中$ n $是$ \ hat fertines的数量，$ \ \ hat fertect { $ m $是边的数量。我们表明，我们可以解决使用或NAND，MAX和MIN的问题作为主要过渡步骤。该方法对于几个问题很有用。其中之一是计算由Zhegalkin多项式表示的布尔公式，该公式是具有共享输入和非恒定深度评估的布尔电路。另外两个是最长的路径搜索加权dags和未加权dag的直径搜索问题。
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.
