View source for QMA

{{Short description|Quantum Merlin Arthur}}
{{about|the complexity class|the coaxial RF connector|QMA and QN connector}}

In [[computational complexity theory]], '''QMA''', which stands for '''Quantum [[Arthur–Merlin protocol|Merlin Arthur]]''', is the set of languages for which, when a string is in the language, there is a polynomial-size quantum proof (a quantum state) that convinces a [[polynomial time]] quantum verifier (running on a [[quantum computer]]) of this fact with high probability. Moreover, when the string is not in the language, every polynomial-size quantum state is rejected by the verifier with high probability.

The relationship between QMA and [[BQP]] is analogous to the relationship between [[complexity classes]] [[NP (complexity)|NP]] and [[P (complexity)|P]]. It is also analogous to the relationship between the probabilistic complexity class [[Arthur–Merlin protocol|MA]] and [[BPP (complexity)|BPP]].

'''QAM''' is a related complexity class, in which fictional agents Arthur and Merlin carry out the sequence: Arthur generates a random string, Merlin answers with a quantum [[certificate (complexity)|certificate]] and Arthur verifies it as a BQP machine.

== Definition ==

A language L is in <math>\mathsf{QMA}(c,s)</math> if there exists a polynomial time quantum verifier V and a polynomial {{tmath|p(x)}} such that:<ref>{{cite arXiv|eprint=quant-ph/0210077v1|first1=Dorit|last1=Aharonov|author1-link= Dorit Aharonov|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=John Watrous (computer scientist)|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>{{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>\forall x \in L</math>, there exists a quantum state <math>|\psi\rangle</math> such that the probability that V accepts the input <math>(|x\rangle, |\psi\rangle)</math> is greater than {{mvar|c}}.
*<math>\forall x \notin L</math>, and for all quantum states <math>|\psi\rangle</math> with at most <math>p(|x|)</math> qubits, the probability that V accepts the input <math>(|x\rangle, |\psi\rangle)</math> is less than {{mvar|s}}.

The complexity class <math>\mathsf{QMA}</math> is defined to be equal to <math>\mathsf{QMA}({2}/{3},1/3)</math>. However, the constants are not too important since the class remains unchanged if {{mvar|c}} and {{mvar|s}} are set to any constants such that {{mvar|c}} is greater than {{mvar|s}}. Moreover, for any polynomials <math>q(n)</math> and <math>r(n)</math>, we have
:<math>\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>.

== Problems in QMA ==

Since many interesting classes are contained in QMA, such as P, BQP and NP, all problems in those classes are also in QMA. However, there are problems that are in QMA but not known to be in NP or BQP. Some such well known problems are discussed below.

A problem is said to be QMA-hard, analogous to [[NP-hard]], if every problem in QMA can be [[Reduction (complexity)|reduced]] to it. A problem is said to be QMA-[[complete (complexity)|complete]] if it is QMA-hard and in QMA.

=== The local Hamiltonian problem ===
A k-local [[Hamiltonian (quantum mechanics)]] <math>H</math> is a [[Hermitian matrix]] acting on n qubits which can be represented as the sum of <math>m</math> Hamiltonian Terms acting upon at most <math>k</math> qubits each.

<math>H = \sum_{i=1}^m H_i</math>

The general k-local Hamiltonian problem is, given a k-local Hamiltonian <math>H</math>, to find the smallest eigenvalue <math>\lambda</math> of <math>H</math>.<ref>{{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=18 April 2021}}</ref> <math>\lambda</math> is also called the ground state energy of the Hamiltonian.

The decision version of the k-local Hamiltonian problem is a type of [[promise problem]] and is defined as, given a k-local Hamiltonian and <math>\alpha, \beta</math> where <math>\alpha > \beta</math>, to decide if there exists a quantum eigenstate <math>|\psi\rangle</math> of <math>H</math> with associated eigenvalue <math>\lambda</math>, such that <math>\lambda \leq \beta</math> or if <math>\lambda \geq \alpha</math>.  

The local Hamiltonian problem is the quantum analogue of [[Maximum satisfiability problem|MAX-SAT]]. The k-local Hamiltonian problem is QMA-complete for k ≥ 2.<ref>{{Cite journal | last1=Kempe | first1=Julia | author1-link = Julia Kempe | last2=Kitaev | first2=Alexei |author2-link= Alexei Kitaev | last3=Regev | first3=Oded | author3-link= Oded Regev (computer scientist) | 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> 

The 2-local Hamiltonian problem restricted to act on a two dimensional grid of [[qubits]], is also QMA-complete.<ref>{{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> It has been shown that the k-local Hamiltonian problem is still QMA-hard even for Hamiltonians representing a 1-dimensional line of particles with nearest-neighbor interactions with 12 states per particle.<ref>{{Cite journal
| doi = 10.1007/s00220-008-0710-3
| volume = 287
| issue = 1
| pages = 41–65
| last1 = Aharonov
| first1 = Dorit | author1-link = Dorit Aharonov
|first2=Daniel | last2 = Gottesman | author2-link = Daniel Gottesman |first3=Sandy | last3 = Irani |first4=Julia | last4= Kempe | author4-link = Julia Kempe
 | 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>
If the system is translationally-invariant, its local Hamiltonian problem becomes QMA<sub>EXP</sub>-complete (as the problem input is encoded in the system size, the verifier now has exponential runtime while maintaining the same promise gap).<ref>{{cite journal |last1=Aharonov |first1=Dorit |last2=Gottesman |first2=Daniel |last3=Irani |first3=Sandy |last4=Kempe |first4=Julia |title=The Power of Quantum Systems on a Line |journal=Communications in Mathematical Physics |date=1 April 2009 |volume=287 |issue=1 |pages=41–65 |doi=10.1007/s00220-008-0710-3|s2cid=1916001 |citeseerx=10.1.1.320.7377 }}</ref><ref>{{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=November 2017 |volume=18 |issue=11 |pages=3449–3513 |doi=10.1007/s00023-017-0609-7|doi-access=free |arxiv=1605.01718 }}</ref>

QMA-hardness results are known for simple [[lattice models]] of [[qubits]] such as the ZX Hamiltonian <ref>{{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>
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> 
where <math>Z, X</math> represent the [[Pauli matrices]] <math>\sigma_z, \sigma_x</math>.  Such models are applicable to universal [[adiabatic quantum computation]].

k-local Hamiltonians problems are analogous to classical [[Constraint Satisfaction Problems]].<ref>{{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=20 April 2021}}</ref> The following table illustrates the analogous gadgets between classical CSPs and Hamiltonians.
{| class="wikitable"
|-
! scope="col" | Classical
! scope="col" | Quantum
! scope="col" | Notes
|-
| Constraint Satisfaction Problem
| Hamiltonian
| 
|-
| Variable
| Qubit
| 
|-
| Constraint
| Hamiltonian Term
| 
|-
| Variable Assignment
| Quantum state
|
|-
| Number of constraints satisfied
| Hamiltonian's energy term
| 
|-
| Optimal Solution
| Hamiltonian's ground state
| The most possible constraints satisfied
|}
===Other QMA-complete problems===
A list of known QMA-complete problems can be found at https://arxiv.org/abs/1212.6312.

== Related classes ==

'''QCMA''' (or '''MQA'''<ref name="JW" />), which stands for Quantum Classical Merlin Arthur (or Merlin Quantum Arthur), is similar to QMA, but the proof has to be a classical string. It is not known whether QMA equals QCMA, although QCMA is clearly contained in QMA.

'''QIP(k)''', which stands for [[Quantum Interactive Polynomial time]] (k messages), is a generalization of QMA where Merlin and Arthur can interact for k rounds. QMA is QIP(1). QIP(2) is known to be in PSPACE.<ref>{{Cite book | last1=Jain | first1=Rahul | last2=Upadhyay | first2=Sarvagya | last3=Watrous | first3=John | author3-link=John Watrous (computer scientist) | title=[[Symposium on Foundations of Computer Science|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 (complexity)|QIP]]''' is QIP(k) where k is allowed to be polynomial in the number of qubits. It is known that QIP(3) = QIP.<ref>{{Cite journal | last1=Watrous | first1=John | author1-link=John Watrous (computer scientist) | 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> It is also known that QIP = [[IP (complexity)|IP]] = [[PSPACE]].<ref>{{cite journal | last1=Jain | first1=Rahul | last2=Ji | first2=Zhengfeng | last3=Upadhyay | first3=Sarvagya | last4=Watrous | first4=John | author4-link=John Watrous (computer scientist) | journal = [[Journal of the ACM]] | year=2011 | title=QIP = PSPACE | volume = 58 | issue = 6 | page = A30 | doi = 10.1145/2049697.2049704| s2cid=265099379 }}
</ref>

== Relationship to other classes ==

QMA is related to other known [[complexity classes]] by the following relations:
:<math>\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}\subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}</math>

The first inclusion follows from the definition of [[NP (complexity)|NP]]. The next two inclusions follow from the fact that the verifier is being made more powerful in each case. QCMA is contained in QMA since the verifier can force the prover to send a classical proof by measuring proofs as soon as they are received. The fact that QMA is contained in [[PP (complexity)|PP]] was shown by [[Alexei Kitaev]] and [[John Watrous (computer scientist)|John Watrous]]. PP is also easily shown to be in [[PSPACE]].

It is unknown if any of these inclusions is unconditionally strict, as it is not even known whether P is strictly contained in PSPACE or P = PSPACE. However, the currently best known upper bounds on QMA are<ref>{{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
}}</ref><ref>{{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> and <math>\mathsf{QMA}\subseteq\mathsf{P^{QMA[log]}}</math>,
where both <math>\mathsf{A_0PP}</math> and <math>\mathsf{P^{QMA[log]}}</math> are contained in <math>\mathsf{PP}</math>. It is unlikely that <math>\mathsf{QMA}</math> equals <math>\mathsf{P^{QMA[log]}}</math>, as this would imply <math>\mathsf{QMA}=\mathsf{co}</math>-<math>\mathsf{QMA}</math>. It is unknown whether  <math>\mathsf{P^{QMA[log]}}\subseteq\mathsf{A_0PP}</math> or vice versa.

==References==
{{reflist|2}}

==External links==
*{{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}}
*{{CZoo|QMA|Q#qma}}

{{quantum computing}}
{{ComplexityClasses}}

[[Category:Probabilistic complexity classes]]
[[Category:Quantum complexity theory]]