[QIP-Sem] QIP seminar, Tue 10/4, 4:15, 32-124, Scott Aaronson

[Peter Shor]

MIT Quantum Information Processing seminar
Tuesday 10/4 at 4:15 in 32-124
-------------------------------------------------

Scott Aaronson (MIT)

The Complexity of Linear Optics

Abstract:

In recent work with Alex Arkhipov, we proposed a rudimentary form of quantum computing, based entirely on linear optics with nonadaptive measurements; and used a connection between linear optics and the permanent function to show that even this limited model could solve sampling and search problems that are intractable for classical computers under plausible complexity assumptions. In this talk, I'll discuss this work in a self-contained way accessible to classical TCS folks, and mention some of its implications for quantum computing experiments in the very near future. I'll also discuss some more general results that emerged from our work. These include: a new equivalence between sampling problems and search problems based on Kolmogorov complexity; a new, linear-optics-based proof of Valiant's famous theorem that the permanent is #P-complete; and a new classical approximation algorithm for the permanent.  Papers: http://arxiv.org/abs/1011.3245 http://arxiv.org/abs/1009.5104 
  http://www.scottaaronson.com/papers/sharp.pdf 

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem