Sublinear quantum algorithms for training linear and kernel-based classifiers

Abstract

We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given $n$ $d$-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with constant margin runs in $\tilde{O}(n+d)$ time. We design sublinear quantum algorithms for the same task running in $\tilde{O}(\sqrt{n}+\sqrt{d})$ time, a quadratic improvement in both $n$ and $d$. Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines. As a side result, we also give sublinear quantum algorithms for approximating the equilibria of $n$-dimensional matrix zero-sum games with optimal complexity $\tilde{\Theta }(\sqrt{n})$.

31 pages, 1 figure

References in corpus (14)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Supervised learning with quantum enhanced feature spaces
• Quantum support vector machine for big data classification
• Strengths and Weaknesses of Quantum Computing
• Quantum principal component analysis
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum algorithms for supervised and unsupervised machine learning
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Quantum Perceptron Models
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Quantum classification of the MNIST dataset with Slow Feature Analysis
• A Survey of Quantum Learning Theory

Cited by in corpus (21)

• Quantum computing for finance
• Towards understanding the power of quantum kernels in the NISQ era
• The complexity of quantum support vector machines
• Quantum Machine Learning for Finance
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Quantum Differentially Private Sparse Regression Learning
• Modified Grover operator for amplitude estimation
• Quantum exploration algorithms for multi-armed bandits
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity
• Small quantum computers and large classical data sets
• Quantum algorithms for hedging and the learning of Ising models
• Quantum Semi-Supervised Kernel Learning
• Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
• Quantum Circuit Parameters Learning with Gradient Descent Using Backpropagation
• A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time
• Quantum and Classical Algorithms for Approximate Submodular Function Minimization
• Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning
• Quantum Alphatron: quantum advantage for learning with kernels and noise
• Quantum Machine Learning For Classical Data
• Quantum Algorithm for Online Convex Optimization
• Quantum Perceptron Revisited: Computational-Statistical Tradeoffs