Source-linked AI summary
Quantum algorithms for supervised and unsupervised machine learning
Seth Lloyd, Masoud Mohseni, Patrick Rebentrost
TL;DR
Large-scale machine learning involves classifying many high-dimensional vectors, while classical approaches typically scale polynomially with dataset size and dimension. The paper develops supervised and unsupervised quantum algorithms for cluster assignment and finding, with runtimes logarithmic in both quantities and an exponential speed-up over classical methods.
Problem
Large-scale machine-learning tasks require manipulating and classifying many high-dimensional vectors, while classical algorithms typically scale polynomially with their number and dimension.
Method
The paper develops supervised and unsupervised quantum algorithms for cluster assignment and cluster finding, using quantum access to high-dimensional data.
Results
O(log MN) runtime yields an exponential speed-up in both the number of vectors and their dimension for the paper’s quantum machine-learning approach.
Takeaways & Limitations
Quantum machine learning could analyze large vector datasets in logarithmic time with respect to dataset size and dimension.
Takeaways & Limitations
Finding the optimal cluster assignment for a set of size k is classically combinatorially hard in k.
Abstract
from arXiv · showhide
Machine-learning tasks frequently involve problems of manipulating and classifying large numbers of vectors in high-dimensional spaces. Classical algorithms for solving such problems typically take time polynomial in the number of vectors and the dimension of the space. Quantum computers are good at manipulating high-dimensional vectors in large tensor product spaces. This paper provides supervised and unsupervised quantum machine learning algorithms for cluster assignment and cluster finding. Quantum machine learning can take time logarithmic in both the number of vectors and their dimension, an exponential speed-up over classical algorithms.
1. Massachusetts Institute of Technology, Research Laboratory for Electronics · 2. Google Research
The paper develops quantum machine-learning methods for supervised cluster assignment and unsupervised clustering of high-dimensional, large-scale data. These methods achieve logarithmic-time operations and exponential speed-ups over known classical algorithms, while also enabling enhanced privacy through limited database access.
- 2. Google Research: Quantum computers can estimate distances and inner products between N-dimensional vectors in O(log N) time.The data can be mapped to quantum states over log2 N qubits, with qRAM loading taking O(log2 N) steps.
- 2. Google Research: Quantum machine learning provides exponential speed-ups over all known classical algorithms for evaluating distances and inner products between large vectors.Classical sampling and estimation of these quantities is described as apparently exponentially hard.
- 2. Google Research: O(log(MN)) time assigns N-dimensional vectors to one of several clusters of M states, compared with O(poly(MN)) for the best known classical algorithm.This yields an exponential speed-up for problems involving large numbers of vectors.
- 2. Google Research: O(k log kMN) time classifies M vectors into k clusters using a quantum version of Lloyd’s k-means algorithm.The method uses a novel version of the quantum adiabatic algorithm.
- 2. Google Research: Quantum machine learning offers exponential speed-ups in both the number of vectors and their dimension.The paper frames this setting as “big quantum data.”
- 2. Google Research: O(log(MN)) quantum database calls suffice for cluster assignment, whereas O(MN) calls are required to uncover the actual data.Users can obtain information about desired patterns while the database owner is assured that only an exponentially small fraction of the database was accessed.
Data preparation and pre-processing
Quantum random access memory enables quantum-parallel access to vector data and efficient preparation of exponentially compressed quantum states. These states support polylogarithmic-time postprocessing and generalized inner-product evaluation.
- Data preparation and pre-processing: qRAM enables quantum-parallel access to data stored as vectors and collections of vectors.The data are assumed to be stored in classical RAM or qRAM, with qRAM providing quantum-parallel access.
- Data preparation and pre-processing: O(log N) steps suffice to construct a quantum state from a vector when its sub-norms are given in qRAM.For a vector with N = 2^n components, state preparation is also described as taking O(log2 N) steps when norms are estimated efficiently.
- Data preparation and pre-processing: O(poly(log N)) postprocessing produces QFT|v⟩ and f(A)|v⟩ for sparse Hermitian A and computable f, including f(A) = A^-1.The postprocessing uses quantum Fourier transforms, matrix inversion, and related operations after exponentially compressed vector states are prepared.
- Data preparation and pre-processing: The resulting quantum vectors permit evaluation of generalized inner products ⟨u|QFT|v⟩ and ⟨u|f(A)|v⟩.These inner products are evaluated between quantum vectors after the stated postprocessing transformations.
Supervised cluster assignment:
Quantum algorithms assign vectors to supervised clusters in O(ε^-1 log(MN)) time and extend quantum speed-ups to unsupervised k-means clustering. Quantum Lloyd’s and adiabatic algorithms reduce dependence on vector number and dimension, with output and gap-related limitations.
- Supervised cluster assignment:: O(ε^-1 log(MN)) time solves supervised assignment when vectors are provided as quantum states.The algorithm assigns a post-processed vector to one of two sets using representative samples.
- Unsupervised quantum learning:: O(M log(MN)) time is required per step by quantum Lloyd’s algorithm, versus O(M^2N) classically when distance estimation takes O(N).Both methods test every vector individually for reassignment at each step.
- Unsupervised quantum learning:: O(k log(MN)) time, or O(log(kMN)), can solve unsupervised learning through an adiabatic reformulation of k-means.The faster dependence on M requires a quantum clustering state rather than explicitly listing all M assignments.
- Unsupervised quantum learning:: O(ε^-1k log(kMN)) constructs the clustering state, decreasing to O(ε^-1 log(kMN)) when clusters are relatively well separated and the adiabatic gap is O(1).The state encodes vector labels correlated with cluster assignments, from which a statistical picture of clustering can be sampled.
- Unsupervised quantum learning:: O(r log(MN)) time finds sets of r vectors expected to lie in the same cluster, while combining attractive and repulsive Hamiltonians finds kr representative groups.Optimal seed sets and clusters are combinatorially hard in k and r, and adiabatic runtime may scale exponentially in those parameters.