1Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, D-14195 Berlijn, Duitsland
2Afdeling Elektrotechniek en Computerwetenschappen, TU Berlijn, D-10587 Berlijn, Duitsland
3FhG SIT, D-64295 Darmstadt, Duitsland
4Helmholtz Center Berlin, D-14109 Berlin, Duitsland
5Afdeling Wiskunde en Informatica, Freie Universität Berlin, D-14195 Berlijn, Duitsland
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
Hier bestuderen we de vergelijkende kracht van klassieke en kwantumleerders voor generatieve modellering binnen het Probably Ongeveer Correct (PAC) raamwerk. Meer specifiek beschouwen we de volgende taak: Gegeven steekproeven van een onbekende discrete kansverdeling, output met hoge waarschijnlijkheid een efficiënt algoritme voor het genereren van nieuwe steekproeven op basis van een goede benadering van de oorspronkelijke verdeling. Ons primaire resultaat is de expliciete constructie van een klasse van discrete kansverdelingen die, onder de beslissende aanname van Diffie-Hellman, aantoonbaar niet efficiënt PAC leerbaar is door een klassiek generatief modelleeralgoritme, maar waarvoor we een efficiënte kwantumleerder construeren. Deze klasse van verdelingen biedt daarom een concreet voorbeeld van een generatief modelleringsprobleem waarvoor kwantumleerlingen een aantoonbaar voordeel vertonen ten opzichte van klassieke leeralgoritmen. Daarnaast bespreken we technieken voor het bewijzen van klassieke generatieve modelleringshardheidsresultaten, evenals de relatie tussen de PAC-leerbaarheid van Booleaanse functies en de PAC-leerbaarheid van discrete kansverdelingen.
► BibTeX-gegevens
► Referenties
[1] LG Valiant. Een theorie van het leerbare. Communications of the ACM, 27 (11): 1134-1142, 1984. 10.1145 / 1968.1972.
https: / / doi.org/ 10.1145 / 1968.1972
[2] MJ Kearns, UV Vazirani en U. Vazirani. Een inleiding tot computationele leertheorie. MIT-pers, 1994a. 10.7551 / mitpress / 3897.001.0001.
https: / / doi.org/ 10.7551 / mitpress / 3897.001.0001
[3] S. Shalev-Shwartz en S. Ben-David. Inzicht in machine learning: van theorie tot algoritmen. Cambridge University Press, 2014. 10.1017 / CBO9781107298019.
https: / / doi.org/ 10.1017 / CBO9781107298019
[4] S. Arunachalam en R. de Wolf. Gastcolumn: een overzicht van de theorie van kwantumonderwijs ACM SIGACT News, 48 (2): 41-67, 2017. 10.1145 / 3106700.3106710.
https: / / doi.org/ 10.1145 / 3106700.3106710
[5] C. Ciliberto, A. Rocchetto, A. Rudi en L. Wossnig. Statistische limieten van kwantumleren onder supervisie. Physical Review A, 102 (4), oktober 2020 / physreva.10.1103.
https: / / doi.org/ 10.1103 / physreva.102.042414
[6] V. Dunjko en HJ Briegel. Machine learning en kunstmatige intelligentie in het kwantumdomein: een overzicht van recente vooruitgang. Rep. Prog. Phys., 81 (7): 074001, 2018. 10.1088 / 1361-6633 / aab406.
https: / / doi.org/ 10.1088 / 1361-6633 / aab406
[7] M. Schuld en F. Petruccione. Begeleid leren met kwantumcomputers. Springer, 2018. 10.1007 / 978-3-319-96424-9.
https://doi.org/10.1007/978-3-319-96424-9
[8] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe en S. Lloyd. Quantum machine learning. Nature, 549 (7671): 195–202, 2017. 10.1038 / nature23474.
https: / / doi.org/ 10.1038 / nature23474
[9] NH Bshouty en JC Jackson. DNF leren over de uniforme distributie met behulp van een kwantumvoorbeeldorakel. SIAM Journal on Computing, 28 (3): 1136-1153, 1998. 10.1145 / 225298.225312.
https: / / doi.org/ 10.1145 / 225298.225312
[10] CL Canonne. Een korte opmerking over het leren van discrete distributies. arXiv-voordruk arXiv: 2002.11457, 2020a.
arXiv: 2002.11457
[11] S. Kamath, A. Orlitsky, D. Pichapati en AT Suresh. Over het leren van distributies van hun steekproeven. In P. Grünwald, E. Hazan en S. Kale, redacteuren, Proceedings of The 28th Conference on Learning Theory, volume 40 van Proceedings of Machine Learning Research, pagina's 1066-1100, Parijs, Frankrijk, 03-06 juli 2015. PMLR . URL http: / / procedures.mlr.press/ v40 / Kamath15.html.
http: / / procedures.mlr.press/ v40 / Kamath15.html
[12] I. Diakonikolas. Gestructureerde distributies leren. Handbook of Big Data, 267, 2016. 10.1201 / b19567.
https: / / doi.org/ 10.1201 / b19567
[13] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville en Y. Bengio. Generatieve vijandelijke netten. In Advances in neurale informatieverwerkingssystemen, pagina's 2672-2680, 2014.
[14] DP Kingma en M. Welling. Variationele bays automatisch coderen. arXiv-voordruk arXiv: 1312.6114, 2013.
arXiv: 1312.6114
[15] I. Kobyzev, S. Prince en M. Brubaker. Stromen normaliseren: een inleiding en herziening van de huidige methoden. IEEE-transacties op patroonanalyse en machine-intelligentie, pagina's 1-16, 2020. 10.1109 / tpami.2020.2992934.
https: / / doi.org/ 10.1109 / tpami.2020.2992934
[16] B. Coyle, D. Mills, V. Danos en E. Kashefi. The Born supremacy: kwantumvoordeel en training van een Ising Born-machine. npj Quantum Information, 6: 60, 2020 / s10.1038-41534-020-00288.
https://doi.org/10.1038/s41534-020-00288-9
[17] J.-G. Liu en L. Wang. Differentieerbaar leren van quantumcircuit Born machines. Phys. Rev.A, 98 (6): 062324, 2018 / PhysRevA.10.1103.
https: / / doi.org/ 10.1103 / PhysRevA.98.062324
[18] M. Benedetti, D. Garcia-Pintos, O. Perdomo, V. Leyton-Ortega, Y. Nam en A. Perdomo-Ortiz. Een generatieve modelleringsaanpak voor het benchmarken en trainen van ondiepe kwantumcircuits. npj Quantum Information, 5 (1), mei 2019 / s10.1038-41534-019-0157.
https://doi.org/10.1038/s41534-019-0157-8
[19] X. Gao, Z. Zhang en L. Duan. Een kwantumalgoritme voor machine learning op basis van generatieve modellen. Science Advances, 4 (12): eaat9004, 2018. 10.1126 / sciadv.aat9004.
https: / / doi.org/ 10.1126 / sciadv.aat9004
[20] P.-L. Dallaire-Demers en N. Killoran. Kwantumgeneratieve vijandige netwerken. Phys. Rev.A, 98, 2018. 10.1103 / physreva.98.012324.
https: / / doi.org/ 10.1103 / physreva.98.012324
[21] L. Hu, S.-H. Wu, W. Cai, Y. Ma, X. Mu, Y. Xu, H. Wang, Y. Song, D.-L. Deng, C.-L. Zou en L. Sun. Kwantumgeneratief vijandelijk leren in een supergeleidend kwantumcircuit. Science Advances, 5 (1): eaav2761, 2019. 10.1126 / sciadv.aav2761.
https: / / doi.org/ 10.1126 / sciadv.aav2761
[22] S. Lloyd en C. Weedbrook. Kwantumgeneratief leren van tegenstanders. Phys. Rev. Lett., 121 (4): 040502, 2018. 10.1103 / PhysRevLett.121.040502.
https: / / doi.org/ 10.1103 / PhysRevLett.121.040502
[23] S. Chakrabarti, H. Yiming, T. Li, S. Feizi en X. Wu. Generatieve vijandige netwerken van Quantum Wasserstein. In Advances in neurale informatieverwerkingssystemen, pagina's 6781-6792, 2019.
[24] G. Verdon, J. Marks, S. Nanda, S. Leichenauer en J. Hidary. Quantum Hamiltonian-ased-modellen en het variationele kwantum-thermalizer-algoritme, 2019. arXiv preprint arXiv: 1910.02071.
arXiv: 1910.02071
[25] S. Aaronson en A. Arkhipov. De computationele complexiteit van lineaire optica. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, pagina 333–342, New York, NY, VS, 2011. Association for Computing Machinery. 10.1145 / 1993636.1993682.
https: / / doi.org/ 10.1145 / 1993636.1993682
[26] MJ Bremner, A. Montanaro en DJ Shepherd. Gemiddelde complexiteit versus simulatie bij benadering van pendelende quantumberekeningen. Phys. Rev. Lett., 117: 080501, aug 2016. 10.1103 / PhysRevLett.117.080501.
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501
[27] F. Arute, K. Arya, R. Babbush, D. Bacon, JC Bardin, R. Barends, R. Biswas, S. Boixo, FGSL Brandao, DA Buell, et al. Kwantumoverheersing met behulp van een programmeerbare supergeleidende processor. Nature, 574 (7779): 505-510, 2019 / s10.1038-41586-019-1666.
https://doi.org/10.1038/s41586-019-1666-5
[28] D. Boneh. De beslissing Diffie-Hellman-probleem. In International Algorithmic Number Theory Symposium, pagina's 48-63. Springer, 1998. 10.1007 / BFb0054851.
https: / / doi.org/ 10.1007 / BFb0054851
[29] M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, RE Schapire en L. Sellie. Over de leerbaarheid van discrete distributies. In Proceedings of the 94th Annual ACM Symposium on Theory of Computing, STOC '273, pagina's 282-1994, New York, NY, VS, 10.1145b. ACM. 195058.195155 / XNUMX.
https: / / doi.org/ 10.1145 / 195058.195155
[30] M. Mosca en C. Zalka. Exacte kwantum-fourier-transformaties en discrete logaritme-algoritmen. International Journal of Quantum Information, 2 (01): 91-100, 2004. 10.1142 / S0219749904000109.
https: / / doi.org/ 10.1142 / S0219749904000109
[31] O. Goldreich, S. Goldwasser en S. Micali. Hoe willekeurige functies te construeren. J. ACM, 33 (4): 792-807, augustus 1986. 10.1145 / 6490.6503.
https: / / doi.org/ 10.1145 / 6490.6503
[32] EL Lehmann en JP Romano. Statistische hypothesen testen. Springer Science & Business Media, 2006. 10.1111 / j.1467-985X.2007.00473_10.x.
https://doi.org/10.1111/j.1467-985X.2007.00473_10.x
[33] O. Goldreich. Fundamenten van cryptografie: deel 1, basisgereedschap. Cambridge University Press, 2007. 10.1017 / CBO9780511546891.
https: / / doi.org/ 10.1017 / CBO9780511546891
[34] J. Katz en Y. Lindell. Inleiding tot moderne cryptografie (Chapman & Hall / Crc Cryptography and Network Security Series). Chapman & Hall / CRC, 2007. 10.1201 / b17668.
https: / / doi.org/ 10.1201 / b17668
[35] M. Zhandry. Hoe kwantum-willekeurige functies te construeren. In Proceedings of the IEEE 2012rd Annual Symposium on Foundations of Computer Science, FOCS '53, pagina's 12-679. IEEE Computer Society, 687. 2012 / FOCS.10.1109.
https: / / doi.org/ 10.1109 / FOCS.2012.37
[36] A. Bogdanov en A. Rosen. Pseudo-willekeurige functies: drie decennia later. In Tutorials on the Foundations of Cryptography, pagina's 79-158. Springer, 2017. 10.1007 / 978-3-319-57048-8_3.
https://doi.org/10.1007/978-3-319-57048-8_3
[37] M. Blum en S. Micali. Hoe cryptografisch sterke reeksen van pseudo-willekeurige bits te genereren. SIAM journal on Computing, 13 (4): 850-864, 1984. 10.1109 / SFCS.1982.72.
https: / / doi.org/ 10.1109 / SFCS.1982.72
[38] M. Naor en O. Reingold. Getaltheoretische constructies van efficiënte pseudo-willekeurige functies. Tijdschrift van de ACM (JACM), 51 (2): 231–262, 2004. 10.1145 / 972639.972643.
https: / / doi.org/ 10.1145 / 972639.972643
[39] RR Farashahi, B. Schoenmakers en A. Sidorenko. Efficiënte pseudowillekeurige generatoren op basis van de ddh-aanname. In International Workshop on Public Key Cryptography, pagina's 426-441. Springer, 2007. 10.1007 / 978-3-540-71677-8_28.
https://doi.org/10.1007/978-3-540-71677-8_28
[40] CL Canonne. Een onderzoek naar distributietests: uw gegevens zijn groot. Maar is het blauw? Nummer 9 in enquêtes onder afgestudeerden. Theory of Computing Library, 2020b. 10.4086 / toc.gs.2020.009.
https: / / doi.org/ 10.4086 / toc.gs.2020.009
[41] G. Valiant en P. Valiant. Een clt en strakke ondergrenzen voor het schatten van entropie. In Electronic Colloquium on Computational Complexity (ECCC), volume 17, pagina 9. Citeseer, 2010.
[42] G. Valiant en P. Valiant. De kracht van lineaire schatters. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pagina's 403-412. IEEE, 2011. 10.1109 / FOCS.2011.81.
https: / / doi.org/ 10.1109 / FOCS.2011.81
[43] G. Valiant en P. Valiant. Een automatische ongelijkheidsbewijs en bijvoorbeeld een optimale identiteitstest. SIAM J. Comput., 46 (1): 429-455, 2017. 10.1137 / 151002526.
https: / / doi.org/ 10.1137 / 151002526
[44] D. Hangleiter, M. Kliesch, J. Eisert en C. Gogolin. Voorbeeldcomplexiteit van apparaatonafhankelijk gecertificeerde kwantumsuprematie. Phys. Rev. Lett., 122: 210502, 2019 / PhysRevLett.10.1103.
https: / / doi.org/ 10.1103 / PhysRevLett.122.210502
[45] Y. Liu, S. Arunachalam en K. Temme. Een rigoureuze en robuuste kwantumversnelling bij machinaal leren onder supervisie. arXiv-voordruk arXiv: 2010.02174, 2020.
arXiv: 2010.02174
[46] K. Pietrzak. Cryptografie van het leren van pariteit met ruis. In International Conference on Current Trends in Theory and Practice of Computer Science, pagina's 99-114. Springer, 2012. 10.1007 / 978-3-642-27660-6_9.
https://doi.org/10.1007/978-3-642-27660-6_9
[47] AW Cross, G. Smith en JA Smolin. Quantum leren robuust tegen ruis. Phys. Rev. A, 92 (1): 012327, 2015. 10.1103 / physreva.92.012327.
https: / / doi.org/ 10.1103 / physreva.92.012327
[48] AB Grilo, I. Kerenidis en T. Zijlstra. Leren-met-fouten-probleem is eenvoudig met kwantummonsters. Phys. Rev.A, 99: 032314, 2019. 10.1103 / physreva.99.032314.
https: / / doi.org/ 10.1103 / physreva.99.032314
[49] D. Riste, MP da Silva, CA Ryan, AW Cross, AD Córcoles, JA Smolin, JM Gambetta, JM Chow en BR Johnson. Demonstratie van kwantumvoordeel bij machine learning. npj Quantum Inf., 3 (1): 1–5, 2017. 10.1038 / s41534-017-0017-3.
https://doi.org/10.1038/s41534-017-0017-3
[50] M. Kearns en L. Valiant. Cryptografische beperkingen bij het leren van booleaanse formules en eindige automaten. Journal of the ACM (JACM), 41 (1): 67-95, 1994. 10.1145 / 174644.174647.
https: / / doi.org/ 10.1145 / 174644.174647
[51] RA Servedio en SJ Gortler. Equivalenties en scheidingen tussen kwantum en klassieke leerbaarheid. SIAM J. Comp., 33 (5): 1067-1092, 2004. 10.1137 / S0097539704412910.
https: / / doi.org/ 10.1137 / S0097539704412910
[52] K. Verbeurgt. DNF leren onder de uniforme verdeling in quasi-polynomiale tijd. In Proceedings van de derde jaarlijkse workshop over computationele leertheorie, pagina's 314-326, 1990. 10.1016 / B978-1-55860-146-8.50027-8.
https://doi.org/10.1016/B978-1-55860-146-8.50027-8
[53] M. Kharitonov. Cryptografische hardheid van distributiespecifiek leren. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC '93, pagina 372-381, New York, NY, VS, 1993. Association for Computing Machinery. 10.1145 / 167088.167197.
https: / / doi.org/ 10.1145 / 167088.167197
[54] M. Kharitonov. Cryptografische ondergrenzen voor leerbaarheid van booleaanse functies op de uniforme distributie. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, pagina 29-36, New York, NY, VS, 1992. Association for Computing Machinery. 10.1145 / 130385.130388.
https: / / doi.org/ 10.1145 / 130385.130388
[55] V. Arvind en NV Vinodchandran. De complexiteit van het precies leren van algebraïsche concepten. In International Workshop on Algorithmic Learning Theory, pagina's 100–112. Springer, 1996. 10.1007 / 3-540-61863-5_38.
https://doi.org/10.1007/3-540-61863-5_38
[56] D. Haussler, M. Kearns, N. Littlestone en MK Warmuth. Equivalentie van modellen voor leerbaarheid van polynomen. Information and Computation, 95 (2): 129-161, 1991. 10.1016 / 0890-5401 (91) 90042-Z.
https://doi.org/10.1016/0890-5401(91)90042-Z
[57] R. Board en L. Pitt. Over de noodzaak van occam-algoritmen. Theoretische informatica, 100 (1): 157-184, 1992. 10.1145 / 100216.100223.
https: / / doi.org/ 10.1145 / 100216.100223
[58] A. Blumer, A. Ehrenfeucht, D. Haussler en MK Warmuth. Leerbaarheid en de vapnik-chervonenkis-dimensie. Journal of the ACM (JACM), 36 (4): 929-965, 1989. 10.1145 / 76359.76371.
https: / / doi.org/ 10.1145 / 76359.76371
[59] X. Gao, S.-T. Wang en L.-M. Duan. Kwantumoverheersing voor het simuleren van een translatie-invariant spinsmodel. Phys. Rev. Lett., 118: 040502, januari 2017. 10.1103 / PhysRevLett.118.040502.
https: / / doi.org/ 10.1103 / PhysRevLett.118.040502
[60] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf en J. Eisert. Architecturen voor kwantumsimulatie die een kwantumsnelheid tonen. Phys. Rev. X, 8: 021010, 2018 / PhysRevX.10.1103.
https: / / doi.org/ 10.1103 / PhysRevX.8.021010
[61] J. Miller, S. Sanders en A. Miyake. Kwantumoverheersing in berekeningen op basis van constante tijdmeting: een uniforme architectuur voor bemonstering en verificatie. Phys. Rev.A, 96 (6): 062320, december 2017. 10.1103 / PhysRevA.96.062320.
https: / / doi.org/ 10.1103 / PhysRevA.96.062320
[62] M. Hayashi en Y. Takeuchi. Kwantumberekeningen voor woon-werkverkeer verifiëren via getrouwheidsschatting van gewogen grafiektoestanden. New J. Phys., 21 (9): 093060, 2019. 10.1088 / 1367-2630 / ab3d88.
https://doi.org/10.1088/1367-2630/ab3d88
Geciteerd door
[1] Yunchao Liu, Srinivasan Arunachalam en Kristan Temme, "Een rigoureuze en robuuste kwantumversnelling in supervised machine learning", arXiv: 2010.02174.
[2] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven en Jarrod R. McClean, "Kracht van gegevens bij het leren van kwantummachines", arXiv: 2011.01938.
[3] Bob Coecke, Giovanni de Felice, Konstantinos Meichanetzidis en Alexis Toumi, "Foundations for Near-Term Quantum Natural Language Processing", arXiv: 2012.03755.
[4] Daniel Herr, Benjamin Obert en Matthias Rosenkranz, "Anomaliedetectie met variationele kwantumgeneratieve vijandige netwerken", arXiv: 2010.10492.
[5] Manuel S. Rudolph, Ntwali Bashige Toussaint, Amara Katabarwa, Sonika Johri, Borja Peropadre en Alejandro Perdomo-Ortiz, "Generation of High-Resolution Handwritten Digits with an Ion-Trap Quantum Computer", arXiv: 2012.03924.
[6] Brian Coyle, Maxwell Henderson, Justin Chan Jin Le, Niraj Kumar, Marco Paini en Elham Kashefi, "Quantum versus Classical Generative Modeling in Finance", arXiv: 2008.00691.
[7] Stefano Mangini, Francesco Tacchino, Dario Gerace, Daniele Bajoni en Chiara Macchiavello, "Quantum computing-modellen voor kunstmatige neurale netwerken", arXiv: 2102.03879.
[8] Murphy Yuezhen Niu, Andrew M. Dai, Li Li, Augustus Odena, Zhengli Zhao, Vadim Smelyanskyi, Hartmut Neven en Sergio Boixo, "Leerbaarheid en complexiteit van kwantummonsters", arXiv: 2010.11983.
[9] Ieva Čepaitė, Brian Coyle en Elham Kashefi, "A Continuous Variable Born Machine", arXiv: 2011.00904.
[10] Marcello Benedetti, Brian Coyle, Mattia Fiorentini, Michael Lubasch en Matthias Rosenkranz, "Variationele gevolgtrekking met een kwantumcomputer", arXiv: 2103.06720.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2021-03-23 10:02:58). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
Kon niet ophalen Door Crossref geciteerde gegevens tijdens laatste poging 2021-03-23 10:02:49: kon niet geciteerde gegevens voor 10.22331 / q-2021-03-23-417 niet ophalen van Crossref. Dit is normaal als de DOI recent is geregistreerd.
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
Coinsmart. Beste Bitcoin-beurs in Europa
Bron: https://quantum-journal.org/papers/q-2021-03-23-417/
