Vi föreslår en enkel men ändå rik modell för att utvidga strategiska spel till kvantinställningen, där vi definierar kvantnash och korrelerad jämvikt och studerar förhållandet mellan klassisk och kvantekvilibria. Till skillnad från allt tidigare arbete som fokuserade på kvalitativa frågor om specifika spel i mycket små storlekar, tar vi kvantitativt upp följande grundläggande fråga för allmänna spel i växande storlekar: Hur mycket "fördel" kan spela kvantstrategier ge, om några? Två åtgärder av fördel studeras. 1. Vad är det för fel på dig? Eftersom spelet främst handlar om varje spelare som försöker maximera individuell payoff, är en naturlig åtgärd ökningen av payoff genom att spela kvant strategier. Vi betraktar naturliga kartläggningar mellan klassiska och kvanttillstånd, och studerar hur väl dessa kartläggningar bevarar jämviktsegenskaper. Bland andra resultat, vi uppvisar en korrelerad jämvikt p vars quantum superposition motsvarighet s p(s) till är långt ifrån att vara ett quantum korrelerad jämvikt; faktiskt en spelare kan öka sin vinst från nästan 0 till nästan 1 i ett [0, 1]-normaliserat spel. Vi uppnår detta genom en tensor produktkonstruktion på noggrant utformade bas fall. Resultatet kan också tolkas som i Meyers jämförelse [47]: I ett tillstånd som ingen klassisk spelare kan vinna, har en spelare som använder kvantdatorer en enorm fördel än att fortsätta att spela klassiskt. 2. Utgångspunkten är följande: Ett annat mått är hårdheten i att generera korrelerad jämvikt, för vilken vi föreslår att studera korrelationskomplexitet, en ny komplexitetsmått för korrelationsgenerering. Vi visar att det finns n-bit korrelerad jämvikt som endast kan genereras av ett EPR-par följt av lokal drift (utan kommunikation), men behöver minst log 2 (n) klassiska delade slumpmässiga bitar plus kommunikation. Den randomiserade nedre gränsen kan förbättras till n, det bästa möjliga, förutsatt (även en mycket svagare version av) en nyligen genomförd gissning i linjär algebra. Vi tror att korrelationen komplexitet, som en komplexitet-teoretisk motsvarighet till den berömda Bell ojämlikhet, har oberoende intresse Tillstånd att göra digitala eller hårda kopior av hela eller en del av detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior bär detta meddelande och den fullständiga hänvisning på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. ITCS '12 Cambridge, Massachusetts, USA Copyright 2012 ACM 978-1-4503-1115-1...$10.00. i både fysik och beräkningskomplex teori och förtjänar fler utforskningar.
Zhang i REF undersökte de dubbla fördelarna med kvantstrategier och föreslog en ny komplexitetsåtgärd som kallas korrelationskomplexitet.
Quantum strategic game theory
{'venue': "ITCS '12", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics', 'Mathematics']}