Commutative version of the k-local Hamiltonian problem and non-triviality check for quantum codes
Commutative version of the k-local Hamiltonian problem and non-triviality check for quantum codes
复制标题
k-局部哈密顿问题的交换版本和量子代码的非平凡性检查
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
M. Vyalyi
中科院分区：
文献类型：
--
作者：
S. Bravyi;M. Vyalyi
量子码的k-局部哈密顿问题的交换形式和非平凡性检验。摘要研究了几类量子码的非平凡性检验问题的复杂性。问题的输入是一族两两交换的Hermitian算子H1，. ..，Hr：（C d）n →（C d）n和一个真实的向量λ =（λ 1，. ..，λ r）。问题是确定由等式H a指定的公共特征空间L λ是否|λ = λ a|其中，a = 1，. ..，r具有正维度。我们考虑两种情况：（i）所有算子Ha是k-局部的;（ii）所有算子Ha是因子分解的.可以很容易地证明，这两个问题都属于QMA类-NP的量子类似物，并且一些NP完全问题可以简化为（i）或（ii）。一个重要的问题是问题（i）或（ii）是否属于NP？我们证明了对于k和d的某些特殊值，答案是肯定的。证明了问题（ii）可化为其特殊情形，使得所有算子Ha都是因子分解投影算子且λ a = 0.在过去的十年里，量子复杂性被广泛研究。许多量子复杂性类被发明出来（要找到它们中的任何一个，请参阅复杂性类的全面列表[1]）。许多有趣的结果是已知的这些类。然而，量子复杂性和经典复杂性之间的确切关系对几乎所有的复杂性都是开放的。本文主要研究经典复杂性类NP及其量子类似物QMA。根据定义，NP MA QMA，其中MA是Merlin-Arthur博弈类-NP类的概率模拟。目前还不知道这些夹杂物是否严格。在[4]中表明，组非成员问题是QMA。这个问题中的群运算是由oracle给出的。从这个结果可以得出，存在一个预言R使得MA R <$QMA R。
Commutative version of the k-local Hamiltonian problem and non-triviality check for quantum codes. Abstract We study a complexity of problems related with non-triviality check for some classes of quantum codes. The input of the problem is a family of pairwise commuting Hermitian operators H 1 ,. .. , H r : (C d) ⊗n → (C d) ⊗n and a real vector λ = (λ 1 ,. .. , λ r). The problem is to determine whether a common eigenspace L λ specified by equalities H a |ψ = λ a |ψ, a = 1,. .. , r has a positive dimension. We consider two cases: (i) all operators H a are k-local; (ii) all operators H a are factorized. It can be easily shown that both problems belong to the class QMA — quantum analogue of NP, and that some NP-complete problems can be reduced to either (i) or (ii). A non-trivial question is whether the problems (i) or (ii) belong to NP? We show that the answer is positive for some special values of k and d. Also we prove that the problem (ii) can be reduced to its special case, such that all operators H a are factorized projectors and all λ a = 0. 1 Formulation of the problems Quantum complexity were studied intensely during the last decade. Many quantum complexity classes were invented (to find any of them see a comprehensive list of complexity classes [1]). Many interesting results are known for these classes. Nevertheless, the exact relationship between quantum and classical complexity classes remain open for almost all of them. In this paper we will focus on the classical complexity class NP and its quantum analogue QMA which was defined in [2], [3]. By definition, NP ⊆ MA ⊆ QMA, where MA is the class of Merlin-Arthur games — probabilistic analogue of the class NP. It is not known whether these inclusions are strict. It was shown in [4] that the group non-membership problem is in QMA. The group operation in this problem is given by oracle. It follows from this result that there exists an oracle R such that MA R ⊂ QMA R .