2026 quantum/classical proof and advice oracle separation
Research context
development · established · As of 2026-10-10
preprint · 2026-02-10
- Study design
- Complexity-theoretic oracle construction using good list-recoverable codes and a code-intersection problem, with exact coherent query/advice models.
- Reported result
- Classical-oracle separations of quantum versus classical witnesses and quantum versus classical advice.
- Limitations
- A relativized mathematical result; preprint status used conservatively and ordinary unrelativized equality/separation is not settled by this construction.
Bostanci, Huang and Vaikuntanathan's 2026 manuscript constructs a classical oracle O with QMA^O not contained in QCMA^O and BQP^O/qpoly not contained in BQP^O/poly, using a code-intersection problem with strong list-recovery properties.
Key knowledge
Bostanci, Huang and Vaikuntanathan's 2026 manuscript constructs a classical oracle O with QMA^O not contained in QCMA^O and BQP^O/qpoly not contained in BQP^O/poly, using a code-intersection problem with strong list-recovery properties. The oracle is classical but permits the declared coherent quantum query access. This updates an old oracle frontier; it does not prove that the ordinary unrelativized classes are unequal or that every quantum witness is practically advantageous.
Conditions and scope
- Oracle access, polynomial proof/advice length and uniform verification are part of the exact relativized model.
- Author manuscript and submission metadata checked 10 October 2026; conservative preprint status, no full independent proof reconstruction.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
- Separating Quantum and Classical Advice with Good Codes (2026 author manuscript)John Bostanci, Andrew Huang and Vinod VaikuntanathanResearch paper · PDF
- Separating Quantum and Classical Advice with Good Codes: submission historyJohn Bostanci, Andrew Huang and Vinod Vaikuntanathan / arXivResearch abstract
Evidence and review
Author checked this English statement, displayed equation where present and stated hypotheses against these source locations: Introduction, Theorems 1.1–1.2 and formal oracle/list-recovery construction; unrelativized boundary; Submission 10 February 2026, author/version metadata and abstract. The check is bounded to the recorded claims; no complete proof reconstruction, software proof replay or universal literature completeness is claimed.
2026-10-10 · Author source-body/statement/equation/domain check, with graph associations scoped individually. Separate independent content/source/inventory review is required before branch closure.
Entry details
Permanent link to this entry ↗- Record identity
- research-info-2026-oracle-separation
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference