Abstract: Although the emergence of a fully-functional quantum computer may still be far away from today, in the near future, it is possible to have medium-size, special-purpose, quantum devices that can perform computational tasks not efficiently simulable with any classical computer. This status is known as quantum supremacy (or quantum advantage), where one of the promising approaches is through the sampling of chaotic quantum circuits. Sampling of ideal chaotic quantum circuits has been argued to require an exponential time for classical devices. A major question is whether quantum supremacy can be maintained under noise without error correction, as the implementation of fault-tolerance would cost lots of extra qubits and quantum gates. Here we show that, for a family of chaotic quantum circuits subject to Pauli errors, there exists an non-exponential classical algorithm capable of simulating the noisy chaotic quantum circuits with bounded errors. This result represents a serious challenge to a previous result in the literature suggesting the failure of classical devices in simulating noisy chaotic circuits with about 48 qubits and depth 25. Moreover, even though our model does not cover all types of experimental errors, from a practical point view, our result describes a well-defined setting where quantum supremacy can be tested against the challenges of classical rivals, in the context of chaotic quantum circuits.
Introduction
We are currently in the "NISQ" (Noisy Intermediate-Scale Quantum) era. While full-scale, error-corrected quantum computers remain a future goal, researchers are actively pursuing "quantum supremacy"—the demonstration of a specific task that a near-term quantum device can perform which a classical supercomputer cannot.
One leading candidate for demonstrating this advantage is the task of sampling from chaotic quantum circuits. The theoretical foundation for this approach relies on the fact that the probability distribution of the outputs of these circuits is incredibly complex, obeying the Porter-Thomas distribution. In an ideal, noiseless environment, a classical computer would require exponential time to mimic this distribution. However, real-world quantum devices are inherently noisy. This paper addresses a central tension in the field: Does noise "wash out" the quantum advantage, making these circuits easy enough for classical algorithms to simulate?
Methodology: Noise as a Low-Pass Filter
The researchers employ a combination of circuit theory and Fourier analysis to develop a classical simulation algorithm. The approach follows several key steps:
- Circuit Mapping: The authors demonstrate that a broad class of chaotic quantum circuits can be decomposed and mapped onto a family of Instantaneous Quantum Polynomial-time (IQP) circuits.
- Noise Modeling: Experimental imperfections are modeled using Pauli errors (specifically bit-flip noise) and depolarizing noise.
- Fourier Analysis: The core insight of the paper is the representation of the circuit's output probability distribution as a sum of Fourier components. The authors prove that noise acts as a "low-pass filter," exponentially suppressing higher-order Fourier components.
- Classical Approximation: Because the most complex parts of the distribution (the high-order Fourier terms) are dampened by noise, a classical algorithm only needs to calculate a limited number of low-order terms to achieve a high-fidelity approximation. The researchers utilize a Monte Carlo-based sampling method to estimate these coefficients efficiently.
Key Insights and Results
The Complexity of Noise
The most profound finding is that noise does not merely reduce accuracy; it fundamentally alters the computational complexity of the simulation. By suppressing the high-frequency Fourier components that represent the "quantumness" of the system, noise smooths the output distribution, making it accessible to classical tracking.
Redefining the Supremacy Frontier
Previous literature suggested that a circuit with approximately 48 qubits and a depth of 25 was safely beyond classical reach. This paper challenges that benchmark, arguing that if realistic noise levels are accounted for, that specific frontier may already be classically simulable. The authors prove the existence of a classical algorithm that can simulate the average $l_1$ norm of noisy chaotic circuits in polynomial time. Furthermore, when using cross-entropy—the metric favored by experimental teams to claim supremacy—the classical algorithm runs in quasi-polynomial time.
The $1/\epsilon$ Scaling
The runtime of the proposed classical algorithm is polynomial in the number of qubits ($n$), but it is highly sensitive to the noise strength ($\epsilon$). The runtime scales as $n^{O(1/\epsilon)}$. This implies that as noise decreases ($\epsilon \to 0$), the classical simulation becomes exponentially more difficult. The battle for quantum supremacy is thus a race between quantum engineers reducing noise and classical theorists refining simulation algorithms.
Limitations and Future Work
While the algorithm is technically "non-exponential," the authors acknowledge that if the noise $\epsilon$ is extremely small, the exponent $1/\epsilon$ becomes large enough to make the simulation practically impossible on current classical hardware.
Additionally, the paper utilizes relatively simple noise models. Real-world hardware faces more complex issues like crosstalk, leakage, and non-Markovian noise, which may affect Fourier suppression differently. Future work may involve optimizing the classical algorithm through techniques like compressed sensing or machine learning to further test the limits of quantum advantage in the NISQ era.
Summary updated