QUROPE Quantum Information Processing and Communication in Europe

The paper provides new evidence that quantum computers cannot be efficiently simulated by classical computers. In particular, the authors consider a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number in each mode. While this model is not known or believed to be universal for quantum computation, it is shown that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions.