Kvantmänguteooria ja Quantum Nashi tasakaalude lähendamise keerukus

Taasavaldanud Platon

järgijaid: 0

John Bostanci¹ ja John Watrous²

¹Columbia ülikooli arvutiteaduse osakond
²Waterloo ülikooli kvantarvutite instituut ja arvutiteaduste kool

Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.

Abstraktne

See artikkel käsitleb kvantmänguteooria üldise sõnastuse keerukusteoreetilisi aspekte, mis modelleerivad strateegilisi interaktsioone kvantteavet töötlevate ja vahetavate ratsionaalsete agentide vahel. Eelkõige tõestame, et arvutuslik probleem ligikaudse Nashi tasakaalu leidmiseks laias kvantmängude klassis on sarnaselt klassikaliste mängude analoogse probleemiga lisatud keerukusklassi PPAD (ja seega täielik). Meie peamine tehniline panus, mis seda kaasamist hõlbustab, on arvutusmängude teooria varasemate meetodite laiendamine strateegiaruumidele, mida iseloomustavad poolkindlad programmid.

Esiletõstetud pilt: interaktsiooni diagramm, mis kujutab mitme pöördega kvantmängu.

► BibTeX-i andmed

@artikkel{Bostanci2022quantumgametheory, doi = {10.22331/q-2022-12-22-882}, url = {https://doi.org/10.22331/q-2022-12-22-882}, title = {Kvantmänguteooria ja kvanti {N}tuha tasakaalu} lähendamise keerukus, autor = {Bostanci, John ja Watrous, John}, ajakiri = {{Kvant}}, issn = {2521-327X}, väljaandja = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, helitugevus = {6}, lehekülge = {882}, kuu = detsember, aasta = {2022} }

► Viited

[1] David Meyer. "Kvantstrateegiad". Physical Review Letters 82, 1052–1055 (1999).
https:///doi.org/10.1103/PhysRevLett.82.1052

[2] Jens Eisert, Martin Wilkens ja Maciej Lewenstein. "Kvantmängud ja kvantstrateegiad". Physical Review Letters 83, 3077–3080 (1999).
https:///doi.org/10.1103/PhysRevLett.83.3077

[3] John von Neumann ja Oskar Morgenstern. “Mänguteooria ja majanduslik käitumine”. Princetoni ülikooli kirjastus. (1953). kolmas trükk.
https:///doi.org/10.1515/9781400829460

[4] John Nash. “Tasakaalupunktid n-inimese mängudes”. Proceedings of the National Academy of Sciences 36, 48–49 (1950).
https:///doi.org/10.1073/pnas.36.1.48

[5] John Nash. "Mittekoostöömängud". Doktoritöö. Princetoni ülikool. (1950).

[6] Hong Guo, Juheng Zhang ja Gary Koehler. "Kvantmängude uuring". Otsuste tugisüsteemid, 46, 318–332 (2008).
https:///doi.org/10.1016/j.dss.2008.07.001

[7] Steven van Enk ja Rob Pike. "Kvantmängude klassikalised reeglid". Physical Review A 66, 024306 (2002).
https:///doi.org/10.1103/PhysRevA.66.024306

[8] Jinshan Wu. "Mänguteooria I uus matemaatiline esitus". Avaldamata käsikiri, arXiv:quant-ph/0404159 (2004).
arXiv:quant-ph/0404159

[9] Jinshan Wu. "Mänguteooria uus matemaatiline esitus II". Avaldamata käsikiri, arXiv:quant-ph/0405183 (2004).
arXiv:quant-ph/0405183

[10] Shengyu Zhang. "Kvantstrateegilise mängu teooria". 3. Innovatsioonid teoreetilises arvutiteaduses konverentsi toimetistes. Lk 39–59. (2012).
https:///doi.org/10.1145/2090236.2090241

[11] Gus Gutoski ja John Watrous. "Kvantmängude üldise teooria poole". In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. Lk 565–574. (2007).
https:///doi.org/10.1145/1250790.1250873

[12] Giulio Chiribella, Giacomo D'Ariano ja Paolo Perinotti. "Kvantahela arhitektuur". Physical Review Letters 101, 060401 (2008).
https:///doi.org/10.1103/PhysRevLett.101.060401

[13] Giulio Chiribella, Giacomo D'Ariano ja Paolo Perinotti. "Kvantvõrkude teoreetiline raamistik". Physical Review A 80, 022339 (2009).
https:///doi.org/10.1103/PhysRevA.80.022339

[14] Constantinos Daskalakis, Paul Goldberg ja Christos Papadimitriou. "Nashi tasakaalu arvutamise keerukus". SIAM Journal on Computing 39, 195–259 (2009).
https:///doi.org/10.1137/070699652

[15] Xi Chen, Xiaotie Deng ja Shang-Hua Teng. "Kahe mängijaga Nashi tasakaalu arvutamise keerukuse lahendamine". ACM ajakiri 56, 14 (2009).
https:///doi.org/10.1145/1516512.1516516

[16] Christos Papadimitriou. "Pariteedi argumendi keerukusest ja muudest ebaefektiivsetest olemasolu tõenditest". 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. "Nashi tasakaalu ja muude fikseeritud punktide keerukuse kohta". SIAM Journal on Computing 39, 2531–2597 (2010).
https:///doi.org/10.1137/080720826

[18] Kathleen Gibbons, Matthew Hoffman ja William Wootters. "Diskreetne faasiruum, mis põhineb lõplikel väljadel". Physical Review A 70, 062101 (2004).
https:///doi.org/10.1103/PhysRevA.70.062101

[19] David Gross. "Hudsoni teoreem lõplike mõõtmetega kvantsüsteemide jaoks". Journal of Mathematical Physics 47, 122107 (2006).
https:///doi.org/10.1063/1.2393152

[20] Sanjeev Arora ja Boaz Barak. "Arvutuslik keerukus: kaasaegne lähenemine". Cambridge University Press. (2009).
https:///doi.org/10.1017/CBO9780511804090

[21] Michael Nielsen ja Isaac Chuang. "Kvantarvutus ja kvantteave". Cambridge University Press. (2000).
https:///doi.org/10.1017/CBO9780511976667

[22] Mark Wilde. "Kvantinformatsiooni teooria". Cambridge University Press. (2017). teine väljaanne.
https:///doi.org/10.1017/9781316809976

[23] John Watrous. "Kvantinformatsiooni teooria". Cambridge University Press. (2018).
https:///doi.org/10.1017/9781316848142

[24] Glen Bredon. "Topoloogia ja geomeetria". Matemaatika lõputekstide 139. köide. Springer. (1993).
https://doi.org/10.1007/978-1-4757-6848-0

[25] Irving Glicksberg. "Kakutani fikseeritud punkti teoreemi täiendav üldistus, rakendades seda Nashi tasakaalupunktidele". Proceedings of the American Mathematical Society 3, 170–174 (1952).
https:///doi.org/10.2307/2032478

[26] John Nash. "Mittekoostöömängud". Annals of Mathematics, teine seeria 54, 286–295 (1951).
https:///doi.org/10.2307/1969529

[27] Martin Grötschel, Laszlo Lovász ja Alexander Schrijver. "Geomeetrilised algoritmid ja kombinatoorne optimeerimine". Springer–Verlag. (1988).
https://doi.org/10.1007/978-3-642-78240-4

[28] Carlton Lemke ja Joseph Howson. "Bimaatriksmängude tasakaalupunktid". Journal of the Society for Industrial and Applied Mathematics 12, 413–423 (1964).
https:///doi.org/10.1137/0112033

Viidatud

[1] Constantin Ickstadt, Thorsten Theobald ja Elias Tsigaridas, “Poolkindlad mängud”, arXiv: 2202.12035.

[2] Rafael Frongillo, "Quantum Information Elicitation", arXiv: 2203.07469.

[3] Rahul Jain, Georgios Piliouras ja Ryann Sim, „Matrixi korduvate kaalude uuendused kvantnullsummamängudes: säilitusseadused ja kordumine”, arXiv: 2211.01681.

Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2022-12-24 16:09:05). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.

On Crossrefi viidatud teenus teoste viitamise andmeid ei leitud (viimane katse 2022-12-24 16:09:03).

See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.