Monikätiset kvanttirosvot: tutkiminen vastaan ​​hyväksikäyttö kvanttitilojen ominaisuuksien oppimisessa

Aikaleima: 29. kesäkuuta 2022 6
Lähdesolmu: 1590105

Josep Lumbreras1, Erkka Haapasalo1ja Marco Tomamichel1,2

1Quantum Technologies -keskus, Singaporen kansallinen yliopisto, Singapore
2Sähkö- ja tietokonetekniikan laitos, tekniikan tiedekunta, Singaporen kansallinen yliopisto, Singapore

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Aloitamme tutkimuksen etsinnän ja hyödyntämisen välisistä kompromisseista kvanttitilojen ominaisuuksien online-oppimisessa. Koska oraakkelilla on peräkkäinen pääsy tuntemattomaan kvanttitilaan, meidän tehtävämme on jokaisella kierroksella valita havaittava joukosta toimia, joilla pyritään maksimoimaan sen odotusarvo tilaan (palkkio). Edellisiltä kierroksilta saatua tietoa tuntemattomasta tilasta voidaan käyttää asteittain parantamaan toiminnan valintaa, mikä pienentää eroa palkinnon ja annetulla toimintasarjalla saavutettavan maksimaalisen palkinnon välillä (katuminen). Tarjoamme erilaisia ​​informaatioteoreettisia alarajoja kumulatiiviselle katumukselle, jota optimaalisen oppijan täytyy kokea, ja osoitamme, että se skaalautuu vähintään pelattujen kierrosten lukumäärän neliöjuureen. Tutkimme myös kumulatiivisen katumuksen riippuvuutta käytettävissä olevien toimien määrästä ja taustalla olevan tilan ulottuvuudesta. Lisäksi esittelemme strategioita, jotka ovat optimaalisia rosvoille, joilla on rajallinen määrä käsiä ja yleinen sekatila.

[Upotetun sisällön]

► BibTeX-tiedot

► Viitteet

[1] T. Lattimore ja C. Szepesvári. "Rostialgoritmit". Cambridge University Press. (2020).
https: / / doi.org/ 10.1017 / +9781108571401

[2] A. Slivkins. "Johdatus monikätisiin rosvoihin". Koneoppimisen perusteet ja suuntaukset 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / +2200000068

[3] S. Bubeck ja N. Cesa-Bianchi. "Stokastisten ja ei-stokastisten monikätisten rosvo-ongelmien pahoitteluanalyysi". Koneoppimisen perusteet ja suuntaukset 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / +2200000024

[4] D. Bouneffouf, I. Rish ja C. Aggarwal. "Tutkimus monikätisten ja kontekstuaalisten rosvojen sovelluksista". Vuonna 2020 IEEE Congress on Evolutionary Computation (CEC). Sivut 1-8. (2020).
https://​/​doi.org/​10.1109/​CEC48606.2020.9185782

L. Tang, R. Rosales, A. Singh ja D. Agarwal. "Automaattinen mainosmuodon valinta kontekstuaalisten rosvojen kautta". 22. ACM International Conference on Information and Knowledge Management -konferenssin julkaisuissa. Sivut 1587–1594. Computing Machinery Association (2013).
https: / / doi.org/ 10.1145 / +2505515.2514700

[6] M. Cohen, I. Lobel ja R. Paes Leme. "Ominaisuuspohjainen dynaaminen hinnoittelu". Management Science 66, 4921–4943 (2020).
https://doi.org/ 10.1287/mnsc.2019.3485

[7] W. Thompson. "Todennäköisyydestä, että yksi tuntematon todennäköisyys ylittää toisen, kun otetaan huomioon kahden näytteen todisteet." Biometrika 25, 285–294 (1933).
https://​/​doi.org/​10.1093/​biomet/​25.3-4.285

[8] H. Robbins. "Joitakin näkökohtia kokeiden peräkkäiseen suunnitteluun". Bulletin of the American Mathematical Society 58, 527–535 (1952).
https:/​/​doi.org/​10.1090/​S0002-9904-1952-09620-8

[9] TL Lai ja H. Robbins. "Asymptoottisesti tehokkaat mukautuvat allokointisäännöt". Advances in Applied Mathematics 6, 4–22 (1985).
https:/​/​doi.org/​10.1016/​0196-8858(85)90002-8

[10] P. Auer, N. Cesa-Bianchi ja P. Fischer. "Rajallisen ajan analyysi moniaseista rosvoongelmasta". Mach. Oppia. 47, 235–256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352

[11] B. Casalé, G. Di Molfetta, H. Kadri, ja L. Ralaivola. "Kvanttirosvot". Quantum Mach. Intell. 2 (2020).
https:/​/​doi.org/​10.1007/​s42484-020-00024-8

[12] D. Wang, X. You, T. Li ja A. Childs. "Kvanttitutkimusalgoritmit monikätisille rosvoille". Tekoälyä käsittelevän AAAI-konferenssin julkaisuissa. Nide 35, sivut 10102–10110. (2021).

[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang ja M. Santha. "Kvanttialgoritmit suojaukseen ja muodostumismallien oppimiseen". Phys. Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418

[14] O. Shamir. "Rostojen lineaarisen optimoinnin monimutkaisuudesta". Proceedings of The 28th Conference on Learning Theory. Proceedings of Machine Learning Researchin osa 40, sivut 1523–1551. PMLR (2015).

[15] P. Rusmevichientong ja J. Tsitsiklis. "Lineaarisesti parametroidut rosvot". Operaatiotutkimuksen matematiikka 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446

[16] J. Barry, DT Barry ja S. Aaronson. "Kvanttiosittain havaittavissa olevat markovin päätöksentekoprosessit". Phys. Rev. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311

[17] M. Ying, Y. Feng ja S. Ying. "Optimaalinen politiikka kvanttimarkovin päätösprosesseille". International Journal of Automation and Computing 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z

[18] M. Paris ja J. Rehacek. "Kvanttitilaestimointi". Springer Publishing Company, Incorporated. (2010). 1. painos.
https: / / doi.org/ 10.1007 / b98673

[19] S. Aaronson. "Kvanttitilojen varjotomografia". Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Sivut 325–338. STOC 2018. Computing Machinery Association (2018).
https: / / doi.org/ 10.1145 / +3188745.3188802

[20] S. Aaronson, X. Chen, E. Hazan, S. Kale ja A. Nayak. "Kvanttitilojen online-oppiminen". Journal of Statistical Mechanics: Theory and Experiment 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988

[21] J. Bretagnolle ja C. Huber. "Estimation des densités: risque minimax". Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 47, 119–137 (1979).
https: / / doi.org/ 10.1007 / BF00535278

[22] M. Müller-Lennert, F. Dupuis, O. Szehr, S. Fehr ja M. Tomamichel. "Kvanttirényi-entropioista: uusi yleistys ja joitain ominaisuuksia". Journal of Mathematical Physics 54, 122203 (2013).
https: / / doi.org/ 10.1063 / +1.4838856

[23] M. Wilde, A. Winter ja D. Yang. "Vahva keskustelu klassiselle sotkeutumiskyvylle ja Hadamard-kanaville kerrostetun Rényi-suhteellisen entropian kautta". Communications in Mathematical Physics 331, 593–622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x

[24] W. Hoeffding. "Rajallisten satunnaismuuttujien summien todennäköisyysepäyhtälöt". Journal of the American Statistical Association 58, 13–30 (1963).
https: / / doi.org/ 10.1080 / +01621459.1963.10500830

[25] P. Auer. "Luottamusrajojen käyttäminen hyväksikäytön ja tutkimuksen välisissä kompromisseissa". J. Mach. Oppia. Res. 3, 397–422 (2003).
https: / / doi.org/ 10.5555 / +944919.944941

[26] D. Varsha, T. Hayes ja S. Kakade. "Stokastinen lineaarinen optimointi rosvopalautteen alla." Oppimisteorian 21. konferenssin julkaisuissa. Sivut 355-366. (2008).

[27] P. Rusmevichientong ja JN Tsitsiklis. "Lineaarisesti parametroidut rosvot". Operaatiotutkimuksen matematiikka 35, 395–411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446

[28] Y. Abbasi-Yadkori, D. Pál ja Cs. Szepesvári. "Parannetut algoritmit lineaarisille stokastisille rosvoille". Kirjassa Advances in Neural Information Processing Systems. Osa 24. Curran Associates, Inc. (2011).

[29] TL Lai. "Adaptiivinen hoidon jakaminen ja monikätinen rosvoongelma". The Annals of Statistics 15, 1091-1114 (1987).
https: / / doi.org/ 10.1214 / AOS / 1176350495

[30] M. Guţă, J. Kahn, R. Kueng ja JA Tropp. "Nopea tomografia optimaalisilla virherajoilla". Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111

[31] T. Lattimore ja B. Hao. "Bandiittivaiheen haku". Kirjassa Advances in Neural Information Processing Systems. osa 34, sivut 18801–18811. Curran Associates, Inc. (2021).

Viitattu

[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang ja Xiaoming Sun, "Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logathmic Rerets", arXiv: 2205.14988.

[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang ja Rui Yang, "Adaptive Online Learning of Quantum States", arXiv: 2206.00220.

Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2022-07-24 00:26:50). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.

On Crossrefin siteerattu palvelu tietoja teosten viittaamisesta ei löytynyt (viimeinen yritys 2022-07-24 00:26:48).

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.

Aikaleima:

Lisää aiheesta Quantum Journal