Paradigmatic quantum devices

点击翻译按钮获取中文摘要

What is the computational power of realistic and comparably simple quantum systems? The highly interdisciplinary research program laid out here addresses this foundational question from two complementing and distinct, yet closely intertwined, angles, taking a fresh perspective. On the one hand, it asks in what precise way realistic paradigmatic quantum devices that are experimentally within reach can outperform classical computers, in a way that does not rely on unproven assumptions. This has profound implications on realizing quantum computational devices the power of which can be stated beyond reasonable doubt. It also has impact on how we grasp the physical Church Turing thesis. On the other hand, we plan to investigate the complexity of quantum simulators, accessible again in present experiments. For this research program to be successful, ideas and methods of quantum many-body physics, quantum simulation, theoretical computer science and complexity, as well as signal processing have to be brought together.