VibeMathedMath problems solved with AI
Sign in

A Quantum Oracle Separation Between QMA(2)\mathsf{QMA}(2) and QMA\mathsf{QMA}

We find a quantum oracle relative to which QMA≠QMA(2)\mathsf{QMA}\neq\mathsf{QMA}(2). As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every ε+δ<1\varepsilon+\delta<1, any (ε,δ)(\varepsilon,\delta)-disentangler requires input size exponential in the number of output qubits.

Result
Proved(see note)
Status
Resolved
AI contribution
AI-discovered
Method
Construction
Field
Quantum complexity theory
Posed by
John Watrous (the no-disentanglers conjecture, as reported by Aaronson, Beigi, Drucker, Fefferman and Shor)
Year posed
2009
Years open
17y
Solved
2026-09-02
Model
ChatGPT 5.6 Sol
Vendor
OpenAI
Collaborators
John Bostanci; Sabee Grewal; Jonas Haferkamp; Andrew Huang; Yeongwoo Hwang; Anand Natarajan; Chinmay Nirkhe
Verification
Unreviewed
Publication
Preprint
Significance
36 / 100
Disclosed cost
—
Wikipedia
6 languages

What was actually shown

The authors construct a unitary oracle UU such thatQMAU≠QMA(2)U. \mathsf{QMA}^{U}\neq\mathsf{QMA}(2)^{U}. Their black-box problem is solvable by a QMA(2)\mathsf{QMA}(2) verifier with one oracle query and linear-size unentangled proofs, whereas any QMA\mathsf{QMA} verifier must use either exponentially many queries or an exponentially large witness.

As a non-oracle consequence, they prove that for every fixed ε,δ≥0\varepsilon,\delta\ge 0 with ε+δ<1\varepsilon+\delta<1, any (ε,δ)(\varepsilon,\delta)-disentangler requires exponentially many input qubits in the number of output qubits, resolving Watrous's no-disentanglers conjecture.

What the AI did

The authors explicitly state that the proof idea underlying the main theorem was generated using ChatGPT 5.6 Sol. They initially directed Sol to the unitary polynomial method of She and Yuen; with minimal further guidance, the model proposed the proof idea used in the paper. The authors then verified, simplified, and developed the argument. The key construction uses symmetric and antisymmetric subspace projectors to make the relevant local-unitary invariant polynomials collapse to a single univariate polynomial, reducing the lower bound to the approximate degree of OR\mathrm{OR}.

Verification

Unreviewed. A 25-page preprint two days old, no peer review, no formalisation. Seven authors, including several who work on exactly this, state that they "verified, simplified, and developed" the model's proof idea and take full responsibility. The argument reduces to the approximate degree of OR through the She-Yuen unitary polynomial method, so it is checkable by anyone who knows that toolkit. Nobody outside the author list has done so on the record.

Sources

Submitted by VibeGene on

Changelog2 changes

Discussion