Exponential-time quantum algorithms for graph coloring problems
Exponential-time quantum algorithms for graph coloring problems
复制标题
图着色问题的指数时间量子算法
DOI：
10.1007/s00453-022-00976-2
复制
发表时间：
2022
期刊：
影响因子：
1.1
通讯作者：
Kazuya Shimizu and Ryuhei Mori
中科院分区：
文献类型：
--
作者：
Liu Chunting;Song Jiangning;Ogata Hiroyuki;Akutsu Tatsuya;Kazuya Shimizu and Ryuhei Mori
已知最快的判定n点图的k-可染性的经典算法需要运行时间为。在这项工作中，我们提出了一种利用量子随机存取存储器(QRAM)计算具有运行时间的指数空间的色数的量子算法。我们的方法是基于Ambainis等人的量子动态规划，并将Grover搜索应用到分支算法中。我们还提出了一种不使用QRAM的多项式空间量子算法来解决有运行时间的图20-着色问题。对于多项式空间量子算法，我们实质上发展了可以通过Grover搜索进行二次改进的时间经典算法。
The fastest known classical algorithm deciding thek-colorability ofn-vertex graph requires running timefor. In this work, we present an exponential-space quantum algorithm computing the chromatic number with running timeusing quantum random access memory (QRAM). Our approach is based on Ambainis et al’s quantum dynamic programming with applications of Grover’s search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 20-coloring problem with running time. For the polynomial-space quantum algorithm, we essentially develop-timeclassicalalgorithms that can be improved quadratically by Grover’s search.