Quantum Alphatron: avantaj cuantic pentru învățarea cu nuclee și zgomot

Quantum Alphatron: avantaj cuantic pentru învățarea cu nuclee și zgomot

Marca temporală: 8 noiembrie 2023, ora 6:33
Nodul sursă: 2377823

Siyi Yang1, Naixu Guo1, Miklos Santha1,2și Patrick Rebentrost1

1Centrul pentru Tehnologii Cuantice, Universitatea Națională din Singapore, Singapore 117543
2Université de Paris, IRIF, CNRS, F-75013 Paris, Franța; MajuLab UMI 3654

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

La interfața învățării automate și a calculului cuantic, o întrebare importantă este ce distribuții pot fi învățate în mod dovedibil cu complexități optime ale eșantionului și cu complexități de timp accelerate cuantic. În cazul clasic, Klivans și Goel au discutat despre $Alphatron$, un algoritm pentru a învăța distribuțiile legate de regresia kernelizată, pe care l-au aplicat și la învățarea rețelelor neuronale cu două straturi. În această lucrare, oferim versiuni cuantice ale Alphatronului în setare tolerantă la erori. Într-un model de învățare bine definit, acest algoritm cuantic este capabil să ofere o accelerare polinomială pentru o gamă largă de parametri ai clasei de concept de bază. Discutăm două tipuri de accelerații, unul pentru evaluarea matricei nucleului și unul pentru evaluarea gradientului în procedura de coborâre a gradientului stocastic. De asemenea, discutăm despre avantajul cuantic în contextul învățării rețelelor neuronale cu două straturi. Munca noastră contribuie la studiul învățării cuantice cu nuclee și din eșantioane.

► Date BibTeX

► Referințe

[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 și Seth Lloyd, „Învățare automată cuantică” 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 și Jay M. Gambetta, „Învățare supravegheată cu spații caracteristice îmbunătățite cuantic” 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 „Calcul cuantic în era NISQ și nu numai” 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 „Învățare automată cuantică în spațiile caracteristice Hilbert” Fiz. Rev. Lett. 122, 040504 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.040504

[30] Ewin Tang „Un algoritm clasic de inspirație cuantică pentru sistemele de recomandare” Proceedings of the 51th 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

Citat de

[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 și 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”, Revista fizică A 105 2, 022414 (2022).

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2023-11-10 23:43:53). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2023-11-10 23:43:52).

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Timestamp-ul:

Mai mult de la Jurnalul cuantic