Speaker
Description
Quantum simulators promise to give rise to new insights into dynamical and static properties of complex quantum systems, beyond what is available on classical supercomputers. There is already some good evidence that quantum simulators have the potential to outperform classical computers. Yet, in order to be prone against arguments claiming a lack of imagination, this superior computational capabilities should be expressed in terms of notions of computational complexity. One of the main milestones in quantum information science is hence to realize quantum devices that exhibit an exponential computational advantage over classical ones without being universal quantum computers in complexity theoretic terms, a state of affairs dubbed exponential quantum computational advantage or simply "quantum computational supremacy". The paradigmatic boson samplers are devices of this type. We end the talk by discussing a number of surprisingly simple and physically plausible schemes that once realized show such a quantum computational supremacy. Both aspects of physical implementation are discussed as well as mathematical arguments used in proofs relating to notions of computational complexity. We will see that while there is good evidence that these devices outperform classical computers, they can still be efficiently and rigorously certified in their trustworthy functioning.
