A Leap from Randomized to Quantum Clustering with Support Vector Machine - A Computation Complexity Analysis

Supervised machine learning deals with developing complex non-linear models, which can be used later to predict the output for a known input. Clustering is usually treated as an unsupervised machine learning task, but we can formulate a solution to a clustering problem by using a supervised classification algorithm [1]. However, these classification algorithms are highly computationally intensive in nature, so the overall complexity in designing a clustering solution is often very costly from an implementation point of view. The more data we use, the more computational power is required too. Recent advancements in quantum computing show promising advantages in dealing with this kind of computational issues we face while training a complex machine-learning algorithm. In this paper, we do a theoretical investigation on the runtime complexity of algorithms, from classical to randomized, and then to quantum frameworks, when designing a clustering algorithm. The analysis shows significant computational advantages with a quantum framework as compared to the classical and randomized versions of the implementation.