One of the crucial steps in building a scalable quantum computer is to identify the noise sources which lead to errors in the process of quantum evolution. Different implementations come with multiple hardware-dependent sources of noise and decoherence making the problem of their detection manyfoldly more complex. We develop a randomized benchmarking algorithm which uses Weyl unitaries to efficiently identify and learn a mixture of error models which occur during the computation. We provide an efficiently computable estimate of the overhead required to compute expectation values on outputs of the noisy circuit relying only on the locality of the interactions and no further assumptions on the circuit structure. The overhead decreases with the noise rate and this enables us to compute analytic noise bounds that imply efficient classical simulability. We apply our methods to ansatz circuits that appear in the variational quantum eigensolver and establish an upper bound on classical simulation complexity as a function of noise, identifying regimes when they become classically efficiently simulatable.
One of the crucial steps in building a scalable quantum computer is to identify the noise sources which lead to errors in the process of quantum evolution. Different implementations come with multiple hardware-dependent sources of noise and decoherence making the problem of their detection manyfoldly more complex. We develop a randomized benchmarking algorithm which uses Weyl unitaries to efficiently identify and learn a mixture of error models which occur during the computation. We provide an efficiently computable estimate of the overhead required to compute expectation values on outputs of the noisy circuit relying only on the locality of the interactions and no further assumptions on the circuit structure. The overhead decreases with the noise rate and this enables us to compute analytic noise bounds that imply efficient classical simulability. We apply our methods to ansatz circuits that appear in the variational quantum eigensolver and establish an upper bound on classical simulation complexity as a function of noise, identifying regimes when they become classically efficiently simulatable.
One of the crucial steps in building a scalable quantum computer is to identify the noise sources which lead to errors in the process of quantum evolution. Different implementations come with multiple hardware-dependent sources of noise and decoherence making the problem of their detection manyfoldly more complex. We develop a randomized benchmarking algorithm which uses Weyl unitaries to efficiently identify and learn a mixture of error models which occur during the computation. We provide an efficiently computable estimate of the overhead required to compute expectation values on outputs of the noisy circuit. The overhead decreases with the noise rate and this enables us to compute analytic noise thresholds that imply efficient classical simulability. We apply our methods to ansatz circuits that appear in the Variational Quantum Eigensolver and establish an upper bound on classical simulation complexity as a function of noise, identifying regimes when they become classically efficiently simulatable.
Noise detrimentally affects quantum computations so that they not only become less accurate but also easier to simulate classically as systems scale up. We construct a classical simulation algorithm, lowesa (low weight efficient simulation algorithm), for estimating expectation values of noisy parameterised quantum circuits with a fixed observable. It combines previous results on spectral analysis of parameterised circuits with Pauli back-propagation and recent ideas for simulations of noisy random circuits. We show, under some conditions on the circuits and mild assumptions on noise, that lowesa gives an efficient, polynomial algorithm in the number of qubits (and depth), with approximation error that vanishes exponentially in the physical error rate and a controllable cutoff parameter. This is valid for any expectation value that may be efficiently evaluated on a quantum computer. We discuss the practical limitations of the method for circuit classes with correlated parameters and its scaling with decreasing error rates.
As quantum devices grow in size while remaining affected by noise, a key challenge is to determine when and how they can surpass classical computation on practical tasks. This requires the development of highly efficient classical simulation algorithms. Pauli backpropagation algorithms are among the most promising, having shown efficiency in simulating certain classes of parameterized quantum circuits, strong candidates for near‑term quantum advantage, under random circuit assumptions and depolarizing noise. However, their efficiency had not been demonstrated for more realistic nonunital noise models, such as amplitude damping, which better capture the behaviour of current hardware. We close this gap by adapting Pauli backpropagation to most single‑qubit noise channels, including nonunital noise, and proving that it remains efficient under these conditions. Our algorithm is parallelizable, memory‑efficient, and requires no assumptions on the locality of the observable, the geometry of the hardware, or the depth of the circuit. While hardware noise can strongly affect computational power in highly structured, fault‑tolerant circuits, our findings indicate little difference for most near‑term variational architectures. This establishes Pauli backpropagation as an efficient method for simulating noisy quantum devices under realistic noise assumptions.While these advances improve our ability to reproduce noisy expectation values of observables, many practical applications, including combinatorial optimization, require direct access to the bitstrings output by quantum circuits, as these encode candidate solutions. Classical replication of such noisy samples has so far been limited beyond the random circuit setting. To bridge this gap, we first focus on problems whose objective functions depend only on two‑body correlations, such as Max‑Cut, and apply Gaussian randomized rounding to the circuit's two‑qubit marginals. This produces classical samples whose expected cost is provably close to that of the noisy quantum device. Large‑scale simulations and experiments on IBMQ hardware confirm that the rounded samples reproduce the full energy distribution, with similar behaviour under various noise models. Coupled with Pauli backpropagation for efficiently estimating noisy marginals, this yields an end‑to‑end classical sampler operating in polynomial time for a broad class of variational circuits. Our results therefore show that sufficiently noisy quantum circuits for combinatorial optimization can be sampled from classically, clarifying where near‑term hardware may or may not outperform classical algorithms.Finally , we go beyond one and two‑body marginals and present an algorithm that samples valid bitstrings directly from a maximum‑entropy distribution matching the given expectation values of the quantum circuit. This method does not rely on the locality or sparsity of the problem's Hamiltonian and performs well across a variety of quantum circuits, including deep circuits on many qubits. When combined with Pauli propagation or error mitigation, it provides a practical pipeline for obtaining samples from quantum circuits in the near term, where full error correction might not yet be available.
Abstract Noise characterization methods such as randomized benchmarking (RB) are critical for the development of scalable quantum computers. Modern RB protocols for multiqubit systems extract physically relevant error rates by exploiting the structure of the group representation generated by the set of benchmarked operations. However, existing techniques become prohibitively inefficient for representations that are highly reducible yet decompose into irreducible subspaces of high dimension. These situations prevail when benchmarking high-dimensional systems such as qudits or bosonic modes, where experimental control is limited to implementing a small subset of all possible unitary operations. We introduce a broad framework for enhancing the sample efficiency of RB that is sufficiently powerful to extend the practical reach of RB beyond the multiqubit setting. Our strategy, which applies to any benchmarking group, uses ‘synthetic’ quantum circuits with classical post-processing of both input and output data to leverage the full structure of reducible superoperator representations. To demonstrate the efficacy of our approach, we develop a detailed theory of RB for systems with rotational symmetry. Such systems carry a natural action of the group SU ( 2 ) , and they form the basis for several novel quantum error-correcting codes. We show that, for experimentally accessible high-spin systems, synthetic RB protocols can reduce the complexity of measuring rotationally invariant error rates by two orders of magnitude relative to standard approaches such as character RB.
A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.
Classical simulations of noisy quantum circuits are instrumental to our understanding of the behavior of real-world quantum systems and the identification of regimes where one expects quantum advantage. In this work, we present a highly parallelizable tensor-network-based classical algorithm, equipped with rigorous accuracy guarantees, for simulating n -qubit quantum circuits with arbitrary single-qubit noise. Our algorithm represents the state of a noisy quantum system by a particular ensemble of matrix product states from which we stochastically sample. Each pure state evolved under a single-qubit noise process is then represented by the ensemble of states that achieves the minimal average entanglement (the entanglement of formation) between the noisy qubit and the remainder. This approach lets us use a more compact representation of the quantum state for a given accuracy requirement and noise level. For a given maximum bond dimension χ and circuit, our algorithm comes with an upper bound on the simulation error, runs in poly ( n , χ ) -time, and improves upon related prior work (1) in scope by extending analytic methods from the three commonly considered noise models to general single-qubit noise, (2) in performance by deriving an exact, closed-form solution to the local entanglement minimization problem, previously approached via variational heuristics, thereby guaranteeing local optimality without numerical optimization overhead, and (3) in conceptual contribution by showing that the fixed unraveling used in prior work becomes equivalent to our choice of unraveling in the special case of depolarizing, dephasing, and amplitude damping noise acting on a maximally entangled state.