The complexity of relating quantum channels to master equations (Q766099)

The completely positive, trace preserving (CPT) maps and Lindblad master equations are studied. The aim of this work is to answer the question: Given a CPT map, is there a Lindblad master equation that generates it (and if so, can we find its form)? This is sometimes known as the Markovianity problem. Physically, it is asking how one can deduce underlying physical processes from experimental observations. The authors give a complexity theoretic answer to this problem: it is NP-hard. The explicit algorithm that reduces the problem to integer semi-definite programming is presented. It is a well-known NP problem. So, 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 the algorithm already gives an efficiently computable criterion. Thus, unless P does equal NP, there cannot exist any simple criterion for determination when a CPT map has a master equation description. However, it is shown that if the system dimension is fixed (relevant for current quantum process tomography experiments), then the authors' 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. This work consists of the following basic parts: introduction, the quantum problem, the classical problem, implications for physics, outline; preliminaries; the quantum problem, the computational Marcovianity problem, the computational Lindblad generator problem; NP-hardness, encoding 1-IN-3SAT, perturbations; an algorithm; the classical problem; conclusions.