Sample-efficient benchmarking of shallow all-to-all random quantum circuits

This paper introduces the nonlinear cross-entropy and a heavy-output-based binary classifier as sample-efficient benchmarks capable of distinguishing noisy shallow all-to-all random quantum circuits from state-of-the-art classical spoofers, supported by analytic derivations and numerical simulations.

The Gist

Imagine you are trying to prove that a new, super-fast race car (a quantum computer) is actually faster than a very clever human driver in a simulator (a classical computer). The problem is, the race car has a shaky engine (noise), and the simulator is getting smarter every day, sometimes tricking us into thinking it's the real car.

This paper is about finding a better way to judge the race, specifically for "shallow" races—short, quick circuits where the car hasn't had time to get fully chaotic yet. The authors propose two new ways to tell the difference between the real quantum car and a fake simulator.

The Problem: The "Fake" Score

In the past, scientists used a test called Linear Cross-Entropy to see if the quantum computer was doing its job. Think of this like a teacher grading a student's essay. If the essay looks like it was written by a human (the quantum computer), the teacher gives a high score.

However, recently, "cheaters" (classical algorithms) learned how to write essays that look just like the human's, even though they didn't actually do the hard work of writing them from scratch. They can "spoof" the test, getting a high score without being a real quantum computer. This is especially true for short, shallow circuits.

The Solution 1: The "Deep Dive" Test (Nonlinear Cross-Entropy)

The authors suggest a new test called Nonlinear Cross-Entropy.

• The Analogy: Imagine the Linear test is like asking, "Did you write a sentence?" The cheater can easily say "Yes" and fake it. The Nonlinear test is like asking, "Write a sentence, and then explain why you chose every single word, and how the letters feel in your mouth."
• How it works: This test looks at the "shape" of the data in a much more complex way. The authors used a mathematical tool called a Brownian Circuit (think of it as a "fluid" version of a quantum circuit that is easier to analyze, like studying water flow instead of individual water molecules) to prove that:
  1. A real, noisy quantum computer will produce a specific "fingerprint" score.
  2. A cheater trying to fake it will get a completely different score.
  3. Even with the "shaky engine" (noise), the real computer's score is distinct enough that you don't need millions of race runs to see the difference. You only need a few samples.

They found that for short circuits, this test is sample-efficient. This means you don't need to run the race a billion times to be sure; a small number of runs is enough to separate the real quantum computer from the cheater.

The Solution 2: The "Heavy Hitter" Detector (Binary Classifier)

The second method is even faster. It's based on a concept called Heavy Output Generation (HOG).

• The Analogy: Imagine a lottery machine. A fair machine picks numbers completely at random. A quantum machine, however, is chaotic and tends to pick certain "lucky" numbers (heavy outputs) more often than others, while avoiding others.
• The Test: The authors created a simple "Yes/No" classifier.
  • You run the circuit once and get a result.
  • You check: "Is this result one of the 'heavy' lucky numbers?"
  • If the answer is "Yes," it's likely the real quantum computer. If "No," it's likely the cheater.
• The Magic: The authors proved that with this method, you only need a number of samples that grows very slowly (logarithmically) as the computer gets bigger.
  • Analogy: If you have a small computer, you might need 10 samples. If you have a huge computer, you might only need 20 samples. You don't need to double your effort every time the computer gets bigger; you just need a tiny bit more. This is incredibly efficient.

How They Did It (The "Secret Sauce")

To prove these ideas work, the authors didn't just guess. They used a clever mathematical trick:

1. The Fluid Model: They modeled the quantum circuits as a "Brownian" fluid. This allowed them to use tools from physics (usually used for studying magnets or heat) to calculate exact formulas for how these circuits behave.
2. The Replica Trick: They imagined running the circuit many times in parallel (like having clones of the computer) to calculate the average behavior. This helped them predict exactly how the scores would look for a real computer versus a cheater.
3. Verification: They also ran computer simulations on up to 40 qubits to confirm that their "fluid" math matched what happens with real, discrete quantum gates.

The Bottom Line

The paper claims that for short, shallow quantum circuits:

1. The Nonlinear Cross-Entropy is a reliable test that can tell a real noisy quantum computer from a classical cheater, even when the computer isn't perfect.
2. A new Binary Classifier (based on "Heavy Outputs") is even more efficient, requiring very few samples to make the distinction.

This gives scientists a new, robust way to prove "Quantum Advantage" (that the quantum computer is doing something a classical computer can't easily fake) without needing error-correction or waiting for the circuits to get very deep.

Technical Summary

Title: Sample-efficient benchmarking of shallow all-to-all random quantum circuits

Problem Statement
Random circuit sampling (RCS) is a primary framework for demonstrating quantum advantage in noisy intermediate-scale quantum (NISQ) hardware. However, existing benchmarks, particularly the linear cross-entropy benchmark (LXEB), have been shown to be vulnerable to "spoofing" by classical algorithms that do not faithfully sample from the ideal output distribution. This vulnerability raises a critical question: are there sample-efficient benchmarks capable of distinguishing genuine noisy quantum hardware from state-of-the-art classical spoofers, specifically in the regime of shallow-depth random circuits? While evidence suggests that sampling from shallow random circuits may be classically intractable beyond a certain depth threshold, no existing benchmark can currently reliably differentiate between a noisy quantum computer and an adversarial classical spoofer in this regime.

Methodology
The authors employ a theoretical framework based on all-to-all Brownian random circuit ensembles. Unlike discrete Haar-random circuits, Brownian circuits are continuous-time analogues composed of random all-to-all 2-qubit interactions governed by Gaussian white-noise couplings. This model serves as an analytically tractable "laboratory" for RCS.

The core technical approach involves:

1. Statistical Mechanics Mapping: The authors map the ensemble average of moments of the unitary matrices (specifically $2k$ copies or replicas) to a quantum statistical mechanics problem at an inverse temperature $\beta$ proportional to the circuit depth. This yields an effective many-body Hamiltonian, $H^{(k)}_{\text{eff}}$.
2. Large-$n$ (Mean-Field) Methods: By utilizing the all-to-all connectivity, the authors apply large-$n$ (mean-field) techniques to solve for the spectrum of $H^{(k)}_{\text{eff}}$. This allows for the exact calculation of arbitrarily high moments of the output probability distribution, a task notoriously difficult for discrete unitary circuits.
3. Replica Tricks: To compute nonlinear quantities like the mean of the logarithm of probabilities (required for cross-entropy), the authors employ replica tricks. This involves computing moments $\langle q^k \rangle$ for integer $k$, analytically continuing to the complex plane, differentiating with respect to $k$, and taking the limit $k \to 0$.
4. Noise Modeling: Single-qubit depolarizing noise is incorporated into the model via perturbation theory, treating the noise rate $\gamma$ as a small parameter relative to the coupling strength $J$.
5. Numerical Validation: The analytical results derived from the Brownian model are corroborated by numerical simulations of discrete all-to-all random quantum circuits composed of Haar-random 2-qubit gates (up to 40 qubits).

Key Contributions and Results

1. Nonlinear Cross-Entropy (log XEB) as a Sample-Efficient Benchmark:
   The paper derives exact analytic expressions for the ensemble-averaged nonlinear cross-entropy ($\log \text{XEB}$) and its variance as a function of circuit depth, system size $n$, and noise rate $\gamma$.

   • Result: In the shallow-depth regime ($\log n \gtrsim \beta J \gg 1$), the signal-to-noise ratio for estimating $\log \text{XEB}$ scales as an inverse polynomial in system size.
   • Implication: Unlike deep circuits where $\log \text{XEB}$ requires exponential samples to estimate, the nonlinear cross-entropy is sample-efficient for shallow circuits. It establishes a strict hierarchy between perfectly clean samplers ($\gamma=0$), noisy quantum samplers ($\gamma > 0$), and the "Harvard" spoofing algorithm (modeled as the limit $\gamma \to \infty$), allowing them to be distinguished reliably.

2. Heavy Output Generation (HOG) Binary Classifier:
   The authors develop a new binary classification protocol based on the concept of "heavy output generation" (HOG), which exploits the tendency of random quantum circuits to produce specific "heavy" bitstrings with higher probability.

   • Result: This classifier features logarithmic sample complexity ($m \sim \log n$) at short depths. It requires only a single bitstring sample to distinguish between a noisy quantum sampler and a classical spoofer with high probability.
   • Mechanism: The classifier utilizes a decision boundary (threshold score $z^*$) that separates the score distributions of clean quantum samplers (which favor high scores) from classical spoofers (which favor low scores). The probability of misclassification decays exponentially with the number of samples.

3. Analytical Expressions:
   The paper provides closed-form expressions for:

   • The mean nonlinear cross-entropy: $\log \text{XEB} = nH\left(\frac{1+a}{2}\right) + \gamma_e - e^{-n\beta\gamma}$ (where $a = e^{-12\beta J}$ and $H$ is binary entropy).
   • The variance of the nonlinear cross-entropy, showing distinct scaling behaviors depending on whether the circuit depth is below or above a crossover point ($c=1/2$).

Significance and Claims
The paper claims to demonstrate that the nonlinear cross-entropy is a viable, sample-efficient benchmark for shallow-depth all-to-all random circuits, a regime where previous benchmarks failed or were spoofed. The authors argue that this metric can reliably distinguish genuine noisy quantum hardware from state-of-the-art classical spoofers (specifically the Harvard algorithm) even in the presence of depolarizing noise.

Furthermore, the proposed HOG-based binary classifier offers a significant practical advantage by reducing the sample complexity from polynomial (required for mean estimation) to logarithmic, enabling rapid verification of quantum advantage with minimal data.

The authors note that while their results are derived using Brownian circuit ensembles, numerical simulations confirm that these findings generalize to discrete all-to-all random circuits. They suggest that these benchmarks could be particularly relevant for future experiments on platforms with all-to-all connectivity, such as neutral atom and trapped-ion quantum computers, where logical random circuit sampling could be evaluated using these metrics. The paper explicitly states that a more rigorous analysis against other potential spoofing algorithms is left for future work.