⚛️ quantum physics

Classically Spoofing System Linear Cross Entropy Score Benchmarking

This paper demonstrates that the System Linear Cross Entropy Score (sXES), a benchmarking metric proposed for quantum supremacy via Hamiltonian simulation that was thought to be classically hard to spoof, can in fact be efficiently simulated by classical computers in certain regimes.

Original authors: Andrew Tanggara, Mile Gu, Kishor Bharti

Published 2026-02-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrew Tanggara, Mile Gu, Kishor Bharti

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

The Big Picture: The "Quantum Cooking" Contest

Imagine a high-stakes cooking competition. On one side, you have a team of Quantum Chefs using a magical, futuristic stove (a quantum computer) to cook a very complex dish. On the other side, you have Classical Chefs using standard, old-school ovens (classical supercomputers).

The Quantum Chefs claim, "We can cook this dish so fast and so perfectly that no Classical Chef could ever do it in a million years." This is what scientists call "Quantum Supremacy."

To prove they are right, the judges need a way to taste the dish and see if it matches the "perfect recipe" (the ideal mathematical outcome).

The Old Judge: The "Linear XEB" Score

For a few years, the judges used a specific tasting metric called Linear Cross-Entropy Benchmarking (Linear XEB).

How it worked: The judges took a sample of the Quantum Chef's dish and checked if the flavors matched the perfect recipe more often than a random guess would.
The Problem: Recently, clever Classical Chefs figured out a shortcut. They realized that for certain types of "sublinear-depth" circuits (think of these as recipes that don't have enough steps to get truly chaotic), they could fake the taste test. They could make their old ovens produce a dish that looked like the Quantum Chef's perfect dish, even though they didn't actually cook it the hard way. This broke the trust in the old metric.

The New Judge: The "sXES" Score

Because the old metric was broken, the Quantum Chefs proposed a new, more complex recipe and a new tasting metric called System Linear Cross Entropy Score (sXES).

The Promise: This new recipe (called mQSVT) is structurally different. It uses a specific pattern of ingredients (gates) that repeats in blocks. The Quantum Chefs argued, "Our new recipe is so different that the Classical Chefs' old shortcuts won't work on it. We need a new rule called sXQUATH which says: 'It is mathematically impossible for a Classical Chef to fake this score efficiently.'"

The Paper's Discovery: The "Pauli Path" Shortcut

The authors of this paper (Andrew, Mile, and Kishor) decided to test the new judge. They asked: "Can a Classical Chef still fake the sXES score, even with this new, complex recipe?"

The Answer: Yes, they can.

Here is how they did it, using an analogy:

1. The "Pauli Path" Algorithm

Imagine the Quantum Recipe is a massive, multi-layered cake. To know exactly how the cake tastes, you usually have to calculate the chemistry of every single crumb. That's impossible for a Classical Chef.

However, the authors found a shortcut. They realized that for this specific type of cake (the mQSVT circuit), you don't need to calculate every crumb. You only need to trace a specific, thin "path" through the cake layers.

They call this the Pauli Path.
Think of it like a "taste test tunnel." Instead of analyzing the whole cake, the Classical Chef sends a probe through a specific tunnel in the cake structure.
Because the Quantum Recipe has a repetitive structure (it uses the same block of ingredients over and over), this tunnel reveals enough information about the whole cake to guess the final taste with surprising accuracy.

2. The "Noise" Factor

The paper also looked at what happens when the kitchen is messy (when the quantum computer is noisy).

In a noisy kitchen, the ingredients get a bit spoiled, and the final dish becomes a bit random.
The authors showed that if the noise is high enough, the Classical Chef's shortcut becomes even better at faking the score. They can produce a "noisy" dish that scores just as high as the real Quantum Chef's noisy dish, making it impossible for the judges to tell the difference.

The Conclusion: The New Judge is Also Flawed

The paper concludes two main things:

The Shortcut Works: The Classical Chef's "Pauli Path" algorithm can efficiently simulate the output of these specific quantum circuits.
The Score is Spoofable: Because the Classical Chef can simulate the output so well, they can also spoof (fake) the sXES benchmark. They can make their classical computer produce a score that looks like a quantum victory, even though they didn't actually do the hard quantum work.

In simple terms: The Quantum Chefs thought they found a new, unbreakable lock (sXES) to prove they were superior. The authors of this paper found a master key (the Pauli Path algorithm) that opens that lock just as easily as the old one.

This means that for these specific types of circuits (sublinear depth), the sXES benchmark is not a reliable way to prove "Quantum Supremacy" yet. The authors argue that we need to invent an even stronger benchmark for the future, one that the "Pauli Path" shortcut cannot break.

Technical Summary: Classically Spoofing System Linear Cross Entropy Score Benchmarking for Sublinear-Depth Circuit

Problem Statement
Recent claims of "quantum supremacy" have largely relied on the Linear Cross-Entropy Benchmarking (Linear XEB) metric to verify that quantum devices perform tasks (such as Random Circuit Sampling) that are intractable for classical computers. The theoretical hardness of classically spoofing Linear XEB rests on the Cross-Entropy Quantum Threshold (XQUATH) conjecture. However, recent work has disproven XQUATH for sublinear-depth circuits, undermining the robustness of Linear XEB as a supremacy benchmark.

In response, a variant benchmark called the System Linear Cross Entropy Score (sXES) was proposed for quantum Hamiltonian simulation experiments using Minimal Quantum Singular Value Transform (mQSVT) circuits. Unlike standard Random Circuit Sampling (RCS), mQSVT circuits possess a distinct structure involving multiple copies of the same unitary $U$ and its conjugate $U^\dagger$ . This structural difference led to the System Linear Cross-Entropy Quantum Threshold Assumption (sXQUATH), which posits that no polynomial-time classical algorithm can approximate the output probabilities of mQSVT circuits with a mean-squared error significantly lower than a trivial uniform approximation. The formal relationship between sXQUATH and XQUATH was previously unclear, leaving open the question of whether existing spoofing techniques could be adapted to refute sXQUATH.

Methodology
The authors employ a Pauli path algorithm to construct an efficient classical approximation for the output probability distribution of mQSVT circuits. The core of their approach involves expanding the circuit's density matrix in terms of normalized Pauli matrices at every layer.

Key technical steps include:

Pauli Path Expansion: The output probability $p(U, x)$ is expressed as a sum over Fourier coefficients corresponding to Pauli paths $s$ . For an mQSVT circuit with $d$ blocks, a Pauli path is a sequence of sub-paths traversing $U$ and $U^\dagger$ .
Overcoming Orthogonality Issues: In standard RCS, the "orthogonality property" ensures that the expectation of the product of Fourier coefficients for distinct paths is zero. This property fails in mQSVT circuits because the same random unitary $U$ appears multiple times (specifically $2d$ times in a $d$ -block circuit). Consequently, the analysis requires higher-order moments (specifically the 4th moment) of Haar-random unitaries, rather than just the 2nd moment used in previous RCS spoofing results.
Weingarten Calculus: To evaluate the expectations of products of transition amplitudes involving multiple copies of the same unitary, the authors utilize Weingarten calculus. This allows them to express Haar-random unitary moments in terms of Weingarten functions and permutation operators.
Specific Path Construction: The authors define a specific, efficiently computable Pauli path $r$ that starts with non-identity Paulis ( $Z \otimes Z$ ) on the first qubit and its coupled partner in the first layer, followed by identity Paulis in subsequent layers. They construct a classical approximation $q(U, x) = 2^{-n} + F(U, r, x)$ , where $F(U, r, x)$ is the Fourier coefficient for path $r$ .

Key Contributions and Results
The paper presents two primary theorems demonstrating the failure of sXQUATH and the spoofability of sXES:

Refutation of sXQUATH (Theorem 1): The authors prove that for single-block ( $d=1$ ) mQSVT circuits with sublinear depth ( $d_U = o(n)$ ), the constructed classical algorithm $q(U, x)$ achieves a mean-squared error (MSE) significantly lower than the trivial approximation ( $2^{-n}$ ). Specifically, they show that the quantity $sXQ$ (the difference in MSE between the trivial and the proposed algorithm) scales as $\Omega(2^{-3n})$ . This directly refutes the sXQUATH conjecture for this regime, proving that a polynomial-time classical algorithm can approximate the output probabilities better than the assumption allows.
Spoofing sXES Benchmark (Theorem 2): The authors demonstrate that the same algorithm can spoof the sXES benchmark for noisy mQSVT circuits. They show that for circuits corrupted by depolarizing noise above a certain threshold, the classical algorithm produces an sXES score comparable to that of a noisy quantum circuit. The spoofed sXES is bounded by $2^{-n}(\sum_{x \neq 0^n} \mathbb{E}_U[p(U, x)] + c d_U)$ , indicating that the benchmark cannot distinguish between the noisy quantum experiment and the classical simulation in these regimes.

Significance
The paper claims that these results extend the seminal findings of Aharonov et al. (2023) regarding the spoofing of Linear XEB in RCS. By showing that sXES is also susceptible to efficient classical spoofing via Pauli path algorithms, the authors argue that:

The complexity-theoretic foundation of sXES (sXQUATH) is fragile, particularly for sublinear-depth circuits.
The structural differences between mQSVT circuits and standard RCS do not provide sufficient protection against current state-of-the-art classical simulation techniques.
Future claims of quantum supremacy, whether based on RCS or Hamiltonian simulation, require new benchmarking tasks with stronger complexity-theoretic guarantees that can rule out spoofing by Pauli path algorithms and similar methods.

The work does not propose new experimental protocols or future applications but serves as a theoretical cautionary result, highlighting the need for more robust verification methods in the pursuit of demonstrating quantum advantage.