Investigating the Relation Between Problem Hardness and QUBO Properties

• URL: http://arxiv.org/abs/2404.02751v1
• Date: Wed, 3 Apr 2024 13:53:03 GMT
• Title: Investigating the Relation Between Problem Hardness and QUBO Properties
• Authors: Thore Gerlach, Sascha Mücke,
• Abstract summary: This work aims to shed some light on the relationship between the problems' properties. We analyze two well-known problems from Machine Learning, namely Clustering and Support Vector Machine (SVM) training. An empirical evaluation provides interesting insights, showing that the spectral gap of Clustering QUBO instances positively correlates with data separability, while for SVM QUBO the opposite is true.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization problems, integral to various scientific and industrial applications, often vary significantly in their complexity and computational difficulty. Transforming such problems into Quadratic Unconstrained Binary Optimization (QUBO) has regained considerable research attention in recent decades due to the central role of QUBO in Quantum Annealing. This work aims to shed some light on the relationship between the problems' properties. In particular, we examine how the spectral gap of the QUBO formulation correlates with the original problem, since it has an impact on how efficiently it can be solved on quantum computers. We analyze two well-known problems from Machine Learning, namely Clustering and Support Vector Machine (SVM) training, regarding the spectral gaps of their respective QUBO counterparts. An empirical evaluation provides interesting insights, showing that the spectral gap of Clustering QUBO instances positively correlates with data separability, while for SVM QUBO the opposite is true.

Related papers

• Solving the Turbine Balancing Problem using Quantum Annealing [0.0]
  We describe how the Turbine Balancing Problem can be solved with quantum computing. Small yet relevant instances occur in industry, which makes the problem interesting for early quantum computing benchmarks.
  arXiv  Detail & Related papers  (2024-05-10T11:52:40Z)
• Trade-off between Bagging and Boosting for quantum separability-entanglement classification [0.0]
  The pros and cons of the proposed random under-sampling boost CHA (RUSBCHA) for the quantum separability problem are compared. The outcomes suggest that RUSBCHA is an alternative to the BCHA approach.
  arXiv  Detail & Related papers  (2024-01-22T15:29:35Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks. In this work, we explore the potential of using this information for probabilistic balanced k-means clustering. Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost. This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
  arXiv  Detail & Related papers  (2023-10-18T17:59:45Z)
• Quantum Vision Clustering [10.360126989185261]
  We present the first clustering formulation tailored for resolution using Adiabatic quantum computing. The proposed approach demonstrates high competitiveness compared to state-of-the-art optimization-based methods. This work showcases the solvability of the proposed clustering problem on current-generation real quantum computers for small examples.
  arXiv  Detail & Related papers  (2023-09-18T16:15:16Z)
• Biclustering Algorithms Based on Metaheuristics: A Review [0.0]
  Biclustering is an unsupervised machine learning technique that simultaneously clusters rows and columns in a data matrix. Finding significant biclusters is an NP-hard problem that can be formulated as an optimization problem. Different metaheuristics have been applied to biclustering problems because of their exploratory capability of solving complex optimization problems in reasonable time.
  arXiv  Detail & Related papers  (2022-03-30T12:16:32Z)
• Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees [115.08148491584997]
  We present the first theoretically grounded distributed methods for solving variational inequalities and saddle point problems using compressed communication: MASHA1 and MASHA2. New algorithms support bidirectional compressions, and also can be modified for setting with batches and for federated learning with partial participation of clients.
  arXiv  Detail & Related papers  (2021-10-07T10:04:32Z)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems. Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
  arXiv  Detail & Related papers  (2021-09-06T14:35:15Z)
• Machine Learning Framework for Quantum Sampling of Highly-Constrained, Continuous Optimization Problems [101.18253437732933]
  We develop a generic, machine learning-based framework for mapping continuous-space inverse design problems into surrogate unconstrained binary optimization problems. We showcase the framework's performance on two inverse design problems by optimizing thermal emitter topologies for thermophotovoltaic applications and (ii) diffractive meta-gratings for highly efficient beam steering.
  arXiv  Detail & Related papers  (2021-05-06T02:22:23Z)
• Bottleneck Problems: Information and Estimation-Theoretic View [2.7793394375935088]
  Information bottleneck (IB) and privacy funnel (PF) are two closely related optimization problems. We show how to evaluate bottleneck problems in closed form by equivalently expressing them in terms of lower envelope or upper envelope of certain functions.
  arXiv  Detail & Related papers  (2020-11-12T05:16:44Z)
• Einselection from incompatible decoherence channels [62.997667081978825]
  We analyze an open quantum dynamics inspired by CQED experiments with two non-commuting Lindblad operators. We show that Fock states remain the most robust states to decoherence up to a critical coupling.
  arXiv  Detail & Related papers  (2020-01-29T14:15:19Z)

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.