Completely positive, trace preserving (CPT) maps and Lindblad master equations are both widely used to describe the dynamics of open quantum systems. The connection between these two descriptions is a classic topic in mathematical physics. One direction was solved by the now famous result due to Lindblad, Kossakowski Gorini and Sudarshan, who gave a complete characterisation of the master equations that generate completely positive semi-groups. However, the other direction has remained open: given a CPT map, is there a Lindblad master equation that generates it (and if so, can we find it's form)? This is sometimes known as the Markovianity problem. Physically, it is asking how one can deduce underlying physical processes from experimental observations. We give a complexity theoretic answer to this problem: it is NP-hard. We also give an explicit algorithm that reduces the problem to integer semi-definite programming, a well-known NP problem. Together, these results imply that resolving the question of which CPT maps can be generated by master equations is tantamount to solving P=NP: any efficiently computable criterion for Markovianity would imply P=NP; whereas a proof that P=NP would imply that our algorithm already gives an efficiently computable criterion. Thus, unless P does equal NP, there cannot exist any simple criterion for determining when a CPT map has a master equation description. However, we also show that if the system dimension is fixed (relevant for current quantum process tomography experiments), then our algorithm scales efficiently in the required precision, allowing an underlying Lindblad master equation to be determined efficiently from even a single snapshot in this case. Our work also leads to similar complexity-theoretic answers to a related long-standing open problem in probability theory.
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.
Markovian open quantum systems are well modeled by the Lindblad Master Equation (ME)
dtdρt=Lρt, where
L is a linear (super-)operator and
ρt is the system state, a positive matrix. When designing or characterizing a quantum system, one is usually interested in the steady state
ρ∞ (such that
Lρ∞=0), the first few excited states, and trajectories
t↦ρt. In finite dimension,
ρt is an
n×n matrix,
L thus typically costs
n4 to store explicitly as a dense matrix, and
O(n6) to diagonalize or invert exactly, making standard linear algebraic techniques expensive for large systems. However,
L usually costs only
O(n3) to apply. This makes iterative methods appealing, but they do not work without a good preconditioner. In this article, our main observation is that a part of the Lindblad equation, corresponding to the so-called no-jump evolution
S, can be inverted efficiently. Using this inverse map, we introduce an auxiliary completely positive trace-preserving (CPTP) map
Φ whose fixed point is directly related to
ρ∞, all the other eigenvalues having smaller magnitude. The map
Φ is thus well suited to iterative methods, and
ρ∞ can be found in a few Arnoldi iterations. Using the same inverse map
S−1 as preconditioner, we compute the low-lying spectrum efficiently via shift-invert Arnoldi, and, as a proof of concept, build an implicit time integrator that is competitive on stiff systems in the low-precision regime. For the steady-state and low excited states problems, our methods scale like
O(n3) per iteration and offer state-of-the-art performance on CPU and GPU.
Abstract The Lindblad equation embodies a fundamental paradigm of the quantum theory of open systems, and the Gorini–Kossakowski–Sudarshan–Lindblad generation theorem says precisely which superoperators can appear on its right-hand side. These are the generators of completely positive (CP) trace-preserving (or nonincreasing) semigroups. We prove a generalization, with time-dependent generator, as an application of an investigation of the geometry of the class of CP maps. The treatment of the finite-dimensional setting is based on a basis-free Choi–Jamiołkowski type isomorphism. The infinite-dimensional case is bootstrapped from the finite-dimensional theory via a sequence of finite-dimensional approximations. Kraus decomposition is established along the way, in the guise of an extremal decomposition of the closed convex cone of CP maps. No appeal is made to results from the representation theory of operator algebras.
A mathematical description of the reduced dynamics of an open quantum system can often be given in terms of a completely positive and trace-preserving map, also known as a quantum channel. In a seminal work by Wolf [], it was shown that deciding whether a given quantum channel was generated from an underlying effective Markovian dynamics, with time-independent generator of Lindblad form, is generally an NP-hard problem. The difficulty is related to the fact that one has to search through all possible branches of the operator logarithm of the map in order to identify if any of the resulting effective generators is of Lindblad form. In this work we show that in cases where one has access to the full reduced dynamics at all previous times (the dynamical map) one can significantly facilitate the search for an effective generator by making use of Floquet theory. By performing a spectral unwinding such that the effective micromotion is minimized, the effective Floquet generator is often an excellent candidate for an effective generator of Lindblad form. This significantly reduces the complexity of the search for an effective Lindbladian in many (though not all) cases. Our results are relevant for engineering Floquet Lindbladians in complex many-body systems.
While quantum master equations (QMEs) are the primary workhorse in quantum information science, quantum optics, spectroscopy, and quantum thermodynamics, bringing an arbitrary
N-level QME into Lindbladian form and verifying complete positivity of the associated quantum dynamical map remain open challenges for
N≥3. We explore and implement two independent methods to accomplish these tasks, which enable one to directly compute the Kossakowski matrix of an arbitrary Markovian QME from its Liouvillian. In the first method, due to Hall, Cresser, Li, and Andersson, the Kossakowski matrix elements are obtained by evaluating the action of the Liouvillian on the orthonormal SU(
N) basis matrices and then computing a sum of matrix-product traces. The second method, developed in this work, is based on the real
N-level coherence vector and relies on the Moore-Penrose pseudo-inverse of a rectangular matrix composed of the structure constants of SU
(N). We show that both methods give identical results, and apply them to establish the complete positivity of the partial secular Bloch-Redfield QME for the
Λ and V-systems driven by incoherent light. We find that the eigenvalues of the Kossakowski matrix of these seemingly different three-level systems are identical, implying close similarities of their dissipative dynamics. By facilitating the expression of multilevel Markovian QMEs in Lindblad form, our results enable testing the QMEs for complete positivity without solving them, as well as restoring complete positivity by keeping only non-negative eigenvalues of the Kossakowski matrix.
We derive continuous-time quantum dynamical semigroups from the local geometric structure of discrete completely positive trace-preserving (CPTP) maps on finite-dimensional Hilbert spaces. Rather than assuming a continuous time parameter and differentiability from the outset, we analyze the convex structure of the CPTP set in a neighborhood of the identity channel, viewed as the neutral element of composition. By characterizing the tangent cone at this boundary point under the trace-preserving constraint, we show that admissible first-order perturbations coincide with generators of Gorini–Kossakowski–Sudarshan–Lindblad (GKSL) form. In this sense, the GKSL structure emerges from the intrinsic convex geometry of the CPTP set. Furthermore, we establish a quantitative scaling result: under an explicit operator-norm error estimate, iterated discrete channels converge uniformly on finite intervals to the semigroup generated by the associated GKSL operator. This provides a precise mathematical link between discrete completely positive dynamics and continuous-time Lindblad evolution, clarifying their structural relationship within the foundations of open quantum dynamics.