One of the questions that drove early work on quantum computing was whether quantum mechanics can be used to produce machines which provide experimental evidence against the extended Church-Turing thesis. The most straightforward way to do so would be to construct a quantum machine that outperforms a classical computer at some well-defined computing task. Such a demonstration goes under the name of quantum advantage in the literature.
A few years ago, it was shown that passive linear optical quantum systems can be used to implement such a problem. This problem, known as boson sampling, has since attracted a great deal of interest from the quantum photonics community, and continues to be one of the driving open problems in our field.
One of the major open theoretical problems in this field is to understand how errors affect the integrity of a boson sampling experiment. Recently, Jelmer Renema has demonstrated an algorithm that exploits one such imperfection, namely distinguishability, to classically simulate a boson sampler. In those regions of the parameter space where this algorithm is efficient, a quantum advantage is excluded.
Jelmer’s talk will consist of two parts. In the first part, he will introduce boson sampling with an emphasis on experimental challenges. He will then move on to a discussion of the classical simulation algorithm in detail.