We introduce the energy-advantage frontier of random circuit sampling (RCS)—the locus in the noise-rate/size plane where the classical and quantum energy-to-solution are equal—and locate it relative to the noise-induced classical-simulability transition. Our firm, model-free result is that the classical sampling-energy floor collapses sharply across the transition, exhibiting a finite-size scaling collapse over exact systems n≤12 (with a collapse exponent of order unity). Built on it, the energy-advantage frontier is distinct from the computational (wall-clock) frontier: in the exascale-classical, few-femtojoule regime, the energy frontier is the more noise-robust, so an energy advantage can persist where a time advantage does not—a projection, not a deployment claim, whose direction reverses outside that regime. We give a conditional Landauer lower bound for sampling, RE≡Ecl/Eq≳2(1.0±0.2)n/n under standard RCS hardness, package RE as a single figure of merit computed by a released open tool (exs), and map an energy-normalized cross-entropy witness within a cost model. A run on a 156-qubit IBM Heron processor tests the fidelity model (no energy is measured on hardware) and shows real noise exceeds the depolarizing idealization, so quoted frontier locations are upper bounds.
We introduce the energy-advantage frontier of random circuit sampling (RCS)—the locus in the noise-rate/size plane where the classical and quantum energy-to-solution are equal—and locate it relative to the noise-induced classical-simulability transition. Our firm, model-free result is that the classical sampling-energy floor collapses sharply across the transition, exhibiting a finite-size scaling collapse over exact systems n≤12 (with a collapse exponent of order unity). Built on it, the energy-advantage frontier is distinct from the computational (wall-clock) frontier: in the exascale-classical, few-femtojoule regime, the energy frontier is the more noise-robust, so an energy advantage can persist where a time advantage does not—a projection, not a deployment claim, whose direction reverses outside that regime. We give a conditional Landauer lower bound for sampling, RE≡Ecl/Eq≳2(1.0±0.2)n/n under standard RCS hardness, package RE as a single figure of merit computed by a released open tool (exs), and map an energy-normalized cross-entropy witness within a cost model. A run on a 156-qubit IBM Heron processor tests the fidelity model (no energy is measured on hardware) and shows real noise exceeds the depolarizing idealization, so quoted frontier locations are upper bounds.
Random circuit sampling (RCS) is a leading candidate for demonstrating quantum advantage, supported by strong complexity-theoretic evidence of hardness in the ideal setting and by rapid experimental progress to date. In practice, however, noise is unavoidable, and a central problem is to identify the noise-strength boundary between classically simulable and classically hard regimes. In this work, we establish an architecture-general hardness bound for this boundary for the standard local depolarizing noise of strength γ. Assuming the standard average-case #P-hardness conjecture for ideal RCS, we show that, for any circuit architecture satisfying this conjecture, noisy RCS on the same architecture remains hard to simulate classically within any inverse-polynomial total variation distance whenever γ=O(logn/(nd)) for n-qubit circuits of depth d, unless the polynomial hierarchy collapses. Crucially, noisy-RCS hardness follows without any additional conjectural or architecture-specific assumption beyond those already entering the ideal-RCS hardness framework. Our proof combines a low-degree polynomial extrapolation with a monotonicity reduction showing that efficient classical simulation at one depolarizing noise strength implies efficient simulation at every larger strength. Together, these ingredients transfer the standard ideal-RCS hardness conjecture to sampling hardness at a prespecified noise strength. Finally, combining the convergence-to-uniformity result of Dalzell et al. [Commun. Math. Phys. 405, 78 (2024)] with our monotonicity reduction yields efficient classical simulation for γ=ω(logn/(nd)) on layered, regularly connected architectures. Thus, wherever the two architectural settings overlap, this identifies γ=Θ(logn/(nd)) as the asymptotic complexity-transition scale.
Code and manuscript for The energy-advantage frontier of random circuit sampling across the simulability transition (Wakaura & Tanimae, QIRI). We study the energy-advantage frontier of random circuit sampling (RCS) — the locus in the noise-rate/size plane where the classical and quantum energy-to-solution are equal — and its relation to the noise-induced classical-simulability transition. The package provides: exact and tensor-network (Liouville-MPS) operator-space entanglement, Landauer-floor energy accounting, the energy/computational advantage frontiers, an energy-charged cross-entropy witness, an IBM hardware interface, and the exs energy-to-solution benchmark CLI. The included PDF is the accompanying manuscript. Validated against exact dense evolution (<1e-2 in OSEE at n=9); full test suite passes. The Liouville-MPS sampler extends the operator-entanglement transition beyond exact density matrices.
We report forward random-circuit sampling (RCS) on the 120-qubit Nighthawk r2 superconducting processor (ibm_phoenix) with square-lattice connectivity, using 61 qubits, native CZ gates, and the standard cloud execution stack with no benchmark-specific calibration. Two independent fidelity estimators---mirror benchmarking and three- and four-patch cross-entropy benchmarking (XEB)---agree with each other at every measured depth, the mirror from 4 to 40 cycles and the patched estimators from 20 to 40 cycles, across more than two orders of magnitude of fidelity decay, and exceed the first-generation Nighthawk r1 device by more than an order of magnitude at fixed depth. The 36-cycle circuits sit at the depth where tensor-network contraction cost saturates at system size: a contraction-cost estimator validated against the published Sycamore and Zuchongzhi networks places the single-amplitude cost at ∼1022 complex operations. At FXEB(36)=2.3×10−3 under favorable memory assumptions this implies 1.2×1027 machine operations within the bounded-fidelity rejection-sampling model --- more than a century of runtime on the Frontier supercomputer --- to collect a 106-sample ensemble, which takes only 19\,s on Nighthawk r2. To our knowledge, this is the first demonstration of quantum advantage for a vanilla random-circuit sampling on a commercially and broadly accessible quantum processor that most non-expert quantum computer users can easily replicate.
Random circuit sampling (RCS) remains one of the most competitive frameworks for demonstrating quantum advantage in near-term noisy intermediate-scale quantum (NISQ) hardware. Unfortunately, absent error-correction, existing benchmarks to characterize these experiments, like linear cross-entropy, have been classically spoofed due to noise. Because of this, there are interesting regimes, like shallow-depth random quantum circuits, where sampling is plausibly classically intractable, but no existing benchmark can distinguish between a noisy quantum computer and an adversarial classical spoofer. In this paper, we demonstrate that the nonlinear cross-entropy provides a sample-efficient benchmark for shallow-depth all-to-all random quantum circuits whose score cleanly separates noisy quantum computers from state-of-the-art classical spoofers, even in the presence of depolarizing noise. Further, we develop a binary classifier based on the notion of heavy output generation that features logarithmic sample complexity at short depth. Our evidence comes from exact analytic expressions for all-to-all Brownian circuit ensembles derived using replica tricks, and numerical simulations that corroborate these results for discrete Haar-random unitary circuits.
Understanding the computational power of noisy intermediate-scale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether error-uncorrected noisy quantum computers can provide computational advantage over classical computers. Specifically, we study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. In particular, we simulate the real-time dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantum system by using a metric we call MPO entanglement entropy. The latter metric is chosen because it determines the cost of classical MPO simulation. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation of 1D noisy systems. Specifically, we show that above the characteristic system size, there is an optimal circuit depth, independent of the system size, where the MPO entanglement entropy is maximized. Most importantly, the maximum achievable MPO entanglement entropy is bounded by a constant that depends only on the gate error rate, not on the system size. We also provide a heuristic analysis to get the scaling of the maximum achievable MPO entanglement entropy as a function of the gate error rate. The obtained scaling suggests that although the cost of MPO simulation does not increase exponentially in the system size above a certain characteristic system size, it does increase exponentially as the gate error rate decreases, possibly making classical simulation practically not feasible even with state-of-the-art supercomputers.
Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. Quantum supremacy experiments have been a major step forward, but gaps remain between the theory behind these experiments and their actual implementations. In this work we initiate the study of the complexity of quantum random circuit sampling experiments with realistic amounts of noise. Actual quantum supremacy experiments have high levels of uncorrected noise and exponentially decaying fidelities. It is natural to ask if there is any signal of exponential complexity in these highly noisy devices. Surprisingly, we show that it remains hard to compute the output probabilities of noisy random quantum circuits without error correction. More formally, so long as the noise rate of the device is below the error detection threshold, we show it is #P-hard to compute the output probabilities of random circuits with a constant rate of noise per gate. This hardness persists even though these probabilities are exponentially close to uniform. Therefore the small deviations away from uniformity are hard to compute, formalizing an important intuition behind Google's supremacy claim. Interestingly these hardness results also have implications for the complexity of experiments in a low-noise setting. The issue here is that prior hardness results for computing output proba-bilities of random circuits are not robust enough to imprecision to connect with the Stockmeyer argument for hardness of sampling from circuits with constant fidelity. We exponentially improve the robustness of prior results to imprecision, both in the cases of Random Circuit Sampling and BosonSampling. In the latter case we bring the proven hardness within a constant factor in the exponent of the robustness required for hardness of sampling for the first time. We then show that our results are in tension with one another - the high-noise result implies the low-noise result is essentially optimal, even with generalizations of our techniques.