QMA

A language L is in ${\displaystyle {\mbox{QMA}}(c,s)}$ if there exists a polynomial time quantum verifier V and a polynomial p(x) such that:[1][2][3]

• ${\displaystyle \forall x\in L}$, there exists a quantum state ${\displaystyle |\psi \rangle }$ such that the probability that V accepts the input ${\displaystyle (|x\rangle ,|\psi \rangle )}$ is greater than ${\displaystyle c}$.
• ${\displaystyle \forall x\notin L}$, for all quantum states ${\displaystyle |\psi \rangle }$, the probability that V accepts the input ${\displaystyle (|x\rangle ,|\psi \rangle )}$ is less than ${\displaystyle s}$.

where ${\displaystyle |\psi \rangle }$ ranges over all quantum states with at most p(|x|) qubits.

The complexity class ${\displaystyle {\mbox{QMA}}}$ is defined to be equal to ${\displaystyle {\mbox{QMA}}({2}/{3},1/3)}$. However, the constants are not too important since the class remains unchanged if ${\displaystyle c}$ and ${\displaystyle s}$ are set to any constants such that ${\displaystyle c}$ is greater than ${\displaystyle s}$. Moreover, for any polynomials ${\displaystyle q(n)}$ and ${\displaystyle r(n)}$, we have

${\displaystyle {\mbox{QMA}}\left({\frac {2}{3}},{\frac {1}{3}}\right)={\mbox{QMA}}\left({\frac {1}{2}}+{\frac {1}{q(n)}},{\frac {1}{2}}-{\frac {1}{q(n)}}\right)={\mbox{QMA}}(1-2^{-r(n)},2^{-r(n)})}$.

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 reduced to it. A problem is said to be QMA-complete if it is QMA-hard and in QMA.

QCMA (or MQA[2]), 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.[10]

QIP is QIP(k) where k is allowed to be polynomial in the number of qubits. It is known that QIP(3) = QIP.[11] It is also known that QIP = IP = PSPACE.[12]

QMA is related to other known complexity classes by the following relations:

${\displaystyle {\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {MA}}\subseteq {\mathsf {QCMA}}\subseteq {\mathsf {QMA}}\subseteq {\mathsf {PP}}\subseteq {\mathsf {PSPACE}}}$

The first inclusion follows from the definition of 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 was shown by Alexei Kitaev and 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 [13] [14]

${\displaystyle {\mathsf {QMA}}\subseteq {\mathsf {A_{0}PP}}}$ and ${\displaystyle {\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}}$,

where both ${\displaystyle {\mathsf {A_{0}PP}}}$ and ${\displaystyle {\mathsf {P^{QMA[log]}}}}$ are contained in ${\displaystyle {\mathsf {PP}}}$. It is unlikely that ${\displaystyle {\mathsf {QMA}}}$ equals either ${\displaystyle {\mathsf {A_{0}PP}}}$ or ${\displaystyle {\mathsf {P^{QMA[log]}}}}$, as equality with the former would collapse the Polynomial-Time Hierarchy (PH), while equality with the latter would imply ${\displaystyle {\mathsf {QMA}}={\mathsf {co}}}$-${\displaystyle {\mathsf {QMA}}}$. It is unknown whether ${\displaystyle {\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}}$ or vice versa.

• 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: QMA