q-means: A quantum algorithm for unsupervised machine learning

Abstract

Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The $q$-means algorithm has convergence and precision guarantees similar to $k$-means, and it outputs with high probability a good approximation of the $k$ cluster centroids like the classical algorithm. Given a dataset of $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V\in {\mathbb{R}}^{N\times d})$ stored in QRAM, the running time of q-means is $\tilde{O}\left(kd\frac{\eta }{{\delta }^2}\kappa (V)(\mu (V)+k\frac{\eta }{\delta })+k^2\frac{{\eta }^{1.5}}{{\delta }^2}\kappa (V)\mu (V)\right)$ per iteration, where $\kappa (V)$ is the condition number, $\mu (V)$ is a parameter that appears in quantum linear algebra procedures and $\eta ={\max }_i||v_i|{|}^2$. For a natural notion of well-clusterable datasets, the running time becomes $\tilde{O}\left(k^{2}d\frac{{\eta }^{2.5}}{{\delta }^3}+k^{2.5}\frac{{\eta }^2}{{\delta }^3}\right)$ per iteration, which is linear in the number of features $d$, and polynomial in the rank $k$, the maximum square norm $\eta$ and the error parameter $\delta$. Both running times are only polylogarithmic in the number of datapoints $N$. Our algorithm provides substantial savings compared to the classical $k$-means algorithm that runs in time $O(kdN)$ per iteration, particularly for the case of large datasets.

References in corpus (2)

• A Quantum Approximate Optimization Algorithm
• Unsupervised Machine Learning on a Hybrid Quantum Computer

Cited by in corpus (37)

• Challenges and Opportunities in Quantum Machine Learning
• Quantum convolutional neural network for classical data classification
• Quantum computing for finance
• Amplitude estimation without phase estimation
• Quantum Algorithms for Deep Convolutional Neural Networks
• Low depth algorithms for quantum amplitude estimation
• Automatic design of quantum feature maps
• Quantum Spectral Clustering
• Faster Amplitude Estimation
• Quantum Machine Learning for Finance
• Quantum Clustering with k-Means: a Hybrid Approach
• Practical Quantum K-Means Clustering: Performance Analysis and Applications in Energy Grid Classification
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• Quantum Differentially Private Sparse Regression Learning
• Tensor networks for interpretable and efficient quantum-inspired machine learning
• Modified Grover operator for amplitude estimation
• Quantum exploration algorithms for multi-armed bandits
• The role of entanglement for enhancing the efficiency of quantum kernels towards classification
• Quantum mean centering for block-encoding-based quantum algorithm
• Quantum Expectation-Maximization Algorithm
• Simulation of a Variational Quantum Perceptron using Grover's Algorithm
• Quantum Expectation-Maximization for Gaussian Mixture Models
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• Quantum algorithms for SVD-based data representation and analysis
• Using k-means assistant event selection strategy to study anomalous quartic gauge couplings at muon colliders
• Unsupervised Event Classification with Graphs on Classical and Photonic Quantum Computers
• Application of quantum-inspired generative models to small molecular datasets
• Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
• Quantum matching pursuit: A quantum algorithm for sparse representations
• Quantum-inspired attribute selection algorithm: A Fidelity-based Quantum Decision Tree
• Non-parametric Semi-Supervised Learning in Many-body Hilbert Space with Rescaled Logarithmic Fidelity
• Bayesian Quantum Amplitude Estimation
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Des-q: a quantum algorithm to provably speedup retraining of decision trees
• A Unified Framework for Quantum Supervised Learning
• Optimizing Quantum Variational Circuits with Deep Reinforcement Learning