Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1005.0005 · Physical Review Letters

Extracting Dynamical Equations from Experimental Data is NP Hard

Toby S. Cubitt, Jens Eisert, Michael M. Wolf

Published Mar 22, 2012• 52 citations
arXivHTMLPDF

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

DOI
10.1103/physrevlett.108.120503

Related papers

Deciding whether a Quantum Channel is Markovian is NP-hard

Toby S. Cubitt, Jens Eisert, Michael M. Wolf

We show that deciding whether a given quantum channel can be generated by a Markovian master equation is an NP-hard problem. As a consequence, this result suggests that extracting the underlyin g physics governing the evolution of a quantum system, as described by its dynamical equations, may be a hard task regardless of how much data is gathered via measurements of the system. On the other hand, if the system dimension is fixed, the problem of deciding whether a process is consistent with being Markovian can be efficiently decided, and we give an explicit algorithm in this case. This work also leads to a complexity-theoretic solution to a long-standing open problem in probability theory.

•Aug 17, 2009•2 citations

Quantum Expression of Classical Chaos

Sudhir R. Jain, Benoît Grémaud, Avinash Khare

Even as we understand for long that the world is quantal and buried in it is classical dynamics which is chaotic, finding eigenfunctions analytically from the the Schroedinger equation has turned out to be a near-impossibility. Here, we discover a class of chaotic quantum systems for which we obtain some analytically exact eigenfunctions in closed form. This paves way to an exact classical and quantum mechanical treatment of chaotic systems. Furthermore, we bring out connections, underlying the discovery, between different areas of physics and mathematics related to universality in fluctuations observed in a wide variety of complex quantum systems.

arXiv:nlin/0107051•Jul 23, 2001•1 citation

Uncomputability and complexity of quantum control

Denys I. Bondar, Alexander Nikolaevich Pechen

In laboratory and numerical experiments, physical quantities are known with a finite precision and described by rational numbers. Based on this, we deduce that quantum control problems both for open and closed systems are in general not algorithmically solvable, i.e., there is no algorithm that can decide whether dynamics of an arbitrary quantum system can be manipulated by accessible external interactions (coherent or dissipative) such that a chosen target reaches a desired value. This conclusion holds even for the relaxed requirement of the target only approximately attaining the desired value. These findings do not preclude an algorithmic solvability for a particular class of quantum control problems. Moreover, any quantum control problem can be made algorithmically solvable if the set of accessible interactions (i.e., controls) is rich enough. To arrive at these results, we develop a technique based on establishing the equivalence between quantum control problems and Diophantine equations, which are polynomial equations with integer coefficients and integer unknowns. In addition to proving uncomputability, this technique allows to construct quantum control problems belonging to different complexity classes. In particular, an example of the control problem involving a two-mode coherent field is shown to be NP-hard, contradicting a widely held believe that two-body problems are easy.

arXiv:1907.10082•Scientific Reports•Jan 27, 2020•18 citations

On the Effective Representation of Quantum Data for Classical Machine Learning Problems

Ilias Κ. Savvas, Andrey V. Chernov, Oleg O. Kartashov +2 more

There is no doubt that quantum computing has opened up new horizons and perspectives in many fields, including scientific research. With the advancement of technology and quantum computers, we can now conduct new kinds of scientific experiments: observing quantum properties of individual systems, atoms, electrons and photons as well as influencing and controlling quantum systems. Quantum mechanics describes the properties of quantum systems by their quantum states. Unlike in classical mechanics, quantum states themselves cannot be directly observed in experiments, so many-body dynamics mathematical simulations are useful. Even though many-body dynamics problems can be solved for limited cases, but when we consider real-world pieces of matter this leads to computation-intensive calculations that are beyond classic digital computers. The memory and time needed to describe the quantum state of a many-body system scales exponentially with the size of the system. This has led physics communities to focus their attention on the algorithms underlying modern machine learning with the goal of making progress in quantum matter research. As a consequence, the successful application of machine learning requires effective and informative data representation. This paper discusses some novel aspects of applying classical machine learning algorithms to quantum data derived from measurements associated with quantum systems in many-body simulation problems. In this paper, we investigate and experimentally demonstrate one of the effective methods of the quantum data representation suited for the classical machine learning applications based on quantum classical shadows.

Panhellenic Conference on Informatics•Nov 25, 2022•0 citations

Chaos and Quantum Mechanics

Salman Habib, Tanmoy Bhattacharya A, Benjamin D. Greenbaum +3 more

The relationship between chaos and quantum mechanics has been somewhat uneasy--even stormy, in the minds of some people. However, much of the confusion may stem from inappropriate comparisons using formal analyses. In contrast, our starting point here is that a complete dynamical description requires a full understanding of the evolution of measured systems, necessary to explain actual experimental results. This is of course true, both classically and quantum mechanically. Because the evolution of the physical state is now conditioned on measurement results, the dynamics of such systems is intrinsically nonlinear even at the level of distribution functions. Due to this feature, the physically more complete treatment reveals the existence of dynamical regimes--such as chaos--that have no direct counterpart in the linear (unobserved) case. Moreover, this treatment allows for understanding how an effective classical behavior can result from the dynamics of an observed quantum system, both at the level of trajectories as well as distribution functions. Finally, we have the striking prediction that time-series from measured quantum systems can be chaotic far from the classical regime, with Lyapunov exponents differing from their classical values. These predictions can be tested in next-generation experiments.

arXiv:quant-ph/0505085•Annals of the New York Academy of Sciences•Jun 1, 2005•24 citations

The Complexity of Relating Quantum Channels to Master Equations

Toby S. Cubitt, Jens Eisert, Michael M. Wolf

Completely positive, trace preserving (CPT) maps and Lindblad master equations are both widely used to describe the dynamics of open quantum systems. The connection between these two descriptions is a classic topic in mathematical physics. One direction was solved by the now famous result due to Lindblad, Kossakowski Gorini and Sudarshan, who gave a complete characterisation of the master equations that generate completely positive semi-groups. However, the other direction has remained open: given a CPT map, is there a Lindblad master equation that generates it (and if so, can we find it's form)? This is sometimes known as the Markovianity problem. Physically, it is asking how one can deduce underlying physical processes from experimental observations. We give a complexity theoretic answer to this problem: it is NP-hard. We also give an explicit algorithm that reduces the problem to integer semi-definite programming, a well-known NP problem. Together, these results imply that resolving the question of which CPT maps can be generated by master equations is tantamount to solving P=NP: any efficiently computable criterion for Markovianity would imply P=NP; whereas a proof that P=NP would imply that our algorithm already gives an efficiently computable criterion. Thus, unless P does equal NP, there cannot exist any simple criterion for determining when a CPT map has a master equation description. However, we also show that if the system dimension is fixed (relevant for current quantum process tomography experiments), then our algorithm scales efficiently in the required precision, allowing an underlying Lindblad master equation to be determined efficiently from even a single snapshot in this case. Our work also leads to similar complexity-theoretic answers to a related long-standing open problem in probability theory.

arXiv:0908.2128•Aug 17, 2009•2 citations
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).
We show that deciding whether a given quantum channel can be generated by a Markovian master equation is an NP-hard problem. As a consequence, this result suggests that extracting the underlyin g physics governing the evolution of a quantum system, as described by its dynamical equations, may be a hard task regardless of how much data is gathered via measurements of the system. On the other hand, if the system dimension is fixed, the problem of deciding whether a process is consistent with being Markovian can be efficiently decided, and we give an explicit algorithm in this case. This work also leads to a complexity-theoretic solution to a long-standing open problem in probability theory.
Even as we understand for long that the world is quantal and buried in it is classical dynamics which is chaotic, finding eigenfunctions analytically from the the Schroedinger equation has turned out to be a near-impossibility. Here, we discover a class of chaotic quantum systems for which we obtain some analytically exact eigenfunctions in closed form. This paves way to an exact classical and quantum mechanical treatment of chaotic systems. Furthermore, we bring out connections, underlying the discovery, between different areas of physics and mathematics related to universality in fluctuations observed in a wide variety of complex quantum systems.
In laboratory and numerical experiments, physical quantities are known with a finite precision and described by rational numbers. Based on this, we deduce that quantum control problems both for open and closed systems are in general not algorithmically solvable, i.e., there is no algorithm that can decide whether dynamics of an arbitrary quantum system can be manipulated by accessible external interactions (coherent or dissipative) such that a chosen target reaches a desired value. This conclusion holds even for the relaxed requirement of the target only approximately attaining the desired value. These findings do not preclude an algorithmic solvability for a particular class of quantum control problems. Moreover, any quantum control problem can be made algorithmically solvable if the set of accessible interactions (i.e., controls) is rich enough. To arrive at these results, we develop a technique based on establishing the equivalence between quantum control problems and Diophantine equations, which are polynomial equations with integer coefficients and integer unknowns. In addition to proving uncomputability, this technique allows to construct quantum control problems belonging to different complexity classes. In particular, an example of the control problem involving a two-mode coherent field is shown to be NP-hard, contradicting a widely held believe that two-body problems are easy.
There is no doubt that quantum computing has opened up new horizons and perspectives in many fields, including scientific research. With the advancement of technology and quantum computers, we can now conduct new kinds of scientific experiments: observing quantum properties of individual systems, atoms, electrons and photons as well as influencing and controlling quantum systems. Quantum mechanics describes the properties of quantum systems by their quantum states. Unlike in classical mechanics, quantum states themselves cannot be directly observed in experiments, so many-body dynamics mathematical simulations are useful. Even though many-body dynamics problems can be solved for limited cases, but when we consider real-world pieces of matter this leads to computation-intensive calculations that are beyond classic digital computers. The memory and time needed to describe the quantum state of a many-body system scales exponentially with the size of the system. This has led physics communities to focus their attention on the algorithms underlying modern machine learning with the goal of making progress in quantum matter research. As a consequence, the successful application of machine learning requires effective and informative data representation. This paper discusses some novel aspects of applying classical machine learning algorithms to quantum data derived from measurements associated with quantum systems in many-body simulation problems. In this paper, we investigate and experimentally demonstrate one of the effective methods of the quantum data representation suited for the classical machine learning applications based on quantum classical shadows.
The relationship between chaos and quantum mechanics has been somewhat uneasy--even stormy, in the minds of some people. However, much of the confusion may stem from inappropriate comparisons using formal analyses. In contrast, our starting point here is that a complete dynamical description requires a full understanding of the evolution of measured systems, necessary to explain actual experimental results. This is of course true, both classically and quantum mechanically. Because the evolution of the physical state is now conditioned on measurement results, the dynamics of such systems is intrinsically nonlinear even at the level of distribution functions. Due to this feature, the physically more complete treatment reveals the existence of dynamical regimes--such as chaos--that have no direct counterpart in the linear (unobserved) case. Moreover, this treatment allows for understanding how an effective classical behavior can result from the dynamics of an observed quantum system, both at the level of trajectories as well as distribution functions. Finally, we have the striking prediction that time-series from measured quantum systems can be chaotic far from the classical regime, with Lyapunov exponents differing from their classical values. These predictions can be tested in next-generation experiments.
Completely positive, trace preserving (CPT) maps and Lindblad master equations are both widely used to describe the dynamics of open quantum systems. The connection between these two descriptions is a classic topic in mathematical physics. One direction was solved by the now famous result due to Lindblad, Kossakowski Gorini and Sudarshan, who gave a complete characterisation of the master equations that generate completely positive semi-groups. However, the other direction has remained open: given a CPT map, is there a Lindblad master equation that generates it (and if so, can we find it's form)? This is sometimes known as the Markovianity problem. Physically, it is asking how one can deduce underlying physical processes from experimental observations. We give a complexity theoretic answer to this problem: it is NP-hard. We also give an explicit algorithm that reduces the problem to integer semi-definite programming, a well-known NP problem. Together, these results imply that resolving the question of which CPT maps can be generated by master equations is tantamount to solving P=NP: any efficiently computable criterion for Markovianity would imply P=NP; whereas a proof that P=NP would imply that our algorithm already gives an efficiently computable criterion. Thus, unless P does equal NP, there cannot exist any simple criterion for determining when a CPT map has a master equation description. However, we also show that if the system dimension is fixed (relevant for current quantum process tomography experiments), then our algorithm scales efficiently in the required precision, allowing an underlying Lindblad master equation to be determined efficiently from even a single snapshot in this case. Our work also leads to similar complexity-theoretic answers to a related long-standing open problem in probability theory.