More on the NP-hardness of inferring dynamics

The previous post on David Voss’ APS piece quibbled perhaps excessively about the definition of NP, but neglected to mention  the actual subject of the piece, which was Cubitt, Eisert and Wolf’s (CEW) recent paper on the NP-hardness of extracting dynamical equations from experimental data.  This paper raises, and partly answers,  some subtle questions about the relation between computation and physics.  For example, one might ask, if the problem of inferring dynamics from experiment is intractable in general, doesn’t this doom the whole program of theoretical physics?  We will argue below that the results of CEW do not support such a  pessimistic view.  What CEW do show about the problem of inferring dynamics from observation (more details here) is that a seemingly easier problem—that of determining whether a given completely-positive trace-preserving map (representing a quantum system’s evolution over a discrete time interval) is consistent with some underlying Markov process operating in continuous time—is NP-complete.   Continuous time Markov processes, described by time-independent Lindblad operators, model the evolution of an open quantum system in contact with a memoryless environment.  Of course this is an approximation, since no environment can be entirely memoryless over very short time intervals, but it works quite well in many practical situations where a quantum system with only a few degrees of freedom interacts with a large, rapidly-relaxing environment such as a heat bath.  For such small systems  NP-completeness does not render a problem intractable, and the result of CEW can be used to infer a very nearly correct dynamical description—a Lindblad equation—from experimental data consisting of discrete time snapshots of the evolving open quantum system.
Suppose on the other hand we apply the CEW algorithm to some experimental data and find that it doesn’t fit any Markovian dynamics.  Then either the data is wrong or memory effects in the environment are too important to  be neglected.  To understand the dynamics of such systems we must treat the environment more respectfully, somehow modeling its most significant memory effects, or, if all else fails, “going to the church of the larger Hilbert space” and treating the system plus environment as a larger closed system, evolving unitarily.  This raises the question of whether an intractability result analogous to CEW’s finding for open systems also applies to unitarily evolving closed quantum systems.  We suspect that it does not, and that the problem of fitting a Hamiltonian to a series of snapshots of a unitarily evolving quantum system may be tractable, at least if the Hamiltonian is of the approximately local form commonly encountered in physics, and if the experimenter is free to choose the times of the snapshots.   The inferability of dynamics from experimental data, which as we indicated above underlies the whole program of theoretical physics, is, we believe, related to the quantum Church-Turing thesis,  that physical processes can be efficiently simulated by a quantum computer.
Be that as it may, what CEW show, in a positive sense, is how (albeit very laboriously for large systems) to infer Markovian dynamics when the Markovian approximation is justified, and in a negative sense, when one should abandon the Markovian approximation and infer the dynamics by other means.