####

####

#### Seminar is being held jointly with Physics Colloquium

A Quantum Computer Can Determine Who Wins a Game Faster Than a Classical Computer

** Professor Edward Farhi **

MIT**
**

**M****onday
October 19, 2009**

**4:00 PM,
**
Schwartz Auditorium, Rockefeller Hall

__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 N final positions but only at N0.753. I
will show that with a quantum computer the exponent can be reduced to
0.5. The technique involves quantum scattering theory and illustrates
how ideas from physics can be used to design quantum algorithms that
outperform even best possible classical algorithms.