Separating Quantum and Classical Advice with Good Codes
Pith reviewed 2026-05-16 05:54 UTC · model grok-4.3
The pith
There exists a classical oracle relative to which QMA is strictly more powerful than QCMA.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof (QMA) and the class of languages that can be verified with a classical proof (QCMA). Our oracles are based on the code intersection problem combined with codes that have extremely good list-recovery properties. This also yields the first unconditional classical oracle separation between BQP/qpoly and BQP/poly.
What carries the argument
The code intersection problem, which asks whether two randomly chosen codes share a common codeword, used together with codes having strong list-recovery properties to define the oracle and enforce the separation.
If this is right
- There is a classical oracle A such that QMA^A is not contained in QCMA^A.
- There is a classical oracle separating BQP/qpoly from BQP/poly.
- The separation requires no quantum oracles and no unproven computational assumptions.
- The same code-based technique applies to other oracle separations between quantum and classical classes.
Where Pith is reading between the lines
- If explicit constructions of the required list-recovery codes can be found, the separated languages could be made concrete rather than oracle-dependent.
- The approach might extend to separate quantum and classical resources in settings without oracles, such as in cryptography or proof systems.
- List-recovery parameters from coding theory appear central to controlling the power of quantum versus classical advice.
- Similar reductions could separate additional pairs of quantum interactive proof classes from their classical counterparts.
Load-bearing premise
Codes exist with list-recovery properties strong enough to make the reduction from the code intersection problem to the desired oracle separation work.
What would settle it
An explicit family of codes that fails to meet the required list-recovery radius and output list size bounds, or a direct computation showing that the code intersection problem does not separate the classes for those codes, would refute the separation.
read the original abstract
We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof ($\mathsf{QMA}$) and the class of languages that can be verified with a classical proof ($\mathsf{QCMA}$). Compared to the recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), our proof is conceptually and technically simpler, and readily extends to other oracle separations. In particular, our techniques yield the first unconditional classical oracle separation between the class of languages that can be decided with quantum advice ($\mathsf{BQP}/\mathsf{qpoly}$) and the class of languages that can be decided with classical advice ($\mathsf{BQP}/\mathsf{poly}$), improving on the quantum oracle separation of Aaronson and Kuperberg (CCC 2007) and the classically-accessible classical oracle separation of Li, Liu, Pelecanos and Yamakawa (ITCS 2024). Our oracles are based on the code intersection problem introduced by Yamakawa and Zhandry (FOCS 2022), combined with codes that have extremely good list-recovery properties.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims an unconditional classical oracle separation between QMA and QCMA, constructed via the Yamakawa-Zhandry code-intersection problem instantiated with codes possessing extremely strong list-recovery properties (radius roughly 1-1/poly and list size poly(log n)). It further claims the first unconditional classical oracle separation between BQP/qpoly and BQP/poly, with a conceptually simpler proof than Bostanci et al. (STOC 2026) that extends readily to other separations.
Significance. If the reduction and code properties hold, the result supplies unconditional classical oracles separating these classes, improving on Aaronson-Kuperberg quantum oracles and Li et al. classically-accessible oracles. The claimed simplicity and extensibility are strengths; the work would tighten the oracle landscape for quantum versus classical verification and advice.
major comments (2)
- [Abstract and §4] Abstract and §4: The oracle separation is defined using a code family C whose list-recovery parameters (radius ~1-1/poly(n), list size poly(log n)) must be strong enough for the quantum verifier to succeed on the hidden intersection while the classical verifier fails. The manuscript invokes “codes that have extremely good list-recovery properties” but supplies neither an explicit construction, a probabilistic existence argument with matching quantitative bounds, nor a reference achieving these exact parameters. This assumption is load-bearing for the oracle to be well-defined and for the reduction from any QMA machine to a list-recovery query on C.
- [§4] §4: The mapping from QMA oracle machines to list-recovery queries on C must be checked for tightness; if the list-recovery radius or list size falls short of the claimed bounds, the classical verifier may succeed on the intersection instance, collapsing the separation. No explicit parameter calculation or failure-probability analysis is provided in the visible sections.
minor comments (1)
- [§2] Notation for the code family C and the intersection problem should be introduced with a self-contained definition before the reduction, to aid readability.
Simulated Author's Rebuttal
We thank the referee for the careful review and for identifying the need for greater explicitness on code parameters and reductions. We will revise the manuscript to include a probabilistic existence argument for the required list-recovery codes and a detailed parameter analysis in §4. These additions will make the oracle construction fully rigorous without altering the core results.
read point-by-point responses
-
Referee: [Abstract and §4] The manuscript invokes “codes that have extremely good list-recovery properties” but supplies neither an explicit construction, a probabilistic existence argument with matching quantitative bounds, nor a reference achieving these exact parameters. This assumption is load-bearing for the oracle to be well-defined and for the reduction from any QMA machine to a list-recovery query on C.
Authors: We agree that the manuscript as written does not contain an explicit probabilistic argument or reference for codes achieving radius roughly 1-1/poly(n) and list size poly(log n). In the revision we will add a short subsection (likely in §3 or an appendix) proving existence via the probabilistic method: a random code of appropriate rate satisfies the list-recovery guarantee with high probability, with explicit calculations matching the quantitative bounds needed for the oracle separation. This will render the construction self-contained. revision: yes
-
Referee: [§4] The mapping from QMA oracle machines to list-recovery queries on C must be checked for tightness; if the list-recovery radius or list size falls short of the claimed bounds, the classical verifier may succeed on the intersection instance, collapsing the separation. No explicit parameter calculation or failure-probability analysis is provided in the visible sections.
Authors: We will expand §4 with a dedicated parameter-tracking subsection. It will explicitly relate the QMA witness length and verification error to the list-recovery radius and list size, showing that the chosen parameters ensure the quantum verifier accepts with probability 2/3 while any classical verifier succeeds with probability at most 1/3 + negl(n). The analysis will include union bounds over the list size and failure probabilities derived from the code properties. revision: yes
Circularity Check
No circularity; derivation reduces to external code existence
full rationale
The paper's central separation is obtained by reducing QMA/QCMA oracle distinctions to the code-intersection problem of Yamakawa-Zhandry (FOCS 2022) instantiated on codes whose list-recovery parameters are treated as an independent existence assumption. No equation or step defines the target separation in terms of itself, renames a fitted parameter as a prediction, or loads the argument on a self-citation whose content is unverified. The cited prior work supplies the intersection problem; the list-recovery codes are an external combinatorial object whose existence is mathematically falsifiable outside the present manuscript. The derivation chain therefore remains non-circular and self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Existence of codes with extremely good list-recovery properties sufficient for the oracle separation
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.