Efficient algorithm for a quantum analogue of 2-SAT
Efficient algorithm for a quantum analogue of 2-SAT
复制标题
DOI：
10.1090/conm/536/10552
复制
发表时间：
2006-02
期刊：
影响因子：
--
通讯作者：
S. Bravyi
中科院分区：
文献类型：
--
作者：
S. Bravyi
研究了可满足性问题的量子模拟的复杂性。量子k-SAT问题是验证是否存在n比特纯态使得其k比特约化密度矩阵在指定子空间上有支撑。我们提出了一个在多项式时间内求解量子2-SAT的经典算法。它推广了经典的2-SAT算法。此外，我们还证明了对于任意k>=4的量子，k-SAT在复杂性类QMA中是完备的，并且有单侧误差.
Complexity of a quantum analogue of the satisfiability problem is studied. Quantum k-SAT is a problem of verifying whether there exists n-qubit pure state such that its k-qubit reduced density matrices have support on prescribed subspaces. We present a classical algorithm solving quantum 2-SAT in a polynomial time. It generalizes the well-known algorithm for the classical 2-SAT. Besides, we show that for any k>=4 quantum k-SAT is complete in the complexity class QMA with one-sided error.