QMA, as an abbreviation forQuantumMerlin Arthur, refers to acomplexity class incomputational complexity theory. It is the set of allformal languages that satisfy the following properties:

1. If astring is in the language, then there is a polynomial-size quantum proof (representable as aquantum state) that convinces apolynomial-time quantum verifier (running on aquantum computer) of this fact with high probability.
2. If a string isnot in the language, every polynomial-size quantum state is rejected by the verifier with high probability.

The relationship between QMA andBQP is analogous to the relationship between the complexity classesNP andP. It is also analogous to the relationship between the probabilistic complexity classesMA andBPP.

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 quantumcertificate and Arthur verifies it as a BQP machine.

A languageL is in${\displaystyle \mathsf{Q}\mathsf{M}\mathsf{A}(c,s)}$ if there exists a polynomial time quantum verifierV and a polynomial⁠${\displaystyle p(x)}$⁠ such that:^[1][2][3]

• ${\displaystyle \mathrm{\forall }x\in L}$, there exists a quantum state${\displaystyle |\psi ⟩}$ such that the probability thatV accepts the input${\displaystyle (|x⟩,|\psi ⟩)}$ is greater thanc.
• ${\displaystyle \mathrm{\forall }x\notin L}$, and for all quantum states${\displaystyle |\psi ⟩}$ with at most${\displaystyle p(|x|)}$qubits, the probability thatV accepts the input${\displaystyle (|x⟩,|\psi ⟩)}$ is less thans.

The complexity class${\displaystyle \mathsf{Q}\mathsf{M}\mathsf{A}}$ is defined to be equal to${\displaystyle \mathsf{Q}\mathsf{M}\mathsf{A}(2/3,1/3)}$. However, the constants are not too important since the class remains unchanged ifc ands are set to any constants such thatc is greater thans. Moreover, for any polynomials${\displaystyle q(n)}$ and${\displaystyle r(n)}$, we have

${\displaystyle \mathsf{Q}\mathsf{M}\mathsf{A}\left(\frac{2}{3},\frac{1}{3}\right)=\mathsf{Q}\mathsf{M}\mathsf{A}\left(\frac{1}{2}+\frac{1}{q(n)},\frac{1}{2}-\frac{1}{q(n)}\right)=\mathsf{Q}\mathsf{M}\mathsf{A}(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 toNP-hard, if every problem in QMA can bereduced to it. A problem is said to be QMA-complete if it is QMA-hard and in QMA.

Ak-localHamiltonian (quantum mechanics)${\displaystyle H}$ is aHermitian matrix acting on n qubits which can be represented as the sum of${\displaystyle m}$ Hamiltonian Terms acting upon at most${\displaystyle k}$ qubits each.

${\displaystyle H=\sum _{i=1}^m{H}_i}$

The generalk-local Hamiltonian problem is, given ak-local Hamiltonian${\displaystyle H}$, to find the smallest eigenvalue${\displaystyle \lambda }$ of${\displaystyle H}$.^[4]${\displaystyle \lambda }$ is also called the ground state energy of the Hamiltonian.

The decision version of thek-local Hamiltonian problem is a type ofpromise problem and is defined as, given ak-local Hamiltonian and${\displaystyle \alpha ,\beta }$ where${\displaystyle \alpha >\beta }$, to decide if there exists a quantum eigenstate${\displaystyle |\psi ⟩}$ of${\displaystyle H}$ with associated eigenvalue${\displaystyle \lambda }$, such that${\displaystyle \lambda \le \beta }$ or if${\displaystyle \lambda \ge \alpha }$.

The local Hamiltonian problem is the quantum analogue ofMAX-SAT. Thek-local Hamiltonian problem is QMA-complete for k ≥ 2.^[5]

The 2-local Hamiltonian problem restricted to act on a two dimensional grid ofqubits, is also QMA-complete.^[6] It has been shown that thek-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.^[7]If the system is translationally-invariant, its local Hamiltonian problem becomes QMA_EXP-complete (as the problem input is encoded in the system size, the verifier now has exponential runtime while maintaining the same promise gap).^[8][9]

QMA-hardness results are known for simplelattice models ofqubits such as the ZX Hamiltonian^[10] where${\displaystyle Z,X}$ represent thePauli matrices${\displaystyle {\sigma }_z,{\sigma }_x}$. Such models are applicable to universaladiabatic quantum computation.

k-local Hamiltonians problems are analogous to classicalConstraint Satisfaction Problems.^[11] The following table illustrates the analogous gadgets between classical CSPs and Hamiltonians.

A list of known QMA-complete problems can be found athttps://arxiv.org/abs/1212.6312.

QCMA (orMQA^[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 forQuantum 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.^[12]

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

QMA is related to other knowncomplexity classes by the following relations:

${\displaystyle \mathsf{P}\subseteq \mathsf{N}\mathsf{P}\subseteq \mathsf{M}\mathsf{A}\subseteq \mathsf{Q}\mathsf{C}\mathsf{M}\mathsf{A}\subseteq \mathsf{Q}\mathsf{M}\mathsf{A}\subseteq \mathsf{P}\mathsf{P}\subseteq \mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}}$

The first inclusion follows from the definition ofNP. 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 inPP was shown byAlexei Kitaev andJohn Watrous. PP is also easily shown to be inPSPACE.

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^[15][16]

${\displaystyle \mathsf{Q}\mathsf{M}\mathsf{A}\subseteq {\mathsf{A}}_{\mathsf{0}}\mathsf{P}\mathsf{P}}$ and${\displaystyle \mathsf{Q}\mathsf{M}\mathsf{A}\subseteq {\mathsf{P}}^{\mathsf{Q}\mathsf{M}\mathsf{A}\mathsf{[}\mathsf{l}\mathsf{o}\mathsf{g}\mathsf{]}}}$,

where both${\displaystyle {\mathsf{A}}_{\mathsf{0}}\mathsf{P}\mathsf{P}}$ and${\displaystyle {\mathsf{P}}^{\mathsf{Q}\mathsf{M}\mathsf{A}\mathsf{[}\mathsf{l}\mathsf{o}\mathsf{g}\mathsf{]}}}$ are contained in${\displaystyle \mathsf{P}\mathsf{P}}$. It is unlikely that${\displaystyle \mathsf{Q}\mathsf{M}\mathsf{A}}$ equals${\displaystyle {\mathsf{P}}^{\mathsf{Q}\mathsf{M}\mathsf{A}\mathsf{[}\mathsf{l}\mathsf{o}\mathsf{g}\mathsf{]}}}$, as this would imply${\displaystyle \mathsf{Q}\mathsf{M}\mathsf{A}=\mathsf{c}\mathsf{o}}$-${\displaystyle \mathsf{Q}\mathsf{M}\mathsf{A}}$. It is unknown whether${\displaystyle {\mathsf{P}}^{\mathsf{Q}\mathsf{M}\mathsf{A}\mathsf{[}\mathsf{l}\mathsf{o}\mathsf{g}\mathsf{]}}\subseteq {\mathsf{A}}_{\mathsf{0}}\mathsf{P}\mathsf{P}}$ 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). Archived fromthe original(PDF) on 2019-11-04. Retrieved2020-02-28.
• Complexity Zoo:QMA

• Probabilistic complexity classes
• Quantum complexity theory

• Articles with short description
• Short description is different from Wikidata