Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.19889

Quantum-to-Classical Computability Transition via Negative Markov Chains

Hugo Lóio, Jacopo De Nardis, Tony Jin

quant-phcond-mat.stat-mechSubmitted Apr 21, 2026• Announced Apr 23, 2026• 2 citations
arXivHTMLPDF

Abstract

We develop a recently introduced representation of quantum dynamics based on sampling negative Markov chain processes. By introducing particles and antiparticles, this formalism maps generic quantum dynamics onto a Markov process defined over an exponentially large configuration space. Within this framework, quantum complexity arises from the proliferation of stochastic particles, which ultimately renders classical simulation and sampling intractable beyond a certain timescale. In the presence of noise, we demonstrate that for any unitary evolution generated by a linear combination of local or pairwise interactions, there exists at least one noise channel that effectively classicalizes the system by suppressing particle growth and making Monte Carlo sampling efficient. As a corollary, we show that for this class of unitaries, 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.

Comments
5 pages, 2 figures, 1 table

Related papers

Classical representation of the dynamics of quantum spin chains

Tony Jin

Since the advent of quantum mechanics, classical probability interpretations have faced significant challenges. A notable issue arises with the emergence of negative probabilities when attempting to define the joint probability of non-commutative observables. In this work, we propose a resolution to this dilemma by introducing an exact representation of the dynamics of quantum spin chains using classical continuous-time Markov chains (CTMCs). These CTMCs effectively model the creation, annihilation, and propagation of pairs of classical particles and antiparticles. The quantum dynamics then emerges by averaging over various realizations of this classical process.

arXiv:2502.10502•SciPost Physics•Sep 9, 2026•2 citations

Interpreting Quantum Learning Models via Stochastic Processes

Johannes Fankhauser, Lukas J. Fiderer, Hans J. Briegel

Quantum machine learning models define probabilistic input--output maps through coherent quantum evolution and measurement. While such models can exhibit computational advantages, their internal functioning and decision making generally resists interpretation in terms of stochastic trajectories through intermediate configurations. In contrast to classical (Markovian) stochastic processes, quantum dynamics generically violates the Chapman--Kolmogorov divisibility condition, preventing a decomposition into probabilistically meaningful intermediate transitions. We develop a probabilistic framework for representing quantum learning models as stochastic processes over configuration spaces where the dynamics are modeled as linear maps on probability distributions. Starting from a fixed POVM, arbitrary quantum channels induce transition kernels on the associated probability representation. For informationally complete POVMs, and in particular SIC-POVMs, these kernels are Markovian but generally quasi-stochastic, with non-classicality appearing as negativity. By contrast, projective spaces admit positive stochastic kernels but generally require non-Markovian dynamics due to the failure of Chapman--Kolmogorov divisibility. This yields a trade-off between negativity and dependence on past configurations, i.e. quantum dynamics can be represented either by Markovian quasi-stochastic maps or by positive stochastic processes with higher Markov order. We discuss how such representations of quantum dynamics can be interpreted as stochastic walks through a memory space in the spirit of Projective Simulation, a model of learning and agency in which decisions arise from random walks over an episodic memory network. We further outline how finite-order stochastic kernels can approximate such quantum deliberation processes and show in what regimes the classical machine learning model is recovered.

quant-pharXiv:2607.17327•Jul 21, 2026•0 citations

Transitions in Computational Complexity of Continuous-Time Local Open Quantum Dynamics

Rahul Trivedi, J. I. Cirac

We analyze the complexity of classically simulating continuous-time dynamics of locally interacting quantum spin systems with a constant rate of entanglement breaking noise. We prove that a polynomial time classical algorithm can be used to sample from the state of the spins when the rate of noise is higher than a threshold determined by the strength of the local interactions. Furthermore, by encoding a 1D fault tolerant quantum computation into the dynamics of spin systems arranged on two or higher dimensional grids, we show that for several noise channels, the problem of weakly simulating the output state of both purely Hamiltonian and purely dissipative dynamics is expected to be hard in the low-noise regime.

arXiv:2110.10638•Physical Review Letters•Dec 22, 2022•13 citations

Simulatability of locally-interacting open quantum spin systems

Rahul Trivedi, J. I. Cirac

We analyze the complexity of classically simulating the dynamics of locally interacting quantum spin systems with a constant rate of entanglement breaking noise. We show that for a system with $n$ spins, a polynomial time classical algorithm can be used to sample within a $O(1/\text{poly}(n))$ total-variation distance of the state of the spins when the rate of noise is sufficiently high. Furthermore, by encoding a 1D fault tolerant quantum computation into the dynamics of open quantum spin systems, we show that for certain physically relevant channels, the problem of sampling from the output state is BQP-complete in the low noise regime. Our results rigorously show the presence of phase transitions in the classical simulatability of the continuous time dynamics of open quantum spin systems.

•Oct 20, 2021•1 citation

Importance sampling scheme for the stochastic simulation of quantum spin dynamics

Stefano De Nicola

The numerical simulation of dynamical phenomena in interacting quantum systems is a notoriously hard problem. Although a number of promising numerical methods exist, they often have limited applicability due to the growth of entanglement or the presence of the so-called sign problem. In this work, we develop an importance sampling scheme for the simulation of quantum spin dynamics, building on a recent approach mapping quantum spin systems to classical stochastic processes. The importance sampling scheme is based on identifying the classical trajectory that yields the largest contribution to a given quantum observable. An exact transformation is then carried out to preferentially sample trajectories that are close to the dominant one. We demonstrate that this approach is capable of reducing the temporal growth of fluctuations in the stochastic quantities, thus extending the range of accessible times and system sizes compared to direct sampling. We discuss advantages and limitations of the proposed approach, outlining directions for further developments.

arXiv:2103.16468•SciPost Physics•Sep 2, 2021•5 citations

Sampling Complexity of Open Quantum Systems

Isobel A. Aloisio, Gregory A. L. White, Charles D. Hill +1 more

Open quantum systems are ubiquitous in the physical sciences, with widespread applications in the areas of chemistry, condensed-matter physics, material science, optics, and many more.Not surprisingly, there is significant interest in their efficient simulation.However, direct classical simulation quickly becomes intractable with coupling to an environment with an effective dimension that grows exponentially.This raises the question: Can quantum computers help model these complex dynamics?A first step in answering this question requires an understanding of the computational complexity of this task.Here, we map the temporal complexity of a process to the spatial complexity of a many-body state using a computational model known as the process-tensor framework.With this, we are able to explore the simulation complexity of an open quantum system as a dynamic sampling problem: a system coupled to an environment can be probed at successive points in time-accessing multitime correlations.The complexity of multitime sampling, which is an important and interesting problem in its own right, contains the complexity of master equations and stochastic maps as a special case.Our results show how the complexity of the underlying quantum stochastic process corresponds to the complexity of the associated family of master equations for the dynamics.We present both analytical and numerical examples where the multitime sampling of an open quantum system is as complex as sampling from a many-body state that is classically hard.This also implies that the corresponding family of master equations is classically hard.Our results pave the way for studying open quantum systems from a complexity-theoretic perspective, highlighting the role quantum computers will play in our understanding of quantum dynamics.

arXiv:2209.10870•PRX Quantum•Apr 19, 2023•17 citations
We develop a recently introduced representation of quantum dynamics based on sampling negative Markov chain processes. By introducing particles and antiparticles, this formalism maps generic quantum dynamics onto a Markov process defined over an exponentially large configuration space. Within this framework, quantum complexity arises from the proliferation of stochastic particles, which ultimately renders classical simulation and sampling intractable beyond a certain timescale. In the presence of noise, we demonstrate that for any unitary evolution generated by a linear combination of local or pairwise interactions, there exists at least one noise channel that effectively classicalizes the system by suppressing particle growth and making Monte Carlo sampling efficient. As a corollary, we show that for this class of unitaries, 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.
Since the advent of quantum mechanics, classical probability interpretations have faced significant challenges. A notable issue arises with the emergence of negative probabilities when attempting to define the joint probability of non-commutative observables. In this work, we propose a resolution to this dilemma by introducing an exact representation of the dynamics of quantum spin chains using classical continuous-time Markov chains (CTMCs). These CTMCs effectively model the creation, annihilation, and propagation of pairs of classical particles and antiparticles. The quantum dynamics then emerges by averaging over various realizations of this classical process.
Quantum machine learning models define probabilistic input--output maps through coherent quantum evolution and measurement. While such models can exhibit computational advantages, their internal functioning and decision making generally resists interpretation in terms of stochastic trajectories through intermediate configurations. In contrast to classical (Markovian) stochastic processes, quantum dynamics generically violates the Chapman--Kolmogorov divisibility condition, preventing a decomposition into probabilistically meaningful intermediate transitions. We develop a probabilistic framework for representing quantum learning models as stochastic processes over configuration spaces where the dynamics are modeled as linear maps on probability distributions. Starting from a fixed POVM, arbitrary quantum channels induce transition kernels on the associated probability representation. For informationally complete POVMs, and in particular SIC-POVMs, these kernels are Markovian but generally quasi-stochastic, with non-classicality appearing as negativity. By contrast, projective spaces admit positive stochastic kernels but generally require non-Markovian dynamics due to the failure of Chapman--Kolmogorov divisibility. This yields a trade-off between negativity and dependence on past configurations, i.e. quantum dynamics can be represented either by Markovian quasi-stochastic maps or by positive stochastic processes with higher Markov order. We discuss how such representations of quantum dynamics can be interpreted as stochastic walks through a memory space in the spirit of Projective Simulation, a model of learning and agency in which decisions arise from random walks over an episodic memory network. We further outline how finite-order stochastic kernels can approximate such quantum deliberation processes and show in what regimes the classical machine learning model is recovered.
We analyze the complexity of classically simulating continuous-time dynamics of locally interacting quantum spin systems with a constant rate of entanglement breaking noise. We prove that a polynomial time classical algorithm can be used to sample from the state of the spins when the rate of noise is higher than a threshold determined by the strength of the local interactions. Furthermore, by encoding a 1D fault tolerant quantum computation into the dynamics of spin systems arranged on two or higher dimensional grids, we show that for several noise channels, the problem of weakly simulating the output state of both purely Hamiltonian and purely dissipative dynamics is expected to be hard in the low-noise regime.
We analyze the complexity of classically simulating the dynamics of locally interacting quantum spin systems with a constant rate of entanglement breaking noise. We show that for a system with nnn spins, a polynomial time classical algorithm can be used to sample within a O(1/poly(n))O(1/\text{poly}(n))O(1/poly(n)) total-variation distance of the state of the spins when the rate of noise is sufficiently high. Furthermore, by encoding a 1D fault tolerant quantum computation into the dynamics of open quantum spin systems, we show that for certain physically relevant channels, the problem of sampling from the output state is BQP-complete in the low noise regime. Our results rigorously show the presence of phase transitions in the classical simulatability of the continuous time dynamics of open quantum spin systems.
The numerical simulation of dynamical phenomena in interacting quantum systems is a notoriously hard problem. Although a number of promising numerical methods exist, they often have limited applicability due to the growth of entanglement or the presence of the so-called sign problem. In this work, we develop an importance sampling scheme for the simulation of quantum spin dynamics, building on a recent approach mapping quantum spin systems to classical stochastic processes. The importance sampling scheme is based on identifying the classical trajectory that yields the largest contribution to a given quantum observable. An exact transformation is then carried out to preferentially sample trajectories that are close to the dominant one. We demonstrate that this approach is capable of reducing the temporal growth of fluctuations in the stochastic quantities, thus extending the range of accessible times and system sizes compared to direct sampling. We discuss advantages and limitations of the proposed approach, outlining directions for further developments.
Open quantum systems are ubiquitous in the physical sciences, with widespread applications in the areas of chemistry, condensed-matter physics, material science, optics, and many more.Not surprisingly, there is significant interest in their efficient simulation.However, direct classical simulation quickly becomes intractable with coupling to an environment with an effective dimension that grows exponentially.This raises the question: Can quantum computers help model these complex dynamics?A first step in answering this question requires an understanding of the computational complexity of this task.Here, we map the temporal complexity of a process to the spatial complexity of a many-body state using a computational model known as the process-tensor framework.With this, we are able to explore the simulation complexity of an open quantum system as a dynamic sampling problem: a system coupled to an environment can be probed at successive points in time-accessing multitime correlations.The complexity of multitime sampling, which is an important and interesting problem in its own right, contains the complexity of master equations and stochastic maps as a special case.Our results show how the complexity of the underlying quantum stochastic process corresponds to the complexity of the associated family of master equations for the dynamics.We present both analytical and numerical examples where the multitime sampling of an open quantum system is as complex as sampling from a many-body state that is classically hard.This also implies that the corresponding family of master equations is classically hard.Our results pave the way for studying open quantum systems from a complexity-theoretic perspective, highlighting the role quantum computers will play in our understanding of quantum dynamics.