The complexity of the local Hamiltonian problem
The complexity of the local Hamiltonian problem
复制标题
DOI：
10.1137/s0097539704445226
复制
发表时间：
2006-01-01
影响因子：
1.6
通讯作者：
Regev, O
中科院分区：
文献类型：
--
作者：
Kempe, J;Kitaev, A;Regev, O
中心点-局部哈密顿问题对于复杂性类QMA是一个自然的完全问题，QMA是NP的量子类比。它在本质上类似于对中心点>；=2是NP完全的最大中心点-SAT。众所周知，对于任何中心点>；=3，该问题都是QMA-完全的。另一方面，1-局部哈密顿量在P中，因此不被认为是QMA-完全的。2-局部哈密顿问题的复杂性一直是一个突出的问题。这里我们解决了这个问题，并证明了它是QMA-完全的。我们提供了两个独立的证明；我们的第一个证明只使用了初等线性代数。我们的第二个证明使用了一个强大的技术来分析两个哈密顿的和；这个技术是基于微扰理论的，我们相信它在其他地方可能会被证明是有用的。利用我们的方法，我们还证明了量子比特上两局域相互作用的绝热计算与标准量子计算是等价的。
The center dot-LOCAL HAMILTONIAN problem is a natural complete problem for the complexity class QMA, the quantum analogue of NP. It is similar in spirit to MAX-center dot-SAT, which is NP-complete for center dot >= 2. It was known that the problem is QMA-complete for any center dot >= 3. On the other hand, 1-LOCAL HAMILTONIAN is in P and hence not believed to be QMA-complete. The complexity of the 2-LOCAL HAMILTONIAN problem has long been outstanding. Here we settle the question and show that it is QMA-complete. We provide two independent proofs; our first proof uses only elementary linear algebra. Our second proof uses a powerful technique for analyzing the sum of two Hamiltonians; this technique is based on perturbation theory and we believe that it might prove useful elsewhere. Using our techniques we also show that adiabatic computation with 2-local interactions on qubits is equivalent to standard quantum computation.