Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2008.04419 · Quantum Information Processing

Balanced k-means clustering on an adiabatic quantum computer

Davis Arthur, Prasanna Date

Published Sep 1, 2021• 64 citations
arXivHTMLPDF
DOI
10.1007/s11128-021-03240-8

Related papers

Ising Models for Binary Clustering via Adiabatic Quantum Computing

Christian Bauckhage, E. Brito, Kostadin Cvejoski +3 more

Lecture notes in computer science•Jan 1, 2018•22 citations

Quantum-Inspired Cluster Optimization: K-Means Versus Quantum K-Means

Manan B. Jain, Kapil G. Ratan, Rashmi Benni

Lecture notes in networks and systems•Jan 1, 2025•0 citations

Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing

Jan-Nico Zaech, Martin Danelljan, Tolga Birdal +1 more

Adiabatic quantum computing (AQC) is a promising approach for discrete and often NP-hard optimization prob-lems. Current AQCs allow to implement problems of re-search interest, which has sparked the development of quan-tum representations for many computer vision tasks. De-spite requiring multiple measurements from the noisy AQC, current approaches only utilize the best measurement, dis-carding 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 ad-ditional 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:2310.12153•IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings•Jun 16, 2024•4 citations

QUBO formulations for training machine learning models

Prasanna Date, Davis Arthur, Lauren Pusey-Nazzaro

Training machine learning models on classical computers is usually a time and compute intensive process. With Moore's law nearing its inevitable end and an ever-increasing demand for large-scale data analysis using machine learning, we must leverage non-conventional computing paradigms like quantum computing to train machine learning models efficiently. Adiabatic quantum computers can approximately solve NP-hard problems, such as the quadratic unconstrained binary optimization (QUBO), faster than classical computers. Since many machine learning problems are also NP-hard, we believe adiabatic quantum computers might be instrumental in training machine learning models efficiently in the post Moore's law era. In order to solve problems on adiabatic quantum computers, they must be formulated as QUBO problems, which is very challenging. In this paper, we formulate the training problems of three machine learning models-linear regression, support vector machine (SVM) and balanced k-means clustering-as QUBO problems, making them conducive to be trained on adiabatic quantum computers. We also analyze the computational complexities of our formulations and compare them to corresponding state-of-the-art classical approaches. We show that the time and space complexities of our formulations are better (in case of SVM and balanced k-means clustering) or equivalent (in case of linear regression) to their classical counterparts.

arXiv:2008.02369•Scientific Reports•May 11, 2021•130 citations

A quantum algorithm of K-means toward practical use

Hiroshi Ohno

Quantum Information Processing•Apr 1, 2022•15 citations

Balanced K-means using Quantum annealing

Ahmed Zaiou, Younès Bennani, Basarab Mateï +1 more

In this paper, we propose a new quantum version of the Balanced K-means algorithm in the D-wave quantum annealer. D-wave 2000Q quantum computer has been used by many papers in the last few years to solve optimization problems and for finding the global minimum of the balanced K-means optimization problem. However, in this paper, we modify the quadratic unconstrained binary optimization (QUBO) formulation of the Balanced K-means that has been proposed in a recent paper. Our modification is trained on different data sets: Iris, Wine and Breast Cancer. Also, we performed a comparative analysis between the two approaches (our approach and the paper's approach) to find the one that assigns the largest number of data to clusters and we also use the Davies-Bouldi metric to prove that our method gives the best clustering.

IEEE Symposium Series on Computational Intelligence (SSCI)•Dec 5, 2021•8 citations
Adiabatic quantum computing (AQC) is a promising approach for discrete and often NP-hard optimization prob-lems. Current AQCs allow to implement problems of re-search interest, which has sparked the development of quan-tum representations for many computer vision tasks. De-spite requiring multiple measurements from the noisy AQC, current approaches only utilize the best measurement, dis-carding 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 ad-ditional 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.
Training machine learning models on classical computers is usually a time and compute intensive process. With Moore's law nearing its inevitable end and an ever-increasing demand for large-scale data analysis using machine learning, we must leverage non-conventional computing paradigms like quantum computing to train machine learning models efficiently. Adiabatic quantum computers can approximately solve NP-hard problems, such as the quadratic unconstrained binary optimization (QUBO), faster than classical computers. Since many machine learning problems are also NP-hard, we believe adiabatic quantum computers might be instrumental in training machine learning models efficiently in the post Moore's law era. In order to solve problems on adiabatic quantum computers, they must be formulated as QUBO problems, which is very challenging. In this paper, we formulate the training problems of three machine learning models-linear regression, support vector machine (SVM) and balanced k-means clustering-as QUBO problems, making them conducive to be trained on adiabatic quantum computers. We also analyze the computational complexities of our formulations and compare them to corresponding state-of-the-art classical approaches. We show that the time and space complexities of our formulations are better (in case of SVM and balanced k-means clustering) or equivalent (in case of linear regression) to their classical counterparts.
In this paper, we propose a new quantum version of the Balanced K-means algorithm in the D-wave quantum annealer. D-wave 2000Q quantum computer has been used by many papers in the last few years to solve optimization problems and for finding the global minimum of the balanced K-means optimization problem. However, in this paper, we modify the quadratic unconstrained binary optimization (QUBO) formulation of the Balanced K-means that has been proposed in a recent paper. Our modification is trained on different data sets: Iris, Wine and Breast Cancer. Also, we performed a comparative analysis between the two approaches (our approach and the paper's approach) to find the one that assigns the largest number of data to clusters and we also use the Davies-Bouldi metric to prove that our method gives the best clustering.