Efficient Optimization with Higher-Order Ising Machines

• URL: http://arxiv.org/abs/2212.03426v1
• Date: Wed, 7 Dec 2022 03:18:05 GMT
• Title: Efficient Optimization with Higher-Order Ising Machines
• Authors: Connor Bybee, Denis Kleyko, Dmitri E. Nikonov, Amir Khosrowshahi, Bruno A. Olshausen, Friedrich T. Sommer
• Abstract summary: We show that higher-order Ising machines can solve satisfiability problems more resource-efficiently than traditional second-order Ising machines. Our results improve the current state-of-the-art for Ising machines.
• Score: 5.697064222465131
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Boolean \textit{k}-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines.

Related papers

• Tensor Network Based HOBO Solver [0.0]
  The proposed solver is a promising tool with significant potential for future extensions in terms of formulation. This solver holds promising potential for a wide range of applications in quantum computing.
  arXiv  Detail & Related papers  (2024-07-23T00:33:34Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints. We demonstrate its effectiveness on two well-known real-world applications.
  arXiv  Detail & Related papers  (2024-06-14T15:59:36Z)
• All-to-all reconfigurability with sparse and higher-order Ising machines [0.0]
  We introduce a multiplexed architecture that emulates all-to-all network functionality. We show that running the adaptive parallel tempering algorithm demonstrates competitive algorithmic and prefactor advantages. scaled magnetic versions of p-bit IMs could lead to orders of magnitude improvements over the state of the art for generic optimization.
  arXiv  Detail & Related papers  (2023-11-21T20:27:02Z)
• CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity [110.50364486645852]
  Communication complexity has become a major bottleneck for speeding up training and scaling up machine numbers. We propose Common Om REOm, which can be used to compress information transmitted between machines.
  arXiv  Detail & Related papers  (2023-09-23T08:45:27Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Augmented Electronic Ising Machine as an Effective SAT Solver [0.6999740786886535]
  We show that an Augmented Ising Machine for SAT (AIMS) outperforms state-of-the-art software-based, GPU-based and conventional hardware SAT solvers by orders of magnitude.
  arXiv  Detail & Related papers  (2023-05-01T02:28:42Z)
• 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)
• Comparing the Digital Annealer with Classical Evolutionary Algorithm [0.0]
  Examples of solvers that use specialised hardware are IBM's Quantum System One and D-wave's Quantum Annealer (QA) and Fujitsu's Digital Annealer (DA)
  arXiv  Detail & Related papers  (2022-05-26T19:04:20Z)
• Ising machines as hardware solvers of combinatorial optimization problems [1.8732539895890135]
  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.
  arXiv  Detail & Related papers  (2022-04-01T08:24:06Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNF-based SAT and MaxSAT solvers are central to logic synthesis and verification systems. In this work, we propose a one-shot model derived from the Transformer architecture to solve the MaxSAT problem.
  arXiv  Detail & Related papers  (2021-07-15T04:47:35Z)

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.