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

Deciding whether a Quantum Channel is Markovian is NP-hard

Toby S. Cubitt, Jens Eisert, Michael M. Wolf

Published Aug 17, 2009• 2 citations
OpenAlex

Abstract

We show that deciding whether a given quantum channel can be generated by a Markovian master equation is an NP-hard problem. As a consequence, this result suggests that extracting the underlyin g physics governing the evolution of a quantum system, as described by its dynamical equations, may be a hard task regardless of how much data is gathered via measurements of the system. On the other hand, if the system dimension is fixed, the problem of deciding whether a process is consistent with being Markovian can be efficiently decided, and we give an explicit algorithm in this case. This work also leads to a complexity-theoretic solution to a long-standing open problem in probability theory.

Related papers

Assessing Non-Markovian Quantum Dynamics

Michael M. Wolf, Jens Eisert, Toby S. Cubitt +1 more

We investigate what a snapshot of a quantum evolution--a quantum channel reflecting open system dynamics--reveals about the underlying continuous time evolution. Remarkably, from such a snapshot, and without imposing additional assumptions, it can be decided whether or not a channel is consistent with a time (in)dependent Markovian evolution, for which we provide computable necessary and sufficient criteria. Based on these, a computable measure of "Markovianity" is introduced. We discuss how the consistency with Markovian dynamics can be checked in quantum process tomography. The results also clarify the geometry of the set of quantum channels with respect to being solutions of time (in)dependent master equations.

arXiv:0711.3172•Physical Review Letters•Oct 6, 2008•604 citations

Extracting Dynamical Equations from Experimental Data is NP Hard

Toby S. Cubitt, Jens Eisert, Michael M. Wolf

The behavior of any physical system is governed by its underlying dynamical equations. Much of physics is concerned with discovering these dynamical equations and understanding their consequences. In this Letter, we show that, remarkably, identifying the underlying dynamical equation from any amount of experimental data, however precise, is a provably computationally hard problem (it is NP hard), both for classical and quantum mechanical systems. As a by-product of this work, we give complexity-theoretic answers to both the quantum and classical embedding problems, two long-standing open problems in mathematics (the classical problem, in particular, dating back over 70 years).

arXiv:1005.0005•Physical Review Letters•Mar 22, 2012•53 citations

Signs of the rates in the Lindblad master equations can always be arbitrarily determined

Le Hu, Andrew N. Jordan

Determining the Markovianity and non-Markovianity of a quantum process is a critical problem in the theory of open quantum systems, as their behaviors differ significantly in terms of complexity. It is well recognized that a quantum process is Markovian if and only if the quantum master equation can be written in the standard Lindblad form with all rates nonnegative for all time. However, here we present a striking result that \textit{any} finite-dimensional open quantum system dynamics can be described by a quantum master equation in the Lindblad form with all rates nonnegative for all time. In fact, it can be shown that one can arbitrarily decide the sign of the rates in any case at any time interval. Note that here we take an unconventional approach where the quantum master equation we construct will in general be state-dependent, which means that the Hamiltonian, jump operators and rates will all depend on the current state of the density matrix $ρ(t)$. Our findings raise serious questions on the current criterion in determining Markovianity and non-Markovianity in open quantum system dynamics.

arXiv:2310.17881•Oct 27, 2023•2 citations

Computational Complexity of Optimally Encoding a Qubit

Idris Delsol, Omar Fawzi, Akshay Ramachandran

We consider the problem of optimally encoding a qubit for a given noise channel. We show that deciding if a quantum channel can perfectly preserve a qubit is NP-hard. Equivalently, determining if the quantum independence number of a quantum graph is ≥ 2 is NP-hard. In addition, we show that computing the optimal fidelity can be expressed as a simple semidefinite program with an isometry constraint, or equivalently a rank constraint.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

Universal simulation of Markovian open quantum systems

Ryan Sweke, Ilya Sinayskiy, Denis Bernard +1 more

We consider the problem of constructing a ``universal set'' of Markovian processes, such that any Markovian open quantum system, described by a one-parameter semigroup of quantum channels, can be simulated through sequential simulations of processes from the universal set. In particular, for quantum systems of dimension $d$, we explicitly construct a universal set of semigroup generators, parametrized by ${d}^{2}\ensuremath{-}3$ continuous parameters, and prove that a necessary and sufficient condition for the dynamical simulation of a $d$-dimensional Markovian quantum system is the ability to implement (a) quantum channels from the semigroups generated by elements of the universal set of generators, and (b) unitary operations on the system. Furthermore, we provide an explicit algorithm for simulating the dynamics of a Markovian open quantum system using this universal set of generators, and show that it is efficient, with respect to this universal set, when the number of distinct Lindblad operators (representing physical dissipation processes) scales polynomially with respect to the number of subsystems.

arXiv:1503.05028•Physical Review A•Jun 8, 2015•68 citations

Non-Markovian master equations from piecewise dynamics

Bassano Vacchini

We construct a large class of completely positive and trace-preserving non-Markovian dynamical maps for an open quantum system. These maps arise from a piecewise dynamics for statistical operators characterized by a continuous time evolution interrupted by jumps, randomly distributed in time and described by a quantum channel. The state of the open system is shown to obey a closed evolution equation, given by a master equation with a memory kernel and an inhomogeneous term. The non-Markovianity of the obtained dynamics is explicitly assessed studying the behavior of the distinguishability of two different initial system's states with elapsing time.

arXiv:1301.2902•Physical Review A•Mar 8, 2013•63 citations
We show that deciding whether a given quantum channel can be generated by a Markovian master equation is an NP-hard problem. As a consequence, this result suggests that extracting the underlyin g physics governing the evolution of a quantum system, as described by its dynamical equations, may be a hard task regardless of how much data is gathered via measurements of the system. On the other hand, if the system dimension is fixed, the problem of deciding whether a process is consistent with being Markovian can be efficiently decided, and we give an explicit algorithm in this case. This work also leads to a complexity-theoretic solution to a long-standing open problem in probability theory.
We investigate what a snapshot of a quantum evolution--a quantum channel reflecting open system dynamics--reveals about the underlying continuous time evolution. Remarkably, from such a snapshot, and without imposing additional assumptions, it can be decided whether or not a channel is consistent with a time (in)dependent Markovian evolution, for which we provide computable necessary and sufficient criteria. Based on these, a computable measure of "Markovianity" is introduced. We discuss how the consistency with Markovian dynamics can be checked in quantum process tomography. The results also clarify the geometry of the set of quantum channels with respect to being solutions of time (in)dependent master equations.
The behavior of any physical system is governed by its underlying dynamical equations. Much of physics is concerned with discovering these dynamical equations and understanding their consequences. In this Letter, we show that, remarkably, identifying the underlying dynamical equation from any amount of experimental data, however precise, is a provably computationally hard problem (it is NP hard), both for classical and quantum mechanical systems. As a by-product of this work, we give complexity-theoretic answers to both the quantum and classical embedding problems, two long-standing open problems in mathematics (the classical problem, in particular, dating back over 70 years).
Determining the Markovianity and non-Markovianity of a quantum process is a critical problem in the theory of open quantum systems, as their behaviors differ significantly in terms of complexity. It is well recognized that a quantum process is Markovian if and only if the quantum master equation can be written in the standard Lindblad form with all rates nonnegative for all time. However, here we present a striking result that \textit{any} finite-dimensional open quantum system dynamics can be described by a quantum master equation in the Lindblad form with all rates nonnegative for all time. In fact, it can be shown that one can arbitrarily decide the sign of the rates in any case at any time interval. Note that here we take an unconventional approach where the quantum master equation we construct will in general be state-dependent, which means that the Hamiltonian, jump operators and rates will all depend on the current state of the density matrix ρ(t)ρ(t)ρ(t). Our findings raise serious questions on the current criterion in determining Markovianity and non-Markovianity in open quantum system dynamics.
We consider the problem of constructing a ``universal set'' of Markovian processes, such that any Markovian open quantum system, described by a one-parameter semigroup of quantum channels, can be simulated through sequential simulations of processes from the universal set. In particular, for quantum systems of dimension ddd, we explicitly construct a universal set of semigroup generators, parametrized by ${d}^{2}\ensuremath{-}3$ continuous parameters, and prove that a necessary and sufficient condition for the dynamical simulation of a ddd-dimensional Markovian quantum system is the ability to implement (a) quantum channels from the semigroups generated by elements of the universal set of generators, and (b) unitary operations on the system. Furthermore, we provide an explicit algorithm for simulating the dynamics of a Markovian open quantum system using this universal set of generators, and show that it is efficient, with respect to this universal set, when the number of distinct Lindblad operators (representing physical dissipation processes) scales polynomially with respect to the number of subsystems.
We construct a large class of completely positive and trace-preserving non-Markovian dynamical maps for an open quantum system. These maps arise from a piecewise dynamics for statistical operators characterized by a continuous time evolution interrupted by jumps, randomly distributed in time and described by a quantum channel. The state of the open system is shown to obey a closed evolution equation, given by a master equation with a memory kernel and an inhomogeneous term. The non-Markovianity of the obtained dynamics is explicitly assessed studying the behavior of the distinguishability of two different initial system's states with elapsing time.