Quantum computers and simulators promise computational capabilities that go far beyond those of classical computers. They claim to provide insights into strongly correlated quantum matter that are difficult to come by with classical means. Experimental progress in realizing
quantum devices has been rapid in recent years. While this is enormously exciting as such, it also opens up new research questions.
So - in what sense can we hope for quantum devices to be able to compute properties beyond classical means? In the technical part of
this talk, we will pose variations of this question in three readings. Firstly, we will witness how efficiently verifiable quantum advantages
can be conceived. Secondly, we will look at notions of machine learning that are much in the focus of attention; but to date, most
insights in this realm are of a purely heuristic nature. Thus, we will have a look at a rigorous exponential separation of quantum devices
over classical ones in meaningful learning tasks. Thirdly, we will investigate the intricate but simple question of how one can actually
ensure that the quantum device has done what it is supposed to do. In each of these themes, we connect to ongoing activities in the Bavarian research landscape.