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 properties of a possibly stable super dense form of matter called "Strange Matter" and with Charles Alcock and Angela Olinto he studied the properties of "Strange Stars." His interest then shifted to general relativity and he and Alan Guth studied the classical and quantum prospects of making a new inflationary universe in the laboratory today. He, Guth and others also studied obstacles to constructing a time machine.

More recently, Farhi has been studying how to use quantum mechanics to gain algorithmic speedup in solving problems that are difficult for conventional computers. He and Sam Gutmann proposed the idea of designing algorithms based on quantum walks, which has been used to demonstrate the power of quantum computation over classical. They, along with Jeffrey Goldstone and Michael Sipser, introduced the idea of quantum computation by adiabatic evolution, which has generated much interest in the quantum computing community. This group was tied for first in showing that there is a problem that cannot be sped up by a quantum computer. In 2007, Farhi, Goldstone and Gutmann showed that a quantum computer can determine who wins a game faster than a classical computer.

Edward Farhi continues to work on quantum computing but keeps a close eye on particle physics and recent developments in cosmolo

VIEW VIDEO

http://www.youtube.com/watch?v=gKA1k3VJDq8