A Linear Time Algorithm for Quantum 2-SAT
A Linear Time Algorithm for Quantum 2-SAT
复制标题
DOI：
10.4230/lipics.ccc.2016.27
复制
发表时间：
2015-08
期刊：
影响因子：
--
通讯作者：
N. D. Beaudrap;Sevag Gharibian
中科院分区：
文献类型：
--
作者：
N. D. Beaudrap;Sevag Gharibian
布尔约束满足问题 3-SAT 可以说是典型的 NP 完全问题。相比之下，2-SAT不仅可以在多项式时间内决定，而且实际上可以在确定性线性时间内决定。 2006年，Bravyi提出了k-SAT到量子环境的物理驱动推广，定义了“量子k-SAT”问题。他证明量子 2-SAT 在经典计算机上也可以在多项式时间内求解，特别是在确定性时间 O(n^4) 中，假设在有理数的域扩展上进行单位成本算术，其中 n 是变量的数量。在本文中，我们提出了一种量子 2-SAT 算法，该算法以线性时间运行，即变量和子句数量分别为 n 和 m 的确定性时间 O(n+m)。我们的方法利用了 Laumann 等人的转移矩阵技术。 [QIC, 2010] 用于研究随机量子 2-SAT 的相变，与 Even、Itai 和 Shamir（基于回溯）[SICOMP, 1976] 和 Aspvall、Plass 和 Tarjan（基于强连通分量）[IPL, 1979] 的线性时间 2-SAT 算法有相似之处。
The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unit-cost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2-SAT which runs in linear time, i.e. deterministic time O(n+m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].