QMA¶
QMA is a recurring computational complexity, quantum computing identity in which polynomial-size quantum witnesses are verified in quantum polynomial time with bounded completeness and soundness error.
Core Idea¶
QMA—Quantum Merlin–Arthur—is the class of decision or promise problems for which a polynomial-size quantum witness can be checked by a polynomial-time quantum verifier with a bounded completeness–soundness gap. For a yes-instance, there must exist a witness state that makes the verifier accept with probability at least the completeness threshold \(c\). For a no-instance, every witness state of the allowed size must be accepted with probability at most the soundness threshold \(s\).
Scope of Application¶
-
Complexity classification. Problems are placed in QMA only after witness size, verifier resources, completeness, soundness, and promise are specified.
-
Completeness proofs. Polynomial-time reductions to or from canonical problems identify the class's hardest representative structure.
-
Local Hamiltonian. Low-energy quantum states provide the canonical QMA witness and make this the central complete-problem habitat.
-
Containment and separation research. QMA is compared with BQP, QCMA, NP, PP, PSPACE, and variants under explicit complexity assumptions.
-
Gap amplification. Verification procedures transform completeness and soundness while controlling witness and circuit resources.
Clarity¶
QMA separates efficient quantum verification from efficient quantum solution. Its name fixes the quantifiers that informal talk of a ‘quantum proof’ can obscure: some polynomial-size witness must make a yes-instance accept with high probability, whereas every allowed witness must fail to make a no-instance accept beyond the soundness bound. It also keeps membership, hardness, and completeness distinct.
Manages Complexity¶
QMA compresses an enormous variety of quantum verification procedures into a witness size, verifier runtime, completeness threshold, soundness threshold, and promise gap. Once those quantities scale polynomially and remain separated, amplification makes particular constant thresholds secondary. The analyst need not inspect every alleged proof state in a no-instance; the universal soundness requirement summarizes them as a maximum acceptance probability. Problems can then be routed by containment, reduction, hardness, and completeness.
Abstract Reasoning¶
Membership move. From a polynomial-size quantum witness and polynomial-time verifier satisfying completeness and soundness bounds, infer QMA membership. Hardness move. From an efficient reduction of every QMA problem to a target, infer QMA-hardness; combine with membership only then to infer completeness. Soundness move. In a no-instance, reason universally over all allowed witnesses rather than evaluating one failed proof. Amplification move. From a nonzero inverse-polynomial or constant gap under the standard conditions, infer that repeated verification can reduce error without changing the class. Boundary move.
Knowledge Transfer¶
Within the home domain. QMA transfers literally across quantum-complexity problems whose yes-instances admit polynomial-size quantum witnesses verified with bounded error by efficient quantum computation. Completeness, soundness, amplification, reductions, and verifier circuits retain exact meanings. Beyond the home domain (C — formal class). The construct applies to any encoded decision problem satisfying this verification definition; application subject matter can vary without metaphor. Its limit is conceptual: QMA is not a physical certification protocol, not arbitrary quantum advantage, and not classical NP with merely faster hardware. Claims require explicit encodings, promise gaps, resource bounds, and reductions.
Relationships to Other Abstractions¶
Current abstraction QMA Domain-specific
Parents (1) — more general patterns this builds on
-
QMA is a kind of Complexity Class Domain-specific
QMA is a domain-specific kind of Complexity Class: QMA is a recurring computational complexity, quantum computing identity in which polynomial-size quantum witnesses are verified in quantum polynomial time with bounded completeness and soundness error.
Hierarchy paths (6) — routes to 5 parentless roots
- QMA → Complexity Class → Classification
- QMA → Complexity Class → Complexity (Time/Space) → Complexity
- QMA → Complexity Class → Complexity (Time/Space) → Constraint
- QMA → Complexity Class → Complexity (Time/Space) → Scaling and Scale Dependence → Scale
- QMA → Complexity Class → Complexity (Time/Space) → Asymptotic Behavior → Scaling and Scale Dependence → Scale
- QMA → Complexity Class → Complexity (Time/Space) → Asymptotic Behavior → Approximation → Representation → Abstraction
Neighborhood in Abstraction Space¶
QMA sits in a sparse region of the domain-specific corpus (69th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Computational Complexity & Hardness (17 abstractions)
Nearest neighbors
- NTIME — 0.86
- Exact Quantum Polynomial Time — 0.85
- Elementary-embedding large-cardinal schema — 0.85
- Computational hardness assumption — 0.83
- Complexity Class — 0.83
Computed from structural-signature embeddings · 2026-10-08