pith. sign in

arxiv: 2604.26921 · v1 · submitted 2026-04-29 · 🪐 quant-ph · cs.CC

En Route to a Standard QMA1 vs. QCMA Oracle Separation

David Miloschewsky , Supartha Podder , Dorian Rudolph This is my paper

Pith reviewed 2026-05-07 10:39 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords QMA1QCMAoracle separationquantum witnessesperfect completenessadaptive roundsground state preparation
0
0 comments X

The pith

A classical oracle exists relative to which a language is in QMA1 but not in QCMA when the verifier is limited to polynomially many adaptive rounds and exponentially many parallel queries per round.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a classical oracle that places a specific language inside QMA1 while keeping it outside QCMA under tight restrictions on the classical verifier. This separation holds even though the verifier can make exponentially many parallel queries in each of its polynomially many adaptive rounds. The authors also derandomize an earlier permutation-oracle result to obtain an in-place oracle separation between the same classes. They further examine versions of the classes that use an exponentially small completeness-soundness gap and extract consequences for approximate preparation of ground states of sparse Hamiltonians given oracle access.

Core claim

There exists a classical oracle relative to which a language lies in QMA1 but not in QCMA when the QCMA verifier is restricted to polynomially many adaptive rounds and exponentially many parallel queries per round; a derandomized in-place oracle also separates the classes, and similar separations hold for fixed exponentially small gaps but not for arbitrarily small gaps.

What carries the argument

The classical oracle that enforces membership in QMA1 via quantum witnesses while blocking any polynomially adaptive, exponentially parallel QCMA verifier from deciding the language.

If this is right

  • QMA1 is strictly stronger than this restricted form of QCMA relative to the oracle.
  • An in-place classical oracle separates QMA1 from QCMA without needing a random permutation.
  • Separations persist when the completeness-soundness gap is a fixed exponential but may disappear if the gap can shrink arbitrarily.
  • Approximate ground-state preparation from sparse Hamiltonian oracles inherits bounded-adaptivity limitations in the frustration-free case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The separation may collapse if the QCMA verifier is allowed unlimited adaptive rounds, suggesting the round bound is essential.
  • The result constrains how much adaptivity is needed for classical verifiers to simulate quantum witnesses even with massive parallel query power.
  • Similar oracle techniques could be tested on other promise classes such as QMA versus QMA with small gap.

Load-bearing premise

The QCMA verifier is forbidden from using more than polynomially many adaptive rounds or from exceeding exponentially many parallel queries inside each round.

What would settle it

An explicit construction of a QCMA verifier that decides the same language with polynomially many adaptive rounds and exponentially many parallel queries per round, relative to the constructed oracle.

read the original abstract

We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in $\mathsf{QMA}_1$ but not in $\mathsf{QCMA}$ when the $\mathsf{QCMA}$ verifier is only allowed polynomially many adaptive rounds and exponentially many parallel queries per round. Additionally, we derandomize the permutation-oracle separation of Fefferman and Kimmel, obtaining an in-place oracle separation between $\mathsf{QMA}_1$ and $\mathsf{QCMA}$. Furthermore, we focus on $\mathsf{QCMA}$ and $\mathsf{QMA}$ with an exponentially small gap, where we show a separation assuming the gap is fixed, but not when it may be arbitrarily small. Finally, we derive consequences for approximate ground-state preparation from sparse Hamiltonian oracle access, including a bounded-adaptivity frustration-free variant.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper constructs a classical oracle relative to which a language is in QMA1 but not in QCMA when the QCMA verifier is restricted to polynomially many adaptive rounds and exponentially many parallel queries per round. It derandomizes the Fefferman-Kimmel permutation-oracle separation to obtain an in-place oracle separation between QMA1 and QCMA. It also establishes a separation between QCMA and QMA with a fixed exponentially small completeness-soundness gap (but not for arbitrarily small gaps) and derives consequences for approximate ground-state preparation from sparse Hamiltonian oracle access, including a bounded-adaptivity frustration-free variant.

Significance. If the oracle constructions and derandomization hold, this provides a meaningful intermediate result toward a standard (unrestricted) QMA1 vs. QCMA oracle separation, with direct implications for the power of quantum witnesses under perfect completeness. The derandomization of the permutation-oracle result and the fixed-gap separation strengthen prior work using standard oracle techniques. The consequences for frustration-free ground-state preparation from Hamiltonian oracles are a notable application. The manuscript ships explicit constructions and derives falsifiable predictions about verifier restrictions and gap sizes.

minor comments (3)
  1. §1 (Introduction): The motivation for restricting the QCMA verifier to polynomially many adaptive rounds could be expanded with a brief comparison to the unrestricted case, to better contextualize why this is an 'en route' result.
  2. §3 (Oracle construction): The notation for the in-place oracle could be clarified in the first paragraph; it is not immediately clear how it differs from the standard permutation oracle without cross-referencing the Fefferman-Kimmel result.
  3. §5 (Gap results): Table 1 or the corresponding theorem statement should explicitly state the dependence of the gap size on the oracle size to make the 'fixed vs. arbitrary' distinction easier to verify at a glance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our work and for recommending minor revision. The referee's summary correctly captures the main contributions: the classical oracle separation under polynomially adaptive rounds with exponential parallel queries, the derandomization of the Fefferman-Kimmel result to an in-place oracle, the fixed-gap separation between QCMA and QMA, and the consequences for approximate ground-state preparation. We address the report below.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper constructs an explicit classical oracle separation between QMA1 and a polynomially adaptive, exponentially parallel-query QCMA using standard diagonalization and derandomization techniques applied to the external Fefferman-Kimmel permutation-oracle result. All load-bearing steps (oracle definition, gap analysis, and ground-state consequences) are stated as direct constructions or reductions from prior external work rather than self-referential definitions, fitted parameters renamed as predictions, or self-citation chains. The verifier restrictions and fixed-gap assumption are explicit hypotheses of the claimed theorems, not smuggled in or derived by construction from the target separation itself. The derivation remains self-contained against external benchmarks in quantum complexity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, new entities, or non-standard axioms are visible. The work rests on standard definitions of QMA1, QCMA, and oracle models from prior literature.

axioms (1)
  • standard math Standard axioms and definitions of quantum complexity classes QMA1 and QCMA
    The separation statements presuppose the usual definitions of these classes and oracle access.

pith-pipeline@v0.9.0 · 5447 in / 1105 out tokens · 45451 ms · 2026-05-07T10:39:57.336468+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Quantum NP-a survey.quant-ph/0210077,

    [AN02] Dorit Aharonov and Tomer Naveh. Quantum NP-a survey.quant-ph/0210077,

    work page arXiv

  2. [2]

    Oracle separation of QMA and QCMA with bounded adaptivity

    [BDK24] Shalev Ben-David and Srijita Kundu. Oracle separation of QMA and QCMA with bounded adaptivity. In51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), pages 21–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik,

    work page 2024

  3. [3]

    On the Power of Nonstandard Quantum Oracles

    [BFM23] Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. On the Power of Nonstandard Quantum Oracles. In Omar Fawzi and Michael Walter, editors,18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), vol- ume 266 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:25, Dagstuhl, Germany,

    work page 2023

  4. [4]

    Public-key quantum fire and key-fire from classical oracles.arXiv preprint arXiv:2504.16407,

    [CGS25] Alper Cakan, Vipul Goyal, and Omri Shmueli. Public-key quantum fire and key-fire from classical oracles.arXiv preprint arXiv:2504.16407,

    work page arXiv

  5. [5]

    Quantum vs

    [FK18] Bill Fefferman and Shelby Kimmel. Quantum vs. Classical Proofs and Subset Verification. In Igor Potapov, Paul Spirakis, and James Worrell, editors,43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:23, Dagstuhl, Germany,

    work page 2018

  6. [6]

    [FL18] Bill Fefferman and Cedric Yen-Yu Lin

    Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. [FL18] Bill Fefferman and Cedric Yen-Yu Lin. A Complete Characterization of Unitary Quan- tum Space. In Anna R. Karlin, editor,9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 4:1–4:21, Dagstuhl, Germany,

    work page 2018

  7. [7]

    Group order is in qcma

    [GNT25] Fran¸ cois Le Gall, Harumichi Nishimura, and Dhara Thakkar. Group order is in qcma. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1128–1143,

    work page 2025

  8. [8]

    Quantum Search with In-Place Queries

    [HRY25] Blake Holman, Ronak Ramachandran, and Justin Yirka. Quantum Search with In-Place Queries. In Bill Fefferman, editor,20th Conference on the Theory of Quantum Computa- tion, Communication and Cryptography (TQC 2025), volume 350 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:18, Dagstuhl, Germany,

    work page 2025

  9. [9]

    The complexity of quantum disjointness

    [Kla17] Hartmut Klauck. The complexity of quantum disjointness. In42nd International Sympo- sium on Mathematical Foundations of Computer Science (MFCS 2017). Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik,

    work page 2017

  10. [10]

    Quantum oracle separations from complex but easily specified states

    [Lar21] Nicholas Laracuente. Quantum oracle separations from complex but easily specified states. arXiv:2104.07247,

    work page arXiv

  11. [11]

    Classical vs quantum advice and proofs under classically-accessible oracle

    [LLPY24] Xingjian Li, Qipeng Liu, Angelos Pelecanos, and Takashi Yamakawa. Classical vs quantum advice and proofs under classically-accessible oracle. In15th Innovations in Theoretical Computer Science Conference (ITCS 2024), pages 72–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik,

    work page 2024

  12. [12]

    Component mixers and a hardness result for counterfeiting quantum money.arXiv:1107.0321,

    [Lut11] Andrew Lutomirski. Component mixers and a hardness result for counterfeiting quantum money.arXiv:1107.0321,

    work page arXiv

  13. [13]

    A computational separation between quantum no- cloning and no-telegraphing

    [NZ24] Barak Nehoran and Mark Zhandry. A computational separation between quantum no- cloning and no-telegraphing. In15th Innovations in Theoretical Computer Science Con- ference (ITCS 2024), pages 82–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik,

    work page 2024

  14. [14]

    On the power of quantum proofs

    [RS04] Ran Raz and Amir Shpilka. On the power of quantum proofs. InProceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pages 260–274. IEEE,

    work page 2004

  15. [15]

    Toward separating QMA from QCMA with a classical oracle

    24 [Zha25] Mark Zhandry. Toward separating QMA from QCMA with a classical oracle. In16th Innovations in Theoretical Computer Science Conference (ITCS 2025), pages 95–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik,

    work page 2025