在计算复杂性理论中，QMA（，意为量子梅林-亚瑟）是一个复杂性类，它包含了这样一类决策问题：对于一个答案为“是”的实例，证明者（梅林）可以提供一个多项式大小的量子证明（一个量子态），使验证者（亚瑟）在多项式时间内能够以高概率确信其为“是”（这被称为完备性）；反之，对于答案为“否”的实例，任何证明都将以高概率被验证者拒绝（这被称为可靠性）。
QMA 与 BQP 的关系，可类比于经典复杂性类中 NP 与 P 的关系，以及概率复杂性类中 MA 与 BPP 的关系。
定义
一个语言 L 属于 \mathsf{QMA}(c,s)，如果存在一个多项式时间量子验证者 V 和一个多项式 p(n)（其中 n 为输入 x 的长度），满足：
- 对于所有 x \in L，存在一个量子态 |\psi\rangle，使得验证者 V 接受输入 (|x\rangle, |\psi\rangle) 的概率大于 c。
- 对于所有 x \notin L，以及所有最多包含 p(|x|) 个量子比特的量子态 |\psi\rangle，验证者 V 接受输入 (|x\rangle, |\psi\rangle) 的概率小于 s。
复杂性类 \mathsf{QMA} 被定义为等于 \mathsf{QMA}(2/3, 1/3)。然而，这些常数并不十分重要，因为如果将 c 和 s 设置为任何满足 c > s 的常数，该复杂性类保持不变。此外，对于任何多项式 q(n) 和 r(n)，我们有：\mathsf{QMA}\left(\frac{2}{3},\frac{1}{3}\right) =\mathsf{QMA}\left(\frac{1}{2}+\frac{1}{q(n)},\frac{1}{2}-\frac{1}{q(n)}\right)=\mathsf{QMA}(1-2^{-r(n)},2^{-r(n)})
QMA中的问题
由于许多有意义的复杂性类，如P、BQP和NP，都包含在QMA中，所以这些类中的所有问题也都在QMA中。然而，存在一些问题属于QMA，但目前尚不知道它们是否属于NP或BQP。下面将讨论一些这类著名的问题。
一个问题被称为QMA困难（），类似于NP困难，如果QMA中的每个问题都可以归约到它。如果一个问题是QMA困难的并且属于QMA，则称其为QMA完全（）的。
局域哈密顿量问题
一个k-局域哈密顿量（） H 是一个作用于 n 个量子比特的厄米矩阵，它可以表示为 m 个哈密顿量项的总和，每个项最多作用于 k 个量子比特。H = \sum_{i=1}^m H_i一般的k-局域哈密顿量问题是，给定一个k-局域的哈密顿量 H，找出 H 的最小本征值 \lambda。 \lambda 也称为该哈密顿量的基态能量。
k-局域哈密顿量问题的判定版本是一种承诺问题，定义为：给定一个k-局域哈密顿量和两个实数 \alpha, \beta 且 \alpha > \beta，判断是否存在 H 的一个量子本征态 |\psi\rangle，其对应的本征值 \lambda 满足 \lambda \leq \beta，或者是否对于所有本征态其本征值 \lambda \geq \alpha。
局域哈密顿量问题是MAX-SAT的量子对应物。对于 k \ge 2，k-局域哈密顿量问题是QMA完全的。
限制在二维量子比特网格上作用的2-局域哈密顿量问题也是QMA完全的。 研究表明，即使对于表示一维粒子链且每个粒子具有12个状态的最近邻相互作用哈密顿量，k-局域哈密顿量问题仍然是QMA困难的。如果系统是平移不变的，其局域哈密顿量问题变为QMAEXP-完全（因为问题输入被编码在系统大小中，验证者现在具有指数级运行时间，同时保持相同的承诺间隙）。
目前已知，一些简单的量子比特晶格模型，如ZX哈密顿量，具有QMA困难性（）：
H_{ZX} = \sum_{i}h_i Z_i + \sum_{i} \Delta_i X_i + \sum_{i其中 Z, X 代表泡利矩阵 \sigma_z, \sigma_x。这类模型适用于普适绝热量子计算。
k-局域哈密顿量问题类似于经典的约束满足问题。下表说明了经典约束满足问题和哈密顿量之间的类似组件。
其他QMA完全问题
已知的QMA完全问题列表可在 https://arxiv.org/abs/1212.6312 找到。
相关类别
QAM（）是一个与 QMA 密切相关的变体。在 QAM 协议中，验证者亚瑟首先向证明者梅林发送一个随机字符串（即“公共硬币”），梅林再以此为依据提供证明。
QCMA（，有时也写作MQA
QIP 则代表“量子交互式证明”（），它与QIP(k)类似，但允许交互的轮数k是输入规模（例如量子比特数量）的多项式函数。研究表明，只需三轮交互就足以达到QIP的全部计算能力，即 \mathsf{QIP}(3) = \mathsf{QIP}。 此外，一个重要的结论是，QIP与经典的交互式证明系统 IP 以及PSPACE等价，即 \mathsf{QIP} = \mathsf{IP} = \mathsf{PSPACE}。
与其他复杂性类的关系
QMA与其他已知的复杂性类的关系如下：\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}\subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}第一个包含关系源于NP的定义。接下来的两个包含关系是因为验证者在每种情况下都变得更强大。QCMA包含在QMA中，因为验证者可以通过在接收到证明后立即进行测量来强制证明者发送经典证明。QMA包含在PP中的事实由阿列克谢·基塔耶夫（）和约翰·沃特罗斯（）证明。PP也很容易证明包含在PSPACE中。
目前尚不清楚这些包含关系是否有任何一个是严格的，因为甚至连P是否严格包含在PSPACE中（即P = PSPACE是否成立）都未知。然而，目前已知的QMA的最佳上界是： \mathsf{QMA}\subseteq\mathsf{A_0PP} 且 \mathsf{QMA}\subseteq\mathsf{P^{QMA[log]}}，其中 \mathsf{A_0PP} 和 \mathsf{P^{QMA[log]}} 都包含在 \mathsf{PP} 中。 \mathsf{QMA} 不太可能等于 \mathsf{P^{QMA[log]}}，因为这将意味着 \mathsf{QMA}=\mathsf{co}-\mathsf{QMA}。目前尚不清楚 \mathsf{P^{QMA[log]}}\subseteq\mathsf{A_0PP} 或反之是否成立。
参考文献
外部链接
*
*
*
评论 (0)