In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the nonprobabilistic 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.
Contents
- Definition
- Problems in QMA
- The local Hamiltonian problem
- Other QMA complete problems
- Related classes
- Relationship to other classes
- References
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 greater 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.
Definition
A language L is in
where
The complexity class
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
The local Hamiltonian problem is the quantum analogue of MAX-SAT. A Hamiltonian is a Hermitian matrix acting on quantum states, thus it is
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
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
The Hamiltonians for the QMA-complete problem can also be restricted to act on a two dimensional grid of qubits or a line of quantum particles with 12 states per particle.
Other QMA-complete problems
A list of known QMA-complete problems can be found at http://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 strict. It is not even known whether P is strictly contained in PSPACE or P = PSPACE.