 # Can dynamical equations be deduced from measurement data?

• Toby Cubitt (Bristol)
• Thursday 28 May 2009, 14:15-15:15
• MR2, Centre for Mathematical Sciences.

Alternate title (for probability and stats people): “Laying the embedding problem for stochastic matrices to rest.”

A stochastic matrix is “embeddable” iff it can be generated by a continuous-time Markov process. The problem of deciding whether a stochastic matrix is embeddable was originally posed at least as far back as 1937, yet has remained open until now. Analogously, a quantum channel is “Markovian” iff it can be generated by a master equation. Deciding whether a channel is Markovian is the converse problem to Linblad’s famous 1976 result, characterising the generators of completely-positive semi-groups. Using tools from complexity theory, I will finally lay both these problems to rest, by proving that they are NP-hard.

Why should you care about these seemingly esoteric problems in probability and operator theory?

Because “continuous-time Markov processes” and “master equations” are, to a physicist, just mathematical names for the dynamical equations that describe the behaviour of physical systems. And a large part of physics boils down to discovering and understanding dynamical equations: Newton’s great achievement was to give us the dynamical equations for celestial mechanics, Schroedinger’s, to give us the dynamical equations for quantum particles. Like most things in physics, we typically figure out dynamical equations by doing experiments, gathering measurement data, and analysing it in order to learn about the underlying physics. But NP-hardness of the embedding and Markovianity problems leads to a startling conclusion: no matter how much measurement data we might gather, it is in general impossible to deduce the underlying dynamical equations from that data. (Or to be more precise, unless P=NP, it would take such a long time as to be completely impractical.) Which raises intriguing questions about how exactly we learn about physics in the first place…!

This talk is part of the CQIF Seminar series.