David A. Meyer,
``Quantum games and quantum algorithms'',
to appear in the AMS Contemporary Mathematics volume: Quantum Computation and Quantum Information Science;
expanded version of an invited talk presented at the Special Session on Quantum Computation and Information at the Joint Mathematics Meetings, Washington, DC, 19-22 January 2000.
A quantum algorithm for an oracle problem can be understood as a quantum strategy for a player in a two-player zero-sum game in which the other player is constrained to play classically. I formalize this correspondence and give examples of games (and hence oracle problems) for which the quantum player can do better than would be possible classically. The most remarkable example is the Bernstein-Vazirani quantum search algorithm which I show creates no entanglement at any timestep.
PlainTeX (10 pages): PostScript (156K),
This paper expands on my reply to comments of S. J. van Enk and others on ``Quantum strategies''.