QMA

QMA, as an abbreviation for Quantum Merlin Arthur, refers to a complexity class in computational complexity theory.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

QMA, as an abbreviation for Quantum Merlin Arthur, refers to a complexity class in computational complexity theory. It is the set of all formal languages that satisfy the following properties: # If a string is in the language, then there is a polynomial-size quantum proof (representable as a quantum state) that convinces a polynomial-time quantum verifier (running on a quantum computer) of this fact with high probability. # If a string is not in the language, 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 the complexity classes NP and P. It is also analogous to the relationship between the probabilistic complexity classes 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.

QMA, as an abbreviation for Quantum Merlin Arthur, refers to a complexity class in computational complexity theory. It is the set of all formal languages that satisfy the following properties: If a string is in the language, then there is a polynomial-size quantum proof (representable as a quantum state) that convinces a polynomial-time quantum verifier (running on a quantum computer) of this fact with high probability.

If a string is not in the language, 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 the complexity classes NP and P. It is also analogous to the relationship between the probabilistic complexity classes 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. \mathsf{QMA}\left(\frac{2}{3},\frac{1}{3}\right) =\mathsf{QMA}\left(\frac{1}{2}+\frac{1}{q(n)},\frac{1}{2}-\frac{1}{q(n)}\right)=\mathsf{QMA}(1-2^{-r(n)},2^{-r(n)}) . H = \sum_{i=1}^m H_i The general k-local Hamiltonian problem is, given a k-local Hamiltonian H , to find the smallest eigenvalue \lambda of H . \lambda 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 \alpha, \beta where \alpha > \beta , to decide if there exists a quantum eigenstate |\psi\rangle of H with associated eigenvalue \lambda , such that \lambda \leq \beta or if \lambda \geq \alpha . 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 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). QMA-hardness results are known for simple lattice models of qubits such as the ZX Hamiltonian H_{ZX} = \sum_{i}h_i Z_i + \sum_{i} \Delta_i X_i + \sum_{i where Z, X represent the Pauli matrices \sigma_z, \sigma_x . 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. 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. 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 \mathsf{QMA}\subseteq\mathsf{A_0PP} and \mathsf{QMA}\subseteq\mathsf{P^{QMA[log]}} , where both \mathsf{A_0PP} and \mathsf{P^{QMA[log]}} are contained in \mathsf{PP} . It is unlikely that \mathsf{QMA} equals \mathsf{P^{QMA[log]}} , as this would imply \mathsf{QMA}=\mathsf{co} - \mathsf{QMA} .

It is unknown whether \mathsf{P^{QMA[log]}}\subseteq\mathsf{A_0PP} or vice versa.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368670417 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.