Revised: December 30, 2012

Published: February 9, 2013

**Keywords:**#P, bosons, BQP, linear optics, permanent, polynomial hierarchy, random self-reducibility, sampling

**Categories:**quantum, complexity theory, #P, BQP, permanent, polynomial-time hierarchy, random self-reducibility, boson, optics, linear optics, sampling, quantum sampling

**ACM Classification:**F.1.2, F.1.3

**AMS Classification:**81P68, 68Q17, 68Q15

**Abstract:**
[Plain Text Version]

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.
Our first result says that, if there exists a polynomial-time classical
algorithm that samples from the same probability distribution as a
linear-optical network, then
${\mathsf P}^{\mathsf{\#P}}=\mathsf{BPP}^{\mathsf{NP}}$,
and hence the polynomial hierarchy collapses to the third
level. Unfortunately, this result assumes an extremely accurate simulation.
Our main result suggests that even an approximate or noisy classical
simulation would already imply a collapse of the polynomial hierarchy.
For this, we need two unproven conjectures: the *Permanent-of-Gaussians
Conjecture*, which says that it is $\mathsf{\#P}$-hard to approximate the
permanent of a matrix $A$ of independent $\mathcal{N}\left( 0,1\right)$
Gaussian entries, with high probability over $A$; and the *Permanent
Anti-Concentration Conjecture*, which says that $\left\vert
\operatorname*{Per}\left( A\right) \right\vert
\geq\sqrt{n!}/\operatorname*{poly}\left( n\right)$
with high probability over $A$. We
present evidence for these conjectures, both of which seem interesting even
apart from our application.
This paper does not assume knowledge of quantum optics. Indeed, part of its
goal is to develop the beautiful theory of noninteracting bosons underlying
our model, and its connection to the permanent function, in a self-contained
way accessible to theoretical computer scientists.

An extended abstract of this article appeared in the Proceedings of STOC 2011.