• Featured in Physics
  • Editors' Suggestion

Extracting Dynamical Equations from Experimental Data is NP Hard

Toby S. Cubitt, Jens Eisert, and Michael M. Wolf
Phys. Rev. Lett. 108, 120503 – Published 22 March 2012
Physics logo See Synopsis: The Unbearable Hardness of Physics
PDFHTMLExport Citation

Abstract

The behavior of any physical system is governed by its underlying dynamical equations. Much of physics is concerned with discovering these dynamical equations and understanding their consequences. In this Letter, we show that, remarkably, identifying the underlying dynamical equation from any amount of experimental data, however precise, is a provably computationally hard problem (it is NP hard), both for classical and quantum mechanical systems. As a by-product of this work, we give complexity-theoretic answers to both the quantum and classical embedding problems, two long-standing open problems in mathematics (the classical problem, in particular, dating back over 70 years).

  • Figure
  • Received 24 June 2011

DOI:https://doi.org/10.1103/PhysRevLett.108.120503

© 2012 American Physical Society

Synopsis

Key Image

The Unbearable Hardness of Physics

Published 22 March 2012

Researchers have proved that extracting dynamical equations from data is in general a computationally hard problem.

See more in Physics

Authors & Affiliations

Toby S. Cubitt1, Jens Eisert2, and Michael M. Wolf3

  • 1Departamento de Análisis Matemático, Universidad Complutense de Madrid, Plaza de Ciencias 3, Ciudad Universitaria, 28040 Madrid, Spain
  • 2Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
  • 3Zentrum Mathematik, Technische Universität München, 85748 Garching, Germany

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 108, Iss. 12 — 23 March 2012

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×