BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Can dynamical equations be deduced from measurement data? - Toby C
 ubitt (Bristol)
DTSTART:20090528T131500Z
DTEND:20090528T141500Z
UID:TALK17966@talks.cam.ac.uk
CONTACT:Lawrence Ioannou
DESCRIPTION:Alternate title (for probability and stats people): "Laying th
 e embedding problem for stochastic matrices to rest."\n\nA stochastic matr
 ix is "embeddable" iff it can be generated by a\ncontinuous-time Markov pr
 ocess. The problem of deciding whether a\nstochastic matrix is embeddable 
 was originally posed at least as far back\nas 1937\, yet has remained open
  until now. Analogously\, a quantum channel\nis "Markovian" iff it can be 
 generated by a master equation. Deciding\nwhether a channel is Markovian i
 s the converse problem to Linblad's famous\n1976 result\, characterising t
 he generators of completely-positive\nsemi-groups. Using tools from comple
 xity theory\, I will finally lay both\nthese problems to rest\, by proving
  that they are NP-hard.\n\nWhy should you care about these seemingly esote
 ric problems in probability\nand operator theory?\n\nBecause "continuous-t
 ime Markov processes" and "master equations" are\, to\na physicist\, just 
 mathematical names for the dynamical equations that\ndescribe the behaviou
 r of physical systems. And a large part of physics\nboils down to discover
 ing and understanding dynamical equations: Newton's\ngreat achievement was
  to give us the dynamical equations for celestial\nmechanics\, Schroedinge
 r's\, to give us the dynamical equations for quantum\nparticles. Like most
  things in physics\, we typically figure out dynamical\nequations by doing
  experiments\, gathering measurement data\, and analysing\nit in order to 
 learn about the underlying physics. But NP-hardness of the\nembedding and 
 Markovianity problems leads to a startling conclusion: no\nmatter how much
  measurement data we might gather\, it is in general\nimpossible to deduce
  the underlying dynamical equations from that data.\n(Or to be more precis
 e\, unless P=NP\, it would take such a long time as to\nbe completely impr
 actical.) Which raises intriguing questions about how\nexactly we learn ab
 out physics in the first place...!\n
LOCATION:MR2\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR