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.