QMA, quantum witnesses and local Hamiltonians
Research context
postgraduate concept · established · As of 2026-10-10
QMA gives a polynomial-time quantum verifier a polynomial-qubit witness, accepting some witness on yes-instances and rejecting every witness on no-instances with a bounded completeness/soundness gap.
Key knowledge
QMA gives a polynomial-time quantum verifier a polynomial-qubit witness, accepting some witness on yes-instances and rejecting every witness on no-instances with a bounded completeness/soundness gap. The 2-local Hamiltonian promise problem is QMA-complete with a polynomially resolvable energy gap under the stated input encoding. Preparing or verifying a particular low-energy state is different from efficiently deciding all instances, and the promise gap is essential.
Values and equations
H=sum_j H_j; YES:lambda_min(H)≤a; NO:lambda_min(H)≥b; b−a≥1/poly(n)
- H_j
- Explicitly encoded bounded-norm 2-local Hermitian terms
- a,b
- Promise energy thresholds
- n
- Number of qubits/input-size scale under the specified encoding
Conditions and scope
- Specify local term norms/precision, number of terms, energy thresholds and inverse-polynomial promise gap.
- A QMA witness may be consumed by verification; naive reuse and classical witness substitution require separate theorems.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Author checked this English statement, displayed equation where present and stated hypotheses against these source locations: §IV BQP/resource/oracle model, §V QMA promises and 2-local Hamiltonian Theorem 8; historical survey. The check is bounded to the recorded claims; no complete proof reconstruction, software proof replay or universal literature completeness is claimed.
2026-10-10 · Author source-body/statement/equation/domain check, with graph associations scoped individually. Separate independent content/source/inventory review is required before branch closure.
Entry details
Permanent link to this entry ↗- Record identity
- research-info-qma-hamiltonian
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference