The complexity of relating quantum channels to master equations

DOI10.1007/S00220-011-1402-YzbMATH Open1243.81100arXiv0908.2128OpenAlexW2130724093WikidataQ57637227 ScholiaQ57637227MaRDI QIDQ766099FDOQ766099

Authors: Toby Cubitt, Jens Eisert, Michael M. Wolf 

Publication date: 23 March 2012

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0908.2128

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

zbMATH Keywords

NP-hardquantum tomographysemi-definite programmingMarkovianity problem

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
• Markov Chains
• Semidefinite Programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Completely positive linear maps on complex matrices
• On the generators of quantum dynamical semigroups
• The complexity of satisfiability problems
• Title not available (Why is that?)
• Statistical Structure of Quantum Theory
• The imbedding problem for finite Markov chains
• Dividing quantum channels
• Assessing non-Markovian quantum dynamics.
• On the imbedding problem for stochastic and doubly stochastic matrices
• Characterizations of embeddable \(3 \times 3\) stochastic matrices with a negative eigenvalue
• The Logarithm Function for Finite-State Markov Semi-Groups
• Some Results on the Imbedding Problem for Finite Markov Chains
• Embeddable Markov matrices
• Classical deterministic complexity of Edmonds' Problem and quantum entanglement
• Error and Perturbation Bounds for Subspaces Associated with Certain Eigenvalue Problems
• Linear transformations which preserve trace and positive semidefiniteness of operators
• Continuity properties of fractional powers, of the logarithm, and of holomorphic semigroups
• Computational complexity of the quantum separability problem
• Integer optimization on convex semialgebraic sets
• Title not available (Why is that?)
• Infinitely Divisible Markov Mappings in Quantum Probability Theory
• On Uniqueness of the Logarithm for Markov Semi-Groups

Cited In (17)

• Irreversible quantum evolution with quadratic generator: Review
• Dynamical maps beyond Markovian regime
• Select topics in open quantum systems
• The complexity of divisibility
• Necessary criteria for Markovian divisibility of linear maps
• Embeddability of real and positive operators
• Log-convex set of Lindblad semigroups acting on N-level system
• Almost all quantum channels are diagonalizable
• Machine learning versus semidefinite programming approach to a particular problem of the theory of open quantum systems
• Dissipative and non-dissipative single-qubit channels: dynamics and geometry
• Asymptotic Floquet states of open quantum systems: the role of interaction
• Channel divergences and complexity in algebraic QFT
• Accessible Maps in a Group of Classical or Quantum Channels
• Finding the Kraus decomposition from a master equation and vice versa
• Roots of completely positive maps
• Quantum and classical dynamical semigroups of superchannels and semicausal channels
• Machine learning approach to the Floquet-Lindbladian problem

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)