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. =A0In 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.