The complexity of relating quantum channels to master equations
From MaRDI portal
Publication:766099
Linear programming (90C05) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum measurement theory, state operations, state preparations (81P15) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum state estimation, approximate cloning (81P50) Open systems, reduced dynamics, master equations, decoherence (81S22) Channel models (including quantum) in information and communication theory (94A40) Complexity of computation (including implicit computational complexity) (03D15) Monotone and positive operators on ordered Banach spaces or other ordered topological vector spaces (47H07)
Abstract: 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.
Recommendations
- Complexity and Capacity Bounds for Quantum Channels
- Asymptotics of quantum channels
- Quantumness of channels
- Note on transmitted complexity for quantum dynamical systems
- Channel divergences and complexity in algebraic QFT
- A General Theory of Comparison of Quantum Channels (and Beyond)
- Information theoretic representations of qubit channels
- Parametrizing quantum states and channels
- Capacities of quantum channels and how to find them
- Quantum Markov chains, sufficiency of quantum channels, and Rényi information measures
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 4155605 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- scientific article; zbMATH DE number 3533576 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 635657 (Why is no real title available?)
- Assessing non-Markovian quantum dynamics.
- Characterizations of embeddable \(3 \times 3\) stochastic matrices with a negative eigenvalue
- Classical deterministic complexity of Edmonds' Problem and quantum entanglement
- Completely positive linear maps on complex matrices
- Computational complexity of the quantum separability problem
- Continuity properties of fractional powers, of the logarithm, and of holomorphic semigroups
- Dividing quantum channels
- Embeddable Markov matrices
- Error and Perturbation Bounds for Subspaces Associated with Certain Eigenvalue Problems
- Infinitely Divisible Markov Mappings in Quantum Probability Theory
- Integer optimization on convex semialgebraic sets
- Linear transformations which preserve trace and positive semidefiniteness of operators
- Markov Chains
- Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
- On Uniqueness of the Logarithm for Markov Semi-Groups
- On the generators of quantum dynamical semigroups
- On the imbedding problem for stochastic and doubly stochastic matrices
- Semidefinite Programming
- Some Results on the Imbedding Problem for Finite Markov Chains
- Statistical Structure of Quantum Theory
- The Logarithm Function for Finite-State Markov Semi-Groups
- The complexity of satisfiability problems
- The imbedding problem for finite Markov chains
Cited in
(19)- Necessary criteria for Markovian divisibility of linear maps
- Select topics in open quantum systems
- Channel divergences and complexity in algebraic QFT
- Log-convex set of Lindblad semigroups acting on N-level system
- Quantum and classical dynamical semigroups of superchannels and semicausal channels
- Asymptotic Floquet states of open quantum systems: the role of interaction
- Irreversible quantum evolution with quadratic generator: review
- The complexity of divisibility
- Accessible Maps in a Group of Classical or Quantum Channels
- Machine learning approach to the Floquet-Lindbladian problem
- Roots of completely positive maps
- Dynamical maps beyond Markovian regime
- Finding the Kraus decomposition from a master equation and vice versa
- Model dynamics for quantum computing
- Embeddability of real and positive operators
- Almost all quantum channels are diagonalizable
- Dissipative and non-dissipative single-qubit channels: dynamics and geometry
- Machine learning versus semidefinite programming approach to a particular problem of the theory of open quantum systems
- Chaos amplification process can be described by the GKSL master equation
This page was built for publication: The complexity of relating quantum channels to master equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q766099)
