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.