All Abstracts | Poster Abstracts | Talk Abstracts | Tutorial Abstracts

A quantum computer can determine who wins a game faster than a classical computer

Edward Farhi, Massachusetts Institute of Technology

(Session 6 : Saturday from 08:30-09:15)

Abstract. Imagine a game where two players go back and forth making moves and at the end of a fixed number of moves the position is either a win or a loss for the first player. In this case, if both players play best possible, it is determined at the first move who wins or loses. To figure out who will be the winner you need not look at all of the final positions but only at N^.753 where N is the number of final positions. I will show that with a quantum computer the exponent can be reduced to 1/2. The technique involves quantum scattering theory.