Abstract

The belief that nature cannot be simulated efficiently at the quantum level by a Turing machine, and conversely that a device exploiting quantum capabilities should be able to outperform classical computers, lies at the heart of quantum information. Still, no experimental evidence for this conjecture has been achieved so far, since the requirements for a large scale universal quantum computer able to outperform a classical one are extremely demanding. For this reason, the idea of finding classically-hard computational problems which could be solved efficiently by a simpler, non-universal quantum device has recently raised a considerable interest. The Boson Sampling problem [1] is one of the main candidates for this purpose. It consists of picking a complex-valued random m × n unitary matrix U and sampling from the probability distribution, over all the possible n × n submatrices of U, given by the permanent of the submatrix (a calculation which is known to be classically intractable). A relatively simple quantum device can be designed to solve efficiently the same problem: a bunch of n indistinguishable photons injected in n fixed inputs of an m × m linear interferometer will evolve following the same permanent formula. It has been conjectured that a device working with few tens of photons interfering through few hundreds of modes would start to challenge the performances of current supercomputers. The main obstacle towards this endeavour is represented by the limited scalability of current photon generation schemes. Indeed, photon sources based on Spontaneous Parametric DownConversion (SPDC) are the candidate of choice in terms of photon indistinguishability and simplicity of the apparatus. In fact, small-scale implementations using SPDC have been reported [2–5]. However, the limited efficiency avoids using SPDC for scaling up to generation of tens of photons.

© 2015 IEEE