Source-linked AI summary
Quantum support vector machine for big data classification
Patrick Rebentrost, Masoud Mohseni, Seth Lloyd
TL;DR
Classical support vector machines can be costly for high-dimensional data and large training sets. This paper implements an SVM on a quantum computer with logarithmic complexity in feature size and training-set size, yielding exponential speed-up when classical sampling takes polynomial time.
Problem
The paper addresses whether support vector machines can be implemented efficiently on quantum computers for high-dimensional data and large training sets.
Method
The approach reformulates the SVM as a least-squares problem and uses quantum phase estimation, matrix inversion, and non-sparse kernel-matrix exponentiation.
Results
The quantum SVM scales as O(log MN) in training and classification, providing exponential speed-up when classical sampling requires polynomial time.
Takeaways & Limitations
The work provides an example of a quantum big-data algorithm for support vector machine classification.
Takeaways & Limitations
The method assumes access to quantum training-data oracles and is fastest when the kernel matrix is effectively low rank, while small eigenvalues can worsen conditioning.
Abstract
from arXiv · showhide
Supervised machine learning is the classification of new data based on already classified training examples. In this work, we show that the support vector machine, an optimized binary classifier, can be implemented on a quantum computer, with complexity logarithmic in the size of the vectors and the number of training examples. In cases when classical sampling algorithms require polynomial time, an exponential speed-up is obtained. At the core of this quantum big data algorithm is a non-sparse matrix exponentiation technique for efficiently performing a matrix inversion of the training data inner-product (kernel) matrix.
APPENDIX A: ESTIMATING THE TRACE OF THE · KERNEL MATRIX
The appendix describes an efficient quantum procedure for estimating the trace of the kernel matrix. It constructs a Hamiltonian from training-data norms, evolves a superposition state, and measures an ancilla after choosing a small-time regime.
- KERNEL MATRIX: The trace of the kernel matrix can be efficiently evaluated using a method similar to [14].The appendix presents this as the starting point for the trace-estimation procedure.
- KERNEL MATRIX: The procedure generates the Hamiltonian Htr from training-data norms accessed through the training-data oracle.The Hamiltonian is expressed using norm-dependent terms and an ancilla operator σx.
- KERNEL MATRIX: Applying e−iHtrt evolves the input state into a superposition whose amplitudes depend on cos(|x_j|t) and sin(|x_j|t).The evolved state includes separate ancilla components associated with these trigonometric factors.
- KERNEL MATRIX: The evolution is applied to the state |ψ⟩, which is defined as a normalized superposition over the training-data indices.The supplied passage begins the explicit state definition with |ψ⟩=1/.
- KERNEL MATRIX: The time t is chosen so that |x_j|t ≪1 for every training example.This small-angle condition is imposed before measuring the ancilla.
- KERNEL MATRIX: Measuring the ancilla in the |1⟩ state provides the successful measurement event for the estimation procedure.The supplied passage states that the ancilla is measured in |1⟩ after the small-time condition is selected.
- KERNEL MATRIX: The success probability is given as 1/M times a sum over the training examples.The supplied expression is truncated after 1/M PM, so no further form is added.
- KERNEL MATRIX: The resulting measurement enables estimation of the trace of K.The appendix explicitly links the measurement outcome to trace estimation.
APPENDIX B: LOW-RANK APPROXIMATION
The appendix analyzes a rank-one low-rank approximation of the kernel matrix and derives its effect on the classifier solution. Although the approximation yields a sub-optimally small margin, all training examples still contribute through their projections onto the first principal component.
- Classifier solution: The initial construction has a sub-optimally small margin 2/|w| when b = 0 and K = 0.This setup follows from γ^-1α = y and the corresponding expression for w.
- Rank-one approximation: A rank-one kernel approximation K ≈ λ1u1u1^T is introduced, with u1 related to the first principal component of the training data.The elements of u1 are inner products between training vectors and the first principal component.
- Rank-one approximation: The approximate inverse (K + γ^-1I)^-1 is obtained as γ(I − cu1u1^T) using the Sherman–Morrison formula, where c = γλ1/(1 + γλ1).This provides an explicit matrix-inversion expression for the low-rank kernel approximation.
- Classifier solution: The resulting weight vector w = γΣ_m ym(x_m − cu1u1^Tx_m) incorporates each training label through its example’s projection onto the first principal component.The correction depends on the respective projection of each training example.
- Classifier solution: All training examples contribute to the low-rank solution, unlike stochastic gradient approaches that sample only a small subset.The appendix explicitly contrasts full-example contribution under the approximation with subset sampling in stochastic gradient methods.
APPENDIX C: ERROR OF QUANTUM LOW-RANK · APPROXIMATION
The quantum speed-up applies when the kernel matrix is low-rank, with a few O(1) eigenvalues and many O(1/M) eigenvalues initially unknown. The approximation retains only the O(1) eigenvalues, producing a Frobenius-norm error between K and Kq.
- APPROXIMATION: The quantum speed-up holds when the kernel matrix has a few O(1) eigenvalues and many O(1/M) eigenvalues.All eigenvalues are initially unknown.
- APPROXIMATION: The quantum algorithm accounts only for the O(1) eigenvalues, which incur an approximation error E.The passage identifies this as the low-rank approximation error.
- APPROXIMATION: E is defined as the Frobenius/Hilbert-Schmidt norm ||K−Kq||F of the difference between K and Kq.K is the low-rank matrix and Kq is its quantum approximation.
- APPROXIMATION: The error expression depends on the eigenvalues λi of K and the assumption of O(M) small eigenvalues.The supplied passage begins the resulting scaling as E = O(1/, but the expression is truncated.