Noise Can Simplify Quantum Systems, Enabling Efficient Classical Simulations

A new pathway to understand the boundary between quantum and classical computational power has been identified by Hugo Lóio of PSL Research University and colleagues. The work uses negative Markov chains to represent quantum dynamics, revealing that complexity arises from the uncontrolled growth of stochastic particles within the system. Specifically, they prove that certain noise channels can effectively ‘classicalise’ quantum systems, such as open quantum spin chains, by limiting particle proliferation and enabling efficient classical simulation once a critical noise threshold is reached. This finding offers insight into controlling quantum dynamics and potentially using noise to enable classical computation of otherwise intractable quantum processes. Noise-induced classicality in open quantum spin chains Carlo sampling efficiency has been demonstrated. Consequently, the dynamics of an open quantum spin chain subject to depolarizing noise undergoes an exact transition to classical simulability once the noise strength exceeds a critical threshold, efficiently determined for any model. The ability to access systems and dynamical regimes beyond the reach of classical computers is a major promise of quantum simulation. Current quantum platforms operate in the noisy intermediate-scale quantum (NISQ) regime, where the number of qubits is limited and noise remains significant. Therefore, understanding when the simulation of a given quantum system remains genuinely hard for classical computers, and when it can instead be efficiently reproduced classically, is vital. This question is directly relevant to experimental claims of quantum advantage, many of which have been challenged by increasingly powerful classical simulation methods. In many such cases, classical algorithms explicitly exploit the presence of noise, driving the output distribution toward a trivial one or effectively reducing the accessible Hilbert space, thereby rendering classical simulation efficient. Several works in recent years have shown that efficient classical sampling is possible in generic noisy quantum systems whenever the output distribution satisfies anticoncentration. For broad classes of circuits above a constant noise threshold, a critical noise rate exists beyond which efficient classical simulation becomes possible through methods based on percolation arguments. A new noise-induced quantum-to-classical computability transition, based on the feasibility of Monte Carlo sampling and an associated sign-problem transition, has been uncovered. Generally, quantum dynamics cannot be formulated as a Markov chain because the effective transition rates are not always positive. This difficulty can be overcome by introducing two species of stochastic particles and antiparticles that encode the sign structure. In this representation, quantum complexity reappears in the exponential growth of the number of particles with time, making the computation infeasible beyond a certain timescale. The main result is that a critical amount of noise always exists above which all effective transition rates become positive, thereby restoring a genuine stochastic description and making Monte Carlo sampling efficient. This transition appears to be distinct from those previously studied and is not directly tied to standard complexity quantifiers such as entanglement. Instead, it is governed solely by a transition between a simulable regime with only positive weights and one with negative weights, similarly to previous work. Remarkably, a gauge freedom in the Markov chain description of quantum dynamics was found, playing a role analogous to the basis rotations used to tame the sign problem in equilibrium quantum Monte Carlo. The formalism of negative Markov chains (NMCs) was first introduced and an exact mapping of quantum dynamics onto a classical stochastic process in an exponentially large configuration space was established. This classical representation possesses an intrinsic gauge freedom, which can be exploited to enforce complete cancellation of particle proliferation once the noise exceeds a critical threshold. This approach was illustrated with an application to the noisy transverse-field Ising model (TFIM), reviewing the NMC formalism for quantum spin chains, as introduced in a prior publication. Consider a quantum spin chain in d dimensions, of length L and total site number N = Ld, evolving under the Lindbladian L: dtρ = L(ρ) := −i[H, ρ] + Σk A†kρAk − 1/2 Σk AkA†kρ. The negative Markov chain formalism describes a process that takes place on all possible 6N configurations, each weighted by an occupation number that can be negative. The Hamiltonian determines the transition rates M+ and M− between different configurations. A transition with M+CC′ decreases the occupation number of the source configuration nC′ by 1 while increasing the target occupation number nC. Conversely, the transition M−CC′ does the reverse, i.e. it increases nC′ by 1 and decreases nC by 1. Computational complexity arises from the need to track the occupation number of every copy. The classical continuous-time Markov chain (CTMC) case is recovered when M− = 0, allowing simulation via classical Monte Carlo. The goal is to describe this time evolution in terms of a Markov chain on a classical configuration space C made of the 6N elements C = ({+, −} × {x, y, z})N, where {+, −} denotes the orientation of the spin along a given axis. An element C ∈ C is a classical configuration of the spin chain, associated with the Hilbert space vector |C⟩. Note that {|C⟩}C∈C is an overcomplete basis. Let PC:= |C⟩⟨C| and pC(t) be the probability of finding the system in the classical configuration C at time t: pC(t) := 1/3N try(ρtPC). Since pC ≥ 0 and ΣC∈C pC = 1, pC is a well-defined probability distribution. Its time evolution is inherited from the equation: dtpC = 1/3N try(ρtL∗(PC)), with L∗ the dual of L. Since L∗(PC) is Hermitian (but not necessarily traceless), it can in general be decomposed on the basis of Pauli strings (including the identity). These Pauli strings can in turn be decomposed on the projectors PC, resulting in L∗(PC) = ΣC′ MCC′PC′. This decomposition is not unique due to the identity operator in a Pauli string, creating an inherent ambiguity and crucial gauge freedom that is explored later. Projecting onto ρ one obtains dtpC = ΣC′=C MCC′pC′ − MC′CpC, where the relation MCC = − ΣC′=C MC′C is used, following from probability conservation. The previous equation is nearly that of a continuous-time Markov chain (CTMC). The coefficients MCC′ are real due to the Hermiticity of L∗(PC), but they do not satisfy the required positivity. This places one in the realm of CTMCs with negative rates, a scenario recently examined. First, entirely positive transition rates for C = C′ are defined as M±CC′ := ±θ(±MCC′)MCC′, where θ is the Heaviside function. Then, the configuration space is doubled, and particle states are denoted with a • and antiparticle states with a ◦: C → C × {•, ◦}. The probability pC of the original process is decomposed as the difference pC = p•C − p◦C. After a few elementary manipulations, the equation can be obtained from dtp•/◦C = ΣC′=C M+CC′p•/◦C′ − M+C′Cp•/◦C + M−CC′p◦/•C′ − M−C′Cp•/◦C + VCp•/◦C, with VC:= 2 ΣC′=C M−C′C. This equation now defines a well-defined Markov process with entirely positive rates given by M+ and M− and creation or branching rates given by VC. Due to the latter, the state of the system for a given realization of the process is now described by a collection of 2 × 6N numbers n•/◦C indicating the occupation of configuration C in terms of particles and antiparticles. Whenever a particle and an antiparticle meet, they annihilate each other. Hence, a single number nC:= n•C − n◦C ∈ Z suffices to keep track of the state of the system. The configuration space is then ZC, meaning there are Ω replicas of the original spin chain, where Ω = ΣC∈C |nC|. A state η ∈ ZC is the collection of numbers {nC}C∈C. Let sC:= sign(nC). The update rules can be read from the equation to be: η → η ± sC′(−δC′ + δC) with probability |nC′|M±CC′dt, and are illustrated schematically in Figure 1. The M+ transition has the usual interpretation for a CTMC, where a state with configuration C′ goes to C, while M− can be interpreted as a transition from C′ to C carrying a negative sign. Starting with Ω(t = 0) = 1, the original probabilities are extracted by averaging over different realizations of the process, i.e. pC = E[nC]0. Note that while pC is constrained to be positive, for a given realization, nC can be ‘off-shell’, i.e. it may take any integer value, positive or negative. The rules preserve the total relative number of particles ΣC nC. A key advantage of obtaining a CTMC description of the quantum dynamics is that it enables the simulation of individual trajectories, paving the way for classical Monte Carlo methods. In a given realization, the simulation proceeds by updating the occupation numbers η according to the transition rules. Let Ωocc = ΣC(1 − δnC,0) denote the number of occupied configurations; the size of η is therefore Ωocc and is time-dependent. By organizing η in a tree structure, the cost per fixed time step scales as O(ΩlogΩocc logN), where logΩocc is the cost of searching for an element in η, Ω is the number of times this operation must be performed, and logN is the computational complexity required to compute a transition for a single particle. A simple heuristic picture for the growth of Ω(t) is as follows. At early times, when the number of occupied configurations is low, it is expected that the growth is controlled by the negative weights VC ∼ N and thus to be exponential in time and system size, Ω(t) ∼ eμtN. Assuming that the configurations are populated uniformly, a simple estimate for μ is: μ:= 2d/6k ΣC=C′ M(k)−CC′ , where d is the dimension and M(k)− is the local negative transition matrix acting on k sites. At late times, the growth is damped by the fact that particles and antiparticles start to annihilate. If saturation occurs, and again assuming uniform population, then the saturation value is (see Appendix E for details): Ωsat:= −2/6N log(1 − ΣC=C′ M(k)−CC′ / ΣC=C′ M(k)CC′). While the late-time behaviour is more favourable, the early exponential growth in t and N prevents the simulation of large system sizes. Nevertheless, for open quantum systems, the proliferation of stochastic particles can be suppressed by the presence of noise, allowing a reduction in computational complexity. Specifically, there exists at least one noise channel that classicalizes the system and enables efficient Monte Carlo sampling. This formalism maps generic quantum dynamics onto a Markov process defined over an exponentially large configuration space. Quantum complexity arises from the growth of particle numbers with time, rendering classical simulation intractable beyond a certain timescale. As a corollary, the dynamics of an open quantum spin chain subject to depolarizing noise undergoes an exact transition to classical simulability once the noise strength exceeds a critical threshold, which can be efficiently determined for any model. A representation of quantum dynamics is developed based on sampling negative Markov chain processes, introducing particles and antiparticles to encode the sign structure. The system is described by a classical configuration space comprising 6 N elements, where N is the total number of sites. Each configuration is associated with a probability, and its time evolution is determined by transition rates between configurations. Depolarizing noise eliminates particle proliferation in quantum spin chains enabling classical Particle proliferation, a key obstacle to classical simulation of quantum spin chains, has been reduced to zero in open quantum systems subjected to depolarizing noise exceeding a critical threshold. Previously, the number of stochastic particles, representing quantum complexity, grew exponentially with system size and time, rendering Monte Carlo sampling intractable. This transition to classical simulability occurs when noise strength surpasses a model-dependent critical value, efficiently determined using a novel algorithm applicable to any quantum spin chain.

The team’s approach leverages a gauge freedom within the negative Markov chain formalism, effectively cancelling negative weights and restoring a genuine stochastic description.

The team confirmed the elimination of particle proliferation extends to larger systems, demonstrating a stable particle count even with 16 qubits and beyond. Analysis of the two-dimensional transverse field Ising model, a benchmark for quantum simulation, revealed that particle growth rates decreased to zero when noise strength exceeded a specific value, as predicted by their theoretical framework. Further simulations showcased that, using this noise, the team accurately reproduced two-point correlation functions, measuring entanglement, across the system, comparing results from classical Monte Carlo methods with exact diagonalisation techniques for up to 16 qubits. Depolarizing noise simplifies calculations in limited quantum spin chain models The ability to accurately model quantum systems is hampered by the exponential growth of computational demands as complexity increases.

This research offers a route around that limitation, demonstrating that carefully applied noise can simplify calculations for certain quantum spin chains. However, the current findings rely on a specific type of noise, depolarizing, and crucially, on interactions limited to nearest neighbours or pairs of sites. Acknowledging that these results currently apply to a restricted set of conditions. The research demonstrated that introducing depolarizing noise to quantum spin chains can render them classically simulable. This means that, for these systems, calculations which would normally require exponentially increasing computational power become manageable. Specifically, the proliferation of stochastic particles, representing quantum complexity, ceased when noise strength exceeded a critical threshold. The authors confirmed this effect in systems of up to 16 qubits and suggest their algorithm can efficiently determine this threshold for any quantum spin chain model. 👉 More information🗞 Quantum-to-Classical Computability Transition via Negative Markov Chains🧠 ArXiv: https://arxiv.org/abs/2604.19889 Tags: