  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.
