Small quantum computers and large classical data sets
arXiv:2004.00026
Abstract
We introduce hybrid classical-quantum algorithms for problems involving a large classical data set X and a space of models Y such that a quantum computer has superposition access to Y but not X. These algorithms use data reduction techniques to construct a weighted subset of X called a coreset that yields approximately the same loss for each model. The coreset can be constructed by the classical computer alone, or via an interactive protocol in which the outputs of the quantum computer are used to help decide which elements of X to use. By using the quantum computer to perform Grover search or rejection sampling, this yields quantum speedups for maximum likelihood estimation, Bayesian inference and saddle-point optimization. Concrete applications include k-means clustering, logistical regression, zero-sum games and boosting.
arXiv comment25 pages
References in corpus (26)
- An overview of gradient descent optimization algorithms
- Quantum Machine Learning
- A variational eigenvalue solver on a quantum processor
- A Quantum Approximate Optimization Algorithm
- Quantum Circuit Learning
- Quantum Amplitude Amplification and Estimation
- Circuit-centric quantum classifiers
- Quantum random access memory
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Quantum machine learning: a classical perspective
- A Quantum Algorithm for Finding the Minimum
- Architectures for a quantum random access memory
- A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
- Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
- Speed-up via Quantum Sampling
- Coresets for Scalable Bayesian Logistic Regression
- Quantum Algorithms for Fixed Qubit Architectures
- Quantum speedup of classical mixing processes
- Quantum walks can find a marked element on any graph
- Automated Scalable Bayesian Inference via Hilbert Coresets
- Almost uniform sampling via quantum walks
- Quantum algorithms and lower bounds for convex optimization
- Sublinear quantum algorithms for training linear and kernel-based classifiers
- Quantum Speed-ups for Semidefinite Programming
- Quantum algorithms for zero-sum games
- Validated Variational Inference via Practical Posterior Error Bounds