At the interface of machine learning and quantum computing, an important question is what distributions can be learned provably with optimal sample complexities and with quantum-accelerated time complexities. In the classical case, Klivans and Goel discussed the $Alphatron$, an algorithm to learn distributions related to kernelized regression, which they also applied to the learning of two-layer neural networks. In this work, we provide quantum versions of the Alphatron in the fault-tolerant setting. In a well-defined learning model, this quantum algorithm is able to provide a polynomial speedup for a large range of parameters of the underlying concept class. We discuss two types of speedups, one for evaluating the kernel matrix and one for evaluating the gradient in the stochastic gradient descent procedure. We also discuss the quantum advantage in the context of learning of two-layer neural networks. Our work contributes to the study of quantum learning with kernels and from samples.
 Jonathan Allcock, Chang-Yu Hsieh, Iordanis Kerenidis, and Shengyu Zhang, ``Quantum Algorithms for Feedforward Neural Networks'' ACM Transactions on Quantum Computing 1 (2020).
 Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor, Michele Mosca, and Priyaa Varshinee Srinivasan, ``On the robustness of bucket brigade quantum RAM'' New Journal of Physics 17, 123010 (2015).
 Peter L. Bartlettand Shahar Mendelson ``Rademacher and Gaussian Complexities: Risk Bounds and Structural Results'' J. Mach. Learn. Res. 3, 463–482 (2003).
 Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias J. Osborne, Robert Salzmann, Daniel Scheiermann, and Ramona Wolf, ``Training deep quantum neural networks'' Nature Communications 11, 808 (2020).
 Fernando G.S.L. Brandaoand Krysta M. Svore ``Quantum Speed-Ups for Solving Semidefinite Programs'' 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) 415–426 (2017).
 Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, ``Quantum amplitude amplification and estimation'' Contemporary Mathematics 305, 53–74 (2002).
 Yudong Cao, Gian Giacomo Guerreschi, and Alán Aspuru-Guzik, ``Quantum Neuron: an elementary building block for machine learning on quantum computers'' arXiv:1711.11240 (2017).
 C. Ciliberto, M. Herbster, A. D. Ialongo, M. Pontil, A. Rocchetto, S. Severini, and L. Wossnig, ``Quantum machine learning: A classical perspective'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 474, 20170551 (2018).
 C. Dürrand P. Høyer ``A quantum algorithm for finding the minimum'' arXiv:9607014 (1996).
 Andrá s Gilyén, Srinivasan Arunachalam, and Nathan Wiebe, ``Optimizing quantum optimization algorithms via faster quantum gradient computation'' Society for Industrial Applied Mathematics (2019).
 Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, ``Quantum Random Access Memory'' Phys. Rev. Lett. 100, 160501 (2008).
 Surbhi Goeland Adam R. Klivans ``Learning Neural Networks with Two Nonlinear Layers in Polynomial Time'' Proceedings of the Thirty-Second Conference on Learning Theory 99, 1470–1499 (2019).
 Lov Groverand Terry Rudolph ``Creating superpositions that correspond to efficiently integrable probability distributions'' arXiv preprint quant-ph/0208112 (2002).
 Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, ``Quantum Algorithm for Linear Systems of Equations'' Phys. Rev. Lett. 103, 150502 (2009).
 Vojtěch Havlíček, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta, ``Supervised learning with quantum-enhanced feature spaces'' Nature 567, 209–212 (2019).
 M.J. Kearnsand R.E. Schapire ``Efficient distribution-free learning of probabilistic concepts'' Proceedings  31st Annual Symposium on Foundations of Computer Science 382–391 vol.1 (1990).
 Adam Klivansand Raghu Meka ``Learning Graphical Models Using Multiplicative Weights'' 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) 343–354 (2017).
 Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu, ``Sublinear quantum algorithms for training linear and kernel-based classifiers'' Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA 97, 3815–3824 (2019).
 Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir, ``On the Computational Efficiency of Training Neural Networks'' Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1 855–863 (2014).
 Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik, ``The theory of variational hybrid quantum-classical algorithms'' New Journal of Physics 18, 023023 (2016).
 Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd, ``Quantum Support Vector Machine for Big Data Classification'' Phys. Rev. Lett. 113, 130503 (2014).
 Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray, Xin Wang, Siyi Yang, and Miklos Santha, ``Quantum algorithms for hedging and the learning of Ising models'' Phys. Rev. A 103, 012418 (2021).
 Itay Safranand Ohad Shamir ``Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks'' Proceedings of the 34th International Conference on Machine Learning - Volume 70 2979–2987 (2017).
 Bernhard Schölkopfand Alexander J Smola ``Learning with kernels: support vector machines, regularization, optimization, and beyond'' MIT press (2002).
 Maria Schuldand Nathan Killoran ``Quantum Machine Learning in Feature Hilbert Spaces'' Phys. Rev. Lett. 122, 040504 (2019).
 Ewin Tang ``A Quantum-Inspired Classical Algorithm for Recommendation Systems'' Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 217–228 (2019).
 Nathan Wiebe, Daniel Braun, and Seth Lloyd, ``Quantum Algorithm for Data Fitting'' Phys. Rev. Lett. 109, 050505 (2012).
 João F. Doriguello, Alessandro Luongo, Jinge Bao, Patrick Rebentrost, and Miklos Santha, "Quantum algorithm for stochastic optimal stopping problems with applications in finance", arXiv:2111.15332, (2021).
 Yusen Wu, Bujiao Wu, Jingbo Wang, and Xiao Yuan, "Quantum Phase Recognition via Quantum Kernel Methods", Quantum 7, 981 (2023).
 Armando Bellante and Stefano Zanero, "Quantum matching pursuit: A quantum algorithm for sparse representations", Physical Review A 105 2, 022414 (2022).
The above citations are from SAO/NASA ADS (last updated successfully 2023-12-07 00:44:27). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2023-12-07 00:44:25).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.