Proving Quantum Speedups for Random Circuit Families
October 13th, 2017 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