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:1510.02800 · Physical Review A

Learning optimal quantum models is NP-hard

Cyril Stark

Published Feb 8, 2018• 6 citations
arXivHTMLPDF

Abstract

Physical modeling translates measured data into a physical model. Physical modeling is a major objective in physics and is generally regarded as a creative process. How good are computers at solving this task? Here, we show that in the absence of physical heuristics, the inference of optimal quantum models cannot be computed efficiently (unless $\text{P}=\text{NP}$). This result illuminates rigorous limits to the extent to which computers can be used to further our understanding of nature.

DOI
10.1103/physreva.97.020103

Related papers

Any realistic model of a physical system must be computationally realistic

Arkady Bolotin

It is argued that any possible definition of a realistic physics theory – i.e., a mathematical model representing the real world – cannot be considered comprehensive unless it is supplemented with requirement of being computationally realistic. That is, the mathematical structure of a realistic model of a physical system must allow the collection of all the system's physical quantities to compute all possible measurement outcomes on some computational device not only in an unambiguous way but also in a reasonable amount of time. In the paper, it is shown that a deterministic quantum model of a microscopic system evolving in isolation should be regarded as realistic since the NP-hard problem of finding the exact solution to the Schrödinger equation for an arbitrary physical system can be surely solved in a reasonable amount of time in the case, in which the system has just a small number of degrees of freedom. In contrast to this, the deterministic quantum model of a truly macroscopic object ought to be considered as non-realistic since in a world of limited computational resources the intractable problem possessing that enormous amount of degrees of freedom would be the same as mere unsolvable.

arXiv:1405.3569•Journal of Physics Conference Series•Jan 21, 2015•2 citations

Physical Models for Quantum Computers

Hans A. De Raedt, Kristel F. L. Michielsen, Seiji Miyashita +1 more

We discuss the impact of the physical implementation of a quantum computer on its computational efficiency, using computer simulations of physical models of quantum computer hardware. We address the computational efficiency of practical procedures to extract the results of a quantum computation from the wave function respresenting the final state of the quantum computer.

Progress of Theoretical Physics Supplement•Jan 1, 2002•4 citations

Unifying Deep Learning and Integer Programming through Graph Representations

PAULO SÉRGIO DE ANDRADE

Integer Programming (IP) constitutes a formidable framework for modeling and solving a vast array of real-world combinatorial optimization problems. However, the NP-hard nature of IPs often renders exact solutions computationally intractable for large-scale instances. Concurrently, deep learning (DL) has demonstrated unprecedented success in learning complex patterns and making data-driven predictions across various domains. This paper explores a novel paradigm for unifying these two powerful methodologies by leveraging graph representations. We propose a framework where IP problems are first translated into a rich graph structure, capturing variables, constraints, and their interdependencies. Graph Neural Networks (GNNs) are then employed to learn intricate features from these graph representations, which can subsequently inform or augment traditional IP solvers. Specifically, we investigate how GNNs can predict effective branching decisions, generate cutting planes, or guide primal heuristics, thereby accelerating the search for optimal or near-optimal integer solutions. This unification aims to transcend the limitations of purely heuristic approaches by grounding DL predictions within the rigorous mathematical framework of IP, while simultaneously injecting learning-based intelligence into the traditionally exact yet computationally intensive optimization process. Our approach seeks to develop hybrid algorithms that combine the generalization capabilities of deep learning with the guarantee-seeking nature of integer programming, potentially leading to significant advancements in solving complex optimization challenges.

•Nov 22, 2025•0 citations

QUBO for training regression models

M. Caruso, Daniel Escánez-Expósito, Pino Caballero‐Gil +1 more

A constantly increasing number of parameters in modern machine learning models has become a significant bottleneck in their efficient training, resulting in a disproportionate consumption of resources, expressed in terms of energy and computational time. The vast majority of such resources are allocated to the training phase rather than the inference stage, leading to an inefficient process [1] , [2] , [3] . This study addresses this problem by introducing a quantum alternative for training machine learning models, formalized as a Quadratic Unconstrained Binary Optimization ( QUBO ) problem. Adiabatic quantum computers have shown promise in approximately solving certain NP -hard problems, such as QUBO , potentially offering speed advantages over classical computers in specific scenarios [ 4 , 5, [6] , [7] ]. Given that many machine learning problems are also NP -hard, adiabatic quantum computers could play a pivotal role in efficiently training machine learning models. Furthermore, inspired by the ones’ complement binary numeral system, this work includes the proposal of an efficient binary-to-decimal encoding, which improves data representation in the quantum context. A concrete implementation of a regression training problem on specific quantum hardware is also presented here, the results of which suggest that the adoption of quantum techniques in model training allows not only to address the problem of parameter explosion but also to offer promising prospects for significantly accelerate the training process by exploiting the unique properties of quantum computation.

Journal of Computational and Applied Mathematics•Apr 2, 2026•0 citations

Limits on Efficient Computation in the Physical World

Scott Aaronson

More than a speculative technology, quantum computing seems to challenge our most basic intuitions about how the physical world should behave. In this thesis I show that, while some intuitions from classical computer science must be jettisoned in the light of modern physics, many others emerge nearly unscathed; and I use powerful tools from computational complexity theory to help determine which are which.

arXiv:quant-ph/0412143•Dec 20, 2004•25 citations

Using Quantum Computers to Learn Physics

Nathan Wiebe

Since its inception at the beginning of the twentieth century, quantum mechanics has challenged our conceptions of how the universe ought to work; however, the equations of quantum mechanics can be too computationally difficult to solve using existing computers for even modestly large systems. Here I will show that quantum computers can sometimes be used to address such problems and that quantum computer science can assign formal complexities to learning facts about nature. Hence, computer science should not only be regarded as an applied science; it is also of central importance to the foundations of science.

arXiv:1401.4507•Jan 18, 2014•1 citation
Physical modeling translates measured data into a physical model. Physical modeling is a major objective in physics and is generally regarded as a creative process. How good are computers at solving this task? Here, we show that in the absence of physical heuristics, the inference of optimal quantum models cannot be computed efficiently (unless P=NP\text{P}=\text{NP}P=NP). This result illuminates rigorous limits to the extent to which computers can be used to further our understanding of nature.
It is argued that any possible definition of a realistic physics theory – i.e., a mathematical model representing the real world – cannot be considered comprehensive unless it is supplemented with requirement of being computationally realistic. That is, the mathematical structure of a realistic model of a physical system must allow the collection of all the system's physical quantities to compute all possible measurement outcomes on some computational device not only in an unambiguous way but also in a reasonable amount of time. In the paper, it is shown that a deterministic quantum model of a microscopic system evolving in isolation should be regarded as realistic since the NP-hard problem of finding the exact solution to the Schrödinger equation for an arbitrary physical system can be surely solved in a reasonable amount of time in the case, in which the system has just a small number of degrees of freedom. In contrast to this, the deterministic quantum model of a truly macroscopic object ought to be considered as non-realistic since in a world of limited computational resources the intractable problem possessing that enormous amount of degrees of freedom would be the same as mere unsolvable.
Integer Programming (IP) constitutes a formidable framework for modeling and solving a vast array of real-world combinatorial optimization problems. However, the NP-hard nature of IPs often renders exact solutions computationally intractable for large-scale instances. Concurrently, deep learning (DL) has demonstrated unprecedented success in learning complex patterns and making data-driven predictions across various domains. This paper explores a novel paradigm for unifying these two powerful methodologies by leveraging graph representations. We propose a framework where IP problems are first translated into a rich graph structure, capturing variables, constraints, and their interdependencies. Graph Neural Networks (GNNs) are then employed to learn intricate features from these graph representations, which can subsequently inform or augment traditional IP solvers. Specifically, we investigate how GNNs can predict effective branching decisions, generate cutting planes, or guide primal heuristics, thereby accelerating the search for optimal or near-optimal integer solutions. This unification aims to transcend the limitations of purely heuristic approaches by grounding DL predictions within the rigorous mathematical framework of IP, while simultaneously injecting learning-based intelligence into the traditionally exact yet computationally intensive optimization process. Our approach seeks to develop hybrid algorithms that combine the generalization capabilities of deep learning with the guarantee-seeking nature of integer programming, potentially leading to significant advancements in solving complex optimization challenges.
A constantly increasing number of parameters in modern machine learning models has become a significant bottleneck in their efficient training, resulting in a disproportionate consumption of resources, expressed in terms of energy and computational time. The vast majority of such resources are allocated to the training phase rather than the inference stage, leading to an inefficient process [1] , [2] , [3] . This study addresses this problem by introducing a quantum alternative for training machine learning models, formalized as a Quadratic Unconstrained Binary Optimization ( QUBO ) problem. Adiabatic quantum computers have shown promise in approximately solving certain NP -hard problems, such as QUBO , potentially offering speed advantages over classical computers in specific scenarios [ 4 , 5, [6] , [7] ]. Given that many machine learning problems are also NP -hard, adiabatic quantum computers could play a pivotal role in efficiently training machine learning models. Furthermore, inspired by the ones’ complement binary numeral system, this work includes the proposal of an efficient binary-to-decimal encoding, which improves data representation in the quantum context. A concrete implementation of a regression training problem on specific quantum hardware is also presented here, the results of which suggest that the adoption of quantum techniques in model training allows not only to address the problem of parameter explosion but also to offer promising prospects for significantly accelerate the training process by exploiting the unique properties of quantum computation.
Since its inception at the beginning of the twentieth century, quantum mechanics has challenged our conceptions of how the universe ought to work; however, the equations of quantum mechanics can be too computationally difficult to solve using existing computers for even modestly large systems. Here I will show that quantum computers can sometimes be used to address such problems and that quantum computer science can assign formal complexities to learning facts about nature. Hence, computer science should not only be regarded as an applied science; it is also of central importance to the foundations of science.