Balanced k-Means Clustering on an Adiabatic Quantum Computer

• URL: http://arxiv.org/abs/2008.04419v1
• Date: Mon, 10 Aug 2020 21:15:47 GMT
• Title: Balanced k-Means Clustering on an Adiabatic Quantum Computer
• Authors: Davis Arthur, Prasanna Date
• Abstract summary: We present a quantum approach to solving the balanced $k$-means clustering training problem on the D-Wave 2000Q adiabatic quantum computer. Existing classical approaches scale poorly for large datasets and only guarantee a locally optimal solution.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adiabatic quantum computers are a promising platform for approximately solving challenging optimization problems. We present a quantum approach to solving the balanced $k$-means clustering training problem on the D-Wave 2000Q adiabatic quantum computer. Existing classical approaches scale poorly for large datasets and only guarantee a locally optimal solution. We show that our quantum approach better targets the global solution of the training problem, while achieving better theoretic scalability on large datasets. We test our quantum approach on a number of small problems, and observe clustering performance similar to the best classical algorithms.

Related papers

• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• Adiabatic Quantum Support Vector Machines [0.8445084028034932]
  We describe an adiabatic quantum approach for training support vector machines. We show that the time complexity of our quantum approach is an order of magnitude better than the classical approach.
  arXiv  Detail & Related papers  (2024-01-23T04:50:13Z)
• 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)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Quantum spectral clustering algorithm for unsupervised learning [0.8399688944263843]
  We propose a circuit design to implement spectral clustering on a quantum processor with a substantial speedup. Compared with the established quantum $k$-means algorithms, our method does not require a quantum random access memory or a quantum adiabatic process.
  arXiv  Detail & Related papers  (2022-03-07T05:06:47Z)
• 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)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.