论文标题
一组量子2-SAT问题的量子算法
Quantum algorithm of a set of quantum 2-sat problem
论文作者
论文摘要
我们提出了一组量子2-可满足性（Q2SAT）问题的量子绝热算法，这是对2-可效性（2SAT）问题的概括。对于Q2SAT问题，我们构建了与Heisenberg链相似的哈密顿量。给定Q2SAT问题的所有解决方案涵盖了归化基态的子空间。哈密顿量已成为绝热的发展，因此该系统留在退化的子空间中。我们的数值结果表明，我们的算法的时间复杂性为$ O（n^{3.9}）$，用于产生针对条款数量$ M = DN（n-1）/2 \（d \ Lesssim 0.1）的问题的非平凡解决方案。我们讨论算法与已知量子和经典算法的优势。
We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem, which is a generalization of 2-satisfiability (2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain. All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states. The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace. Our numerical results suggest that the time complexity of our algorithm is $O(n^{3.9})$ for yielding non-trivial solutions for problems with the number of clauses $m=dn(n-1)/2\ (d\lesssim 0.1)$. We discuss the advantages of our algorithm over the known quantum and classical algorithms.
