Google Tech Talks April, 2 2008 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 N^0.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. Speaker: Edward Farhi Professor of Physics; Director, Center for Theoretical Physics Massachusetts Institute of Technology Research Interests: Edward Farhi was trained as a theoretical particle physicist but has also worked on astrophysics, general relativity, and the foundations of quantum mechanics. His present interest is the theory of quantum computation. As a graduate student, Farhi invented the jet variable “Thrust,” which is used to describe how particles in high energy accelerator collisions come out in collimated streams. He then worked with Leonard Susskind on grand unified theories with electro-weak dynamical symmetry breaking. He and Larry Abbott proposed an (almost viable) model in which quarks, leptons, and massive gauge bosons are composite. With Robert Jaffe, he worked out many of the …
