BosonSampling Is Far From Uniform

Understand

BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer.

• In arXiv:1306.3995, Gogolin et al.
• claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random outcome, at least "without detailed a priori knowledge"; or at any rate, that telling the two apart might itself be a hard problem.
• We first answer these claims---explaining why the first is based on a definition of "a priori knowledge" so strange that, were it adopted, almost no quantum algorithm could be distinguished from a pure random-number source; while the second is neither new nor a practical obstacle to interesting BosonSampling experiments.