QMA

在计算复杂性理论中，QMA（英語：Quantum Merlin Arthur，意为量子梅林-亚瑟）指的是一类语言的集合。对于这些语言中的任何一个字符串，如果该字符串确实属于该语言，那么存在一个多项式大小的量子证明（一个量子态），它能够以高概率说服一个多项式时间量子验证者（在量子计算机上运行）相信此事实。反之，如果该字符串不属于该语言，那么任何多项式大小的量子态都会以高概率被验证者拒绝。

QMA与BQP之间的关系，类似于复杂性类中NP与P之间的关系，也类似于概率复杂性类MA与BPP之间的关系。

QAM（Quantum Arthur Merlin，意为量子亚瑟-梅林）是一个相关的复杂性类。在这个模型中，虚构的代理人亚瑟和梅林按以下顺序进行交互：亚瑟生成一个随机字符串，梅林以量子证书作为回应，然后亚瑟如同一个BQP机器一样来验证这个证书。

定义

一个语言 $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困难（QMA-hard），类似于NP困难，如果QMA中的每个问题都可以归约到它。如果一个问题是QMA困难的并且属于QMA，则称其为QMA完全（QMA-complete）的。

局域哈密顿量问题

一个k-局域哈密顿量（k-local Hamiltonian） $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\geq 2$，k-局域哈密顿量问题是QMA完全的。

限制在二维量子比特网格上作用的2-局域哈密顿量问题也是QMA完全的。 研究表明，即使对于表示一维粒子链且每个粒子具有12个状态的最近邻相互作用哈密顿量，k-局域哈密顿量问题仍然是QMA困难的。如果系统是平移不变的，其局域哈密顿量问题变为QMA_EXP-完全（因为问题输入被编码在系统大小中，验证者现在具有指数级运行时间，同时保持相同的承诺间隙）。

目前已知，一些简单的量子比特晶格模型，如ZX哈密顿量，具有QMA困难性（QMA-hardness）：$$H_{ZX}=\sum _{i}h_{i}Z_{i}+\sum _{i}\Delta _{i}X_{i}+\sum _{i<j}J^{ij}Z_{i}Z_{j}+\sum _{i<j}K^{ij}X_{i}X_{j}$$其中 $Z,X$ 代表泡利矩阵 $\sigma _{z},\sigma _{x}$。这类模型适用于普适绝热量子计算。

k-局域哈密顿量问题类似于经典的约束满足问题。下表说明了经典约束满足问题和哈密顿量之间的类似组件。

经典	量子	注释
约束满足问题	哈密顿量
变量	量子比特
约束	哈密顿量项
变量赋值	量子态
满足的约束数量	哈密顿量的能量项
最优解	哈密顿量的基态	满足尽可能多的约束

其他QMA完全问题

已知的QMA完全问题列表可在 https://arxiv.org/abs/1212.6312 找到。

相关类别

QCMA（Quantum Classical Merlin Arthur，有时也写作MQA，对应Merlin Quantum Arthur）与QMA类似，其核心区别在于证明方（梅林）提供的证明必须是一个经典字符串，而非量子态。目前尚不清楚QMA是否等同于QCMA，尽管QCMA显然是QMA的一个子集（即${\mathsf {QCMA}}\subseteq {\mathsf {QMA}}$）。

QIP(k) 全称为“量子交互式多项式时间（k条消息）”（Quantum Interactive Polynomial time (k messages)），可以看作是QMA的推广。在该模型中，梅林（证明者）和亚瑟（验证者）可以进行 $k$ 轮交互。因此，QMA本质上就是QIP(1)（即只有一轮交互，梅林发送证明，亚瑟进行验证）。目前已知 QIP(2)（两轮交互）包含在复杂性类PSPACE中。

QIP 则代表“量子交互式证明”（Quantum Interactive Proof），它与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中的事实由阿列克谢·基塔耶夫（Alexei Kitaev）和约翰·沃特罗斯（John Watrous）证明。PP也很容易证明包含在PSPACE中。

目前尚不清楚这些包含关系是否有任何一个是严格的，因为甚至连P是否严格包含在PSPACE中（即P = PSPACE是否成立）都未知。然而，目前已知的QMA的最佳上界是： ${\mathsf {QMA}}\subseteq {\mathsf {A_{0}PP}}$ 且 ${\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}$，其中 ${\mathsf {A_{0}PP}}$ 和 ${\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_{0}PP}}$ 或反之是否成立。

外部链接

• Aaronson, Scott. PHYS771 Lecture 13: How Big are Quantum States?. 
• Gharibian, Sevag. Lecture 5: Quantum Merlin Arthur (QMA) and strong error reduction (PDF). 
• Complexity Zoo:Q - Complexity Zoo. complexityzoo.net. [2025-05-22].