Classical Computers Very Likely Can Not Efficiently Simulate Multimode Linear Optical Interferometers with Arbitrary Fock-State Inputs--An Elementary Argument

Aaronson and Arkhipov recently used computational complexity theory to argue that classical computers very likely cannot efficiently simulate linear, multimode, quantum-optical interferometers with arbitrary Fock-state inputs [S. Aaronson and A. Arkhipov, Theory of Computing, 9, 143(2013)]. Here we present an elementary argument that utilizes only techniques from quantum optics. We explicitly construct the Hilbert space for such an interferometer and show that that its dimension scales exponentially with all the physical resources. We also show in a simple example just how the Schr\"odinger and Heisenberg pictures of quantum theory, while mathematically equivalent, are not in general computationally equivalent. Finally, we conclude our argument by comparing the symmetry requirements of multi-particle bosonic to fermionic interferometers and, using simple physical reasoning, connect the non-simulatablity of the bosonic device to the complexity of computing the permanent of a large matrix.