Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
QMA
Summary
In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the set of languages for which, when a string is in the language, 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 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 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.
A language L is in if there exists a polynomial time quantum verifier V and a polynomial p(x) such that:
there exists a quantum state such that the probability that V accepts the input is greater than c.
for all quantum states , the probability that V accepts the input is less than s.
where ranges over all quantum states with at most qubits.
The complexity class is defined to be equal to . 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 and , we have
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.
A k-local Hamiltonian (quantum mechanics) is a Hermitian matrix acting on n qubits which can be represented as the sum of Hamiltonian Terms acting upon at most qubits each.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.