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:2008.00466 · Communications Physics

Computational complexity continuum within Ising formulation of NP problems

Kirill P. Kalinin, Natalia G. Berloff

Published Jan 12, 2022• 64 citations
arXivHTMLPDF

Abstract

Abstract A promising approach to achieve computational supremacy over the classical von Neumann architecture explores classical and quantum hardware as Ising machines. The minimisation of the Ising Hamiltonian is known to be NP-hard problem yet not all problem instances are equivalently hard to optimise. Given that the operational principles of Ising machines are suited to the structure of some problems but not others, we propose to identify computationally simple instances with an ‘optimisation simplicity criterion’. Neuromorphic architectures based on optical, photonic, and electronic systems can naturally operate to optimise instances satisfying this criterion, which are therefore often chosen to illustrate the computational advantages of new Ising machines. As an example, we show that the Ising model on the Möbius ladder graph is ‘easy’ for Ising machines. By rewiring the Möbius ladder graph to random 3-regular graphs, we probe an intermediate computational complexity between P and NP-hard classes with several numerical methods. Significant fractions of polynomially simple instances are further found for a wide range of small size models from spin glasses to maximum cut problems. A compelling approach for distinguishing easy and hard instances within the same NP-hard class of problems can be a starting point in developing a standardised procedure for the performance evaluation of emerging physical simulators and physics-inspired algorithms.

DOI
10.1038/s42005-021-00792-0

Related papers

Photonic Ising machines for combinatorial optimization problems

Yuan Gao, Guanyu Chen, Qi Luo +3 more

The demand for efficient solvers of complicated combinatorial optimization problems, especially those classified as NP-complete or NP-hard, has recently led to increased exploration of novel computing architectures. One prominent collective state computing paradigm embodied in the so-called Ising machines has recently attracted considerable research attention due to its ability to optimize complex problems with large numbers of interacting variables. Ising model-inspired solvers, thus named due to mathematical similarities to the well-known model from solid-state physics, represent a promising alternative to traditional von Neumann computer architectures due to their high degree of inherent parallelism. While there are many possible physical realizations of Ising solvers, just as there are many possible implementations of any binary computer, photonic Ising machines (PIMs) use primarily optical components for computation, taking advantage of features like lower power consumption, fast calculation speeds, the leveraging of physical optics to perform the calculations themselves, possessing decent scalability and noise tolerance. Photonic computing in the form of PIMs may offer certain computational advantages that are not easily achieved with non-photonic approaches and is nonetheless an altogether fascinating application of photonics to computing. In this review, we provide an overview of Ising machines generally, introducing why they are useful, what types of problems they can tackle, and how different Ising solvers can be compared and benchmarked. We delineate their various operational mechanisms, advantages, and limitations vis-à-vis non-photonic Ising machines. We describe their scalability, interconnectivity, performance, and physical dimensions. As research in PIMs continues to progress, there is a potential that photonic computing could well emerge as a way to handle large and challenging optimization problems across diverse domains. This review serves as a comprehensive resource for researchers and practitioners interested in understanding capabilities and potential of PIMs in addressing such complex optimization problems.

Applied Physics Reviews•Oct 14, 2024•40 citations

The Ising Machine as a Physical Non-Deterministic Computing Device: Formal Proof, Polynomial-Time Equivalence for NP, and Cryptographic Implications at Scale

Kaoru Aguilera Katayama

We present a rigorous, self-contained proof that an idealised Ising Machine (IM)-defined axiomatically from the experimentally observed properties of coherent Ising machines (CIMs), quantum annealers, and memristive/optical Ising processors-satisfies every clause of the canonical definition of a non-deterministic computing device in the sense of Turing (1936), Rabin and Scott (1959), and Cook (1971). Concretely, we show that (i) The physical ground-state search performed by an N-spin Ising Machine is not a deterministic computation: the machine simultaneously and physically explores an exponential number of spin configurations, and the branch that is "selected" (the ground state) is not the output of any single deterministic trajectory. (ii) There exists a polynomial-time simulation of any non-deterministic Turing machine (NDTM) by a suitably scaled Ising Machine, and conversely, every Ising Machine computation can be simulated by an NDTM in polynomial time. Hence the Ising Machine decides exactly the class NP in polynomial physical time. (iii) Because NP is, by definition, the class of languages decidable in polynomial time on a non-deterministic machine, a scalable Ising Machine would solve every NP problem in polynomial time, rendering all cryptographic schemes whose security relies on NP-hard or presumed-intractable problems (RSA, ECC, lattice-based, subset-sum-based, code-based, etc.) insecure. The argument is structured axiomatically: we first isolate the minimal physical axioms an Ising Machine must satisfy, then construct a formal mapping to the NDTM model, and finally derive the complexity-theoretic and cryptographic consequences. We discuss the crucial role of the scalability assumption and the engineering gap that currently prevents the full realisation of the threat.

•Mar 24, 2026•0 citations

How to Boost Ising Machines' Ability to Find Optimum Solutions: a Bifurcation Analysis

Jacob Lamers, Guy Verschaffelt, Guy Van der Sande

Photonic Ising machines are a recent and promising non-von Neuman architecture to efficiently solve large NP-hard optimization problems. This is done by letting spins evolve to the ground state of the Ising system. However, the Ising machine does not always relax to this ground state and can get trapped in local minima, resulting in suboptimal solutions. Here, we show that Ising-encoded optimization problems implemented on analog Ising machines can be divided in three difficulty classes and we propose an annealing scheme to efficiently solve two of them. Furthermore, we show that changing the physical implementation of the Ising machine can cause a problem to change difficulty class, rendering it potentially a lot more easy to solve.

OptoElectronics and Communications Conference and International Conference on Photonics in Switching and Computing (OECC/PSC)•Sep 26, 2023•0 citations

Identifying hard native instances for the maximum-independent-set problem on neutral-atom quantum processors

Pierre Cazals, Aymeric François, Loïc Henriet +9 more

The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods.

arXiv:2502.04291•Physical Review Applied•Jan 29, 2026•27 citations

Classical combinatorial optimization scaling for random Ising models on 2D heavy-hex graphs

Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz

Abstract Motivated by near term quantum computing hardware limitations, combinatorial optimization problems that can be addressed by current quantum algorithms and noisy hardware with little or no overhead are used to probe capabilities of quantum algorithms such as the quantum approximate optimization algorithm. In this study, a specific class of near term quantum computing hardware defined combinatorial optimization problems, Ising models on heavy-hex graphs both with and without geometrically local cubic terms, are examined for their classical computational hardness via empirical computation time scaling quantification. Specifically the time-to-solution (TTS) metric using the classical heuristic simulated annealing is measured for finding optimal variable assignments (ground states), as well as the time required for the optimization software Gurobi to find an optimal variable assignment. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. 100 000 spin variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time TTS scaling when sampled using simulated annealing. These findings point to the necessity of developing and testing more complex, namely more densely connected, optimization problems in order for quantum computing to ever have a practical advantage over classical computing. Our results are another illustration that different classical algorithms can indeed have exponentially different running times, thus making the identification of the best practical classical technique important in any quantum computing vs. classical computing comparison.

arXiv:2412.15572•Journal of Physics Communications•Apr 27, 2026•2 citations

Nonstoquastic Hamiltonians and quantum annealing of an Ising spin glass

Layla Hormozi, Ethan Brown, Giuseppe Carleo +1 more

Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.

arXiv:1609.06558•Physical review. B./Physical review. B•May 15, 2017•109 citations
Abstract A promising approach to achieve computational supremacy over the classical von Neumann architecture explores classical and quantum hardware as Ising machines. The minimisation of the Ising Hamiltonian is known to be NP-hard problem yet not all problem instances are equivalently hard to optimise. Given that the operational principles of Ising machines are suited to the structure of some problems but not others, we propose to identify computationally simple instances with an ‘optimisation simplicity criterion’. Neuromorphic architectures based on optical, photonic, and electronic systems can naturally operate to optimise instances satisfying this criterion, which are therefore often chosen to illustrate the computational advantages of new Ising machines. As an example, we show that the Ising model on the Möbius ladder graph is ‘easy’ for Ising machines. By rewiring the Möbius ladder graph to random 3-regular graphs, we probe an intermediate computational complexity between P and NP-hard classes with several numerical methods. Significant fractions of polynomially simple instances are further found for a wide range of small size models from spin glasses to maximum cut problems. A compelling approach for distinguishing easy and hard instances within the same NP-hard class of problems can be a starting point in developing a standardised procedure for the performance evaluation of emerging physical simulators and physics-inspired algorithms.
The demand for efficient solvers of complicated combinatorial optimization problems, especially those classified as NP-complete or NP-hard, has recently led to increased exploration of novel computing architectures. One prominent collective state computing paradigm embodied in the so-called Ising machines has recently attracted considerable research attention due to its ability to optimize complex problems with large numbers of interacting variables. Ising model-inspired solvers, thus named due to mathematical similarities to the well-known model from solid-state physics, represent a promising alternative to traditional von Neumann computer architectures due to their high degree of inherent parallelism. While there are many possible physical realizations of Ising solvers, just as there are many possible implementations of any binary computer, photonic Ising machines (PIMs) use primarily optical components for computation, taking advantage of features like lower power consumption, fast calculation speeds, the leveraging of physical optics to perform the calculations themselves, possessing decent scalability and noise tolerance. Photonic computing in the form of PIMs may offer certain computational advantages that are not easily achieved with non-photonic approaches and is nonetheless an altogether fascinating application of photonics to computing. In this review, we provide an overview of Ising machines generally, introducing why they are useful, what types of problems they can tackle, and how different Ising solvers can be compared and benchmarked. We delineate their various operational mechanisms, advantages, and limitations vis-à-vis non-photonic Ising machines. We describe their scalability, interconnectivity, performance, and physical dimensions. As research in PIMs continues to progress, there is a potential that photonic computing could well emerge as a way to handle large and challenging optimization problems across diverse domains. This review serves as a comprehensive resource for researchers and practitioners interested in understanding capabilities and potential of PIMs in addressing such complex optimization problems.
We present a rigorous, self-contained proof that an idealised Ising Machine (IM)-defined axiomatically from the experimentally observed properties of coherent Ising machines (CIMs), quantum annealers, and memristive/optical Ising processors-satisfies every clause of the canonical definition of a non-deterministic computing device in the sense of Turing (1936), Rabin and Scott (1959), and Cook (1971). Concretely, we show that (i) The physical ground-state search performed by an N-spin Ising Machine is not a deterministic computation: the machine simultaneously and physically explores an exponential number of spin configurations, and the branch that is "selected" (the ground state) is not the output of any single deterministic trajectory. (ii) There exists a polynomial-time simulation of any non-deterministic Turing machine (NDTM) by a suitably scaled Ising Machine, and conversely, every Ising Machine computation can be simulated by an NDTM in polynomial time. Hence the Ising Machine decides exactly the class NP in polynomial physical time. (iii) Because NP is, by definition, the class of languages decidable in polynomial time on a non-deterministic machine, a scalable Ising Machine would solve every NP problem in polynomial time, rendering all cryptographic schemes whose security relies on NP-hard or presumed-intractable problems (RSA, ECC, lattice-based, subset-sum-based, code-based, etc.) insecure. The argument is structured axiomatically: we first isolate the minimal physical axioms an Ising Machine must satisfy, then construct a formal mapping to the NDTM model, and finally derive the complexity-theoretic and cryptographic consequences. We discuss the crucial role of the scalability assumption and the engineering gap that currently prevents the full realisation of the threat.
Photonic Ising machines are a recent and promising non-von Neuman architecture to efficiently solve large NP-hard optimization problems. This is done by letting spins evolve to the ground state of the Ising system. However, the Ising machine does not always relax to this ground state and can get trapped in local minima, resulting in suboptimal solutions. Here, we show that Ising-encoded optimization problems implemented on analog Ising machines can be divided in three difficulty classes and we propose an annealing scheme to efficiently solve two of them. Furthermore, we show that changing the physical implementation of the Ising machine can cause a problem to change difficulty class, rendering it potentially a lot more easy to solve.
The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods.
Abstract Motivated by near term quantum computing hardware limitations, combinatorial optimization problems that can be addressed by current quantum algorithms and noisy hardware with little or no overhead are used to probe capabilities of quantum algorithms such as the quantum approximate optimization algorithm. In this study, a specific class of near term quantum computing hardware defined combinatorial optimization problems, Ising models on heavy-hex graphs both with and without geometrically local cubic terms, are examined for their classical computational hardness via empirical computation time scaling quantification. Specifically the time-to-solution (TTS) metric using the classical heuristic simulated annealing is measured for finding optimal variable assignments (ground states), as well as the time required for the optimization software Gurobi to find an optimal variable assignment. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. 100 000 spin variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time TTS scaling when sampled using simulated annealing. These findings point to the necessity of developing and testing more complex, namely more densely connected, optimization problems in order for quantum computing to ever have a practical advantage over classical computing. Our results are another illustration that different classical algorithms can indeed have exponentially different running times, thus making the identification of the best practical classical technique important in any quantum computing vs. classical computing comparison.
Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.