BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Can dynamical equations be deduced from measuremen
t data? - Toby Cubitt (Bristol)
DTSTART;TZID=Europe/London:20090528T141500
DTEND;TZID=Europe/London:20090528T151500
UID:TALK17966AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/17966
DESCRIPTION:Alternate title (for probability and stats people)
: "Laying the embedding problem for stochastic mat
rices to rest."\n\nA stochastic matrix is "embedda
ble" iff it can be generated by a\ncontinuous-time
Markov process. The problem of deciding whether a
\nstochastic matrix is embeddable was originally p
osed at least as far back\nas 1937\, yet has remai
ned open until now. Analogously\, a quantum channe
l\nis "Markovian" iff it can be generated by a mas
ter equation. Deciding\nwhether a channel is Marko
vian is the converse problem to Linblad's famous\n
1976 result\, characterising the generators of com
pletely-positive\nsemi-groups. Using tools from co
mplexity theory\, I will finally lay both\nthese p
roblems to rest\, by proving that they are NP-hard
.\n\nWhy should you care about these seemingly eso
teric problems in probability\nand operator theory
?\n\nBecause "continuous-time Markov processes" an
d "master equations" are\, to\na physicist\, just
mathematical names for the dynamical equations tha
t\ndescribe the behaviour of physical systems. And
a large part of physics\nboils down to discoverin
g and understanding dynamical equations: Newton's\
ngreat achievement was to give us the dynamical eq
uations for celestial\nmechanics\, Schroedinger's\
, to give us the dynamical equations for quantum\n
particles. Like most things in physics\, we typica
lly figure out dynamical\nequations by doing exper
iments\, gathering measurement data\, and analysin
g\nit in order to learn about the underlying physi
cs. But NP-hardness of the\nembedding and Markovia
nity problems leads to a startling conclusion: no\
nmatter how much measurement data we might gather\
, it is in general\nimpossible to deduce the under
lying dynamical equations from that data.\n(Or to
be more precise\, unless P=NP\, it would take such
a long time as to\nbe completely impractical.) Wh
ich raises intriguing questions about how\nexactly
we learn about physics in the first place...!\n
LOCATION:MR2\, Centre for Mathematical Sciences
CONTACT:Lawrence Ioannou
END:VEVENT
END:VCALENDAR