1Centre for Quantum Technologies, National University of Singapore, Singapore 117543
2Université de Paris, IRIF, CNRS, F-75013 Paris, France; MajuLab UMI 3654
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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.
► BibTeX data
► References
[1] Jonathan Allcock, Chang-Yu Hsieh, Iordanis Kerenidis, and Shengyu Zhang, “Quantum Algorithms for Feedforward Neural Networks” ACM Transactions on Quantum Computing 1 (2020).
https://doi.org/10.1145/3411466
[2] J. van Apeldoornand A. Gilyén “Quantum algorithms for zero-sum games” arXiv:1904.03180 (2019).
https://doi.org/10.48550/arXiv.1904.03180
[3] 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).
https://doi.org/10.1088/1367-2630/17/12/123010
[4] Peter L. Bartlettand Shahar Mendelson “Rademacher and Gaussian Complexities: Risk Bounds and Structural Results” J. Mach. Learn. Res. 3, 463–482 (2003).
https://doi.org/10.5555/944919.944944
[5] 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).
https://doi.org/10.1038/s41467-020-14454-2
[6] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd, “Quantum machine learning” Nature 549, 195–202 (2017).
https://doi.org/10.1038/nature23474
[7] 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).
https://doi.org/10.1109/FOCS.2017.45
[8] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, “Quantum amplitude amplification and estimation” Contemporary Mathematics 305, 53–74 (2002).
https://doi.org/10.1090/conm/305/05215
[9] 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).
https://doi.org/10.48550/arXiv.1711.11240
[10] 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).
https://doi.org/10.1098/rspa.2017.0551
[11] C. Dürrand P. Høyer “A quantum algorithm for finding the minimum” arXiv:9607014 (1996).
https://doi.org/10.48550/arXiv.quant-ph/9607014
[12] Andrá s Gilyén, Srinivasan Arunachalam, and Nathan Wiebe, “Optimizing quantum optimization algorithms via faster quantum gradient computation” Society for Industrial Applied Mathematics (2019).
https://doi.org/10.1137/1.9781611975482.87
[13] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, “Architectures for a quantum random access memory” Phys. Rev. A 78, 052310 (2008).
https://doi.org/10.1103/PhysRevA.78.052310
[14] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, “Quantum Random Access Memory” Phys. Rev. Lett. 100, 160501 (2008).
https://doi.org/10.1103/PhysRevLett.100.160501
[15] 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).
https://doi.org/10.48550/arXiv.1709.06010
[16] Lov Groverand Terry Rudolph “Creating superpositions that correspond to efficiently integrable probability distributions” arXiv preprint quant-ph/0208112 (2002).
https://doi.org/10.48550/arXiv.quant-ph/0208112
[17] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, “Quantum Algorithm for Linear Systems of Equations” Phys. Rev. Lett. 103, 150502 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502
[18] 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).
https://doi.org/10.1038/s41586-019-0980-2
[19] M.J. Kearnsand R.E. Schapire “Efficient distribution-free learning of probabilistic concepts” Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science 382–391 vol.1 (1990).
https://doi.org/10.1109/FSCS.1990.89557
[20] Adam Klivansand Raghu Meka “Learning Graphical Models Using Multiplicative Weights” 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) 343–354 (2017).
https://doi.org/10.1109/FOCS.2017.39
[21] 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).
https://doi.org/10.48550/arXiv.1904.02276
[22] 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).
https://doi.org/10.5555/2968826.2968922
[23] 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).
https://doi.org/10.1088/1367-2630/18/2/023023
[24] John Preskill “Quantum Computing in the NISQ era and beyond” Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[25] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd, “Quantum Support Vector Machine for Big Data Classification” Phys. Rev. Lett. 113, 130503 (2014).
https://doi.org/10.1103/PhysRevLett.113.130503
[26] 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).
https://doi.org/10.1103/PhysRevA.103.012418
[27] 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).
https://doi.org/10.5555/3305890.3305989
[28] Bernhard Schölkopfand Alexander J Smola “Learning with kernels: support vector machines, regularization, optimization, and beyond” MIT press (2002).
https://doi.org/10.7551/mitpress/4175.001.0001
[29] Maria Schuldand Nathan Killoran “Quantum Machine Learning in Feature Hilbert Spaces” Phys. Rev. Lett. 122, 040504 (2019).
https://doi.org/10.1103/PhysRevLett.122.040504
[30] 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).
https://doi.org/10.1145/3313276.3316310
[31] M.D. Vose “A linear algorithm for generating random numbers with a given distribution” IEEE Transactions on Software Engineering 17, 972–975 (1991).
https://doi.org/10.1109/32.92917
[32] A. J. Walker “New fast method for generating discrete random numbers with arbitrary frequency distributions” Electronics Letters 10, 127–128 (1974).
https://doi.org/10.1049/el:19740097
[33] Nathan Wiebe, Daniel Braun, and Seth Lloyd, “Quantum Algorithm for Data Fitting” Phys. Rev. Lett. 109, 050505 (2012).
https://doi.org/10.1103/PhysRevLett.109.050505
Cited by
[1] Lukas Mouton, Florentin Reiter, Ying Chen, and Patrick Rebentrost, “Deep learning-based quantum algorithms for solving nonlinear partial differential equations”, arXiv:2305.02019, (2023).
[2] Yusen Wu, Bujiao Wu, Jingbo Wang, and Xiao Yuan, “Quantum Phase Recognition via Quantum Kernel Methods”, arXiv:2111.07553, (2021).
[3] 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).
[4] Debbie Lim and Patrick Rebentrost, “A Quantum Online Portfolio Optimization Algorithm”, arXiv:2208.14749, (2022).
[5] Jeong Yu Han and Patrick Rebentrost, “Quantum advantage for multi-option portfolio pricing and valuation adjustments”, arXiv:2203.04924, (2022).
[6] Yusen Wu, Bujiao Wu, Jingbo Wang, and Xiao Yuan, “Quantum Phase Recognition via Quantum Kernel Methods”, Quantum 7, 981 (2023).
[7] 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-11-09 23:41:37). 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-11-09 23:41:35).
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.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-11-08-1174/
