Lesson plan
QMA
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.
Article summary
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.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.