1304.4206 (Bryan T. Gard et al.)

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

Bryan T. Gard, Robert M. Cross, Moochan B. Kim, Hwang Lee, Jonathan P. Dowling

Aaronson and Arkhipov recently used computational complexity theory to argue that classical computers very likely cannot efficiently simulate linear, multimode, quantum\textendash optical interferometers with arbitrary Fock\textendash state inputs [S. Aaronson and A. Arkhipov, arXiv:1011.3245]. 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. Finally we also show that the Schr\"{o}dinger and Heisenberg pictures of quantum theory, while mathematically equivalent, are not in general computationally equivalent.

View original: http://arxiv.org/abs/1304.4206