Teoria dei giochi quantistici e complessità dell'approssimazione degli equilibri quantistici di Nash

Ripubblicato da Platone

Seguaci: 0

Giovanni Bostanci¹ ed Giovanni Watrous²

¹Dipartimento di Informatica, Columbia University
²Institute for Quantum Computing e School of Computer Science, Università di Waterloo

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

Questo articolo si occupa degli aspetti teorici della complessità di una formulazione generale della teoria quantistica dei giochi che modellizza le interazioni strategiche tra agenti razionali che elaborano e scambiano informazioni quantistiche. In particolare, dimostriamo che il problema computazionale di trovare un equilibrio di Nash approssimato in un'ampia classe di giochi quantistici è, come l'analogo problema per i giochi classici, incluso nella (e quindi completo per) la classe di complessità PPAD. Il nostro principale contributo tecnico, che facilita questa inclusione, è un'estensione di metodi precedenti nella teoria dei giochi computazionali a spazi strategici caratterizzati da programmi semidefiniti.

Immagine di presentazione: diagramma di un'interazione che rappresenta un gioco quantistico a più turni.

► dati BibTeX

@article{Bostanci2022quantumgametheory, doi = {10.22331/q-2022-12-22-882}, url = {https://doi.org/10.22331/q-2022-12-22-882}, title = {Quantum game theory and the complexity of approximating quantum {N}ash equilibria}, author = {Bostanci, John and Watrous, John}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {6}, pages = {882}, month = dec, year = {2022} }

► Riferimenti

, David Mayer. "Strategie quantistiche". Lettere di revisione fisica 82, 1052–1055 (1999).
https: / / doi.org/ 10.1103 / PhysRevLett.82.1052

, Jens Eisert, Martin Wilkens e Maciej Lewenstein. "Giochi quantistici e strategie quantistiche". Lettere di revisione fisica 83, 3077–3080 (1999).
https: / / doi.org/ 10.1103 / PhysRevLett.83.3077

, John von Neumann e Oskar Morgenstern. “Teoria dei giochi e comportamento economico”. Stampa dell'Università di Princeton. (1953). terza edizione.
https: / / doi.org/ 10.1515 / 9781400829460 mila

, Giovanni Nash. "Punti di equilibrio nei giochi n-persone". Atti della National Academy of Sciences 36, 48-49 (1950).
https: / / doi.org/ 10.1073 / pnas.36.1.48

, Giovanni Nash. "Giochi non cooperativi". Tesi di dottorato. Università di Princeton. (1950).

, Hong Guo, Juheng Zhang e Gary Koehler. "Un'indagine sui giochi quantistici". Sistemi di supporto alle decisioni 46, 318–332 (2008).
https:///doi.org/10.1016/j.dss.2008.07.001

, Steven van Enk e Rob Pike. "Regole classiche nei giochi quantistici". Revisione fisica A 66, 024306 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.66.024306

, Jinshan Wu. "Una nuova rappresentazione matematica della teoria dei giochi I". Manoscritto non pubblicato, arXiv:quant-ph/0404159 (2004).
arXiv: Quant-ph / 0404159

, Jinshan Wu. "Una nuova rappresentazione matematica della teoria dei giochi II". Manoscritto non pubblicato, arXiv:quant-ph/0405183 (2004).
arXiv: Quant-ph / 0405183

, Shengyu Zhang. "Teoria quantistica dei giochi strategici". In Atti della terza conferenza sulle innovazioni nella scienza dell'informatica teorica. Pagine 3–39. (59).
https: / / doi.org/ 10.1145 / 2090236.2090241 mila

, Gus Gutoski e John Watrous. "Verso una teoria generale dei giochi quantistici". In Atti del 39° simposio annuale ACM sulla teoria dell'informatica. Pagine 565–574. (2007).
https: / / doi.org/ 10.1145 / 1250790.1250873 mila

, Giulio Chiribella, Giacomo D'Ariano, Paolo Perinotti. "Architettura del circuito quantistico". Lettere di revisione fisica 101, 060401 (2008).
https: / / doi.org/ 10.1103 / PhysRevLett.101.060401

, Giulio Chiribella, Giacomo D'Ariano, Paolo Perinotti. "Quadro teorico per reti quantistiche". Revisione fisica A 80, 022339 (2009).
https: / / doi.org/ 10.1103 / PhysRevA.80.022339

, Constantinos Daskalakis, Paul Goldberg e Christos Papadimitriou. "La complessità del calcolo di un equilibrio di Nash". SIAM Journal on Computing 39, 195–259 (2009).
https: / / doi.org/ 10.1137 / 070699652 mila

, Xi Chen, Xiaotie Deng e Shang-Hua Teng. "Risolvere la complessità del calcolo degli equilibri di Nash a due giocatori". Giornale dell'ACM 56, 14 (2009).
https: / / doi.org/ 10.1145 / 1516512.1516516 mila

, Christos Papadimitriou. "Sulla complessità dell'argomento della parità e altre inefficienti prove di esistenza". Journal of Computer and System Sciences 48, 498–532 (1994).
https://doi.org/10.1016/S0022-0000(05)80063-7

, Kousha Etessami e Mihalis Yannakakis. "Sulla complessità degli equilibri di Nash e altri punti fermi". SIAM Journal on Computing 39, 2531–2597 (2010).
https: / / doi.org/ 10.1137 / 080720826 mila

, Kathleen Gibbons, Matthew Hoffman e William Wootters. "Spazio delle fasi discreto basato su campi finiti". Revisione fisica A 70, 062101 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.062101

, Davide Grosso. "Teorema di Hudson per sistemi quantistici a dimensione finita". Giornale di fisica matematica 47, 122107 (2006).
https: / / doi.org/ 10.1063 / 1.2393152 mila

, Sanjeev Arora e Boaz Barak. "Complessità computazionale: un approccio moderno". Pressa dell'Università di Cambridge. (2009).
https: / / doi.org/ 10.1017 / CBO9780511804090

, Michael Nielsen e Isaac Chuang. "Calcolo quantistico e informazione quantistica". Pressa dell'Università di Cambridge. (2000).
https: / / doi.org/ 10.1017 / CBO9780511976667

, Marco Wilde. "Teoria dell'informazione quantistica". Pressa dell'Università di Cambridge. (2017). seconda edizione.
https: / / doi.org/ 10.1017 / 9781316809976 mila

, Giovanni Watrous. "Teoria dell'informazione quantistica". Pressa dell'Università di Cambridge. (2018).
https: / / doi.org/ 10.1017 / 9781316848142 mila

, Glen Bredon. "Topologia e geometria". Volume 139 di Testi di Laurea in Matematica. Primavera. (1993).
https://doi.org/10.1007/978-1-4757-6848-0

, Irving Glicksberg. “Un'ulteriore generalizzazione del teorema del punto fisso di Kakutani, con applicazione ai punti di equilibrio di Nash”. Atti dell'American Mathematical Society 3, 170–174 (1952).
https: / / doi.org/ 10.2307 / 2032478 mila

, Giovanni Nash. "Giochi non cooperativi". Annali di matematica, seconda serie 54, 286–295 (1951).
https: / / doi.org/ 10.2307 / 1969529 mila

, Martin Grötschel, Laszlo Lovász e Alexander Schrijver. “Algoritmi geometrici e ottimizzazione combinatoria”. Springer-Verlag. (1988).
https://doi.org/10.1007/978-3-642-78240-4

, Carlton Lemke e Joseph Howson. “Punti di equilibrio dei giochi bimatrice”. Journal of the Society for Industrial and Applied Mathematics 12, 413–423 (1964).
https: / / doi.org/ 10.1137 / 0112033 mila

Citato da

[1] Constantin Ickstadt, Thorsten Theobald e Elias Tsigaridas, “Giochi semidefiniti”, arXiv: 2202.12035.

[2] Rafael Frongillo, “Elicitazione di informazioni quantistiche”, arXiv: 2203.07469.

[3] Rahul Jain, Georgios Piliouras e Ryann Sim, "Aggiornamenti dei pesi moltiplicativi della matrice nei giochi quantistici a somma zero: leggi di conservazione e ricorrenza", arXiv: 2211.01681.

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2022-12-24 16:09:05). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2022-12-24 16:09:03).

Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.