Transformation-Dependent Performance-Enhancement of Digital Annealer for 3-SAT

• URL: http://arxiv.org/abs/2312.11645v1
• Date: Mon, 18 Dec 2023 19:01:02 GMT
• Title: Transformation-Dependent Performance-Enhancement of Digital Annealer for 3-SAT
• Authors: Christian M\"unch, Fritz Schinkel, Sebastian Zielinski, Stefan Walter
• Abstract summary: We study a hard class of problems which can be formulated as QUBOs, namely Boolean satisfiability (SAT) problems, and specifically 3-SAT. We study the transformations' influence on the problem solution, using Digital Annealer as a special-purpose solver. We show that the Digital Annealer outperforms a quantum annealer in solving hard 3-SAT instances.
• Score: 0.6827423171182154
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quadratic Unconstrained Binary Optimization (QUBO) problems are NP-hard problems and many real-world problems can be formulated as QUBO. Currently there are no algorithms known that can solve arbitrary instances of NP-hard problems efficiently. Therefore special-purpose hardware such as Digital Annealer, other Ising machines, as well as quantum annealers might lead to benefits in solving such problems. We study a particularly hard class of problems which can be formulated as QUBOs, namely Boolean satisfiability (SAT) problems, and specifically 3-SAT. One intriguing aspect about 3-SAT problems is that there are different transformations from 3-SAT to QUBO. We study the transformations' influence on the problem solution, using Digital Annealer as a special-purpose solver. Besides well-known transformations we investigate a novel in this context not yet discussed transformation, using less auxiliary variables and leading to very good performance. Using exact diagonalization, we explain the differences in performance originating from the different transformations. We envision that this knowledge allows for specifically engineering transformations that improve a solvers capacity to find high quality solutions. Furthermore, we show that the Digital Annealer outperforms a quantum annealer in solving hard 3-SAT instances.

Related papers

• An encoding of argumentation problems using quadratic unconstrained binary optimization [1.104960878651584]
  We develop a way to encode several NP-Complete problems in Abstract Argumentation to Quadratic Unconstrained Binary Optimization problems. With the QUBO formulation, exploiting new computing architectures, such as Quantum and Digital Annealers, is possible. We performed tests to prove the correctness and applicability of classical problems in Argumentation and enforcement of argument sets.
  arXiv  Detail & Related papers  (2024-09-09T11:29:46Z)
• 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)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  This paper presents and describes a hybrid quantum computing strategy for solving 3-SAT problems. The performance of this approximation has been tested over a set of representative scenarios when dealing with 3-SAT from the quantum computing perspective.
  arXiv  Detail & Related papers  (2023-06-07T12:19:22Z)
• Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations [9.466991829376576]
  We will introduce the name Pattern QUBO for a concept that has been used implicitly in the construction of 3SAT-to-QUBO transformations before. We will show that approximate 3SAT-to-QUBO transformations can nevertheless be very effective in some cases.
  arXiv  Detail & Related papers  (2023-05-04T08:57:51Z)
• Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study [9.466991829376576]
  We show that the choice of QUBO transformation can significantly impact the number of correct solutions the quantum annealer returns. We also empirically show that the number of different quadratic values of a QUBO instance, combined with their range, can significantly impact the solution quality.
  arXiv  Detail & Related papers  (2023-05-01T08:40:58Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  The amplitude amplification algorithm can be applied to unstructured search for satisfying variable assignments. The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy Intermediate-Scale Quantum devices. We introduce amplitude amplification-inspired variants of QAOA to improve the success probability for 3SAT.
  arXiv  Detail & Related papers  (2023-03-02T11:52:39Z)
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm [4.03537866744963]
  We show that the adaptive-bias QAOA (ab-QAOA) greatly improves performance in the hard region of the 3-SAT problems and hard region of the Max-3-SAT problems. Our work paves the way for realizing quantum advantages for optimization problems on NISQ devices.
  arXiv  Detail & Related papers  (2022-10-06T11:25:26Z)
• 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)
• Machine Learning Methods in Solving the Boolean Satisfiability Problem [72.21206588430645]
  The paper reviews the recent literature on solving the Boolean satisfiability problem (SAT) with machine learning techniques. We examine the evolving ML-SAT solvers from naive classifiers with handcrafted features to the emerging end-to-end SAT solvers such as NeuroSAT.
  arXiv  Detail & Related papers  (2022-03-02T05:14:12Z)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)

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.