QMA

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.

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 $\mbox{QMA}(c,s)$ if there exists a polynomial time quantum verifier V and a polynomial p(x) such that:^[1][2]

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

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

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

$\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)})$.

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 $2^n \times 2^n$ 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 $a< b \in [0,1]$, such that $\frac{1}{b-a}=O(n^c)$ 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.^[3]

QMA-hardness results are known for even simplistic and physically realistic lattice models of qubits such as ^[4] $H = \sum_{i}h_i Z_i + \sum_{i<j}J^{ij}Z_iZ_i + \sum_{i<j}K^{ij}X_iX_i$ where $Z, X$ represent the Pauli matrices $\sigma_z, \sigma_x$. Such models are applicable to universal adiabatic quantum computation.

The Hamiltonians for the QMA-complete problem can also be restricted to act on a two dimensional grid of qubits^[5] or a line of quantum particles with 12 states per particle.^[6]

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^[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.^[7]

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

Relationship to other classes

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

$\mbox{P} \subseteq \mbox{NP} \subseteq \mbox{MA} \subseteq \mbox{QCMA} \subseteq \mbox{QMA}\subseteq \mbox{PP} \subseteq \mbox{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 strict. It is not even known whether P is strictly contained in PSPACE or P = PSPACE.

References

1. Aharonov, Dorit; Naveh, Tomer (2002). "Quantum NP – A Survey". arXiv:quant-ph/0210077v1.
2. Watrous, John (2009). "Quantum Computational Complexity". In Meyers, Robert A. Encyclopedia of Complexity and Systems Science. pp. 7174–7201. arXiv:0804.3401. doi:10.1007/978-0-387-30440-3_428.
3. Kempe, Julia; Kitaev, Alexei; Regev, Oded (2006). "The complexity of the local Hamiltonian problem". SIAM Journal on Computing 35 (5): 1070–1097. arXiv:quant-ph/0406180v2. doi:10.1137/S0097539704445226..
4. Biamonte, Jacob; Love, Peter (2008). "Realizable Hamiltonians for universal adiabatic quantum computers". Physical Review A 78 (1): 012352. arXiv:0704.1287. doi:10.1103/PhysRevA.78.012352..
5. Oliveira, Roberto; Terhal, Barbara M. (2008). "The complexity of quantum spin systems on a two-dimensional square lattice". Quantum Information and Computation 8 (10): 900–924. arXiv:quant-ph/0504050.
6. Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (2009). "The power of quantum systems on a line". Communications in Mathematical Physics 287 (1): 41–65. doi:10.1007/s00220-008-0710-3.
7. Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009). "Two-message quantum interactive proofs are in PSPACE". Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09). IEEE Computer Society. pp. 534–543. doi:10.1109/FOCS.2009.30. ISBN 978-0-7695-3850-1.
8. Watrous, John (2003). "PSPACE has constant-round quantum interactive proof systems". Theoretical Computer Science 292 (3): 575–588. doi:10.1016/S0304-3975(01)00375-9.
9. Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2011). "QIP = PSPACE". Journal of the ACM 58 (6): A30. doi:10.1145/2049697.2049704.

External links

• Aaronson, Scott. "PHYS771 Lecture 13: How Big are Quantum States?".
• Complexity Zoo: QMA