Practical implementation of a quantum backtracking algorithm
Practical implementation of a quantum backtracking algorithm
复制标题
量子回溯算法的实际实现
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Maxime Remaud
中科院分区：
文献类型：
--
作者：
S. Martiel;Maxime Remaud
在以前的工作中，Montanaro提出了一种方法来获得回溯算法的量子加速比，这是一种解决约束满足问题（CSP）的通用元算法。在这项工作中，我们得到了这种方法的空间效率的实现。假设我们要解决一个CSP与$m$约束$n$变量和这些变量取其值的域的并集是基数$d$。然后，我们证明了Montanaro的回溯算法的实现可以通过使用$O（n \log d）$数据量子位来完成。我们详细介绍了一个实现的谓词相关联的CSP与一个额外的寄存器的$O（\log m）$量子位。我们明确我们的实现图着色和SAT问题，并提出模拟结果。最后，我们讨论了在量子环境中使用静态和动态变量排序算法的影响。
In previous work, Montanaro presented a method to obtain quantum speedups for backtracking algorithms, a general meta-algorithm to solve constraint satisfaction problems (CSPs). In this work, we derive a space efficient implementation of this method. Assume that we want to solve a CSP with $m$ constraints on $n$ variables and that the union of the domains in which these variables take their value is of cardinality $d$. Then, we show that the implementation of Montanaro's backtracking algorithm can be done by using $O(n \log d)$ data qubits. We detail an implementation of the predicate associated to the CSP with an additional register of $O(\log m)$ qubits. We explicit our implementation for graph coloring and SAT problems, and present simulation results. Finally, we discuss the impact of the usage of static and dynamic variable ordering heuristics in the quantum setting.
分支定界算法的量子加速
影响因子：
4.2
作者：
Montanaro A
通讯作者：
Montanaro A