PaperlayerView exact revision on arXiv

Source-linked AI summary

QMA has perfect completeness

Sabee Grewal, Dorian Rudolph

arXiv:2609.13032v1quant-phcs.CC

TL;DR

QMA verifiers may reject honest proofs with nonzero probability, raising whether every QMA system can be made perfectly complete. The paper uses a finite cyclic-history test and proves that QMA can be made perfectly complete; its arithmetic approach does not extend to arbitrary quantum oracles.

  • Problem

    When completeness is below one, an honest prover may be rejected with nonzero probability, motivating whether QMA can be made perfectly complete.

    Source: §1 · p. 1

  • Method

    Merlin supplies a succinct exact rational Γ_z, which lets Arthur close a finite history of A^t|z⟩ terms into a cycle and check global consistency.

    Source: §1.2 · pp. 4–5

  • Results

    QMA verifiers can be made perfectly complete, with exact cyclic consistency in the YES case and a constant violation in the NO case.

    Source: §1 · p. 2, §1.2 · p. 5

  • Takeaways & Limitations

    The result establishes a fixed finite gate set with rational matrix entries for perfectly complete QMA verifiers.

    Source: §1 · p. 2

    The proof does not relativize to arbitrary quantum oracles because they need not preserve the arithmetic structure used for succinct Γ_z descriptions.

    Source: §1.2 · p. 5

Abstract

from arXiv · show

We prove $\mathsf{QMA} = \mathsf{QMA_1}$, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and $X$ gates, yielding a universal gate set for $\mathsf{QMA_1}$. As a consequence, quantum $3$-SAT is $\mathsf{QMA}$-complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$.

1 Introduction

The paper proves that QMA can be made perfectly complete and gives a finite-history consistency test that accepts YES instances exactly while separating NO instances by a constant amount.

1 Introduction

  • QMA = QMA1: every QMA proof system can be made perfectly complete using a fixed finite gate set with rational matrix entries.The verifier’s completeness is one on YES instances, rather than merely bounded below one.Source: §1 · pp. 1–2

1.1 Further consequences

  • Quantum 3-SAT and XZ-quantum 6-SAT are QMA-complete consequences of the perfect-completeness result.The quantum 3-SAT result follows from its QMA1-completeness with Clifford+T verifiers; the XZ-quantum 6-SAT result follows from its QMA_G2-completeness.Source: §1.1 · p. 2
  • Gapped clique homology is QMA-complete for weighted and unweighted graphs.Source: §1.1 · p. 3
  • Under classical XOR access, QMA and its G2-restricted perfectly complete variant coincide; known classical-oracle QMA/QCMA separations then also separate QMA1 from QCMA.The equality also holds for in-place permutation oracles. The cited separations are due to [BHNZ26] and [BHV26].Source: §1.1 · p. 3

1.2 Proof overview

  • The cyclic test is exact for an honest YES history, while every allowed NO-case operator C_z,β has norm at most 2/3.This global test rejects arbitrary purported history states, regardless of how their norm is distributed across the clock register.Source: §1.2 · p. 5
  • Merlin can provide a succinct exact rational Γ_z, letting Arthur close a finite history of A^t|z⟩ terms into a cycle.The powers of A are not physical time evolution; the resulting history can have a highly nonuniform clock distribution.Source: §1.2 · pp. 4–5
  • Compiling into G2 supplies the dyadic arithmetic used for succinct Γ_z descriptions, a structure arbitrary quantum oracles need not preserve.The construction therefore does not relativize to quantum oracles.Source: §1.2 · pp. 4–5

1.3 Open problems

  • Whether BQP = BQP1 or QMA(2) = QMA1(2) remains open; the proof lacks a prover to supply the exact value in BQP and an operator-norm bound for QMA(2).The existence of universal finite gate sets for BQP1 and QMA1(2) also remains open.Source: §1.3 · p. 6

2 Preliminaries

The preliminaries define QMA verification through an acceptance operator and distinguish bounded-error QMA, which is gate-set independent, from perfectly complete classes, which are indexed by gate set. They also state that reversible classical arithmetic is available over {X, CNOT, Toffoli}.

  • A verifier V on proof register X and ancilla register Y initialized to |0⟩ has acceptance operator E, and proof ρ is accepted with probability Tr(Eρ).Source: §2 · p. 6
  • QMA_G(c,s) requires some proof accepted with probability at least c on YES inputs and every proof accepted with probability at most s on NO inputs.Source: §2 · p. 6
  • For universal gate sets and 0 < s < c < 1, QMA_G(c,s) is independent of the gate set and constants, while QMA_G(c,s) is contained in QMA for any gate set.Source: §2 · p. 6
  • Perfectly complete QMA_G^1 is indexed by the gate set; for gate sets implementing G2 exactly, parallel repetition preserves perfect completeness while reducing soundness from s to s^r.Source: §2 · p. 6
  • Classical reversible arithmetic on polynomially many bits with workspace returned to zero is available over {X, CNOT, Toffoli}.Source: §2 · p. 6

3 Proof of perfect completeness

The proof compiles QMA verifiers into a gate set with controlled dyadic arithmetic, then uses exact rational witnesses and a cyclic history constraint to obtain perfect completeness. A block-encoded kernel test preserves a constant soundness gap, and the construction also relativizes to classical oracles.

3.1 Dyadic verifiers

  • Every QMA verifier can be compiled into G2, where 2^(2g)E is an integer matrix and E has a known dyadic denominator of polynomial size.This exact arithmetic makes entries of powers of E describable using polynomially many bits.Source: §3.1 · p. 7

3.2 A cyclic constraint

  • A YES instance has some z with an exactly describable rational Γz > 2, yielding a history state in the kernel of I − Cz,Γ; on NO instances the kernel condition fails by a constant amount.The cyclic operator advances through powers of A and closes the history using the claimed Γz.Source: §3.2 · p. 8

3.3 The QMA1 verifier

  • Arthur tests the history state's kernel condition with a block encoding whose designated outcome has probability proportional to the squared constraint norm.The index register realizes the rational closing coefficient b/a exactly through the relative counts assigned to branches.Source: §3.3 · p. 9
  • YES instances have a proof accepted with probability 1, while every proof on a NO instance is accepted with probability at most 1 − 1/576.The verifier is polynomial-size over G2, establishing QMA = QMA1.Source: §3.3 · p. 11
  • The construction relativizes to classical oracles, so the cited classical-oracle separations of QMA from QCMA also separate QMA1 from QCMA.The stated relativization covers standard XOR access and in-place permutation oracles.Source: §3.3 · p. 11

Tool and computational resource disclosure.

The paper discloses extensive use of generative AI in developing and writing the work, while assigning responsibility for its correctness and content to the authors.

Tool and computational resource disclosure

Loading 2609.13032v1…