1Tietojenkäsittelytieteen laitos, Columbia University
2Institute for Quantum Computing ja tietojenkäsittelytieteen laitos, Waterloon yliopisto
Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.
Abstrakti
Tämä artikkeli käsittelee kvanttipeliteorian yleisen muotoilun monimutkaisuusteoreettisia näkökohtia, jotka mallintavat kvanttitietoa prosessoivien ja vaihtavien rationaalisten tekijöiden strategisia vuorovaikutuksia. Erityisesti todistamme, että laskennallinen ongelma likimääräisen Nash-tasapainon löytämiseksi laajassa kvanttipelien luokassa on, kuten klassisten pelien analoginen ongelma, sisältyy (ja siksi täydellinen) kompleksisuusluokkaan PPAD. Pääasiallinen tekninen panoksemme, joka helpottaa tätä sisällyttämistä, on laskennallisen peliteorian aikaisempien menetelmien laajentaminen strategiatiloihin, joille on ominaista puolimääräiset ohjelmat.
Suositeltu kuva: Kaavio vuorovaikutuksesta, joka edustaa monikierrosta kvanttipeliä.
► BibTeX-tiedot
► Viitteet
[1] David Meyer. "Kvanttistrategiat". Physical Review Letters 82, 1052–1055 (1999).
https: / / doi.org/ 10.1103 / PhysRevLett.82.1052
[2] Jens Eisert, Martin Wilkens ja Maciej Lewenstein. "Kvanttipelit ja kvanttistrategiat". Physical Review Letters 83, 3077–3080 (1999).
https: / / doi.org/ 10.1103 / PhysRevLett.83.3077
[3] John von Neumann ja Oskar Morgenstern. "Peliteoria ja taloudellinen käyttäytyminen". Princeton University Press. (1953). kolmas painos.
https: / / doi.org/ 10.1515 / +9781400829460
[4] John Nash. "Tasapainopisteet n-henkilön peleissä". Proceedings of the National Academy of Sciences 36, 48–49 (1950).
https: / / doi.org/ 10.1073 / pnas.36.1.48
[5] John Nash. "Yhteistyöpelit". Tohtorin väitöskirja. Princetonin yliopisto. (1950).
[6] Hong Guo, Juheng Zhang ja Gary Koehler. "Tutkimus kvanttipeleistä". Decision Support Systems 46, 318–332 (2008).
https:///doi.org/10.1016/j.dss.2008.07.001
[7] Steven van Enk ja Rob Pike. "Kvanttipelien klassiset säännöt". Physical Review A 66, 024306 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.66.024306
[8] Jinshanin Wu. "Peliteorian uusi matemaattinen esitys I". Julkaisematon käsikirjoitus, arXiv:quant-ph/0404159 (2004).
arXiv: kvant-ph / 0404159
[9] Jinshanin Wu. "Peliteorian uusi matemaattinen esitys II". Julkaisematon käsikirjoitus, arXiv:quant-ph/0405183 (2004).
arXiv: kvant-ph / 0405183
[10] Shengyu Zhang. "Kvanttistrategisen pelin teoria". Tietojenkäsittelyteorian 3. innovaatiot -konferenssin julkaisussa. Sivut 39-59. (2012).
https: / / doi.org/ 10.1145 / +2090236.2090241
[11] Gus Gutoski ja John Watrous. "Kohti kvanttipelien yleistä teoriaa". Proceedings of the 39th Annual ACM Symposium on Theory of Computing. Sivut 565-574. (2007).
https: / / doi.org/ 10.1145 / +1250790.1250873
[12] Giulio Chiribella, Giacomo D'Ariano ja Paolo Perinotti. "Kvanttipiiriarkkitehtuuri". Physical Review Letters 101, 060401 (2008).
https: / / doi.org/ 10.1103 / PhysRevLett.101.060401
[13] Giulio Chiribella, Giacomo D'Ariano ja Paolo Perinotti. "Kvanttiverkkojen teoreettinen kehys". Physical Review A 80, 022339 (2009).
https: / / doi.org/ 10.1103 / PhysRevA.80.022339
[14] Constantinos Daskalakis, Paul Goldberg ja Christos Papadimitriou. "Nash-tasapainon laskemisen monimutkaisuus". SIAM Journal on Computing 39, 195–259 (2009).
https: / / doi.org/ 10.1137 / +070699652
[15] Xi Chen, Xiaotie Deng ja Shang-Hua Teng. "Kahden pelaajan Nash-tasapainon laskemisen monimutkaisuuden ratkaiseminen". Journal of the ACM 56, 14 (2009).
https: / / doi.org/ 10.1145 / +1516512.1516516
[16] Christos Papadimitriou. "Pariteettiargumentin monimutkaisuudesta ja muista tehottomista olemassaolon todisteista". Journal of Computer and system Sciences 48, 498–532 (1994).
https://doi.org/10.1016/S0022-0000(05)80063-7
[17] Kousha Etessami ja Mihalis Yanakakis. "Nashin tasapainojen ja muiden kiinteiden pisteiden monimutkaisuudesta". SIAM Journal on Computing 39, 2531–2597 (2010).
https: / / doi.org/ 10.1137 / +080720826
[18] Kathleen Gibbons, Matthew Hoffman ja William Wootters. "Diskreetti vaiheavaruus, joka perustuu äärellisiin kenttiin". Physical Review A 70, 062101 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.062101
[19] David Gross. "Hudsonin lause äärellisulotteisille kvanttijärjestelmille". Journal of Mathematical Physics 47, 122107 (2006).
https: / / doi.org/ 10.1063 / +1.2393152
[20] Sanjeev Arora ja Boaz Barak. "Laskennallinen monimutkaisuus: moderni lähestymistapa". Cambridge University Press. (2009).
https: / / doi.org/ 10.1017 / CBO9780511804090
[21] Michael Nielsen ja Isaac Chuang. "Kvanttilaskenta ja kvanttitieto". Cambridge University Press. (2000).
https: / / doi.org/ 10.1017 / CBO9780511976667
[22] Mark Wilde. "Kvanttiinformaatioteoria". Cambridge University Press. (2017). toinen painos.
https: / / doi.org/ 10.1017 / +9781316809976
[23] John Watrous. "Kvanttitiedon teoria". Cambridge University Press. (2018).
https: / / doi.org/ 10.1017 / +9781316848142
[24] Glen Bredon. "Topologia ja geometria". Osa 139 of Graduate Texts in Mathematics. Springer. (1993).
https://doi.org/10.1007/978-1-4757-6848-0
[25] Irving Glicksberg. "Kakutanin kiinteän pisteen lauseen lisäyleistys, jota sovelletaan Nashin tasapainopisteisiin". Proceedings of the American Mathematical Society 3, 170–174 (1952).
https: / / doi.org/ 10.2307 / +2032478
[26] John Nash. "Yhteistyöpelit". Annals of Mathematics, toinen sarja 54, 286–295 (1951).
https: / / doi.org/ 10.2307 / +1969529
[27] Martin Grötschel, Laszlo Lovász ja Alexander Schrijver. "Geometriset algoritmit ja kombinatorinen optimointi". Springer-Verlag. (1988).
https://doi.org/10.1007/978-3-642-78240-4
[28] Carlton Lemke ja Joseph Howson. "Bimatrix-pelien tasapainopisteet". Journal of the Society for Industrial and Applied Mathematics 12, 413–423 (1964).
https: / / doi.org/ 10.1137 / +0112033
Viitattu
[1] Constantin Ickstadt, Thorsten Theobald ja Elias Tsigaridas, "Semidefinite games", arXiv: 2202.12035.
[2] Rafael Frongillo, "Quantum Information Elicitation", arXiv: 2203.07469.
[3] Rahul Jain, Georgios Piliouras ja Ryann Sim, "Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence", arXiv: 2211.01681.
Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2022-12-24 16:09:05). 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-12-24 16:09:03).
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.
