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.

Version: v1 · 2026-09-28 · History
Domain-specific #: 11590
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Computational Complexity, Quantum Computing → Computer Science & Software Engineering

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\). The universal quantifier over all purported proofs in the no-case is as important as the existence of one convincing proof in the yes-case. Standard definitions choose constants such as \(c=2/3\) and \(s=1/3\), but amplification makes the particular separated constants inessential.

The class formalizes efficient quantum verification rather than efficient quantum solution. The witness may be an unknown multi-qubit state supplied by an untrusted prover; the verifier applies a polynomial-size quantum circuit and measures an output qubit. Because quantum states cannot generally be copied or read as classical descriptions, QMA is not obtained by simply replacing a classical verifier's hardware. Its acceptance relation must account for superposition, entanglement, measurement, and the possibility that a malicious witness exploits them. BQP is contained in QMA because a verifier may ignore the witness, and classical NP certificates can be encoded in computational-basis states, placing NP within QMA. Whether the inclusions collapse is a separate question.

QMA-completeness identifies problems that capture the full verification power of the class under efficient reductions. The \(k\)-local Hamiltonian promise problem is canonical: given a sum of local quantum interactions and separated energy thresholds, decide whether the ground-state energy lies below the lower threshold or above the upper one. A low-energy quantum state serves as the witness. The promise gap matters; inputs whose energy falls between the thresholds need not be classified. QMA is therefore not a synonym for quantum computation generally, for QMA-hardness alone, or for the interactive class QIP. It is a precisely quantified witness–verifier abstraction with resource bounds and probabilistic guarantees.

Structural Signature¶

Sig role-phrases:

the decision-or-promise instance — an encoded input whose yes/no classification is required only outside any declared promise gap
the untrusted quantum witness — a polynomial-size state that may convince the verifier on a yes-instance
the polynomial quantum verifier — a uniformly efficient quantum circuit that processes the instance and witness and measures acceptance
the existential completeness clause — at least one allowed witness makes every yes-instance accepted with probability at least \(c\)
the universal soundness clause — every allowed witness for a no-instance is accepted with probability at most \(s\)
the bounded probability gap — separated thresholds \(c>s\) whose conventional constant values can be amplified
the resource envelope — polynomial witness size, circuit size, runtime, and precision bounding the verification procedure
the reduction structure — efficient mappings used to define QMA-hard and QMA-complete problems
the canonical energy witness — a low-energy state demonstrating the yes-side of local-Hamiltonian instances

What It Is Not¶

Not all quantum computation. QMA classifies efficiently quantum-verifiable decision or promise problems, not every task a quantum computer can perform.
Not efficient solution by the verifier. The verifier checks a supplied witness; the definition does not require it to discover the witness or solve the instance unaided.
Not a classical NP verifier on quantum hardware. An untrusted quantum state introduces superposition, entanglement, measurement, and no-cloning constraints absent from classical certificates.
Not QMA-hardness alone. Completeness additionally requires membership in QMA under the chosen efficient reduction.
Not classification inside the promise gap. For a promise problem such as local Hamiltonian, inputs between the separated thresholds need not receive a prescribed answer.
Not dependent on the conventional ⅔ and ⅓ constants. Any efficiently separated completeness–soundness gap of the standard kind can be amplified.
Not the interactive class QIP. QMA supplies a single quantum witness followed by verification, rather than a general multi-round interaction.

Scope of Application¶

QMA applies to asymptotic decision or promise problems whose yes-instances admit polynomial-size quantum witnesses verifiable by uniform polynomial-time quantum circuits.

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.
Variant analysis. Multiple proofs, classical witnesses, interaction, restricted gates, and exponentially small gaps define different classes unless equivalence is proved.
Applicability boundary. Laboratory preparation, general quantum optimization, and QMA-hardness alone do not establish membership in the class.

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. The sharper complexity question is whether a bounded-error quantum verifier can check a supplied quantum state within polynomial resources and a stated promise gap.

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. This small resource-and-quantifier signature makes local Hamiltonians, quantum proofs, and verifier circuits comparable without erasing the distinction between finding a witness and checking one.

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. Do not infer that the verifier can construct the witness or solve unaided.

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.

Examples¶

Canonical¶

In the k-local Hamiltonian problem, an input describes a Hamiltonian H that is the sum of terms, each acting on at most k qubits, together with thresholds a<b separated by an inverse-polynomial gap. The promise is that the smallest eigenvalue is either at most a or at least b. On a yes-instance, Merlin can send a low-energy quantum state. Arthur's polynomial-size quantum verifier samples or combines local energy measurements so that such a witness is accepted with high probability. On a no-instance, every possible witness has energy above the upper threshold and must be rejected with bounded error. This problem is the canonical QMA-complete analogue of Boolean satisfiability's role for NP.

Mapped back: The threshold-separated Hamiltonian is the decision-or-promise instance. The low-energy state is the untrusted quantum witness and the canonical energy witness; Arthur is the polynomial quantum verifier, with the existential completeness clause, universal soundness clause, and bounded probability gap.

Applied / In Practice¶

A proposed quantum verification protocol may ask whether a many-body system has a state satisfying a collection of local constraints. The verifier cannot classically receive a full amplitude list, but can receive copies or encodings of a polynomial-size quantum witness and perform efficient local tests. To claim membership in QMA, the protocol must specify an input encoding, polynomial resource bounds, a yes-witness strategy, and a soundness statement against every malicious witness on no-instances. Repeating or amplifying the verification can widen confidence while preserving polynomial resources. Merely running a quantum experiment or obtaining a low measured energy is not enough; the promise gap and adversarial soundness are the class-defining work.

Mapped back: The encoded constraint system supplies the decision-or-promise instance and the submitted state supplies the untrusted quantum witness. Efficient local tests enforce the resource envelope; amplification acts on the bounded probability gap, while universal quantification over cheating states is the universal soundness clause.

Structural Tensions¶

T1 — Identity versus admissible variation. QMA must remain recognizable across legitimate variants. Admissible variation is bounded by this condition: Problems are placed in QMA only after witness size, verifier resources, completeness, soundness, and promise are specified. The stable element is expressed by this invariant: 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. Treating every surface change as a new abstraction fragments the identity, while allowing a change to the constitutive relation produces a false positive.

Diagnostic: After the proposed variation, can an analyst still establish this invariant: 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?

T2 — Recognition versus proxy. The domain needs observable or inferential evidence for QMA, but the evidence is not automatically the identity. The working recognition rule is: the untrusted quantum witness — a polynomial-size state that may convince the verifier on a yes-instance. A familiar indicator can occur without the defining relation, and the relation can persist when a customary detector is unavailable.

Diagnostic: Does the evidence establish the defining claim—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—or only a correlated sign?

T3 — Definition versus operational judgment. A compact definition aids reuse, whereas actual classification in computational complexity can require expert decisions about boundary conditions, measurements, conventions, or exceptions. The class formalizes efficient quantum verification rather than efficient quantum solution. The definition must constrain those judgments without pretending that every admissible case can be recognized from a label alone.

Diagnostic: Which observation would make a competent practitioner reject the classification under the stated definition?

T4 — Scope versus overextension. QMA has a genuine habitat in which problems are placed in QMA only after witness size, verifier resources, completeness, soundness, and promise are specified. Yet Laboratory preparation, general quantum optimization, and QMA-hardness alone do not establish membership in the class. A useful application map therefore has to be broad enough to cover recurring practice and narrow enough to exclude merely topical or metaphorical occurrences.

Diagnostic: Can the claimed application fill the same carrier and relation roles, or has only the name traveled?

T5 — Transfer versus domain accent. Knowledge about QMA can travel within its home domain, and some structural lessons may travel farther. QMA transfers literally across quantum-complexity problems whose yes-instances admit polynomial-size quantum witnesses verified with bounded error by efficient quantum computation. What transfers must be separated from the specialist vocabulary, warrant, and closure conditions that remain anchored in computational complexity.

Diagnostic: Is the receiving case a literal instance of QMA, a co-instance of Complexity Class, or only an analogy?

T6 — Autonomy versus reduction. QMA is a strict specialization of Complexity Class, but the edge does not erase the domain differentia. The broader node supplies only the necessary structural relation; computational complexity supplies the carrier, warrant, boundary, and exception conditions expressed by this identity: 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. The entry is over-split if those conditions add no discriminating work and under-specified if the parent alone is used for cases that require them.

Diagnostic: Can a domain expert use the added conditions to distinguish QMA from another case that equally instantiates Complexity Class?

Structural–Framed Character¶

QMA is mixed: structurally specifiable but materially dependent on its disciplinary frame. Its structural side consists of the carrier the decision-or-promise instance — an encoded input whose yes/no classification is required only outside any declared promise gap and the constitutive relation 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. Its framed side comes from computational complexity, which fixes what the terms denote, what counts as evidence, and when a qualification or exception defeats the classification.

Across the principal tests, the entry is not merely a free-floating pattern. Evaluative weight: the identity can be stated descriptively even when its use has practical or normative consequences. Practice dependence: the untrusted quantum witness — a polynomial-size state that may convince the verifier on a yes-instance. Institutional stabilization: disciplinary conventions may stabilize the name and test without necessarily creating every underlying event or relation. Vocabulary portability: the invariant is 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. Import versus recognition: an outside case qualifies literally only if the same typed roles and collapse condition are available; otherwise the comparison is analogical.

The reusable remainder is Complexity Class under a reviewed subsumption relation. That node preserves the necessary cross-domain organization after the computational complexity-specific carrier, evidence, and exceptions are removed. QMA remains autonomous because its recognition and collapse conditions distinguish cases that the parent alone leaves together.

Structural Core vs. Domain Accent¶

What is skeletal. The portable skeleton is a typed carrier organized by a constitutive relation, an invariant, a recognition test, and a collapse condition. Here the carrier is the decision-or-promise instance — an encoded input whose yes/no classification is required only outside any declared promise gap. The decisive relation is 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, which also states the controlling invariant at this level. Stripped of specialist nouns, this organization is represented by Complexity Class.

What is domain-bound. computational complexity supplies the actual objects or agents, admissible transformations, units or conventions, standards of warrant, and named exceptions. In this case, recognition requires evidence for the untrusted quantum witness — a polynomial-size state that may convince the verifier on a yes-instance. Admissible variation is bounded by the condition that problems are placed in QMA only after witness size, verifier resources, completeness, soundness, and promise are specified, and the classification collapses when qMA classifies efficiently quantum-verifiable decision or promise problems, not every task a quantum computer can perform. These are constitutive differentia, not illustrative decoration.

Why it remains a domain-specific node. The reviewed DAG relation is subsumption to Complexity Class. Outside computational complexity, the parent captures only the reusable structural remainder. The specialist name remains literal only where the canonical energy witness — a low-energy state demonstrating the yes-side of local-Hamiltonian instances can be established under the domain's standards of warrant.

This entry is a kind of Complexity Class.

Immediate parent — Complexity Class (subsumption). 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. The parent supplies the necessary broader identity—Sort computational problems into a small lattice of named strata — P, NP, PSPACE, and their kin — by the resource bound they admit under a fixed model, so that placing a problem by one reduction transitively imports its whole feasibility profile.—while the candidate adds the source-domain carrier, recognition rule, and failure conditions. The defining source account begins: 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.
Nearest catalog surface declined — Quantum Interactive Polynomial Time (QIP). Its rematch score was 0.289113. Retrieval proximity did not establish synonymy or parentage; the carrier, invariant, and collapse condition remain different.
Related reasoning operations. Evidence, comparison, boundary testing, and representation can support a case without becoming additional DAG parents.

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.

Neighborhood in Abstraction Space¶

QMA sits in a sparse region of the domain-specific corpus (69^th 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

Not to Be Confused With¶

Complexity Class. This is the reviewed immediate parent or structural prerequisite, not a synonym. Tell: retain QMA only when the domain-specific relation 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. and its source-domain warrant are established; otherwise route the case to Complexity Class.
Quantum Calculus. This is the closest catalog retrieval surface, not an accepted synonym or parent. Tell: Ask which entry's carrier, invariant, and collapse test the case actually satisfies; shared vocabulary or a score of 0.697874 is insufficient.
Not all quantum computation. QMA classifies efficiently quantum-verifiable decision or promise problems, not every task a quantum computer can perform. Tell: Require the positive recognition condition that the untrusted quantum witness — a polynomial-size state that may convince the verifier on a yes-instance.
Not efficient solution by the verifier. The verifier checks a supplied witness; the definition does not require it to discover the witness or solve the instance unaided. Tell: Replace the familiar surface feature and test whether 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.
A detector, representation, or consequence. A method may reveal QMA, a notation may describe it, and an outcome may follow from it without any of those being identical to the abstraction. Tell: Would the defining relation remain if the present detector, notation, or downstream effect changed?
A metaphorical transfer. A case outside the home domain may resemble the structure while lacking its native role types and standards of warrant. Tell: If only the general organization survives, route the comparison to Complexity Class rather than treating it as another QMA instance.

References¶

Frozen Wikipedia revision: https://en.wikipedia.org/wiki/QMA (revision 1368670417).
DOI: https://doi.org/10.1007/978-0-387-30440-3_428
DOI: https://doi.org/10.1561/0400000066
DOI: https://doi.org/10.1137/S0097539704445226
DOI: https://doi.org/10.26421/QIC8.10-2
DOI: https://doi.org/10.1007/s00220-008-0710-3
DOI: https://doi.org/10.1007/s00023-017-0609-7
DOI: https://doi.org/10.1103/PhysRevA.78.012352
DOI: https://doi.org/10.1109/FOCS.2009.30
Supporting reference preserved in the packet: https://www.cs.cmu.edu/~odonnell/quantum15/lecture24.pdf
Supporting reference preserved in the packet: http://henryyuen.net/fall2020/complexity_of_entanglement_notes.pdf
Supporting reference preserved in the packet: https://web.archive.org/web/20250228110611/https://www.henryyuen.net/fall2020/complexity_of_entanglement_notes.pdf
Supporting reference preserved in the packet: https://arxiv.org/abs/1212.6312
Supporting reference preserved in the packet: http://scholarbank.nus.edu.sg/handle/10635/40740
Supporting reference preserved in the packet: https://eccc.weizmann.ac.il/eccc-reports/2003/TR03-021/index.html
Supporting reference preserved in the packet: http://www.scottaaronson.com/democritus/lec13.html
Supporting reference preserved in the packet: http://groups.uni-paderborn.de/fg-qi/courses/UPB_QCOMPLEXITY/2019/notes/Lecture%205%20-%20Quantum%20Merlin%20Arthur%20(QMA)%20and%20strong%20error%20reduction.pdf

The frozen Wikipedia revision is discovery provenance. The cited source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; URL transport failure alone was not treated as substantive contradiction.