OP-3009OpenQuantum information

Perfect completeness for finite-register QMA

In the finite-register circuit model with Hadamard, $T$ and CNOT gates and computational-basis initialization/measurement, determine whether $\mathsf{QMA}_1=\mathsf{QMA}$ . Here $\mathsf{QMA}_1$ requires acceptance probability exactly one for some witness on ev

Source-reported statusAs of 2026-09-04Source & evidence ↓

Read original source ↗ 0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

Ordinary QMA permits completeness error; QMA1 does not. Exact acceptance is sensitive to the gate convention, so approximate universality alone cannot be used to transfer a perfect-completeness theorem between models.

What is known: Aaronson constructed a quantum oracle relative to which $\mathsf{QMA}_1\ne\mathsf{QMA}$ . This is a quantum-oracle obstruction, not a classical-oracle separation and not an equality theorem.

Jeffery–Witteveen prove $\mathsf{QMA}=\mathsf{QMA}^{\infty}=\mathsf{QMA}_1^{\infty}$ when the verifier has their specified infinite-dimensional counter with an efficient shift operation. The result, posted in June 2025 and published in PRL in May 2026, removes completeness error using an additional infinite register. Truncation also gives stronger finite-dimensional completeness amplification, but not exactly perfect completeness in ordinary finite-register QMA. The standard equality remains open. Related: A3, A8.

Progress & source assessment

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.

published: Perfect completeness is achievable with a specified infinite counter; this does not settle the ordinary finite-register problem. Evidence

References

[1]Aaronson, 'On perfect completeness for QMA', Quantum Inf. Comput. 9 (2009) link
[2]Jeffery & Witteveen, 'QMA = QMA1 with an infinite counter', PRL (2026; preprint 2025) link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.