Extracting dynamical equations from experimental data is NP-hard

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 work, 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).

For mathematical details, see arXiv:0908.2128[math-ph]. v2: final version, accepted in Phys. Rev. Lett

References in corpus (5)

• Assessing non-Markovian dynamics
• Dividing Quantum Channels
• Non-Markovian generalization of the Lindblad theory of open quantum systems
• Process tomography of ion trap quantum gates
• Quantum process tomography and Linblad estimation of a solid state qubit

Cited by in corpus (21)

• Quantum Non-Markovianity: Characterization, Quantification and Detection
• Discovering physical concepts with neural networks
• Quantum channels and memory effects
• The prediction of future from the past: an old problem from a modern perspective
• Identifying Coupling Structure in Complex Systems through the Optimal Causation Entropy Principle
• Machine-assisted discovery of relationships in astronomy
• Quantum discord and non-Markovianity of quantum dynamics
• Thermodynamic costs of Turing Machines
• Causation entropy from symbolic representations of dynamical systems
• From empirical data to continuous Markov processes: a systematic approach
• Entanglement of nanoelectromechanical oscillators by Cooper-pair tunneling
• The Role of Data in Model Building and Prediction: A Survey Through Examples
• Theoretical investigations of an information geometric approach to complexity
• The Complexity of Divisibility
• Learning optimal quantum models is NP-hard
• Quantum and classical dynamical semigroups of superchannels and semicausal channels
• Quantum optimal control in quantum technologies. Strategic report on current status, visions and goals for research in Europe
• Roots of Completely Positive Maps
• Information geometric complexity of entropic motion on curved statistical manifolds
• Revisiting thermodynamics in computation and information theory
• Precision Medicine as an Accelerator for Next Generation Cognitive Supercomputing