[BHV26] Separating Quantum and Classical Advice with Good Codes

Authors: John Bostanci, Andrew Huang, Vinod Vaikuntanathan | Venue: ECCC 2026 | Source

Abstract

We give a conceptually and technically simpler proof of the classical oracle separation between QMA and QCMA from [BHNZ25], using good error-correcting codes. We also give the first unconditional classical oracle separation between BQP/qpoly and BQP/poly, improving on the quantum oracle separation of Aaronson–Kuperberg [AK07]. The key technique encodes the separating problem using a good linear code, allowing a clean information-theoretic argument to replace the bosonic second-quantization machinery of the original proof.