In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the deterministic complexity class NP or the probabilistic complexity class MA. It is related to BQP in the same way NP is related to P, or MA is related to BPP.
Informally, it is the set of decision problems for which when the answer is YES, there is a polynomial-size quantum proof (a quantum state) which convinces a polynomial-time quantum verifier of the fact with high probability. Moreover, when the answer is NO, every polynomial-size quantum state is rejected by the verifier with high probability.
More precisely, the proofs have to be verifiable in polynomial time on a quantum computer, such that if the answer is indeed YES, the verifier accepts a correct proof with probability greater than 2/3, and if the answer is NO, then there is no proof which convinces the verifier to accept with probability less than 1/3. As is usually the case, the constants 2/3 and 1/3 can be changed. Changing 2/3 to any constant strictly between 1/2 and 1, or changing 1/3 to any constant strictly between 0 and 1/2, does not change the class QMA.
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.
- , there exists a quantum state such that the probability that V accepts the input is greater than .
- , for all quantum states , the probability that V accepts the input is less than .
where ranges over all quantum states with at most p(x) qubits.
The complexity class is defined to be equal to . However, the constants are not too important since the class remains unchanged if and are set to any constants such that is greater than . Moreover, for any polynomials and , 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.
The local Hamiltonian problem
The local Hamiltonian problem is the quantum analogue of MAX-SAT. A Hamiltonian is a Hermitian matrix acting on quantum states, thus it is for a system of n qubits. A k-local Hamiltonian is a Hamiltonian which can be written as the sum of Hamiltonians, each of which act non-trivially on at most k qubits (instead of all n qubits).
The k-local Hamiltonian problem, which is a promise problem, is defined as follows. The input is a k-local Hamiltonian acting on n qubits, which is the sum of polynomially many Hermitian matrices that act on only k qubits. The input also contains two numbers , such that for some constant c. The problem is to determine whether the smallest eigenvalue of this Hamiltonian is less than a or greater than b, promised that one of these is the case.
The k-local Hamiltonian is QMA-complete for k ≥ 2.
QMA-hardness results are known for even simplistic and physically realistic lattice models of qubits such as  where represent the Pauli matrices . Such models are applicable to universal adiabatic quantum computation.
Other QMA-complete problems
A list of known QMA-complete problems can be found at http://arxiv.org/abs/1212.6312.
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.
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 strict. It is not even known whether P is strictly contained in PSPACE or P = PSPACE.
- Dorit Aharonov; Tomer Naveh (2002). "Quantum NP - A Survey". arXiv:quant-ph/0210077v1 [quant-ph].
- John Watrous (2008). "Quantum Computational Complexity". arXiv:0804.3401v1 [quant-ph].
- Kempe, Julia; Kitaev, Alexei; Regev, Oded (2006). "The Complexity of the Local Hamiltonian Problem". SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 35 (5): 1070–1097. arXiv:quant-ph/0406180v2. doi:10.1137/S0097539704445226. ISSN 1095-7111..
- Biamonte, Jacob; Love, Peter (2008). "Realizable Hamiltonians for Universal Adiabatic Quantum Computers". Phys. Rev. A (Physical Review) 78 (1): 012352. arXiv:0704.1287. doi:10.1103/PhysRevA.78.012352..
- Oliveira, Roberto; Barbara M Terhal (2008). "The complexity of quantum spin systems on a two-dimensional square lattice". Quant. Inf, Comp. 8 (10): 0900–0924. arXiv:quant-ph/0504050.
- Aharonov, Dorit; Daniel Gottesman; Sandy Irani; Julia Kempe (2009-04-01). "The Power of Quantum Systems on a Line". Communications in Mathematical Physics 287 (1): 41–65. doi:10.1007/s00220-008-0710-3.
- Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009). "Two-Message Quantum Interactive Proofs Are in PSPACE". FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society. pp. 534–543. ISBN 978-0-7695-3850-1.
- Watrous, John (2003). "PSPACE has constant-round quantum interactive proof systems". Theor. Comput. Sci. (Essex, UK: Elsevier Science Publishers Ltd.) 292 (3): 575–588. doi:10.1016/S0304-3975(01)00375-9. ISSN 0304-3975.
- Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2010). "QIP = PSPACE". STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing. ACM. pp. 573–582. ISBN 978-1-4503-0050-6.