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.
Nearest-neighbour clustering is a powerful set of heuristic algorithms that find natural application in the decoding of signals transmitted using theM-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.
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 not currently 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.
Quantum machine learning promises computational advantages for certain tasks, yet rigorous empirical evaluation of quantum clustering algorithms against classical baselines remains limited. This paper presents a comprehensive implementation and comparative analysis of two quantum K-means clustering algorithms—SWAP Test-based and Quantum Fidelity-based—against classical K-means on benchmark datasets. Both quantum approaches employ amplitude encoding to map classical data into quantum state amplitudes and use quantum-native distance metrics derived from inner products in Hilbert space. All three methods are evaluated on the ENB2012 energy efficiency dataset (768 samples, 8 features) and a synthetically expanded high-dimensional dataset (4,998 samples, 16 features), measuring silhouette score, inertia, and wall-clock execution time across cluster counts k ∈ {2, . . . , 7}. The experiments, conducted on Qiskit’s AerSimulator and Statevector backends, show that classical K-means achieves substantially higher silhouette scores (0.391 vs. 0.031 on the original dataset) and orders-of-magnitude faster execution. A rigorous analysis attributes these results to three factors: (i) the information loss inherent in amplitude encoding normalization, (ii) the geometric mismatch between Euclidean and Hilbert-space distance metrics, and (iii) the absence of quantum parallelism in classical simulation. The implications for quantum advantage in unsupervised learning are discussed and concrete requirements for near-term quantum hardware to achieve competitive clustering performance are outlined.
This work introduces a quantum K-Nearest Neighbor (K-NN) classifier algorithm. The algorithm utilizes angle encoding through a Quantum Random Access Memory (QRAM) using n number of qubit addresses with O(log(n)) space complexity. It incorporates Grover’s algorithm and the quantum SWAP-Test to identify similar states and determine the nearest neighbors with high probability, achieving Om search complexity, where m is the qubit address. We implement a simulation of the algorithm using IBM’s Qiskit with GPU support, applying it to the Iris and MNIST datasets with two different angle encodings. The experiments employ multiple QRAM cell sizes (8, 16, 32, 64, 128) and perform ten trials per size. According to the performance, accuracy values in the Iris dataset range from 89.3 ± 5.78% to 94.0 ± 1.56%. The MNIST dataset’s mean binary accuracy values range from 79.45 ± 18.84% to 94.00 ± 2.11% for classes 0 and 1. Additionally, a comparison of the results of this proposed approach with different state-of-the-art versions of QK-NN and the classical K-NN using Scikit-learn. This method achieves a 96.4 ± 2.22% accuracy in the Iris dataset. Finally, this proposal contributes an experimental result to the state of the art for the MNIST dataset, achieving an accuracy of 96.55 ± 2.00%. This work presents a new implementation proposal for QK-NN and conducts multiple experiments that yield more robust results than previous implementations. Although our average performance approaches still need to surpass the classic results, an experimental increase in the size of QRAM or the amount of data to encode is not achieved due to limitations. However, our results show promising improvement when considering working with more feature numbers and accommodating more data in the QRAM.
Classical machine learning algorithms are increasingly challenged by the growing complexity of datasets, motivating the exploration of quantum computing as a potential solution. However, current literature lacks comprehensive empirical analyses directly benchmarking classical algorithms against quantum-assisted counterparts for small but high-dimensional standardized datasets. This research aims to address this gap by comparing the performance of the k-means clustering algorithm on classical and hybrid quantum-classical computing platforms. Using a small dataset, we assess computational speed, clustering accuracy, and scalability. Our findings reveal that while hybrid quantum implementations offer theoretical benefits, in practice they incur significantly higher computational overhead and reduced clustering accuracy due to current technological constraints. These insights highlight the critical need for improved quantum hardware and algorithms, guiding future research directions in quantum-enhanced machine learning.
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.
This study explores the integration of quantum data embedding techniques into classical machine learning (ML) algorithms; to assess performance enhancements and computational implications across a spectrum of models. We explored various classical-to-quantum mapping methods; ranging from basis encoding and angle encoding to amplitude encoding; for encoding classical data. We conducted an extensive empirical study encompassing popular ML algorithms, including Logistic Regression, K-Nearest Neighbors, Support Vector Machines, and ensemble methods like Random Forest, LightGBM, AdaBoost, and CatBoost. Our findings reveal that quantum data embedding contributes to improved classification accuracy and F1 scores, particularly notable in models that inherently benefit from enhanced feature representation. We observed nuanced effects on running time, with low-complexity models exhibiting moderate increases and more computationally intensive models experiencing discernible changes. Notably, ensemble methods demonstrated a favorable balance between performance gains and computational overhead. This study underscores the potential of quantum data embedding to enhance classical ML models and emphasizes the importance of weighing performance improvements against computational costs. Future research may involve refining quantum encoding processes to optimize computational efficiency and explore scalability for real-world applications. Our work contributes to the growing body of knowledge on the intersection of quantum computing and classical machine learning, offering insights for researchers and practitioners seeking to harness the advantages of quantum-inspired techniques in practical scenarios.