⚛️ quantum physics

Separating Quantum and Classical Advice with Good Codes

This paper presents a conceptually and technically simpler proof of an unconditional classical oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$ , while also establishing the first such separation between $\mathsf{BQP}/\mathsf{qpoly}$ and $\mathsf{BQP}/\mathsf{poly}$ by leveraging the code intersection problem combined with codes possessing strong list-recovery properties.

Original authors: John Bostanci, Andrew Huang, Vinod Vaikuntanathan

Published 2026-04-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: John Bostanci, Andrew Huang, Vinod Vaikuntanathan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, impossible puzzle. You have two types of helpers: a Classical Helper who gives you a written note with instructions, and a Quantum Helper who gives you a mysterious, glowing crystal that holds the answer in a state of "superposition" (a bit like a spinning coin that is both heads and tails until you look at it).

The big question in computer science for decades has been: Is the glowing crystal actually more powerful than the written note? Can the Quantum Helper solve problems that the Classical Helper simply cannot, even if the Classical Helper is allowed to use a super-fast quantum computer to read the note?

This paper, titled "Separating Quantum and Classical Advice with Good Codes," says a resounding YES. The authors have proven that, under certain conditions, the Quantum Helper (using "quantum advice") is strictly more powerful than the Classical Helper (using "classical advice").

Here is how they did it, explained through simple analogies.

1. The Setup: The "Code Intersection" Game

Imagine a giant library containing billions of books (these are "codewords"). Each book has a unique barcode.

The Game: You are given a specific "target code" (a hash value). Your job is to find a book in the library whose barcode matches that target.
The Twist: The library is organized by a secret, random rule (a function $H$ ) that turns book pages into barcodes. Without knowing the rule, finding the right book is like finding a needle in a haystack.

The Quantum Advantage:
The authors show that if you have a Quantum Crystal (quantum advice) that contains a "superposition" of all the books and their barcodes, a quantum computer can use a clever trick (called the Yamakawa-Zhandry algorithm) to instantly find the matching book. It's like having a magical map that highlights the needle.

The Classical Struggle:
If you only have a Written Note (classical advice), you can't hold the "superposition" of all books. You have to guess. The paper proves that no matter how smart your written note is, you cannot reliably find the needle in the haystack for every possible target code.

2. The Secret Ingredient: "Good Codes" and "Biased Oracles"

Previous attempts to prove this used "Folded Reed-Solomon codes," which are like a specific type of library organization. The authors realized these weren't "good" enough to make the proof simple and unbreakable.

Instead, they used Multiplicity Codes.

The Analogy: Imagine a library where books are arranged not just by title, but by how many times a specific letter appears in the title, the author's name, and the publication date. This creates a highly structured, rigid system.
Why it matters: These codes have a property called "List Recovery." It means if you have a few clues (a partial barcode), you can narrow down the possibilities to a very small list of books. The authors proved that with these specific codes, a Classical Helper cannot narrow down the list enough to win, but a Quantum Helper can.

The "Biased" Trick:
To make the math work, the authors tweaked the rules of the game. Instead of the barcodes being completely random, they made them biased.

Analogy: Imagine the library is designed so that 90% of the books have barcodes starting with "0000..." and only 10% start with "1111...".
The Result: This bias makes it much easier for the Quantum Helper to find the needle (because the "noise" is lower), but it doesn't help the Classical Helper much at all. It's like the Quantum Helper has a flashlight that works perfectly in the dim light, while the Classical Helper is still stumbling in the dark.

3. The "Cloning" Problem: Why Classical Advice Fails

The core of the proof relies on a fundamental law of physics: You cannot clone a quantum state.

The Classical Helper: If you give a Classical Helper a note, they can read it, copy it, and run the same test 1,000 times. If they fail once, they can try again with the exact same note.
The Quantum Helper: If you give a Quantum Helper a crystal, and they measure it to check an answer, the crystal "collapses." The magic is gone. They can't just "re-run" the test with the same crystal.

The authors designed a game where the Classical Helper must be able to re-run the test many times to win. Because the Quantum Helper's crystal is "fragile" (it can't be cloned), the Classical Helper's strategy of "try, fail, try again with the same note" fails. The Quantum Helper, however, uses the crystal's unique properties to solve the problem in one go.

4. The Big Picture: Why This Matters

Before this paper, we knew that Quantum computers were faster at some things (like factoring numbers). But we didn't know if they were fundamentally more powerful when given a "cheat sheet" (advice).

BQP/poly: Problems solvable by a quantum computer with a classical cheat sheet.
BQP/qpoly: Problems solvable by a quantum computer with a quantum cheat sheet.

This paper proves that BQP/qpoly is strictly bigger than BQP/poly.

The Takeaway:
There are problems that a quantum computer can solve if it is given a "quantum cheat sheet," but it is mathematically impossible for it to solve those same problems even if it has the best possible "classical cheat sheet."

Summary in a Sentence

By creating a specific, highly structured puzzle (using "good codes" and "biased rules"), the authors proved that a quantum computer with a quantum "cheat sheet" can solve problems that are completely impossible for a quantum computer with a classical "cheat sheet," because the quantum cheat sheet holds information that cannot be copied or written down.

1. Problem Statement

The paper addresses two fundamental open questions in quantum complexity theory regarding the power of quantum versus classical resources:

Proofs: Are the complexity classes QMA (Quantum Merlin-Arthur, with quantum proofs) and QCMA (Quantum Classical Merlin-Arthur, with classical proofs) distinct?
Advice: Are the classes BQP/qpoly (BQP with quantum advice) and BQP/poly (BQP with classical advice) distinct?

While unconditional separations in the standard model are currently out of reach (implying breakthroughs like $P \neq PSPACE$ ), the authors aim to provide unconditional classical oracle separations. Previous work had achieved this for QMA vs. QCMA using complex "spectral Forrelation" oracles, but the separation for BQP/qpoly vs. BQP/poly remained open.

2. Methodology and Core Techniques

The authors construct a new oracle based on a modified Code Intersection Problem, leveraging Multiplicity Codes and Biased Oracles.

A. The Code Intersection Problem

The core problem involves finding a codeword $c$ in a linear code $C$ such that a hash function $H$ maps $c$ to a specific target string $x$ (i.e., $H(c) = x$ ).

Quantum Advantage: Using the Yamakawa-Zhandry (YZ) algorithm, a quantum computer can solve this efficiently if given a specific "advice state" encoding the preimages of $H$ .
Classical Hardness: The authors argue that a classical prover (in QCMA) cannot provide enough information to solve this for all inputs without revealing too much structure, which can be exploited to break the separation.

B. Key Technical Innovations

To achieve a classical oracle separation (where the oracle is a classical function, not a unitary), the authors introduce three critical modifications to the standard YZ framework:

Biased Oracles:
- Standard YZ algorithms assume a random hash function $H$ . However, the authors use a biased distribution where $H(i, \sigma) = 0$ with high probability ( $p \gg 1/2$ ).
- Purpose: This reduces the "noise" (Hamming weight) in the error distribution when decoding the dual code. This allows the use of codes with sub-constant relative distance (which are necessary for the next step) while still ensuring the quantum algorithm succeeds with high probability.
Multiplicity Codes and List Recovery:
- The authors instantiate the code $C$ using Univariate Multiplicity Codes (specifically, codes based on Hasse derivatives).
- Why Multiplicity Codes? Unlike the Folded Reed-Solomon (FRS) codes used in previous works, Multiplicity Codes possess near-optimal list-recovery properties.
- Role in Proof: To rule out QCMA, the authors use an "entropic" argument. If a QCMA verifier exists, one can construct a "guesser" that samples codewords and their hashes without oracle queries. List-recovery properties ensure that to produce $\ell$ distinct codewords, the guesser must correctly guess $\Omega(\ell \cdot n)$ symbols. The bias of the oracle makes guessing these symbols exponentially unlikely, creating a contradiction.
Restriction to Low Hamming Weight Inputs:
- Because the oracle is biased toward 0, the quantum algorithm can only efficiently invert inputs $x$ with low Hamming weight (specifically $x \| 0^{n-k}$ ).
- The problem is redefined to only require distinguishing sets based on these low-weight inputs. This restriction is crucial for maintaining the efficiency of the quantum decoder while keeping the classical guessing probability negligible.

C. The Separation Strategy

QMA Containment: The quantum prover sends the "YZ advice state" (a superposition of preimages). The verifier uses the biased YZ algorithm to generate a valid codeword $v$ for a random query $x$ and checks it against the oracle.
QCMA Impossibility: The authors show that any QCMA verifier implies the existence of a "sampler" (Guesser) that can output valid $(x, v)$ $(x, v)$ pairs without oracle access.
- They use the Hybrid Lemma to show that if the verifier succeeds, the sampler can extract new valid pairs with non-negligible probability.
- By iterating this, the sampler produces many pairs.
- Contradiction: The List Recovery property of Multiplicity Codes dictates that producing $\ell$ pairs requires guessing $\Omega(\ell \cdot n)$ symbols. The Bias of the oracle makes the probability of guessing these symbols correctly exponentially small ( $\approx (1-p)^{\text{symbols}}$ ), which is far smaller than the probability required by the QCMA assumption.

3. Key Contributions

First Unconditional Classical Oracle Separation for BQP/qpoly vs. BQP/poly:
- The paper proves $BQP^{O}/qpoly \not\subseteq BQP^{O}/poly$ .
- This improves upon the previous best result (Li et al., ITCS 2024), which only separated these classes in a "classically-accessible" oracle model.
- The separation is robust: it holds even against algorithms with quantum oracle access but classical advice.
Simplified Separation for QMA vs. QCMA:
- While Bostanci et al. (STOC 2026) recently separated QMA and QCMA, their proof relied on complex spectral Forrelation and Hamiltonian learning techniques.
- This paper provides a conceptually and technically simpler proof using the Code Intersection Problem and Multiplicity Codes.
New Oracle Construction:
- The oracle is based on the Code Intersection Subset Size (CISS) problem.
- It distinguishes between a "YES" instance (where the set of valid codewords is large) and a "NO" instance (where the set is small), using the structural properties of Multiplicity Codes to enforce hardness for classical witnesses.

4. Results

Theorem 1.1: There exists a classical oracle $\mathcal{O}$ such that $QMA^{\mathcal{O}} \not\subseteq QCMA^{\mathcal{O}}$ .
Theorem 1.2: There exists a classical oracle $\mathcal{O}$ such that $BQP^{\mathcal{O}}/qpoly \not\subseteq BQP^{\mathcal{O}}/poly$ .
Structural Insight: The authors show that their oracle separates $NP^{\mathcal{O}} \cap coNP^{\mathcal{O}} \cap BQP^{\mathcal{O}}/qpoly$ from $BQP^{\mathcal{O}}/poly$ , indicating a structural difference from previous oracles based on spectral Forrelation (which are linked to QMA-complete problems).

5. Significance

Resolution of Long-Standing Open Problems: The paper resolves the question of whether quantum advice is strictly more powerful than classical advice in the oracle model, a question open since Aaronson and Kuperberg (2007).
Simplification of Complexity Theory: By replacing heavy machinery (like spectral Forrelation and Hamiltonian learning) with coding theory (list recovery and biased oracles), the authors make the separation more accessible and adaptable.
Cryptographic Implications: The separation relies on the "unclonability" of quantum advice. The paper discusses connections to Quantum Money and Copy-Protected Software, suggesting that the techniques used here (encoding information in quantum states that cannot be cloned but can be verified) could inspire new cryptographic primitives.
Coding Theory Applications: The work highlights the utility of Multiplicity Codes and their duals in complexity theory, specifically their ability to provide both efficient decoding (for the quantum side) and strong list-recovery (for the classical lower bound).

In summary, this paper establishes a definitive classical oracle separation between quantum and classical proofs/advice by ingeniously combining biased oracles with the strong list-recovery properties of Multiplicity Codes, offering a simpler and more powerful framework than previous approaches.