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:2308.03949 · Entropy

Quantum and Quantum-Inspired Stereographic K Nearest-Neighbour Clustering

Alonso Viladomat Jasso, Ark Modi, Roberto Ferrara, Janis Nötzel, Christian Deppe, Maximilian Schaedler, Fred Fung

Published Sep 20, 2023• 13 citations
arXivHTMLPDF

Abstract

Nearest-neighbour clustering is a simple yet powerful machine learning algorithm that finds natural application in the decoding of signals in classical optical-fibre communication systems. Quantum k-means clustering promises a speed-up over the classical k-means algorithm; however, it has been shown to currently not provide this speed-up for decoding optical-fibre signals due to the embedding of classical data, which introduces inaccuracies and slowdowns. Although still not achieving an exponential speed-up for NISQ implementations, this work proposes the generalised inverse stereographic projection as an improved embedding into the Bloch sphere for quantum distance estimation in k-nearest-neighbour clustering, which allows us to get closer to the classical performance. We also use the generalised inverse stereographic projection to develop an analogous classical clustering algorithm and benchmark its accuracy, runtime and convergence for decoding real-world experimental optical-fibre communication data. This proposed `quantum-inspired' algorithm provides an improvement in both the accuracy and convergence rate with respect to the k-means algorithm. Hence, this work presents two main contributions. Firstly, we propose the general inverse stereographic projection into the Bloch sphere as a better embedding for quantum machine learning algorithms; here, we use the problem of clustering quadrature amplitude modulated optical-fibre signals as an example. Secondly, as a purely classical contribution inspired by the first contribution, we propose and benchmark the use of the general inverse stereographic projection and spherical centroid for clustering optical-fibre signals, showing that optimizing the radius yields a consistent improvement in accuracy and convergence rate.

DOI
10.3390/e25091361

Related papers

Testing of Hybrid Quantum-Classical K-Means for Nonlinear Noise Mitigation

Ark Modi, Alonso Viladomat Jasso, Roberto Ferrara +4 more

Nearest-neighbour clustering is a powerful set of heuristic algorithms that find natural application in the decoding of signals transmitted using the$M$-Quadrature Amplitude Modulation ($M$-QAM) protocol. Lloyd et al. proposed a quantum version of the algorithm that promised an exponential speedup. We analyse the performance of this algorithm by simulating the use of a hybrid quantum-classical implementation of it upon 16-QAM and experimental 64-QAM data. We then benchmark the implementation against the classical k-means clustering algorithm. The choice of quantum encoding of the classical data plays a significant role in the performance, as it would for the hybrid quantum-classical implementation of any quantum machine learning algorithm. In this work, we use the popular angle embedding method for data embedding and the swap test for overlap estimation. The algorithm is emulated in software using Qiskit and tested on simulated and real-world experimental data. The discrepancy in accuracy from the perspective of the induced metric of the angle embedding method is discussed, and a thorough analysis regarding the angle embedding method in the context of distance estimation is provided. We detail an experimental optic fibre setup as well, from which we collect 64-QAM data. This is the dataset upon which the algorithms are benchmarked. Finally, some promising current and future directions for further research are discussed.

arXiv:2308.03540•Globecom•Dec 4, 2023•3 citations

Quantum K-medians Algorithm Using Parallel Euclidean Distance Estimator

Amanuel Tamirat Getachew

Quantum machine learning, though in its initial stage, has demonstrated its potential to speed up some of the costly machine learning calculations when compared to the existing classical approaches. Among the challenging subroutines, computing distance between with the large and high-dimensional data sets by the classical k-medians clustering algorithm is one of them. To tackle this challenge, this paper proposes an efficient quantum k-medians clustering algorithm using the powerful quantum Euclidean estimator algorithm. The proposed quantum k-medians algorithm has provided an exponential speed up as compared to the classical version of it. If and only if we allow the input and the output vectors to be quantum states. The proposed algorithm implementation handled in python with the help of third-party module known as QISKit. The implemented quantum algorithm was executed on the IBM Quantum simulators through cloud. The results from the experiment and simulation suggest that quantum distance estimator algorithms could give benefits for other distance-based machine learning algorithms like k-nearest neighbor classification, support vector machine, hierarchical clustering and k-means clustering. This work sheds light on the bright future of the age of big data making use of exponential speed up provided by quantum theory.

arXiv:2012.11139•Dec 21, 2020•2 citations

Hybrid Quantum--Classical k-Means Clustering via Quantum Feature Maps

Syed M. Abdullah, Alisha Baba, Muhammad Siddique +1 more

Clustering is one of the most fundamental tasks in machine learning, and the k-means clustering algorithm is perhaps one of the most widely used clustering algorithms. However, it suffers from several limitations, such as sensitivity to centroid initialization, difficulty capturing non-linear structure, and poor performance in high-dimensional spaces. Recent work has proposed improved initialization strategies and quantum-assisted distance computation, but the similarity metric itself has largely remained classical. In this study, we propose a quantum-enhanced variant of k-means that replaces the Euclidean distance with a quantum kernel derived from the inner product between feature-mapped quantum states. Using the Iris dataset, we use multiple quantum feature maps, including entangled SU2 and ZZ circuits, to embed classical data into a higher-dimensional Hilbert space where cluster structures become more separable. We will also be testing using another dataset, namely the breast cancer dataset. Similarity between data points is computed through the inner product between two states. Our results show that this approach achieves improved clustering stability and competitive accuracy compared to the classical algorithm, with the SU2 feature map yielding an accuracy of 88.6 % on the Iris dataset and 91.0 % on the breast cancer dataset, despite operating on NISQ-feasible shallow circuits. These findings suggest that quantum kernels provide a richer similarity landscape than traditional distance metrics, offering a promising path toward more robust unsupervised learning in the NISQ era.

quant-pharXiv:2604.07873•Apr 10, 2026•0 citations

Multi-class quantum k-nearest-neighbour classification in a single quantum circuit

Razieh Abdolahi, M. Reza Soleymani, Walaa Hamouda

Abstract In this paper we present a novel quantum k-nearest-neighbour circuit. The k-nearest-neighbour problem asks for the K closest stored points to a query among all data; quantum interference allows every stored point of every class to be compared in a single execution, a substantial computational gain. Quantum k-nearest-neighbour designs to date have rested on assumed primitives—quantum random-access memory, oracle access, amplitude-amplified search—which remain hypothetical and serve mainly to set limits on what the algorithms could achieve, or they restrict the distance metric or the number of classes. Our design uses none of these: no quantum random-access memory, no oracle, no metric restriction, no binary-class limit, and every operation is a practically implementable gate. Training members of each class are loaded into a dedicated register in superposition, a butterfly network of controlled-SWAP stages routes all classes to a common comparison position, and the class and member identity of every neighbour is read directly from the measurement statistics. The architecture rests on closed-form expressions for the post-selected probabilities and a geometric analysis showing that inverse stereographic projection carries the Euclidean nearest-neighbour ranking onto state fidelity with a sharp distortion bound. In simulation the circuit reproduces its intended decision rule exactly, and its accuracy matches classical k-nearest neighbours across a controlled benchmark at a realistic measurement budget. Every loading and sampling cost is stated in full—costs that most prior work hides by assuming quantum random-access memory.

•Oct 8, 2026•0 citations

Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning

Nathan Wiebe, Ashish Kapoor, Krysta M. Svore

We present quantum algorithms for performing nearest-neighbor learning and $k$--means clustering. At the core of our algorithms are fast and coherent quantum methods for computing the Euclidean distance both directly and via the inner product which we couple with methods for performing amplitude estimation that do not require measurement. We prove upper bounds on the number of queries to the input data required to compute such distances and find the nearest vector to a given test example. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to Monte Carlo algorithms. We also study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.

Quantum Information and Computation•Mar 1, 2015•243 citations

Quantum-data-adaptive clustering algorithm

Meng-Ting Yang, Yu Huang, Lu Yan +1 more

Abstract Quantum state clustering provides a powerful tool for quantum information processing. This paper focuses on the classification of single-qubit pure and mixed states via clustering algorithms, and discovers that the classical K -means algorithm has two limitations in clustering quantum states: the Euclidean distance cannot accurately reflect the similarity between quantum states, and the centroid update based on the arithmetic mean frequently fails to yield valid quantum states. To address these issues, we propose two distance metrics for quantum states: the dynamic distance and the Bloch distance, and adopt the K -medoids method to update the centroid, ensuring that the cluster center always remains a valid quantum state, thereby designing a quantum-data-adaptive clustering algorithm. Experimental results show that the dynamic distance achieves a clustering accuracy as high as 91.4 % , but at the cost of higher computational complexity. In contrast, the Bloch distance significantly reduces computational complexity while maintaining clustering performance comparable to that of the dynamic distance, achieving a clustering accuracy of 87.4 % . This paper provides a practical method for achieving efficient and reliable clustering of single-qubit quantum states.

Laser Physics Letters•Jul 1, 2026•0 citations
Nearest-neighbour clustering is a simple yet powerful machine learning algorithm that finds natural application in the decoding of signals in classical optical-fibre communication systems. Quantum k-means clustering promises a speed-up over the classical k-means algorithm; however, it has been shown to currently not provide this speed-up for decoding optical-fibre signals due to the embedding of classical data, which introduces inaccuracies and slowdowns. Although still not achieving an exponential speed-up for NISQ implementations, this work proposes the generalised inverse stereographic projection as an improved embedding into the Bloch sphere for quantum distance estimation in k-nearest-neighbour clustering, which allows us to get closer to the classical performance. We also use the generalised inverse stereographic projection to develop an analogous classical clustering algorithm and benchmark its accuracy, runtime and convergence for decoding real-world experimental optical-fibre communication data. This proposed `quantum-inspired' algorithm provides an improvement in both the accuracy and convergence rate with respect to the k-means algorithm. Hence, this work presents two main contributions. Firstly, we propose the general inverse stereographic projection into the Bloch sphere as a better embedding for quantum machine learning algorithms; here, we use the problem of clustering quadrature amplitude modulated optical-fibre signals as an example. Secondly, as a purely classical contribution inspired by the first contribution, we propose and benchmark the use of the general inverse stereographic projection and spherical centroid for clustering optical-fibre signals, showing that optimizing the radius yields a consistent improvement in accuracy and convergence rate.
Nearest-neighbour clustering is a powerful set of heuristic algorithms that find natural application in the decoding of signals transmitted using theMMM-Quadrature Amplitude Modulation (MMM-QAM) protocol. Lloyd et al. proposed a quantum version of the algorithm that promised an exponential speedup. We analyse the performance of this algorithm by simulating the use of a hybrid quantum-classical implementation of it upon 16-QAM and experimental 64-QAM data. We then benchmark the implementation against the classical k-means clustering algorithm. The choice of quantum encoding of the classical data plays a significant role in the performance, as it would for the hybrid quantum-classical implementation of any quantum machine learning algorithm. In this work, we use the popular angle embedding method for data embedding and the swap test for overlap estimation. The algorithm is emulated in software using Qiskit and tested on simulated and real-world experimental data. The discrepancy in accuracy from the perspective of the induced metric of the angle embedding method is discussed, and a thorough analysis regarding the angle embedding method in the context of distance estimation is provided. We detail an experimental optic fibre setup as well, from which we collect 64-QAM data. This is the dataset upon which the algorithms are benchmarked. Finally, some promising current and future directions for further research are discussed.
Quantum machine learning, though in its initial stage, has demonstrated its potential to speed up some of the costly machine learning calculations when compared to the existing classical approaches. Among the challenging subroutines, computing distance between with the large and high-dimensional data sets by the classical k-medians clustering algorithm is one of them. To tackle this challenge, this paper proposes an efficient quantum k-medians clustering algorithm using the powerful quantum Euclidean estimator algorithm. The proposed quantum k-medians algorithm has provided an exponential speed up as compared to the classical version of it. If and only if we allow the input and the output vectors to be quantum states. The proposed algorithm implementation handled in python with the help of third-party module known as QISKit. The implemented quantum algorithm was executed on the IBM Quantum simulators through cloud. The results from the experiment and simulation suggest that quantum distance estimator algorithms could give benefits for other distance-based machine learning algorithms like k-nearest neighbor classification, support vector machine, hierarchical clustering and k-means clustering. This work sheds light on the bright future of the age of big data making use of exponential speed up provided by quantum theory.
Clustering is one of the most fundamental tasks in machine learning, and the k-means clustering algorithm is perhaps one of the most widely used clustering algorithms. However, it suffers from several limitations, such as sensitivity to centroid initialization, difficulty capturing non-linear structure, and poor performance in high-dimensional spaces. Recent work has proposed improved initialization strategies and quantum-assisted distance computation, but the similarity metric itself has largely remained classical. In this study, we propose a quantum-enhanced variant of k-means that replaces the Euclidean distance with a quantum kernel derived from the inner product between feature-mapped quantum states. Using the Iris dataset, we use multiple quantum feature maps, including entangled SU2 and ZZ circuits, to embed classical data into a higher-dimensional Hilbert space where cluster structures become more separable. We will also be testing using another dataset, namely the breast cancer dataset. Similarity between data points is computed through the inner product between two states. Our results show that this approach achieves improved clustering stability and competitive accuracy compared to the classical algorithm, with the SU2 feature map yielding an accuracy of 88.6 % on the Iris dataset and 91.0 % on the breast cancer dataset, despite operating on NISQ-feasible shallow circuits. These findings suggest that quantum kernels provide a richer similarity landscape than traditional distance metrics, offering a promising path toward more robust unsupervised learning in the NISQ era.
Abstract In this paper we present a novel quantum k-nearest-neighbour circuit. The k-nearest-neighbour problem asks for the K closest stored points to a query among all data; quantum interference allows every stored point of every class to be compared in a single execution, a substantial computational gain. Quantum k-nearest-neighbour designs to date have rested on assumed primitives—quantum random-access memory, oracle access, amplitude-amplified search—which remain hypothetical and serve mainly to set limits on what the algorithms could achieve, or they restrict the distance metric or the number of classes. Our design uses none of these: no quantum random-access memory, no oracle, no metric restriction, no binary-class limit, and every operation is a practically implementable gate. Training members of each class are loaded into a dedicated register in superposition, a butterfly network of controlled-SWAP stages routes all classes to a common comparison position, and the class and member identity of every neighbour is read directly from the measurement statistics. The architecture rests on closed-form expressions for the post-selected probabilities and a geometric analysis showing that inverse stereographic projection carries the Euclidean nearest-neighbour ranking onto state fidelity with a sharp distortion bound. In simulation the circuit reproduces its intended decision rule exactly, and its accuracy matches classical k-nearest neighbours across a controlled benchmark at a realistic measurement budget. Every loading and sampling cost is stated in full—costs that most prior work hides by assuming quantum random-access memory.
We present quantum algorithms for performing nearest-neighbor learning and kkk--means clustering. At the core of our algorithms are fast and coherent quantum methods for computing the Euclidean distance both directly and via the inner product which we couple with methods for performing amplitude estimation that do not require measurement. We prove upper bounds on the number of queries to the input data required to compute such distances and find the nearest vector to a given test example. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to Monte Carlo algorithms. We also study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.
Abstract Quantum state clustering provides a powerful tool for quantum information processing. This paper focuses on the classification of single-qubit pure and mixed states via clustering algorithms, and discovers that the classical K -means algorithm has two limitations in clustering quantum states: the Euclidean distance cannot accurately reflect the similarity between quantum states, and the centroid update based on the arithmetic mean frequently fails to yield valid quantum states. To address these issues, we propose two distance metrics for quantum states: the dynamic distance and the Bloch distance, and adopt the K -medoids method to update the centroid, ensuring that the cluster center always remains a valid quantum state, thereby designing a quantum-data-adaptive clustering algorithm. Experimental results show that the dynamic distance achieves a clustering accuracy as high as 91.4 % , but at the cost of higher computational complexity. In contrast, the Bloch distance significantly reduces computational complexity while maintaining clustering performance comparable to that of the dynamic distance, achieving a clustering accuracy of 87.4 % . This paper provides a practical method for achieving efficient and reliable clustering of single-qubit quantum states.