**DOMINIK HANGLEITER**FU Berlin

Recent years have witnessed experiments that reach enormous levels of control over large numbers of degrees of freedom, bringing the demonstration of a speedup of a quantum device over classical devices over within reach. A rigorous demonstration and verification of a quantum speedup must be based upon rigorous complexity-theoretic arguments that take into account the available restricted experimental resources and operations. One promising route towards such an unambiguous demonstration of a quantum speedup is based on sampling from the output distribution of certain random unitary circuits constructed from particular (and possibly restricted) family of gates. Most prominently, ``boson sampling" is an example of such a proposal.
In this blackboard talk I am going to give an overview of the complexity-theoretic argument underlying the classical hardness of such schemes. In particular, I will introduce and discuss the complexity-theoretic assumptions underlying such an argument. I will then sketch how this argument applies to a specific scheme we recently put forward (1703.00466) with the goal of bringing the rigorous complexity-theoretic arguments closer to experimental scenarios available, for example, in a cold-atoms setup. This particular scheme has the additional benefit of being certifiable in a rigorous way using simple measurements only.

**Seminar, October 13, 2017, 11:00. Seminar Room
Hosted by Antonio Acín**