Article

Toward a general theory of quantum games

Authors:

John WatrousAuthors Info & Claims

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

Pages 565 - 574

https://doi.org/10.1145/1250790.1250873

Published: 11 June 2007 Publication History

Abstract

We study properties of quantum strategies, which are complete specifications of a given party's actions in any multiple-round interaction involving the exchange of quantum information with one or more other parties. In particular, we focus on a representation of quantum strategies that generalizes the Choi-Jamiolkowski representation of quantum, with respect to which each strategy is described by a single operations. This new representation associates with each strategy a positive semidefinite operator acting only on the tensor product of its input and output spaces. Various facts about such representations are established, and two applications are discussed: the first is a new and conceptually simple proof of Kitaev's lower bound for strong coin-flipping, and the second is a proof of the exact characterization QRG = EXP of the class of problems having quantum refereed games.

References

[1]

Ambainis, A. A new protocol and lower bounds for quantum coin flipping. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (2001), pp. 134--142.

Digital Library

[2]

Ambainis, A., Buhrman, H., Dodis, Y., and Röhrig, H. Multiparty quantum coin flipping. In Proceedings of the 19th Annual IEEE Conference on Computational Complexity (2004), pp. 250--259.

Digital Library

[3]

Babai, L. Trading group theory for randomness. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (1985), pp. 421--429.

Digital Library

[4]

Babai, L., and Moran, S. Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences 36, 2 (1988), 254--276.

Digital Library

[5]

Benjamin, S., and Hayden, P. Comment on "Quantum games and quantum strategies" . Physical Review Letters 87, 6 (2001), article 069801.

[6]

Brassard, G., Broadbent, A., and Tapp, A. Quantum pseudo-telepathy. Foundations of Physics 35, 11 (2005), 1877--1907.

[7]

Choi, M.-D. Completely positive linear maps on complex matrices. Linear Algebra and Its Applications 10, 3 (1975), 285--290.

[8]

Cleve, R., Hoyer, P., Toner, B., and Watrous, J. Consequences and limits of nonlocal strategies. In Proceedings of the 19th Annual IEEE Conference on Computational Complexity (2004), pp. 236--249.

Digital Library

[9]

Eisert, J., Wilkens, M., and Lewenstein, M. Quantum games and quantum strategies. Physical Review Letters 83, 15 (1999), 3077--3080.

[10]

Enk, Sv., and Pike, R. Classical rules in quantum games. Physical Review A 66 (2002), article 024306.

[11]

Fan, K. Minimax theorems. Proceedings of the National Academy of Sciences 39 (1953), 42--47.

[12]

Feige, U., and Kilian, J. Making games short. In Proceedings of the Twenty-Ninth annual ACM Symposium on Theory of Computing (1997), pp. 506--516.

Digital Library

[13]

Feige, U., and Shamir, A. Multi-oracle interactive protocols with constant space verifiers. Journal of Computer and System Sciences 44 (1992), 259--271.

Digital Library

[14]

Feige, U., Shamir, A., and Tennenholtz, M. The noisy oracle problem. In Advances in Cryptology -- Proceedings of Crypto'88 (1990), vol. 403 of Lecture Notes in Computer Science, Springer--Verlag, pp. 284--296.

Digital Library

[15]

Feigenbaum, J., Koller, D., and Shor, P. A game-theoretic classification of interactive complexity classes. In Proceedings of the 10th Conference on Structure in Complexity Theory (1995), pp. 227--237.

Digital Library

[16]

Goldwasser, S., Micali, S., and Rackoff, C. The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18, 1 (1989), 186--208.

Digital Library

[17]

Grötschel, M., Lovász, L., and Schrijver, A. Geometric Algorithms and Combinatorial Optimization. Springer--Verlag, 1988.

[18]

Gutoski, G. Upper bounds for quantum interactive proofs with competing provers. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity (2005), pp. 334--343.

Digital Library

[19]

Gutoski, G., and Watrous, J. Quantum interactive proofs with competing provers. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (2005), vol. 3404 of Lecture Notes in Computer Science, Springer, pp. 605--616.

Digital Library

[20]

Jamiolkowski, A. Linear transformations which preserve trace and positive semidefiniteness of operators. Reports on Mathematical Physics 3, 4 (1972), 275--278.

[21]

Khachiyan, L. A polynomial time algorithm in linear programming. Soviet Mathematics Doklady 20 (1979), 191--194.

[22]

Kitaev, A. Quantum coin-flipping. Presentation at the 6th Workshop on Quantum Information Processing (QIP 2003), 2002.

[23]

Kitaev, A., Shen, A., and Vyalyi, M. Classical and Quantum Computation, vol47 of Graduate Studies in Mathematics. American Mathematical Society, 2002.

Digital Library

[24]

Kitaev, A., and Watrous, J. Parallelization, amplification, and exponential time simulation of quantum interactive proof system. In Proceedings of the 32nd ACM Symposium on Theory of Computing (2000), pp. 608--617.

Digital Library

[25]

Koller, D., and Megiddo, N. The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior 4 (1992), 528--552.

[26]

Lee, C.-F., and Johnson, N. Efficiency and formalism of quantum games. Physical Review A 67 (2003), article 022311.

[27]

Meyer, D. Quantum strategies. Physical Review Letters 82, 5 (1999), 1052--1055.

[28]

Mochon, C. Quantum weak coin-flipping with bias of 0.192. In 45th Annual IEEE Symposium on Foundations of Computer Science (2004), pp. 2--11.

Digital Library

[29]

Nesterov, Y., and Nemirovski, A. Interior point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics 13 (1994).

[30]

Nielsen, M.A., and Chuang, I.L. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

Digital Library

[31]

Rockafellar, R.T. Convex Analysis. Princeton University Press, 1970.

[32]

Röhrig, H. Quantum Query Complexity and Distributed Computing. PhD thesis, Centrum voor Wiskunde en Informatica, 2004.

[33]

Ville, J. Sur la théorie générale des jeux oú intervient l'habileté des joueurs. Traité du calcul des probabilités et des applications IV, 2 (1938), 105--113.

[34]

Watrous, J. PSPACE has constant-round quantum interactive proof systems. Theoretical Computer Science 292, 3 (2003), 575--588.

Digital Library

Cited By

Costa FBarrett JShrapnel S(2025)A de Finetti theorem for quantum causal structuresQuantum10.22331/q-2025-02-11-16289(1628)Online publication date: 11-Feb-2025
https://doi.org/10.22331/q-2025-02-11-1628
Bansal ASikora J(2025)Breaking barriers in two-party quantum cryptography via stochastic semidefinite programmingQuantum10.22331/q-2025-01-20-16029(1602)Online publication date: 20-Jan-2025
https://doi.org/10.22331/q-2025-01-20-1602
Wang D(2024)Universal quantum computing models: a perspective of resource theoryActa Physica Sinica10.7498/aps.73.2024089373:22(220302)Online publication date: 2024
https://doi.org/10.7498/aps.73.20240893
Show More Cited By

Index Terms

Toward a general theory of quantum games
1. Theory of computation

Recommendations

Playing quantum games by a scheme with pre- and post-selection

We propose a scheme to play quantum games by assuming that the two players interact with each other. Thus, by pre-selection, two players can choose their initial states, and some dilemma in classical game may be removed by post-selection, which is ...
Quantum-Secure Coin-Flipping and Applications
ASIACRYPT '09: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology

In this paper, we prove classical coin-flipping secure in the presence of quantum adversaries. The proof uses a recent result of Watrous [20] that allows quantum rewinding for protocols of a certain form. We then discuss two applications. First, the ...
Construction of general quantum channel for quantum teleportation

We investigate teleportation and controlled teleportation of an arbitrary $$N$$ -qubit state by using a multipartite entanglement channel. By establishing one-to-one correspondence between an $$N$$ -qubit quantum state and a high-dimension quantum state, we ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

June 2007

734 pages

ISBN:9781595936318

DOI:10.1145/1250790

General Chair:
David Johnson
AT&T Labs - Research
,
Program Chair:
Uriel Feige
Microsoft Research and Weizmann Institute

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC07

Sponsor:

STOC07: Symposium on Theory of Computing

June 11 - 13, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

107
Total Citations
View Citations
916
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)11

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Costa FBarrett JShrapnel S(2025)A de Finetti theorem for quantum causal structuresQuantum10.22331/q-2025-02-11-16289(1628)Online publication date: 11-Feb-2025
https://doi.org/10.22331/q-2025-02-11-1628
Bansal ASikora J(2025)Breaking barriers in two-party quantum cryptography via stochastic semidefinite programmingQuantum10.22331/q-2025-01-20-16029(1602)Online publication date: 20-Jan-2025
https://doi.org/10.22331/q-2025-01-20-1602
Wang D(2024)Universal quantum computing models: a perspective of resource theoryActa Physica Sinica10.7498/aps.73.2024089373:22(220302)Online publication date: 2024
https://doi.org/10.7498/aps.73.20240893
Liu QYang Y(2024)Efficient tensor networks for control-enhanced quantum metrologyQuantum10.22331/q-2024-12-18-15718(1571)Online publication date: 18-Dec-2024
https://doi.org/10.22331/q-2024-12-18-1571
Lin WPiliouras GSim RVarvitsiotis A(2024)No-Regret Learning and Equilibrium Computation in Quantum GamesQuantum10.22331/q-2024-12-17-15698(1569)Online publication date: 17-Dec-2024
https://doi.org/10.22331/q-2024-12-17-1569
Milz SQuintino M(2024)Characterising transformations between quantum objects, 'completeness' of quantum properties, and transformations without a fixed causal orderQuantum10.22331/q-2024-07-17-14158(1415)Online publication date: 17-Jul-2024
https://doi.org/10.22331/q-2024-07-17-1415
Taranto PQuintino MMurao MMilz S(2024)Characterising the Hierarchy of Multi-time Quantum Processes with Classical MemoryQuantum10.22331/q-2024-05-02-13288(1328)Online publication date: 2-May-2024
https://doi.org/10.22331/q-2024-05-02-1328
Akibue SKato GTani S(2024)Probabilistic Unitary Synthesis with Optimal AccuracyACM Transactions on Quantum Computing10.1145/36635765:3(1-27)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.1145/3663576
Chiribella G(2024)Extreme quantum states and processes, and extreme points of general spectrahedra in finite dimensional algebrasInternational Journal of Quantum Information10.1142/S021974992440004522:05Online publication date: 27-Jul-2024
https://doi.org/10.1142/S0219749924400045
Eryganov IHrdina JNávrat A(2024)Quantization of two- and three-player cooperative games based on QRAJournal of Physics A: Mathematical and Theoretical10.1088/1751-8121/ad7c9c57:42(425303)Online publication date: 1-Oct-2024
https://doi.org/10.1088/1751-8121/ad7c9c
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten