Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations

• URL: http://arxiv.org/abs/2305.02659v1
• Date: Thu, 4 May 2023 08:57:51 GMT
• Title: Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations
• Authors: Sebastian Zielinski, Jonas N\"u{\ss}lein, Jonas Stein, Thomas Gabor, Claudia Linnhoff-Popien, Sebastian Feld
• Abstract summary: 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.
• Score: 9.466991829376576
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 3SAT instances need to be transformed into instances of Quadratic Unconstrained Binary Optimization (QUBO) to be solved on a quantum annealer. Although it has been shown that the choice of the 3SAT-to-QUBO transformation can impact the solution quality of quantum annealing significantly, currently only a few 3SAT-to-QUBO transformations are known. Additionally, all of the known 3SAT-to-QUBO transformations were created manually (and not procedurally) by an expert using reasoning, which is a rather slow and limiting process. In this paper, 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 provide an in-depth explanation for the idea behind Pattern QUBOs and show its importance by proposing an algorithmic method that uses Pattern QUBOs to create new 3SAT-to-QUBO transformations automatically. As an additional application of Pattern QUBOs and our proposed algorithmic method, we introduce approximate 3SAT-to-QUBO transformations. These transformations sacrifice optimality but use significantly fewer variables (and thus physical qubits on quantum hardware) than non-approximate 3SAT-to-QUBO transformations. We will show that approximate 3SAT-to-QUBO transformations can nevertheless be very effective in some cases.

Related papers

• Solving Max-3SAT Using QUBO Approximation [7.894094635723313]
  We study whether systematically approximating QUBO representations of the MAX-3SAT problem can improve the solution quality when solved on contemporary quantum hardware. In an empirical evaluation, we demonstrate that using our QUBO approximations for solving MAX-3SAT problems on D-Wave's quantum annealer Advantage_System6.4 can yield better results than using state-of-the-art exact QUBO transformations.
  arXiv  Detail & Related papers  (2024-09-24T09:02:34Z)
• Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs [8.364707571011266]
  We propose two methods of using evolutionary algorithms to automatically create QUBO representations of MAX-3SAT problems. We evaluate our created QUBOs on 500 and 1000-clause 3SAT formulae and find competitive performance to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-05-15T11:41:13Z)
• Transformation-Dependent Performance-Enhancement of Digital Annealer for 3-SAT [0.6827423171182154]
  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.
  arXiv  Detail & Related papers  (2023-12-18T19:01:02Z)
• 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)
• 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)
• Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization [10.156623881772362]
  We introduce a novel approach to translate arbitrary 3-SAT instances to Quadratic Unconstrained Binary Optimization (QUBO) Our approach requires fewer couplings and fewer physical qubits than the current state-of-the-art, which results in higher solution quality.
  arXiv  Detail & Related papers  (2023-02-07T15:38:29Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)
• Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions [0.46040036610482665]
  It is useful to have a method for transforming higher degree pseudo-Boolean problems to QUBO format. This paper improves on the existing cubic-to-quadratic transformation approach by minimizing the number of additional variables as well as penalty coefficient.
  arXiv  Detail & Related papers  (2021-07-24T22:13:42Z)
• 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)
• Orbital MCMC [82.54438698903775]
  We propose two practical algorithms for constructing periodic orbits from any diffeomorphism. We also perform an empirical study demonstrating the practical advantages of both kernels.
  arXiv  Detail & Related papers  (2020-10-15T22:25:52Z)

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.