Title: The Classical Complexity of Boson Sampling,
Abstract: We study the classical complexity of the exact Boson Sampling problem where
the objective is to produce provably correct random samples from a particular
quantum mechanical distribution. The computational framework was proposed by
Aaronson and Arkhipov in 2011 as an attainable demonstration of `quantum
supremacy', that is a practical quantum computing experiment able to produce
output at a speed beyond the reach of classical (that is non-quantum) computer
hardware. Since its introduction Boson Sampling has been the subject of intense
international research in the world of quantum computing. On the face of it,
the problem is challenging for classical computation. Aaronson and Arkhipov
show that exact Boson Sampling is not efficiently solvable by a classical
computer unless $P^{\#P} = BPP^{NP}$ and the polynomial hierarchy collapses to
the third level.
The fastest known exact classical algorithm for the standard Boson Sampling
problem takes $O({m + n -1 \choose n} n 2^n )$ time to produce samples for a
system with input size $n$ and $m$ output modes, making it infeasible for
anything but the smallest values of $n$ and $m$. We give an algorithm that is
much faster, running in $O(n 2^n + \operatorname{poly}(m,n))$ time and $O(m)$
additional space. The algorithm is simple to implement and has low constant
factor overheads. As a consequence our classical algorithm is able to solve the
exact Boson Sampling problem for system sizes far beyond current photonic
quantum computing experimentation, thereby significantly reducing the
likelihood of achieving near-term quantum supremacy in the context of Boson
Sampling.