Built on

Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms, 2019, \href
Original
A. W. Harrow and J. Napp · 1901
Earlier work this paper cites.
Duality in quantum quenches and classical approximation algorithms: Pretty good or very bad, 2019, \href
Original
M. B. Hastings · 1904
Earlier work this paper cites.
Sublinear quantum algorithms for training linear and kernel-based classifiers
Original
T. Li, S. Chakrabarti, and X. Wu · 1904
Earlier work this paper cites.
Quantum algorithms for zero-sum games, 2019, \href
Original
J. van Apeldoorn and A. Gilyén · 1904
Earlier work this paper cites.
Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions, 2019, \href
Original
A. W. Harrow and A. Wei · 1907
Earlier work this paper cites.
Practical posterior error bounds from variational objectives
Original
J. Huggins, M. Kasprzak, T. Campbell, and T. Broderick · 1910
Earlier work this paper cites.
An algorithm for quadratic programming
M. Frank and P. Wolfe · 1956
Earlier work this paper cites.
On the uniform convergence of relative frequencies of events to their probabilities
V. Vapnik and A. Chervonenkis · 1971
Earlier work this paper cites.
Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering
M. Inaba, N. Katoh, and H. Imai · 1994
Earlier work this paper cites.
Minimax and Applications
D. Du and P. Pardalos · 1995
Earlier work this paper cites.
A sublinear-time randomized approximation algorithm for matrix games
M. D. Grigoriadis and L. G. Khachiyan · 1995
Earlier work this paper cites.
A quantum algorithm for finding the minimum, 1996, \href
C. Dürr and P. Høyer · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. Grover · 1996
Earlier work this paper cites.
Quantum computation by adiabatic evolution
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser · 2000
Earlier work this paper cites.
Quantum Amplitude Amplification and Estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Earlier work this paper cites.
Adiabatic quantum state generation and statistical zero knowledge
D. Aharonov and A. Ta-Shma · 2003
Earlier work this paper cites.
How significant are the known collision and element distinctness quantum algorithms?
L. Grover and T. Rudolph · 2004
Earlier work this paper cites.
Efficient large scale linear programming support vector machines
S. Sra · 2006
Earlier work this paper cites.
Almost uniform sampling via quantum walks
P. C. Richter · 2007
Earlier work this paper cites.
Quantum speedup of classical mixing processes
P. C. Richter · 2007
Earlier work this paper cites.

Similar

Architectures for a quantum random access memory
Original
V. Giovannetti, S. Lloyd, and L. Maccone · 2008
Cited alongside, same era.
Quantum random access memory
Original
V. Giovannetti, S. Lloyd, and L. Maccone · 2008
Cited alongside, same era.
Impossibility of a quantum speed-up with a faulty oracle
Original
O. Regev and L. Schiff · 2008
Cited alongside, same era.
Speedup via quantum sampling
Original
P. Wocjan and A. Abeyesinghe · 2008
Cited alongside, same era.
Coresets, sparse greedy approximation, and the frank-wolfe algorithm
K. L. Clarkson · 2010
Cited alongside, same era.

Then

An overview of gradient descent optimization algorithms, 2016, \href
Original
S. Ruder · 2016
Later among the works it cites.
Fast-forwarding of Hamiltonians and exponentially precise measurements
Original
Y. Atia and D. Aharonov · 2017
Later among the works it cites.
Practical coreset constructions for machine learning, 2017, \href
Original
O. Bachem, M. Lucic, and A. Krause · 2017
Later among the works it cites.
Quantum machine learning
Original
J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd · 2017
Later among the works it cites.
Quantum speed-ups for solving semidefinite programs
Original

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2020

Small quantum computers and large classical data sets

Harrow, Aram W.

Understand

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.

Built on

Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms, 2019, \href
Original
A. W. Harrow and J. Napp · 1901
Earlier work this paper cites.
Duality in quantum quenches and classical approximation algorithms: Pretty good or very bad, 2019, \href
Original
M. B. Hastings · 1904
Earlier work this paper cites.
Sublinear quantum algorithms for training linear and kernel-based classifiers
Original
T. Li, S. Chakrabarti, and X. Wu · 1904
Earlier work this paper cites.
Quantum algorithms for zero-sum games, 2019, \href
Original
J. van Apeldoorn and A. Gilyén · 1904
Earlier work this paper cites.
Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions, 2019, \href
Original
A. W. Harrow and A. Wei · 1907
Earlier work this paper cites.
Practical posterior error bounds from variational objectives
Original
J. Huggins, M. Kasprzak, T. Campbell, and T. Broderick · 1910
Earlier work this paper cites.
An algorithm for quadratic programming
M. Frank and P. Wolfe · 1956
Earlier work this paper cites.
On the uniform convergence of relative frequencies of events to their probabilities
V. Vapnik and A. Chervonenkis · 1971
Earlier work this paper cites.
Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering
M. Inaba, N. Katoh, and H. Imai · 1994
Earlier work this paper cites.
Minimax and Applications
D. Du and P. Pardalos · 1995
Earlier work this paper cites.
A sublinear-time randomized approximation algorithm for matrix games
M. D. Grigoriadis and L. G. Khachiyan · 1995
Earlier work this paper cites.
A quantum algorithm for finding the minimum, 1996, \href
C. Dürr and P. Høyer · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. Grover · 1996
Earlier work this paper cites.
Quantum computation by adiabatic evolution
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser · 2000
Earlier work this paper cites.
Quantum Amplitude Amplification and Estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Earlier work this paper cites.
Adiabatic quantum state generation and statistical zero knowledge
D. Aharonov and A. Ta-Shma · 2003
Earlier work this paper cites.
How significant are the known collision and element distinctness quantum algorithms?
L. Grover and T. Rudolph · 2004
Earlier work this paper cites.
Efficient large scale linear programming support vector machines
S. Sra · 2006
Earlier work this paper cites.
Almost uniform sampling via quantum walks
P. C. Richter · 2007
Earlier work this paper cites.
Quantum speedup of classical mixing processes
P. C. Richter · 2007
Earlier work this paper cites.

Similar

Architectures for a quantum random access memory
Original
V. Giovannetti, S. Lloyd, and L. Maccone · 2008
Cited alongside, same era.
Quantum random access memory
Original
V. Giovannetti, S. Lloyd, and L. Maccone · 2008
Cited alongside, same era.
Impossibility of a quantum speed-up with a faulty oracle
Original
O. Regev and L. Schiff · 2008
Cited alongside, same era.
Speedup via quantum sampling
Original
P. Wocjan and A. Abeyesinghe · 2008
Cited alongside, same era.
Coresets, sparse greedy approximation, and the frank-wolfe algorithm
K. L. Clarkson · 2010
Cited alongside, same era.

Then

An overview of gradient descent optimization algorithms, 2016, \href
Original
S. Ruder · 2016
Later among the works it cites.
Fast-forwarding of Hamiltonians and exponentially precise measurements
Original
Y. Atia and D. Aharonov · 2017
Later among the works it cites.
Practical coreset constructions for machine learning, 2017, \href
Original
O. Bachem, M. Lucic, and A. Krause · 2017
Later among the works it cites.
Quantum machine learning
Original
J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd · 2017
Later among the works it cites.
Quantum speed-ups for solving semidefinite programs
Original

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Theory and applications of robust optimization

Original

D. Bertsimas, D. B. Brown, and C. Caramanis · 2011

Cited alongside, same era.

A unified framework for approximating and clustering data

Original

D. Feldman and M. Langberg · 2011

Cited alongside, same era.

The multiplicative weights update method: a meta-algorithm and applications

S. Arora, E. Hazan, and S. Kale · 2012

Cited alongside, same era.

Accelerating stochastic gradient descent using predictive variance reduction

R. Johnson and T. Zhang · 2013

Cited alongside, same era.

Quantum rejection sampling

Original

M. Ozols, M. Roetteler, and J. Roland · 2013

Cited alongside, same era.

A quantum approximate optimization algorithm, 2014, \href

Original

E. Farhi, J. Goldstone, and S. Gutmann · 2014

Cited alongside, same era.

A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem

Original

E. Farhi, J. Goldstone, and S. Gutmann · 2014

Cited alongside, same era.

F. G. S. L. Brandão and K. Svore · 2017