A hybrid Quantum proposal to deal with 3-SAT problem

• URL: http://arxiv.org/abs/2306.04378v2
• Date: Wed, 22 Nov 2023 11:20:36 GMT
• Title: A hybrid Quantum proposal to deal with 3-SAT problem
• Authors: Jose J. Paulet, Luis F. LLana, Hernan I. de la Cruz, Mauro Mezzini, Fernando Cuartero and Fernando L. Pelayo
• Abstract summary: 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.
• Score: 75.38606213726906
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Going as far as possible at SAT problem solving is the main aim of our work. For this sake we have made use of quantum computing from its two, on practice, main models of computation. They have required some reformulations over the former statement of 3-SAT problem in order to accomplish the requirements of both techniques. 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.

Related papers

• Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
  We apply variational quantum algorithm QAOA to a variant of satisfiability problem (SAT): Not-All-Equal SAT. We show that while the runtime of both solvers scales exponentially with the problem size, the scaling for QAOA is smaller for large enough circuit depths.
  arXiv  Detail & Related papers  (2024-01-05T15:11:24Z)
• A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation [1.5201992393140886]
  We develop a parallel quantum SAT solver, which reduces the time complexity in each iteration from linear time O(m) to constant time O(1) by utilising extra entangled qubits. We have proved the correctness of our approaches and demonstrated them in simulations.
  arXiv  Detail & Related papers  (2023-08-07T06:52:06Z)
• 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)
• Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs [1.2179548969182574]
  An experiment is presented to demonstrate the use of Rydberg atoms to solve (i.e., to program and obtain the solution of) the satisfiability (3-SAT) problem.
  arXiv  Detail & Related papers  (2023-02-28T07:49:10Z)
• 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)
• 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)
• 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)
• 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)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)

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.