论文标题
树宽的量子加速
Quantum speedups for treewidth
论文作者
论文摘要
在本文中，我们研究了用于计算图形宽度的确切值的量子算法。我们的算法基于Fomin and Villanger（Combinatorica 32，2012）的经典算法，该算法使用$ O（2.616^n）$时间和多项式空间。我们在两个指数空间算法中使用QRAM显示了三种具有以下复杂性的量子算法：$ \ bullet $ $ $ o（1.618^n）$ time和polyenmial空间； $ \ bullet $ $ o（1.554^n）$ time和$ o（1.452^n）$ space; $ \ bullet $ $ o（1.538^n）$时间和空间。相比之下，TreeWidth最快的已知经典算法使用$ O（1.755^n）$时间和空间。前两个速度以相当简单的方式获得。第一个版本另外仅使用Grover的搜索，并提供了二次加速。第二个加速度更高，并且使用了Ambainis等人的Grover搜索和量子指数的动态编程。 （苏打'19）。第三版使用经典算法和树宽的特定属性，并在HyperCube上修改了量子动态编程的修改版本。最后，作为一个小的结果，我们还为以$ o^*（2^n）$时间和$ o^*（\ sqrt {2^n}）$ space进行了新的经典时间空间权衡。
In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses $O(2.616^n)$ time and polynomial space. We show three quantum algorithms with the following complexity, using QRAM in both exponential space algorithms: $\bullet$ $O(1.618^n)$ time and polynomial space; $\bullet$ $O(1.554^n)$ time and $O(1.452^n)$ space; $\bullet$ $O(1.538^n)$ time and space. In contrast, the fastest known classical algorithm for treewidth uses $O(1.755^n)$ time and space. The first two speed-ups are obtained in a fairly straightforward way. The first version uses additionally only Grover's search and provides a quadratic speedup. The second speedup is more time-efficient and uses both Grover's search and the quantum exponential dynamic programming by Ambainis et al. (SODA '19). The third version uses the specific properties of the classical algorithm and treewidth, with a modified version of the quantum dynamic programming on the hypercube. Lastly, as a small side result, we also give a new classical time-space tradeoff for computing treewidth in $O^*(2^n)$ time and $O^*(\sqrt{2^n})$ space.
