Novel Enhanced Unsupervised Quantum Clustering Algorithm


  • Diptanshu Sikdar BASIS Independent Silicon Valley
  • Joe Clapis
  • Swetha Bhattacharya BASIS Independent Silicon Valley



Quantum Computing, Clustering, K-Means, Q-Means, Angle Embedding, Oracle, SWAP Test


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).


Download data is not yet available.

References or Bibliography

Aimeur, E., Brassard, G., & Gambs, S. (2012, August 31). Quantum Speed-up for unsupervised learning - machine learning. SpringerLink.

Kerenidis, I., Landman, J., Luongo, A., & Prakash, A. (2018, December 12). Q-means: A quantum algorithm for unsupervised machine learning. arXiv.

Li, J., & Kais, S. (2021, June 13). Quantum cluster algorithm for Data Classification. arXiv.

MJV Team. (2021, September 23). Types of clustering: Why is it so important for business? MJV Technology & Innovation. Retrieved February 29, 2022, from

Neukart, F., Dollen, D. V., & Seidel, C. (2018, June 14). Quantum-assisted cluster analysis on a quantum annealing device. Frontiers.

Nielsen, M. A., & Chuang, I. L. (2018). Quantum Computation and Quantum Information: 10th anniversary ed. Cambridge University Press.

Pakhira, M. K. (2014). A linear time-complexity K-means algorithm using cluster shifting. IEEE Xplore.

Preskill, J. (2021, June 25). Quantum Computing 40 years later. arXiv.

Wikipedia Staff. (2022, April 26). Elbow method (clustering). Wikipedia. Retrieved March 13, 2022, from

Wikipedia Staff. (2022, February 10). SWAP Test. Wikipedia. Retrieved February 9, 2022, from

Xie, X., Duan, L., Qiu, T. et al. (2021, July 30). Quantum algorithm for MMNG-based DBSCAN. Nature.

Zhang, Y., Lu, K., Gao, Y., & Wang, M. (2013, March 26). NEQR: A novel enhanced quantum representation of digital images. SpringerLink.



How to Cite

Sikdar, D., Clapis, J., & Bhattacharya, S. (2022). Novel Enhanced Unsupervised Quantum Clustering Algorithm. Journal of Student Research, 11(2).



HS Research Projects