Fetching the paper…

Reading the bibliography…

A rigorous and robust quantum speed-up in supervised machine learning · Around

2020

A rigorous and robust quantum speed-up in supervised machine learning

Liu, Yunchao, Arunachalam, Srinivasan, Temme, Kristan

Original
PDF
Post on X

Understand

Over the past few years several quantum machine learning algorithms were proposed that promise quantum speed-ups over their classical counterparts.

Most of these learning algorithms either assume quantum access to data -- making it unclear if quantum speed-ups still exist without making these strong assumptions, or are heuristic in nature with no provable advantage over classical algorithms.
In this paper, we establish a rigorous quantum speed-up for supervised classification using a general-purpose quantum learning algorithm that only requires classical access to data.
Our quantum classifier is a conventional support vector machine that uses a fault-tolerant quantum computer to estimate a kernel function.

Built on

C. Gidney and M. Ekerå, How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits (2019), arXiv:1905.09749 [quant-ph]
Original
1905
Earlier work this paper cites.
C. Ding, T.-Y. Bao, and H.-L. Huang, Quantum-inspired support vector machine (2019), arXiv:1906.08902 [cs.LG]
Original
1906
Earlier work this paper cites.
J. W. Daniel, Mathematical Programming 5
1973
Earlier work this paper cites.
M. Blum and S. Micali, SIAM J. Comput. 13
1984
Earlier work this paper cites.
M. J. Kearns, The computational complexity of machine learning (MIT press, 1990)
1990
Earlier work this paper cites.
B. E. Boser, I. M. Guyon, and V. N. Vapnik, in Proceedings of the Fifth Annual Workshop on Computational Learning Theory , COLT (1992) p. 144–152
1992
Earlier work this paper cites.
M. J. Kearns and U. V. Vazirani, An introduction to computational learning theory (MIT press, 1994)
1994
Earlier work this paper cites.
P. W. Shor, SIAM Journal on Computing 26
1997
Earlier work this paper cites.
J. Shawe-Taylor, P. L. Bartlett, R. C. Williamson, and M. Anthony, IEEE Transactions on Information Theory 44
1998
Earlier work this paper cites.
P. L. Bartlett and P. M. Long, Journal of Computer and System Sciences 56
1998
Earlier work this paper cites.
C. J. Burges, Data Mining and Knowledge Discovery 2
1998
Earlier work this paper cites.
P. Bartlett and J. Shawe-Taylor, Generalization performance of support vector machines and other pattern classifiers, in Advances in Kernel Methods: Support Vector Learning (MIT Press, Cambridge, MA, USA, 1999) p. 43–54
1999
Earlier work this paper cites.
M. Anthony and P. L. Bartlett, Combinatorics, Probability and Computing 9
2000
Earlier work this paper cites.
J. Shawe-Taylor and N. Cristianini, IEEE Transactions on Information Theory 48
2002
Earlier work this paper cites.
R. A. Servedio and S. J. Gortler, SIAM J. Comput. 33
2004
Earlier work this paper cites.
M. Mosca and C. Zalka, International Journal of Quantum Information 02
2004
Earlier work this paper cites.
A. J. Smola and B. Schölkopf, Statistics and Computing 14
2004
Earlier work this paper cites.
R. Sweke, J.-P. Seifert, D. Hangleiter, and J. Eisert, On the quantum versus classical learnability of discrete distributions (2020), arXiv:2007.14451 [quant-ph]
Original
2007
Earlier work this paper cites.

Similar

D. Aharonov and A. Ta‐Shma, SIAM Journal on Computing 37
2007
Cited alongside, same era.
A. W. Harrow, A. Hassidim, and S. Lloyd, Phys. Rev. Lett. 103
2009
Cited alongside, same era.
N. Wiebe, D. Braun, and S. Lloyd, Phys. Rev. Lett. 109
2012
Cited alongside, same era.
S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum algorithms for supervised and unsupervised machine learning (2013), arXiv:1307.0411 [quant-ph]
Original
2013
Cited alongside, same era.
V. Vapnik, The nature of statistical learning theory (Springer science & business media, 2013)
2013
Cited alongside, same era.
P. Rebentrost, M. Mohseni, and S. Lloyd, Phys. Rev. Lett. 113
2014
Cited alongside, same era.

Then

A. Gilyén, S. Lloyd, and E. Tang, Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension (2018), arXiv:1811.04909 [cs.DS]
Original
2018
Later among the works it cites.
N.-H. Chia, H.-H. Lin, and C. Wang, Quantum-inspired sublinear classical algorithms for solving low-rank linear systems (2018), arXiv:1811.04852 [cs.DS]
Original
2018
Later among the works it cites.
K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Physical Review A 98
2018
Later among the works it cites.
E. Farhi and H. Neven, arXiv preprint arXiv:1802.06002 (2018)
Original
2018
Later among the works it cites.
E. Grant, M. Benedetti, S. Cao, A. Hallam, J. Lockhart, V. Stojevic, A. G. Green, and S. Severini, npj Quantum Information 4
2018

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…

S. Aaronson, Nature Physics 11

2015

Cited alongside, same era.

I. Cong and L. Duan, New Journal of Physics 18

2016

Cited alongside, same era.

I. Kerenidis and A. Prakash, Quantum recommendation systems (2016), arXiv:1603.08675 [quant-ph]

2016

Cited alongside, same era.

J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Nature 549

2017

Cited alongside, same era.

S. Arunachalam and R. de Wolf, SIGACT News 48

2017

Cited alongside, same era.

K. Temme, S. Bravyi, and J. M. Gambetta, Phys. Rev. Lett. 119

2017

Cited alongside, same era.

Later among the works it cites.

X. Gao, Z.-Y. Zhang, and L.-M. Duan, Science Advances 4

2018

Later among the works it cites.

G. Carleo, I. Cirac, K. Cranmer, L. Daudet, M. Schuld, N. Tishby, L. Vogt-Maranto, and L. Zdeborová, Rev. Mod. Phys. 91

2019

Later among the works it cites.

F. G. S. L. Brandão, A. Kalev, T. Li, C. Y.-Y. Lin, K. M. Svore, and X. Wu, in 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 132 (2019) pp. 27:1–27:14

2019

Later among the works it cites.

Z. Zhao, J. K. Fitzsimons, and J. F. Fitzsimons, Phys. Rev. A 99

2019

Later among the works it cites.

E. Tang, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , STOC (2019) p. 217–228

2019

Later among the works it cites.

M. Benedetti, E. Lloyd, S. Sack, and M. Fiorentini, Quantum Science and Technology 4

2019

Later among the works it cites.

V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Nature 567

2019

Later among the works it cites.

M. Schuld and N. Killoran, Phys. Rev. Lett. 122

2019

Later among the works it cites.

A. Kandala, K. Temme, A. D. Córcoles, A. Mezzacapo, J. M. Chow, and J. M. Gambetta, Nature 567

2019

Later among the works it cites.

N.-H. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang, and C. Wang, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , STOC (2020) p. 387–400

2020

Closest in time.

M. Schuld, A. Bocharov, K. M. Svore, and N. Wiebe, Physical Review A 101

2020

Closest in time.

A. Grønlund, L. Kamma, and K. G. Larsen, Proceedings of International Conference on Machine Learning, ICML (2020)

2020

Closest in time.