Theory of Computing
-------------------
Title     : The Computational Complexity of Linear Optics
Authors   : Scott Aaronson and Alex Arkhipov
Volume    : 9
Number    : 4
Pages     : 143-252
URL       : https://theoryofcomputing.org/articles/v009a004

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. 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 $P^{#P} = BPP^{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 $\#P$-hard to approximate the permanent of a matrix $A$ of 
independent $N(0,1)$ Gaussian entries, with high probability over $A$; 
and the _Permanent Anti-Concentration Conjecture_, which says that 
$|Per(A)| \geq\sqrt{n!}/poly(n)$ 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.