{"id":6189,"date":"2012-03-24T18:59:37","date_gmt":"2012-03-25T01:59:37","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=6189"},"modified":"2012-03-24T18:59:37","modified_gmt":"2012-03-25T01:59:37","slug":"more-on-the-np-hardness-of-inferring-dynamics","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2012\/03\/24\/more-on-the-np-hardness-of-inferring-dynamics\/","title":{"rendered":"More on the NP-hardness of inferring dynamics"},"content":{"rendered":"

The previous post<\/a> on David Voss’ APS piece quibbled perhaps excessively about the definition of NP, but neglected to mention\u00a0 the actual subject of the piece, which was Cubitt, Eisert and Wolf’s (CEW) recent paper <\/a>on the NP-hardness of extracting dynamical equations from experimental data.\u00a0 This paper raises, and partly answers,\u00a0 some subtle questions about the relation between computation and physics.\u00a0 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?\u00a0 We will argue below that the results of CEW do not support such a\u00a0 pessimistic view.\u00a0 What CEW do show about the problem of inferring dynamics from observation (more details here<\/a>) 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<\/em> underlying Markov process operating in continuous time—is NP-complete.\u00a0\u00a0 Continuous time Markov processes, described by time-independent Lindblad operators, model the evolution of an open quantum system in contact with a memoryless environment.\u00a0 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.\u00a0 For such small systems\u00a0 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.
\nSuppose on the other hand we apply the CEW algorithm to some experimental data and find that it doesn’t fit any Markovian dynamics.\u00a0 Then either the data is wrong or memory effects in the environment are too important to\u00a0 be neglected.\u00a0 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.\u00a0 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.\u00a0 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.\u00a0\u00a0 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,\u00a0 that physical processes can be efficiently simulated by a quantum computer.
\nBe 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.<\/p>\n","protected":false},"excerpt":{"rendered":"

The previous post on David Voss’ APS piece quibbled perhaps excessively about the definition of NP, but neglected to mention\u00a0 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.\u00a0 This paper raises, and partly answers,\u00a0 some subtle questions about … <\/p>\n

Continue reading “More on the NP-hardness of inferring dynamics”<\/span><\/a><\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[32],"tags":[],"class_list":["post-6189","post","type-post","status-publish","format-standard","hentry","category-general"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/6189","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=6189"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/6189\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=6189"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=6189"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=6189"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}