Quantum K-Means

Most quantum clustering algorithms are based on Grover’s search. These clustering algorithms offer a speedup compared with their classical counterparts, but they do not improve the quality of the resulting clustering process. This is based on the belief that if finding the optimal solution for a clustering problem is NP-hard, then quantum computers w'ould also be unable to solve the problem exactly in polynomial time. If we use quantum random access memory (QRAM) [43], an exponential speedup is possible. Centroids are being calculated and vectors are assigned to the closest centroids. The simplest quantum version of X-means clustering calculates, like the classical variant, but using Grover’s search to find the closest ones. The complexity is О (N log (Nd)) since every vector is tested in each step, which is an exponential speedup over the polynomial complexity of classical algorithms. Further improvement is possible if we allow the output to be quantum. Every algorithm that returns the cluster assignment for each A output must have at least О (N) complexity.

Quantum K-Medians

In X-means clustering, the centroid may lie outside the o(^i) manifold in

which the points are located [44]. X-medians bypass this problem by always choosing an element in a cluster to be the center is a flavor of this family of algorithms. This task is achieved by constructing a routine for finding the median in a cluster using Grover’s search and then iteratively calling this routine to reassign elements. The median is identified among a set of points in О (NVN) time. Quantum A'-medians have complexity as opposed to the classical algorithm.

Quantum Hierarchical Clustering

Quantum hierarchical clustering hinges on ideas similar to those of quantum A'-medians clustering. Here we use a quantum algorithm to calculate the maximum distance between two points in a set instead of finding the median. In order to split clusters and reassign the data instances to the most distant pair of instances, we iteratively call this algorithm. This is the divisive form of hierarchical clustering. Quantum divisive clustering О (N log) has much lower complexity compared with the classical limit О (N2).

For cluster finding and cluster assignment, Lloyd et al. [20] used supervised and unsupervised quantum machine learning algorithms. The work shows that quantum machine learning can provide exponential speedups over classical computers for a good number of learning tasks. A quantum computer takes time Oflog(MN)) as compared with time 0(poly(MN)) for the best-known classical during the task of assigning N-dimensional vectors to one of several clusters of M states explaining quantum machine learning can provide an exponential speed-up for problems involving large numbers of vectors as well (“big quantum data”).

Using the quantum adiabatic algorithm (a quantum version of Lloyd’s) to perform A'-means clustering of M vectors into К clusters in time 0(log к (MN)) can be classified. Privacy is also enhanced by quantum machine learning that allows only 0(log (MN)) calls to the quantum database for cluster assignment in comparison to O(MN) to uncover the actual data. The database user can still obtain information about the desired patterns while the database owner is assured that the user has only accessed an exponentially small fraction of the database.

In [45] et al., the authors used a quantum paradigm for speeding up unsupervised learning algorithms and to accelerate learning algorithms by quantizing some of their subroutines. Quantized versions of clustering via minimum divisive clustering, spanning trees and A'-medians that are faster with respect to their classical analogs are given. The work also gives a distributed version of A'-medians that allows the participants to save on the global communication cost of the protocol compared to the classical version is. Lastly, quantum algorithms for the construction of a neighborhood graph are given.


R. Shang et al. [46] present an approach to large-scale CARP called quantum- inspired immune clonal algorithm (QICA-CARP) that chains the feature of quantum computation and artificial immune system grounded on the qubit and the quantum superposition. The convergence rate and the quality of the acquired solutions from experimental results show that QICA-CARP beats other algorithms. R. Xia et al. [47] report a hybrid quantum algorithm hiring a restricted Boltzmann machine to gain accurate molecular potential energy surfaces. For optimizing the primary objective function developing a quantum algorithm, the authors achieved a resourceful technique for the calculation of the electronic ground state energy for a small molecule system. P. Diamandis, et al. [48] described quantum computing promises to model molecular interactions at an atomic level so as to understand various diseases. Using quantum computer simulations can be the way for designing and choosing the next generations of drugs and cancer cures.


For the purpose of solving the dynamic flexible job-shop scheduling problem, T. Ning et al. [49] establishes the mathematical model to minimize the makespan and stability value, an improved double chains quantum genetic algorithm using quantum techniques is proposed. K. Qazi et al. [50] proposed a complex-valued quantum neural network approach to predicting workloads in data centers. According to the results, multi-layered neural networks with multi-valued neurons (MLMVN) show's higher accuracy compared to both long short-term memory recurrent neural network (LSTM-RNN) and echo state network (ESN), for all the prediction lengths. J. Cruz- Benito et al. [51] describe a project of IBM Q team that implements an intelligent system based on a deep learning approach that learns how people code using the Open QASM language to later offer help and guidance to the coders by recommending different code sequences, logical steps or even small pieces of code.


Privacy and cryptography are the main branches in which quantum computing has beared its fruits. Quantum cryptography (QKD) is quite a mature field nowadays in providing a more secure environment for IT use. Useful work and future direction in QKD are available in [52-55]. A detailed discussion about opportunities and challenges of quantum computing in artificial intelligence/machine intelligence is put forward by pioneering w'ork in [56,57]. The implementation of soft computing techniques feasible for quantum computing too is discussed here.

< Prev   CONTENTS   Source   Next >