Computer Science Colloquium
    LECTURE  on Tuesday 04/01/2011
Time+Place : Tuesday 04/01/2011 12:30 room 401 Taub NOTE UNUSUAL TIME AND
Speaker    : Scott Aaronson SPECIAL LECTURE
Affiliation: M I T
Host       : Johann Makowsky
Title      : The Computational Complexity of Linear Optics
Abstract   :
We give new evidence that quantum computers---moreover, rudimentary quantum
computers built entirely out of linear-optical elements---cannot be
efficiently simulated by classical computers. In particular, we define a
model of computation in which identical photons are generated, sent through
a linear-optical network, then nonadaptively measured to count the number of
photons in each mode.
This model is not known or believed to be universal for quantum computation,
and indeed, we discuss the prospects for realizing the model using current
technology. On the other hand, we prove that the model is able to solve
sampling problems and search problems that are classically intractable under
plausible assumptions.
Joint work with Alex Arkhipov.
Visit our home page-   <>
Sun Jan  2 12:48:48 IST 2011
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>