Ising machines as hardware solvers of combinatorial optimization problems

• URL: http://arxiv.org/abs/2204.00276v1
• Date: Fri, 1 Apr 2022 08:24:06 GMT
• Title: Ising machines as hardware solvers of combinatorial optimization problems
• Authors: Naeimeh Mohseni, Peter L. McMahon, Tim Byrnes
• Abstract summary: Ising machines are hardware solvers which aim to find the absolute or approximate ground states of the Ising model. A scalable Ising machine that outperforms existing standard digital computers could have a huge impact for practical applications.
• Score: 1.8732539895890135
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Ising machines are hardware solvers which aim to find the absolute or approximate ground states of the Ising model. The Ising model is of fundamental computational interest because it is possible to formulate any problem in the complexity class NP as an Ising problem with only polynomial overhead. A scalable Ising machine that outperforms existing standard digital computers could have a huge impact for practical applications for a wide variety of optimization problems. In this review, we survey the current status of various approaches to constructing Ising machines and explain their underlying operational principles. The types of Ising machines considered here include classical thermal annealers based on technologies such as spintronics, optics, memristors, and digital hardware accelerators; dynamical-systems solvers implemented with optics and electronics; and superconducting-circuit quantum annealers. We compare and contrast their performance using standard metrics such as the ground-state success probability and time-to-solution, give their scaling relations with problem size, and discuss their strengths and weaknesses.

Related papers

• A Josephson Parametric Oscillator-Based Ising Machine [5.680611147657014]
  This study introduces a Josephson parametric oscillator (JPO)-based tile structure, serving as a fundamental unit for scalable superconductor-based Ising machines. The proposed machine can operate at frequencies of 7.5GHz while consuming significantly less power (by three orders of magnitude) than CMOS-based systems.
  arXiv  Detail & Related papers  (2023-09-06T23:56:30Z)
• Reliable AI: Does the Next Generation Require Quantum Computing? [71.84486326350338]
  We show that digital hardware is inherently constrained in solving problems about optimization, deep learning, or differential equations. In contrast, analog computing models, such as the Blum-Shub-Smale machine, exhibit the potential to surmount these limitations.
  arXiv  Detail & Related papers  (2023-07-03T19:10:45Z)
• On Robust Numerical Solver for ODE via Self-Attention Mechanism [82.95493796476767]
  We explore training efficient and robust AI-enhanced numerical solvers with a small data size by mitigating intrinsic noise disturbances. We first analyze the ability of the self-attention mechanism to regulate noise in supervised learning and then propose a simple-yet-effective numerical solver, Attr, which introduces an additive self-attention mechanism to the numerical solution of differential equations.
  arXiv  Detail & Related papers  (2023-02-05T01:39:21Z)
• Computability of Optimizers [71.84486326350338]
  We will show that in various situations the is unattainable on Turing machines and consequently on digital computers. We prove such results for a variety of well-known problems from very different areas, including artificial intelligence, financial mathematics, and information theory.
  arXiv  Detail & Related papers  (2023-01-15T17:41:41Z)
• The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus [55.58528469973086]
  Quantum computers promise to efficiently solve important problems classical computers never will. A fully automated quantum software stack needs to be developed. This work provides a look "under the hood" of today's tools and showcases how these means are utilized in them, e.g., for simulation, compilation, and verification of quantum circuits.
  arXiv  Detail & Related papers  (2023-01-10T19:00:00Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Electronic structure with direct diagonalization on a D-Wave quantum annealer [62.997667081978825]
  This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer. We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
  arXiv  Detail & Related papers  (2020-09-02T22:46:47Z)
• Complexity continuum within Ising formulation of NP problems [0.0]
  Minimisation of the Ising Hamiltonian is known to be NP-hard problem for certain interaction matrix classes. We propose to identify computationally simple instances with an optimisation simplicity criterion' Such simplicity can be found for a wide range of models from spin glasses to k-regular maximum cut problems.
  arXiv  Detail & Related papers  (2020-08-02T11:36:38Z)
• A CMOS-compatible Ising Machine with Bistable Nodes [0.8090330715662959]
  Physical Ising machines rely on nature to guide a dynamical system towards an optimal state. Quantum annealers are a prominent example of such efforts. integrated electronic designs of Ising machines allow more immediate applications.
  arXiv  Detail & Related papers  (2020-07-13T20:12:50Z)
• Approximate Approximation on a Quantum Annealer [13.66711311825402]
  Many problems of industrial interest are NP-complete, and quickly exhaust resources of computational devices with increasing input sizes. Quantumnealers (QA) are physical devices that aim at this class of problems by exploiting quantum mechanical properties.
  arXiv  Detail & Related papers  (2020-04-20T13:15:20Z)
• Optimizing the Optimizer: Decomposition Techniques for Quantum Annealing [0.0]
  Current generation quantum computers are too small to solve real-world problems. In this work, we explore multiple heterogeneous approaches to solving benchmark problems. Our results indicate that solver performance is highly dependent on the structure of the problem graph.
  arXiv  Detail & Related papers  (2020-01-16T21:35:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.