Efficiently verifiable quantum advantage using error correction

summary

The gist

A key issue in current quantum advantage experiments is that their verification requires a full classical simulation of the ideal computation, which severely limits the credibility and verifiability

In short

The work introduces Hidden Code Sampling (HCS), a task provably hard for classical computers, to verify quantum advantage without full simulation. By using two verification tests—Peak Verification and Syndrome Verification—the scheme allows for checking code state correctness and syndrome distribution in significantly less time than simulating the ideal computation.

Key concepts

Hidden Code Sampling (HCS): A sampling task designed to be hard for classical computers. The output distribution of this task is 'conditionally peaked,' meaning it has sharp peaks that make it easier to verify quantum results quickly compared to simulating the entire process.
Peak Verification: A verification test used by Alice that checks if the code state preparation was correct. It identifies peaks in the distribution using a classical decoder for syndromes and accepts the result only if specific conditions on logical and syndrome outcomes are met.
Syndrome Verification: A statistical test to ensure that the syndromes produced by Bob follow the expected distribution. This is done by computing a Relative Entropy Difference (RED) score against potential spoofing distributions, which is conjectured to be hard for classical algorithms to fool.

Terminology used across episodes

Reinforcement Learning (RL) — explained in 24 episodes
Retrieval-Augmented Generation (RAG) — explained in 16 episodes
Interpretability — explained in 15 episodes
Sample Complexity — explained in 15 episodes
Federated Learning — explained in 14 episodes
Generalization — explained in 13 episodes

This episode discusses

The paper

Efficiently verifiable quantum advantage using error correction · Read on arXiv

Abhinav Deshpande, Bill Fefferman, Soumik Ghosh, Michael Gullans, Dominik Hangleiter

IBM Quantum Research Center · University of Chicago · University of Maryland and NIST, College Park, Maryland · Simons Institute for the Theory of Computing, University of California at Berkeley · ETH Zürich

A key issue with existing quantum advantage experiments is that their verification requires exponential classical time. In this work, we address this challenge by designing a new proposal---Hidden Code Sampling---with efficient classical verification. We use properties of quantum error correction to build an experiment that is "conditionally peaked": conditioned on a subset of qubits, the distribution on another subset is peaked. We give evidence for the classical intractability of this protocol by showing complexity-theoretic hardness of classical simulation, putting our scheme on par with other quantum advantage schemes. A major hurdle in instantiating the scheme concerns distinguishing between two noise channels, one involving local coherent noise and the other involving local Pauli noise. We identify algebraic properties of the underlying codes that enable an efficient distinguisher and construct an explicit code family satisfying these properties while preserving the hardness guarantees. We provide further evidence for soundness of our verification tests by proving an exponential query lower bound for classical algorithms that pass our verification tests in a black-box model.

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai, and with me are Mira and Lev, guest researcher.

Mira: Today's paper: "Efficiently verifiable quantum advantage using error correction".

Kai: A key issue in current quantum advantage experiments is that their verification requires a full classical simulation of the ideal computation,

Mira: First, who's behind it and why it matters.

Paper summary: Kai: So, to recap, this paper introduces Hidden Code Sampling as a new proposal for quantum advantage because its output distribution has these specific peaked characteristics that make verification much faster than full classical simulation.

Mira: They are proposing a two-player protocol where Alice sets up the code structure and keeps the crucial peakedness code secret from Bob, who then prepares and measures the state under an error channel.

Lev: The core claim is that this setup makes sampling from that distribution classically hard unless we accept a collapse of the polynomial hierarchy, which is a very strong statement about classical limitations.

Kai: This matters because currently, verifying quantum experiments demands simulating the ideal computation, and this paper shows a way to verify those claims much more efficiently than simulation allows.

Mira: They demonstrate that this leads to a significant verification-simulation gap of two(k) when using optimal low-rank stabilizer simulators for near-threshold error rates <ref:2510.05262#pg0>.

Lev: This suggests that we can verify the correctness of certain quantum computations without needing to run the full classical simulation, which is a huge hurdle for building trust in these experimental results.

Kai: The paper sets up Peak Verification and Syndrome Verification tests, and they show how these two checks together provide soundness against errors and spoofing attempts, respectively.

Mira: Basically, they're showing that we can distinguish correct states from erroneous or faked ones using these specific statistical estimators for relative entropy difference.

Lev: If you think about running this on real hardware, the requirement for precise error modeling and syndrome measurement in the X basis is what makes it challenging to implement physically right now.

Kai: So, in essence, they are giving us a path toward verifiable quantum advantage by changing *how* we check if our experimental results hold up against classical expectations.

Mira: This research is important because it tackles the credibility bottleneck that limits how much we can trust current quantum claims without resorting to full simulation.

Conclusion: Kai: Considering the title "Efficiently verifiable quantum advantage using error correction," I think this work is about providing a practical way to check if a quantum experiment actually achieved something meaningful without needing to run an impossibly long classical simulation.

Mira: I agree, and the authors' focus on Hidden Code Sampling really gets across how they’re leveraging the conditional peakedness of the distribution to achieve that verification efficiency.

Lev: From my perspective as someone who thinks about running this on hardware, if we can successfully instantiate these code families, it suggests a path where we might be able to validate complex quantum computations on actual physical systems in a way that makes sense for error correction protocols.

Kai: Exactly; the implication is that we move away from waiting for perfect simulation fidelity and instead focus our verification efforts on checking if the experimental measurements satisfy these specific, hard-to-spoof conditions.

Mira: The impact here is shifting the focus from just achieving a result to rigorously proving that result using a framework where classical verification itself is provably hard unless complexity classes change.

Lev: It opens up questions about what kind of quantum advantage we can actually claim if we can't verify it efficiently, and this paper gives us tools to address that limitation.

Kai: So, the main point is that HCS provides a mechanism to make quantum advantage claims much more trustworthy by providing a verification method that is faster than the simulation bottleneck.

More episodes

← Home