QMA

In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the set of languages for which, when the answer is YES, 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 answer is NO, 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 and P. It is also analogous to the relationship between the probabilistic complexity class MA and 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 and Arthur verifies it as a BQP machine.
Definition.
A language L is in formula_1 if there exists a polynomial time quantum verifier V and a polynomial p(x) such that:
where formula_3 ranges over all quantum states with at most p(|x|) qubits.
The complexity class formula_11 is defined to be equal to formula_12. However, the constants are not too important since the class remains unchanged if formula_5 and formula_9 are set to any constants such that formula_5 is greater than formula_9. Moreover, for any polynomials formula_17 and formula_18, we have
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 reduced to it. A problem is said to be QMA-complete if it is QMA-hard and in QMA.
The local Hamiltonian problem.
A k-local Hamiltonian (quantum mechanics) formula_20 is a Hermitian matrix acting on n qubits which can be represented as the sum of formula_21 Hamiltonian Terms acting upon at most formula_22 qubits each.
formula_23
The general k-local Hamiltonian problem is, given a k-local Hamiltonian formula_20, to find the smallest eigenvalue formula_25 of formula_20. formula_25 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 formula_28 where formula_29, to decide if there exists a quantum eigenstate formula_3 of formula_20 with associated eigenvalue formula_25, such that formula_33 or if formula_34. 
The local Hamiltonian problem is the quantum analogue of MAX-SAT. The k-local Hamiltonian problem is QMA-complete for k ≥ 2. 
The 2-local Hamiltonian problem restricted to act on a two dimensional grid of qubits, is also QMA-complete. 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.
If the system is translationally-invariant, its local Hamiltonian problem becomes QMAEXP-complete (as the problem input is encoded in the system size, the verifier now has exponential runtime while maintaining the same promise gap).
QMA-hardness results are known for simple lattice models of qubits such as the ZX Hamiltonian 
formula_35 
where formula_36 represent the Pauli matrices formula_37. Such models are applicable to universal adiabatic quantum computation.
k-local Hamiltonians problems are analogous to classical Constraint Satisfaction Problems. The following table illustrates the analogous gadgets between classical CSPs and Hamiltonians.
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), 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.
QIP is QIP(k) where k is allowed to be polynomial in the number of qubits. It is known that QIP(3) = QIP. It is also known that QIP = IP = PSPACE.
Relationship to other classes.
QMA is related to other known complexity classes by the following relations:
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
where both formula_41 and formula_42 are contained in formula_43. It is unlikely that formula_44 equals either formula_41 or formula_42, as equality with the former would collapse the Polynomial-Time Hierarchy (PH), while equality with the latter would imply formula_47-formula_44. It is unknown whether formula_49 or vice versa.