Matches in DBpedia 2014 for { <http://dbpedia.org/resource/QMA> ?p ?o. }
Showing items 1 to 21 of
21
with 100 items per page.
- QMA abstract "In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the deterministic 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 less 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 greater than 1/2 and 1/3 to any constant strictly lesser than 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.".
- QMA wikiPageExternalLink 1212.6312..
- QMA wikiPageID "23545978".
- QMA wikiPageRevisionID "606782954".
- QMA hasPhotoCollection QMA.
- QMA subject Category:Probabilistic_complexity_classes.
- QMA subject Category:Quantum_complexity_theory.
- QMA type Abstraction100002137.
- QMA type Class107997703.
- QMA type Collection107951464.
- QMA type Group100031264.
- QMA type ProbabilisticComplexityClasses.
- QMA comment "In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the deterministic 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.".
- QMA label "QMA".
- QMA label "QMA".
- QMA sameAs m.06w9zw7.
- QMA sameAs Q4047721.
- QMA sameAs Q4047721.
- QMA sameAs QMA.
- QMA wasDerivedFrom QMA?oldid=606782954.
- QMA isPrimaryTopicOf QMA.