Monday, October 18, 2010
11:00 AM
Computer Studies Bldg. Room 209
Dr. Scott Aaronson
Massachusetts Institute of Technology
The Computational Complexity of Linear Optics
I'll discuss a linear-optics experiment that might be feasible with current technology, and argue that, if the experiment succeeded, it would provide evidence that at least some nontrivial quantum computation is possible in nature. The resources that we consider are not known or believed to be universal for quantum computation; nevertheless, we show that they would allow the solution of certain sampling and search problems that seem to be intractable for classical computers.

Joint work with Alex Arkhipov.

Bio: He is an Associate Professor of Electrical Engineering and Computer Science at MIT, affiliated with CSAIL. His research interests center around the limitations of quantum computers, and computational complexity theory more generally. Received his PhD in Computer Science at University of California, Berkeley. His B.Sc. in Computer Science from Cornell University.

Refreshments will be provided at 10:45 AM