Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study

• URL: http://arxiv.org/abs/2305.00720v1
• Date: Mon, 1 May 2023 08:40:58 GMT
• Title: Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study
• Authors: Sebastian Zielinski, Jonas N\"u{\ss}lein, Jonas Stein, Thomas Gabor, Claudia Linnhoff-Popien, Sebastian Feld
• Abstract summary: 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.
• Score: 9.466991829376576
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: To solve 3SAT instances on quantum annealers they need to be transformed to an instance of Quadratic Unconstrained Binary Optimization (QUBO). When there are multiple transformations available, the question arises whether different transformations lead to differences in the obtained solution quality. Thus, in this paper we conduct an empirical benchmark study, in which we compare four structurally different QUBO transformations for the 3SAT problem with regards to the solution quality on D-Wave's Advantage_system4.1. We show that the choice of QUBO transformation can significantly impact the number of correct solutions the quantum annealer returns. Furthermore, we show that the size of a QUBO instance (i.e., the dimension of the QUBO matrix) is not a sufficient predictor for solution quality, as larger QUBO instances may produce better results than smaller QUBO instances for the same problem. 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.

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)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• 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)
• 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)
• 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-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• 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)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm. Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
  arXiv  Detail & Related papers  (2020-08-12T08:52:50Z)
• Modeling Linear Inequality Constraints in Quadratic Binary Optimization for Variational Quantum Eigensolver [0.0]
  This paper introduces the use of tailored variational forms for variational quantum eigensolver. Four constraints that usually appear in several optimization problems are modeled. The main advantage of the proposed methodology is that the number of parameters on the variational form remain constant.
  arXiv  Detail & Related papers  (2020-07-26T23:36:22Z)

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.