International literature suggests that quantum computers hold the potential for exponential speedup over classical computers, particularly for certain types of optimization problems. However, the practical application of quantum k-means is currently limited by the capabilities of available quantum hardware. As quantum technology improves and more efficient algorithms are developed, quantum k-means may offer advantages for larger datasets and high-dimensional data. This essay presents a comparative study of the k-means clustering algorithm implemented in two runtime environments, C# and Qiskit, with a focus on investigating the potential existence of quantum supremacy for a defined problem. The experiment involves randomly generated data and data tables of different sizes and dimensions. The classical approach utilizes a brute-force enumeration method, while the quantum approach employs a quadratic programming algorithm on a quantum computer using Qiskit. Results show that for small problem sizes, the classical brute-force approach exhibits superior runtime performance compared to the quantum approach. However, the study highlights the challenges in achieving quantum supremacy, as the performance of quantum computers is highly dependent on machine capabilities and qubit numbers.
International literature suggests that quantum computers hold the potential for exponential speedup over classical computers, particularly for certain types of optimization problems. However, the practical application of quantum k-means is currently limited by the capabilities of available quantum hardware. As quantum technology improves and more efficient algorithms are developed, quantum k-means may offer advantages for larger datasets and high-dimensional data. This essay presents a comparative study of the k-means clustering algorithm implemented in two runtime environments, C# and Qiskit, with a focus on investigating the potential existence of quantum supremacy for a defined problem. The experiment involves randomly generated data and data tables of different sizes and dimensions. The classical approach utilizes a brute-force enumeration method, while the quantum approach employs a quadratic programming algorithm on a quantum computer using Qiskit. Results show that for small problem sizes, the classical brute-force approach exhibits superior runtime performance compared to the quantum approach. However, the study highlights the challenges in achieving quantum supremacy, as the performance of quantum computers is highly dependent on machine capabilities and qubit numbers.
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 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.
Every day, humans generate approximately 2.5 billion gigabytes of new data. While this data is crucial in applications such as drug development and cybersecurity, it is mostly unstructured and unlabeled which makes it difficult to process effectively. Businesses and governments alike solve this problem by using machine learning algorithms to characterize the data and make decisions with it. However, conventional machine learning processes consume excessive computational resources and time: one of the most prominent, K-means clustering, has an approximate time complexity of O(n^2), where n is the input data size. This quadratic time complexity causes scalability problems with large datasets. In this project, I have created an improved, more scalable clustering algorithm by leveraging quantum computation. The approach (new Q-means) involves an Angle Embedding Feature Map, an d-dimensional SWAP Test, and a dynamic, threshold distance-based termination criteria. After implementing this algorithm using the IBM Qiskit SDK, the new Q-means algorithm was run several times on different dimensional datasets. On an average, the new Q-means performed 18% better than the K-means algorithm based on the Adjusted Rand Index. In terms of the simulation execution time, the new Q-means was about six times faster than the existing Q-means due to a multi-threaded implementation and faster convergence. The time complexity of the new Q-means without a Quantum Random Access Memory (QRAM) is O(n^2). While the existing Q-means algorithm, which utilizes QRAM, has a time complexity of O(n(log n)^p), the time complexity of the new Q-means with QRAM is significantly better—O(n).
The exponential growth of data and the increasing complexity of high-dimensional classification problems have pushed classical computing methods to their limits. Quantum computing emerges as a promising paradigm to address these challenges. This research article explores advanced quantum algorithms for big data clustering and high-dimensional classification. We investigate quantum versions of K-means, spectral clustering, and support vector machines, comparing their performance with classical counterparts. Our results demonstrate significant speedups in processing time and improvements in clustering quality for high-dimensional datasets. Additionally, we propose a novel quantum-inspired classical algorithm that bridges the gap between quantum and classical approaches. This comprehensive study provides insights into the potential of quantum computing in revolutionizing data analysis and machine learning, paving the way for future advancements in the field.
In the NISQ-era of quantum computing, we should not expect to see quantum devices that provide an exponential improvement in runtime for practical problems, due to the lack of error correction and small number of qubits available. Nevertheless, these devices should be able to provide other performance improvements, particularly when combined with existing classical machines. In this article, we develop several hybrid quantum-classical clustering algorithms that can be employed as subroutines on small, NISQ-era devices. These new hybrid algorithms require a number of qubits that is at most logarithmic in the size of the data, provide performance improvement and/or runtime improvement over their classical counterparts, and do not require a black-box oracle. Consequently, we are able to provide a promising near-term application of NISQ-era devices.
Quantum algorithms can be used to perform unsupervised machine learning tasks like data clustering by mapping the distance between data points to a graph optimization problem (i.e. MAXCUT) and finding optimal solution through energy minimization using hybrid quantum classical methods. Taking advantage of the IBM runtime environment, we benchmark the performance of the "Warm-Start" (ws) variant of Quantum Approximate Optimization Algorithm (QAOA) versus the standard implementation of QAOA and the variational quantum eigensolver (VQE) for unstructured clustering problems using real world dataset with respect to accuracy and execution time. Our numerical results show a strong speedup in execution time for different optimization algorithms using the IBM Qiskit Runtime architecture and increased speedup in classification accuracy in ws-QAOA algorithm