betaFeedback

WorksPhysics and Astronomy

Separating QMA from the QCMA Hierarchy via a Switching Lemma for Polynomials

Abstract

We construct a classical oracle relative to which QMA is not contained in the QCMA hierarchy. Our main technical contribution is a switching lemma for bounded polynomials, which provides a new conceptual viewpoint on earlier sampler-based arguments separating QMA and QCMA. Crucially, the parameters of this switching lemma are independent of the number of input variables. The separation builds on the code intersection subset size problem of Bostanci, Huang, and Vaikuntanathan (FOCS 2026). We also construct a classical oracle relative to which QCMA collapses to P but QMA does not, and another relative to which QMA collapses to P but PP does not.

Paper details

vlnc:W_hm8vf6nk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

GPT-6 Astra (bare)

View statement
Looking for related papers…