"Classical Computers Very Likely Can Not Efficiently Simulate Multimode Linear Optical Interferometers with Arbitrary Fock-State Inputs-An Elementary Argument," Version 3.0.
With thanks to Scott Aaronson and a referee for suggestions for improvement, we have expanded our argument, originally based on the exponential blowup in the Hilbert space for a bosonic, Fock-state interferometer, to analyze the similar exponential blowup for a fermionic, Fock state interferometer. We then examine both interferometers using an input-output formalism that allows us to treat them both as a boundary value problem. In the limit that the particle coherence length is much larger than the interferometer we then, sticking very close to the physics, argue that in order to access these exponentially large Hilbert spaces, the particles must arrive at the beamsplitters in a way that they are indistinguishable there, and thence their multi-particle wavefunctions must be properly symmetrized everywhere in space.
In this model, then, to compute an arbitrary output state (our goal) we must simply prepare an arbitrary input state and then use the efficient matrix transfer to transform the input to the output. Therein lies the rub. For fermions there is an efficient protocol for constructing an arbitrary input state but for bosons there is not. In other words, for a large interferometer, we cannot even setup the initial conditions in the general case, much less compute the corresponding output.
For fermions the appropriate anti-symmetrization of the total input wavefunction (the product of the spatial and spin wavefunctions) may be carried out efficiently (in polynomial time) by constructing and evaluating the Slater determinant of the basis functions. For bosons the equivalent procedure would be to symmetrize the total input wavefunction by using the 'Slater' permanent. (Slater never wrote down any such thing.) In the case of the bosons the most efficient known algorithm for computing the permanent is the Ryser algorithm, discovered 50 years ago, which scales exponentially in the size of the matrix.
Thus we conclude our elementary argument that linear optical interferometers cannot likely be efficiently simulated on a classical computer. We do this using simple arguments from quantum optics and undergraduate quantum physics and without resorting to complexity theoretic notions such as 'collapse of the polynomial hierarchy.' The small amount of quantum computer complexity that remains in our argument can now discuss in language that can be understood by the ordinary quantum physicist on the street (or in the gutter).
An amusing and informative lecture on these results, given this past week at the Quantum Information and Measurement Conference in Rochester, NY, may be found here [PDF, PPT].
With thanks to Scott Aaronson and a referee for suggestions for improvement, we have expanded our argument, originally based on the exponential blowup in the Hilbert space for a bosonic, Fock-state interferometer, to analyze the similar exponential blowup for a fermionic, Fock state interferometer. We then examine both interferometers using an input-output formalism that allows us to treat them both as a boundary value problem. In the limit that the particle coherence length is much larger than the interferometer we then, sticking very close to the physics, argue that in order to access these exponentially large Hilbert spaces, the particles must arrive at the beamsplitters in a way that they are indistinguishable there, and thence their multi-particle wavefunctions must be properly symmetrized everywhere in space.
In this model, then, to compute an arbitrary output state (our goal) we must simply prepare an arbitrary input state and then use the efficient matrix transfer to transform the input to the output. Therein lies the rub. For fermions there is an efficient protocol for constructing an arbitrary input state but for bosons there is not. In other words, for a large interferometer, we cannot even setup the initial conditions in the general case, much less compute the corresponding output.
For fermions the appropriate anti-symmetrization of the total input wavefunction (the product of the spatial and spin wavefunctions) may be carried out efficiently (in polynomial time) by constructing and evaluating the Slater determinant of the basis functions. For bosons the equivalent procedure would be to symmetrize the total input wavefunction by using the 'Slater' permanent. (Slater never wrote down any such thing.) In the case of the bosons the most efficient known algorithm for computing the permanent is the Ryser algorithm, discovered 50 years ago, which scales exponentially in the size of the matrix.
Thus we conclude our elementary argument that linear optical interferometers cannot likely be efficiently simulated on a classical computer. We do this using simple arguments from quantum optics and undergraduate quantum physics and without resorting to complexity theoretic notions such as 'collapse of the polynomial hierarchy.' The small amount of quantum computer complexity that remains in our argument can now discuss in language that can be understood by the ordinary quantum physicist on the street (or in the gutter).
An amusing and informative lecture on these results, given this past week at the Quantum Information and Measurement Conference in Rochester, NY, may be found here [PDF, PPT].
