Efficiently verifiable quantum advantage using error correction

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 of these claims. This work introduces Hidden Code Sampling (HCS), a sampling task provably hard for classical computers, whose output distribution is conditionally peaked, enabling verification in far less time than full simulation.

Hidden Code Sampling (HCS) Scheme

The scheme is based on ideas from quantum error correction and involves a two-player protocol between Alice (the verifier) and Bob (the experimentalist). Alice chooses a CSS code defined by two binary linear codes, CZ and CX. She publishes the hardness code CZ to Bob, while keeping the peakedness code CX secret to compute syndromes. The process requires Bob to prepare a particular code state, apply an error channel modeled by a unitary operation U(θ) (representing coherent errors), and then measure in the X basis. Bob sends these samples back to Alice.

Verification Protocols

Alice runs two verification tests:

1. Peak Verification: This test checks the correctness of the code state preparation by identifying peaks of the distribution using a classical decoder for the syndrome, and accepting if specific conditions on logical and syndrome outcomes are met.

2. Syndrome Verification: This test verifies that the syndromes are distributed according to the correct distribution by computing a statistical estimator for relative entropy difference (RED) against a series of potential spoofing distributions, qref.

Hardness of Sampling

The hardness of sampling is established through several arguments:

1. Theorem 2 proves that BLCProbabilities[n, C, θ] is GapP-hard in the worst case for any binary linear code C and rotation angle θ = Ω(1/poly(n)). This relies on reducing the problem to computing output probabilities of a circuit Q using post-selection gadgets.

2. Conjecture 3 suggests that if a classical sampler can exactly sample from the distribution p(x) = ⟨xH⊗nU(θ)C⟩ 2, then the polynomial hierarchy collapses in the average case for random choices of C and θ.

Verification-Simulation Gap

The scheme achieves a significant gap between simulation and verification costs.

1. Simulation Cost: Using near-Clifford simulators, the cost of approximately sampling up to TVD δ is given by at most O˜(ξ(U)), where the stabilizer extent ξ(e iθZ) is related to sin θ.

2. Verification Cost: For below-threshold error rates, Theorem 9 proves that the syndrome distribution is approximately independent of the logical state, allowing Alice to replace the input state with 0⟩ and reducing verification time on the order of 2(ck).

3. Gap Ratio: This leads to a verification-simulation gap of 2(k) when low-rank stabilizer simulators are optimal, meaning simulation time Θ(2k+n−kx) trails verification time Θ(2n−kx).

Soundness and Completeness

The tests are shown to be sound. The Peak Verification test is robust because any error channel correctable by the code will pass it. The Syndrome Verification test detects spoofing attempts by using the RED score, which is conjectured to be hard to spoof for any classical spoofer, leading to Conjecture 1: there is no classical algorithm that can satisfy both verification checks.

Instantiating the Protocol

The protocol can be instantiated using specific code families. For Peak Verification efficiency, CX must have efficient decoders (e.g., random LDPC codes). For a large verification-simulation gap, the quantum code requires linear rate, i.e., k ∼ n (e.g., Gallager codes or turbo codes). This allows for transversal implementation of non-Clifford gates using products of algebraic codes.

Discussion and Outlook

The work suggests that the scheme is robust to benign experimental noise below a certain threshold angle. While verification remains computationally intensive due to the need to compute outcome probabilities, the gap between simulation and verification persists even if simulation algorithms are improved, unless a fundamentally different algorithm is found. The results open questions regarding the average-case hardness of sampling for practical code families and potential applications in quantum cryptography.

The gist

This work introduces Hidden Code Sampling (HCS), a sampling task provably hard for classical computers whose output distribution is conditionally peaked, enabling verification in far less time than full simulation.

As a fastidious and diligent researcher, I have analyzed this paper, Peaked quantum advantage using error correction. It proposes a novel verification framework called Hidden Code Sampling (HCS) that leverages quantum error correction concepts to create a verification-simulation gap large enough to classically verify quantum advantage claims.

The primary improvement offered by this research is not the creation of a new AI model itself, but rather the development of a more robust and trustworthy framework for deploying and validating future quantum advantage experiments.

Here are the specific improvements that can be made to AI systems (or, more accurately, to the infrastructure and methodology surrounding quantum computation) based on this paper:

1. [Improvement] Development of a Classically Verifiable Quantum Advantage Protocol.

2. [Improvement] Enhanced Robustness Against Classical Spoofing Attacks in Quantum Experiments.

3. [Improvement] Efficient and Scalable Verification of Near-Term Quantum Circuits using Error Correction Principles (HCS).

The improved AI system/framework, utilizing the insights from this paper, can perform the following specific tasks:

1. The system can act as a Quantum Advantage Auditor that takes a proposed quantum experiment (e.g., an IQP circuit) and uses the HCS verification protocol to determine if it genuinely demonstrates quantum advantage.

2. It can verify complex, near-term quantum computations by checking two distinct conditions: first, verifying the conditional peakedness of the output distribution using efficient classical decoders (PeakVerification); and second, verifying that this distribution is statistically far from any plausible classical simulator or spoofer (SyndromeVerification via Relative Entropy Difference).

3. The system can reliably distinguish between a true quantum advantage claim and a false one by exploiting the exponential gap between verification time and full simulation time (the Verification-Simulation Gap), especially when the code rate is linear and the rotation angle is below the error correction threshold. This allows for verification in regimes where classical simulation is infeasible, even if it remains costly.

4. The system can be designed to be robust against classical adversaries attempting to mimic quantum outcomes by using statistical tests (like RED) that are shown to detect deviations from ideal distributions, such as those generated by Pauli spoofer models.

In essence, the improved system moves beyond simply running a quantum algorithm; it provides a mathematically rigorous and computationally feasible method for proving that the output distribution is genuinely quantum and hard to simulate classically.

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.