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• 53 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

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•20 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

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

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•27 citations

The complexity-theoretic Bell inequality

Zhengfeng Ji

Forty years later, a group of computer scientists, Richard Cleve, Peter Høyer, Ben Toner and John Watrous [1], provided a computer science perspective on Bell inequalities in the framework of multi-player one-round games. In a multi-player one-round game, a referee samples and asks questions to multiple non-communicating players and checks the validity of the answers according to some rule. The classical value of the game is the maximum success probability with which the players can pass the referee's check. Multi-player one-round games form a well-studied topic in theoretical computer science and have connections to constraint satisfaction problems, interactive proof systems, probabilistically checkable proof (PCP) and the celebrated PCP theorem. Cleve et al. reformulated Bell inequalities as multi-player one-round games such that the players can achieve a higher success probability, called the quantum value, when they measure a shared entangled state to obtain the answers. They also pointed out that shared entanglement may cause the so-called soundness problem in quantum interactive proof systems, an intriguing phenomenon that leads to a series of investigations on the limitation and power of entanglement in multi-player games. It is well known that it is NP-hard to approximate the classical value of a game to inverse polynomial precision where NP stands for nondeterministic polynomial time. Just how hard is it to approximate the quantum value of a game? We do not know the answer after a decade of research efforts, mainly because the players measure on an arbitrarily high dimensional quantum system. Because of the soundness problem pointed out by Cleve et al., we did not even know how to establish that the quantum value is NP-hard until Kempe et al. finally proved it in 2007 [2]. Very recently, the author established that the quantum value of a game is NEXP-hard to approximate [3,4] where NEXP stands for nondeterministic exponential time. This can be seen as a complexity-theoretic Bell inequality. The standard Bell inequality tells us that the classical and quantum values can be different for a fixed game; our result instead establishes that the computational complexities for approximating the classical and quantum values are different, since NP ≠ NEXP. The complexity of Bell inequalities or the quantum values of multi-player one-round games has deep connections to quantum physics and theoretical computer science as we have already discussed. It is also related to the Connes embedding conjecture in mathematics. Using a group theory approach, Slofstra proved that the problem of determining whether a game has quantum value 1 or not is undecidable [5]. Is the quantum value approximation problem also undecidable or can we establish any complexity upper bound? Only time will tell.

National Science Review•Jul 23, 2018•0 citations

Mathematical Results in Quantum Mechanics

J. Dittrich, Pavel Exner, Miloš Tater

At the age of almost three quarters of a century, quantum mechanics is by all accounts a mature theory. There were times when it seemed that it had borne its best fruit already and would give way to investigation of deeper levels of matter. Today this sounds like rash thinking. Modern experimental techniques have led to discoveries of numerous new quantum effects in solid state, optics and elsewhere. Quantum mechanics is thus gradually becoming a basis for many branches of applied physics, in this way entering our everyday life. While the dynamic laws of quantum mechanics are well known, a proper theoretical understanding requires methods which would allow us to de­ rive the abundance of observed quantum effects from the first principles. In many cases the rich structure hidden in the Schr6dinger equation can be revealed only using sophisticated tools. This constitutes a motivation to investigate rigorous methods which yield mathematically well-founded properties of quantum systems.

Birkhäuser Basel eBooks•Jan 1, 1999•32 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).
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.
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.
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.
Forty years later, a group of computer scientists, Richard Cleve, Peter Høyer, Ben Toner and John Watrous [1], provided a computer science perspective on Bell inequalities in the framework of multi-player one-round games. In a multi-player one-round game, a referee samples and asks questions to multiple non-communicating players and checks the validity of the answers according to some rule. The classical value of the game is the maximum success probability with which the players can pass the referee's check. Multi-player one-round games form a well-studied topic in theoretical computer science and have connections to constraint satisfaction problems, interactive proof systems, probabilistically checkable proof (PCP) and the celebrated PCP theorem. Cleve et al. reformulated Bell inequalities as multi-player one-round games such that the players can achieve a higher success probability, called the quantum value, when they measure a shared entangled state to obtain the answers. They also pointed out that shared entanglement may cause the so-called soundness problem in quantum interactive proof systems, an intriguing phenomenon that leads to a series of investigations on the limitation and power of entanglement in multi-player games. It is well known that it is NP-hard to approximate the classical value of a game to inverse polynomial precision where NP stands for nondeterministic polynomial time. Just how hard is it to approximate the quantum value of a game? We do not know the answer after a decade of research efforts, mainly because the players measure on an arbitrarily high dimensional quantum system. Because of the soundness problem pointed out by Cleve et al., we did not even know how to establish that the quantum value is NP-hard until Kempe et al. finally proved it in 2007 [2]. Very recently, the author established that the quantum value of a game is NEXP-hard to approximate [3,4] where NEXP stands for nondeterministic exponential time. This can be seen as a complexity-theoretic Bell inequality. The standard Bell inequality tells us that the classical and quantum values can be different for a fixed game; our result instead establishes that the computational complexities for approximating the classical and quantum values are different, since NP ≠ NEXP. The complexity of Bell inequalities or the quantum values of multi-player one-round games has deep connections to quantum physics and theoretical computer science as we have already discussed. It is also related to the Connes embedding conjecture in mathematics. Using a group theory approach, Slofstra proved that the problem of determining whether a game has quantum value 1 or not is undecidable [5]. Is the quantum value approximation problem also undecidable or can we establish any complexity upper bound? Only time will tell.
At the age of almost three quarters of a century, quantum mechanics is by all accounts a mature theory. There were times when it seemed that it had borne its best fruit already and would give way to investigation of deeper levels of matter. Today this sounds like rash thinking. Modern experimental techniques have led to discoveries of numerous new quantum effects in solid state, optics and elsewhere. Quantum mechanics is thus gradually becoming a basis for many branches of applied physics, in this way entering our everyday life. While the dynamic laws of quantum mechanics are well known, a proper theoretical understanding requires methods which would allow us to de­ rive the abundance of observed quantum effects from the first principles. In many cases the rich structure hidden in the Schr6dinger equation can be revealed only using sophisticated tools. This constitutes a motivation to investigate rigorous methods which yield mathematically well-founded properties of quantum systems.