  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.
