A quantum constraint problem is a frustration-free Hamiltonian problem: given a collection of local operators, is there a state that is in the ground state of each operator simultaneously? It has previously been shown that these problems can be in P, NP-complete, MA-complete, or QMA_1-complete, but this list has not been shown to be exhaustive. We present three quantum constraint problems, that are (1) BQP_1-complete (also known as coRQP), (2) QCMA_1-complete and (3) coRP-complete. This provides the first natural complete problem for BQP_1. We also show that all quantum constraint problems can be realized on qubits, a trait not shared with classical constraint problems. These results suggest a significant diversity of complexity classes present in quantum constraint problems.
翻译：量子制约问题是一个无挫败的汉密尔顿问题:鉴于当地运营商的集合,每个运营商的地面状态是否同时存在?以前已经表明,这些问题可以在P、NP-完成、MA-完成或QMA_1完成中出现,但这一清单并没有被证明是详尽无遗的。我们提出了三种量子制约问题,即:(1) BQP_1-完成(又称CORQP),(2) QCMA_1-完成和(3) 组合RP-完成。这为BQP_1提供了第一个自然完整的问题。我们还表明,所有量子制约问题都可以在qubit上实现,这种特性与传统制约问题没有共同的特征。这些结果表明,数量制约问题存在多种多样的复杂类别。
相关内容
微信扫码咨询专知VIP会员