Abstract: Aaronson and Arkhipov recently used computational complexity theory to argue that classical computers very likely cannot efficiently simulate linear, multimode, quantum-optical interferometers with single photon inputs. Here we present an elementary argument of the same result that utilizes only techniques from quantum optics. We explicitly construct the Hilbert space for a passive linear optical interferometer with only Fock-state inputs and show that Hilbert space dimension scales exponentially with all the physical resources. We also show in a simple example just how the Schrödinger and Heisenberg pictures of quantum theory, while mathematically equivalent, are not in general computationally equivalent. We conclude our argument by comparing the symmetry requirements of multiparticle bosonic to fermionic interferometers and, using simple physical reasoning, connect the nonsimulatability of the bosonic device to the complexity of computing the permanent of a large matrix. Finally we show how a boson sampling interferometer may be used in the context of quantum metrology.

Date: 15 July 2015