imported>Kurgenera：/* 局域哈密顿量问题 */

2025-10-10T07:32:46Z

局域哈密顿量问题

新页面

在[[计算复杂性理论]]中，'''QMA'''（{{langx|en|Quantum Merlin Arthur}}，意为'''量子梅林-亚瑟'''）是一个[[复杂性类]]，它包含了这样一类[[決策問題|决策问题]]：对于一个答案为“是”的实例，证明者（梅林）可以提供一个[[多项式#计算机科学中的应用|多项式大小]]的量子证明（一个[[量子態|量子态]]），使验证者（亚瑟）在[[多項式時間|多项式时间]]内能够以高概率确信其为“是”（这被称为完备性）；反之，对于答案为“否”的实例，任何证明都将以高概率被验证者拒绝（这被称为可靠性）。

QMA 与 [[BQP]] 的关系，可类比于经典复杂性类中 [[NP (复杂性类)|NP]] 与 [[P (复杂度)|P]] 的关系，以及概率复杂性类中 [[MA (复杂性)|MA]] 与 [[BPP (複雜度)|BPP]] 的关系。

== 定义 ==

一个语言 <math>L</math> 属于 <math>\mathsf{QMA}(c,s)</math>，如果存在一个多项式时间量子验证者 <math>V</math> 和一个多项式 <math>p(n)</math>（其中 <math>n</math> 为输入 <math>x</math> 的长度），满足：<ref name="AharonovNaveh2002">{{cite arXiv|eprint=quant-ph/0210077v1|first1=Dorit|last1=Aharonov|author1-link=多麗特·阿哈羅諾夫|first2=Tomer|last2=Naveh|title=Quantum NP – A Survey|year=2002}}</ref><ref name="JW">{{cite book|arxiv=0804.3401|first=John|last=Watrous|author-link=約翰·沃特羅斯|chapter=Quantum Computational Complexity|year=2009|title=Encyclopedia of Complexity and Systems Science|pages=7174–7201|doi=10.1007/978-0-387-30440-3_428|isbn=978-0-387-75888-6 |s2cid=1380135 |editor-first=Robert A.|editor-last=Meyers}}</ref><ref name="GharibianEtAl2015">{{cite journal |last1=Gharibian |first1=Sevag |last2=Huang |first2=Yichen |last3=Landau |first3=Zeph |last4=Shin |first4=Seung Woo |title=Quantum Hamiltonian Complexity |journal=Foundations and Trends in Theoretical Computer Science |date=2015 |volume=10 |issue=3 |pages=159–282 |doi=10.1561/0400000066|arxiv=1401.3916 |s2cid=47494978 }}</ref>
* 对于所有 <math>x \in L</math>，存在一个量子态 <math>|\psi\rangle</math>，使得验证者 <math>V</math> 接受输入 <math>(|x\rangle, |\psi\rangle)</math> 的概率大于 <math>c</math>。
* 对于所有 <math>x \notin L</math>，以及所有最多包含 <math>p(|x|)</math> 个量子比特的量子态 <math>|\psi\rangle</math>，验证者 <math>V</math> 接受输入 <math>(|x\rangle, |\psi\rangle)</math> 的概率小于 <math>s</math>。

复杂性类 <math>\mathsf{QMA}</math> 被定义为等于 <math>\mathsf{QMA}(2/3, 1/3)</math>。然而，这些常数并不十分重要，因为如果将 <math>c</math> 和 <math>s</math> 设置为任何满足 <math>c > s</math> 的常数，该复杂性类保持不变。此外，对于任何多项式 <math>q(n)</math> 和 <math>r(n)</math>，我们有：<math display="block">\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)})</math>

== QMA中的问题 ==

由于许多有意义的复杂性类，如P、BQP和NP，都包含在QMA中，所以这些类中的所有问题也都在QMA中。然而，存在一些问题属于QMA，但目前尚不知道它们是否属于NP或BQP。下面将讨论一些这类著名的问题。

一个问题被称为QMA困难（{{lang|en|QMA-hard}}），类似于[[NP困难]]，如果QMA中的每个问题都可以[[归约]]到它。如果一个问题是QMA困难的并且属于QMA，则称其为QMA[[完全 (复杂性)|完全]]（{{lang|en|QMA-complete}}）的。

=== 局域哈密顿量问题 ===
一个k-局域[[哈密顿算符 (量子力学)|哈密顿量]]（{{lang|en|k-local Hamiltonian}}） <math>H</math> 是一个作用于 <math>n</math> 个量子比特的[[厄米矩阵]]，它可以表示为 <math>m</math> 个哈密顿量项的总和，每个项最多作用于 <math>k</math> 个量子比特。<math display="block">H = \sum_{i=1}^m H_i</math>一般的k-局域哈密顿量问题是，给定一个k-局域的哈密顿量 <math>H</math>，找出 <math>H</math> 的最小本征值 <math>\lambda</math>。<ref name="ODonnelLecture">{{cite web |last1=O'Donnel |first1=Ryan |title=Lecture 24: QMA: Quantum Merlin Arthur |url=https://www.cs.cmu.edu/~odonnell/quantum15/lecture24.pdf |access-date=2021-04-18 |archive-date=2024-12-03 |archive-url=https://web.archive.org/web/20241203072857/https://www.cs.cmu.edu/~odonnell/quantum15/lecture24.pdf |dead-url=no }}</ref> <math>\lambda</math> 也称为该哈密顿量的基态能量。

k-局域哈密顿量问题的判定版本是一种[[承诺问题]]，定义为：给定一个k-局域哈密顿量和两个实数 <math>\alpha, \beta</math> 且 <math>\alpha > \beta</math>，判断是否存在 <math>H</math> 的一个量子本征态 <math>|\psi\rangle</math>，其对应的本征值 <math>\lambda</math> 满足 <math>\lambda \leq \beta</math>，或者是否对于所有本征态其本征值 <math>\lambda \geq \alpha</math>。

局域哈密顿量问题是[[最大可满足性问题|MAX-SAT]]的量子对应物。对于 <math>k \ge 2</math>，k-局域哈密顿量问题是QMA完全的。<ref name="KempeKitaevRegev2006">{{Cite journal | last1=Kempe | first1=Julia | author1-link = 茱莉婭·肯佩 | last2=Kitaev | first2=Alexei |author2-link= 阿列克谢·基塔耶夫 | last3=Regev | first3=Oded | author3-link= 奥代德·雷格夫 | title=The complexity of the local Hamiltonian problem | year=2006 | journal=[[SIAM Journal on Computing]] | volume=35 | issue=5 | pages=1070–1097 | arxiv=quant-ph/0406180v2 | doi=10.1137/S0097539704445226}}</ref>

限制在二维[[量子比特]]网格上作用的2-局域哈密顿量问题也是QMA完全的。<ref name="OliveiraTerhal2008">{{cite journal | last1 = Oliveira | first1 = Roberto |first2=Barbara M. | last2 = Terhal | title = The complexity of quantum spin systems on a two-dimensional square lattice | volume = 8 | pages = 900–924 | journal = Quantum Information and Computation | year = 2008 | issue = 10 | doi = 10.26421/QIC8.10-2 | arxiv = quant-ph/0504050 | bibcode = 2005quant.ph..4050O | s2cid = 3262293 }}</ref> 研究表明，即使对于表示一维粒子链且每个粒子具有12个状态的最近邻相互作用哈密顿量，k-局域哈密顿量问题仍然是QMA困难的。<ref name="AGIK2009">{{Cite journal | doi = 10.1007/s00220-008-0710-3 | volume = 287 | issue = 1 | pages = 41–65 | last1 = Aharonov | first1 = Dorit | author1-link = 多麗特·阿哈羅諾夫 |first2=Daniel | last2 = Gottesman | author2-link = 丹尼爾·戈特斯曼 |first3=Sandy | last3 = Irani |first4=Julia | last4= Kempe | author4-link = 茱莉婭·肯佩 | title = The power of quantum systems on a line | journal = [[Communications in Mathematical Physics]] | year = 2009 | bibcode=2009CMaPh.287...41A | arxiv= 0705.4077| s2cid = 1916001 }}</ref>如果系统是平移不变的，其局域哈密顿量问题变为QMA<sub>EXP</sub>-完全（因为问题输入被编码在系统大小中，验证者现在具有指数级运行时间，同时保持相同的承诺间隙）。<ref name="AGIK2009"/><ref name="BauschCubittOzols2017">{{cite journal |last1=Bausch |first1=Johannes |last2=Cubitt |first2=Toby |last3=Ozols |first3=Maris |title=The Complexity of Translationally Invariant Spin Chains with Low Local Dimension |journal=Annales Henri Poincaré |date=2017-11 |volume=18 |issue=11 |pages=3449–3513 |doi=10.1007/s00023-017-0609-7|doi-access=free |arxiv=1605.01718 }}</ref>

目前已知，一些简单的[[量子比特]][[晶格模型]]，如ZX哈密顿量，具有QMA困难性（{{Lang|en|QMA-hardness}}）：<ref name="BiamonteLove2008">{{Cite journal | last1=Biamonte | first1=Jacob | last2=Love | first2=Peter | title=Realizable Hamiltonians for universal adiabatic quantum computers | journal=[[Physical Review A]] | year=2008 | volume=78 | issue=1 | pages=012352 | arxiv=0704.1287 | doi=10.1103/PhysRevA.78.012352 | bibcode=2008PhRvA..78a2352B| s2cid=9859204 }}</ref><math display="block">
H_{ZX} = \sum_{i}h_i Z_i + \sum_{i} \Delta_i X_i + \sum_{i<j}J^{ij}Z_iZ_j + \sum_{i<j}K^{ij}X_iX_j
</math>其中 <math>Z, X</math> 代表[[泡利矩阵]] <math>\sigma_z, \sigma_x</math>。这类模型适用于普适[[绝热量子计算机|绝热量子计算]]。

k-局域哈密顿量问题类似于经典的[[約束滿足問題|约束满足问题]]。<ref name="YuenEntanglement">{{cite web |last1=Yuen |first1=Henry |title=The Complexity of Entanglement |url=http://henryyuen.net/fall2020/complexity_of_entanglement_notes.pdf |website=henryyuen.net |access-date=2021-05-20 |archive-date=2025-02-28 |archive-url=https://web.archive.org/web/20250228110611/https://www.henryyuen.net/fall2020/complexity_of_entanglement_notes.pdf |dead-url=no }}</ref>下表说明了经典约束满足问题和哈密顿量之间的类似组件。
{| class="wikitable"
|-
! scope="col" | 经典
! scope="col" | 量子
! scope="col" | 注释
|-
| 约束满足问题
| 哈密顿量
|
|-
| 变量
| 量子比特
|
|-
| 约束
| 哈密顿量项
|
|-
| 变量赋值
| 量子态
|
|-
| 满足的约束数量
| 哈密顿量的能量项
|
|-
| 最优解
| 哈密顿量的基态
| 满足尽可能多的约束
|}

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

== 相关类别 ==
'''QAM'''（{{lang|en|Quantum Arthur Merlin}}）是一个与 QMA 密切相关的变体。在 QAM 协议中，验证者亚瑟首先向证明者梅林发送一个随机字符串（即“公共硬币”），梅林再以此为依据提供证明。<ref>{{Cite web |title=Quantum Arthur-Merlin Games |url=https://arxiv.org/abs/cs/0506068 |website=arXiv.org |date=2005-06-15 |language=en |last=Marriott |first=Chris |last2=Watrous |first2=John |access-date=2025-05-23}}</ref>

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

'''QIP(k)''' 全称为“量子交互式多项式时间（k条消息）”（{{lang|en|Quantum Interactive Polynomial time (k messages)}}），可以看作是QMA的推广。在该模型中，梅林（证明者）和亚瑟（验证者）可以进行 <math>k</math> 轮交互。因此，QMA本质上就是QIP(1)（即只有一轮交互，梅林发送证明，亚瑟进行验证）。目前已知 QIP(2)（两轮交互）包含在复杂性类[[PSPACE]]中。<ref name="JainUpadhyayWatrous2009">{{Cite book |last1=Jain |first1=Rahul |last2=Upadhyay |first2=Sarvagya |last3=Watrous |first3=John |author3-link=約翰·沃特羅斯 |title=Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09) |publisher=IEEE Computer Society |isbn=978-0-7695-3850-1 |year=2009 |chapter=Two-message quantum interactive proofs are in PSPACE |doi=10.1109/FOCS.2009.30 |pages=534–543 |arxiv=0905.1300 |s2cid=6869749}}</ref>

'''[[QIP]]''' 则代表“量子交互式证明”（{{lang|en|Quantum Interactive Proof}}），它与QIP(k)类似，但允许交互的轮数<math>k</math>是输入规模（例如[[量子比特]]数量）的[[多项式]]函数。研究表明，只需三轮交互就足以达到QIP的全部计算能力，即 <math>\mathsf{QIP}(3) = \mathsf{QIP}</math>。<ref name="Watrous2003TCS">{{Cite journal | last1=Watrous | first1=John | author1-link=約翰·沃特羅斯 | title=PSPACE has constant-round quantum interactive proof systems | year=2003 | journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume=292 | issue=3 | pages=575–588 | doi=10.1016/S0304-3975(01)00375-9 | doi-access=free }}</ref> 此外，一个重要的结论是，QIP与经典的交互式证明系统 IP 以及[[PSPACE]]等价，即 <math>\mathsf{QIP} = \mathsf{IP} = \mathsf{PSPACE}</math><ref name="JainJiUpadhyayWatrous2011">{{cite journal | last1=Jain | first1=Rahul | last2=Ji | first2=Zhengfeng | last3=Upadhyay | first3=Sarvagya | last4=Watrous | first4=John | author4-link=約翰·沃特羅斯 | journal = [[Journal of the ACM]] | year=2011 | title=QIP = PSPACE | volume = 58 | issue = 6 | page = A30 | doi = 10.1145/2049697.2049704| s2cid=265099379 }}</ref>。

== 与其他复杂性类的关系 ==

QMA与其他已知的[[复杂性类]]的关系如下：<math display="block">\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}\subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}</math>第一个包含关系源于[[NP (复杂性类)|NP]]的定义。接下来的两个包含关系是因为验证者在每种情况下都变得更强大。QCMA包含在QMA中，因为验证者可以通过在接收到证明后立即进行测量来强制证明者发送经典证明。QMA包含在[[PP (複雜度)|PP]]中的事实由[[阿列克谢·基塔耶夫]]（{{lang|en|Alexei Kitaev}}）和[[约翰·沃特罗斯]]（{{lang|en|John Watrous}}）证明。PP也很容易证明包含在[[PSPACE]]中。

目前尚不清楚这些包含关系是否有任何一个是严格的，因为甚至连P是否严格包含在PSPACE中（即P = PSPACE是否成立）都未知。然而，目前已知的QMA的最佳上界是：<ref name="Vyalyi2003">{{cite journal | last = Vyalyi | first = Mikhail N. | title = QMA = PP implies that PP contains PH | journal = Electronic Colloquium on Computational Complexity | year = 2003 | url = https://eccc.weizmann.ac.il/eccc-reports/2003/TR03-021/index.html | access-date = 2025-05-22 | archive-date = 2023-12-06 | archive-url = https://web.archive.org/web/20231206114655/https://eccc.weizmann.ac.il//eccc-reports/2003/TR03-021/index.html | dead-url = no }}</ref><ref name="GharibianYirka2019">{{cite journal | last1 = Gharibian | first1 = Sevag | last2 = Yirka | first2 = Justin | title = The complexity of simulating local measurements on quantum systems | journal = Quantum | year = 2019 | volume = 3 | page = 189 | doi=10.22331/q-2019-09-30-189 | doi-access = free | arxiv = 1606.05626 }}</ref> <math>\mathsf{QMA}\subseteq\mathsf{A_0PP}</math> 且 <math>\mathsf{QMA}\subseteq\mathsf{P^{QMA[log]}}</math>，其中 <math>\mathsf{A_0PP}</math> 和 <math>\mathsf{P^{QMA[log]}}</math> 都包含在 <math>\mathsf{PP}</math> 中。 <math>\mathsf{QMA}</math> 不太可能等于 <math>\mathsf{P^{QMA[log]}}</math>，因为这将意味着 <math>\mathsf{QMA}=\mathsf{co}</math>-<math>\mathsf{QMA}</math>。目前尚不清楚 <math>\mathsf{P^{QMA[log]}}\subseteq\mathsf{A_0PP}</math> 或反之是否成立。

== 参考文献 ==
{{reflist|2}}

== 外部链接 ==
*{{cite web|url=http://www.scottaaronson.com/democritus/lec13.html|title=PHYS771 Lecture 13: How Big are Quantum States?|last=Aaronson|first=Scott}}
*{{cite web|url=http://groups.uni-paderborn.de/fg-qi/courses/UPB_QCOMPLEXITY/2019/notes/Lecture%205%20-%20Quantum%20Merlin%20Arthur%20(QMA)%20and%20strong%20error%20reduction.pdf|title=Lecture 5: Quantum Merlin Arthur (QMA) and strong error reduction|last=Gharibian|first=Sevag}}
*{{Cite web |title=Complexity Zoo:Q - Complexity Zoo |url=https://complexityzoo.net/Complexity_Zoo:Q#qma |website=complexityzoo.net |access-date=2025-05-22}}

{{量子计算}}
{{复杂度类}}
[[Category:量子信息]]
[[Category:复杂性理论]]

QMA - 版本历史

imported>Kurgenera：​/* 局域哈密顿量问题 */

imported>Kurgenera：/* 局域哈密顿量问题 */