Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing

• URL: http://arxiv.org/abs/2310.12153v2
• Date: Wed, 1 May 2024 15:54:34 GMT
• Title: Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing
• Authors: Jan-Nico Zaech, Martin Danelljan, Tolga Birdal, Luc Van Gool,
• Abstract summary: 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.
• Score: 93.83016310295804
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adiabatic quantum computing (AQC) is a promising approach for discrete and often NP-hard optimization problems. Current AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for many computer vision tasks. Despite requiring multiple measurements from the noisy AQC, current approaches only utilize the best measurement, discarding information contained in the remaining ones. 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.

Related papers

• Identifying Bottlenecks of NISQ-friendly HHL algorithms [0.0]
  We study noise resilience of NISQ-adaptation Iterative QPE and its HHL algorithm. Results indicate that noise mitigation techniques, such as Qiskit readout and Mthree readout packages, are insufficient for enabling results recovery even in the small instances tested here.
  arXiv  Detail & Related papers  (2024-06-10T14:11:27Z)
• 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)
• Multi-sequence alignment using the Quantum Approximate Optimization Algorithm [0.0]
  We present a Hamiltonian formulation and implementation of the Multiple Sequence Alignment problem with the variational Quantum Approximate Optimization Algorithm (QAOA) We consider a small instance of our QAOA-MSA algorithm in both a quantum simulator and its performance on an actual quantum computer. While the ideal solution to the instance of MSA investigated is shown to be the most probable state sampled for a shallow p5 quantum circuit, the level of noise in current devices is still a formidable challenge.
  arXiv  Detail & Related papers  (2023-08-23T12:46:24Z)
• Exploring the Potential of Qutrits for Quantum Optimization of Graph Coloring [0.0]
  Qutrits may be useful in solving some problems on near-term devices. We run noiseless simulations using PennyLane to compare the formulation against qubit-based QAOA. This work suggests that qutrits may be useful in solving some problems on near-term devices, however further work is required to assess their potential in a noisy environment.
  arXiv  Detail & Related papers  (2023-08-15T21:31:37Z)
• Potential and limitations of quantum extreme learning machines [55.41644538483948]
  We present a framework to model QRCs and QELMs, showing that they can be concisely described via single effective measurements. Our analysis paves the way to a more thorough understanding of the capabilities and limitations of both QELMs and QRCs.
  arXiv  Detail & Related papers  (2022-10-03T09:32:28Z)
• 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)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• 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)

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.