The potential of analog quantum simulators: Tools for economical certification and assessment of their computational power

量子模拟器有望在微观层面上理解物理世界，这在经典计算机上的数值模拟似乎是无法实现的。从物理角度来看，特别有希望的是所谓的模拟模拟器，它允许在实验室精确控制的条件下探测复杂的量子动力学。事实上，近年来，模拟仿真已经成为一个非常活跃的研究领域。尽管如此，许多概念性问题仍有待解决；如果要实现最终的承诺，就必须找到这些问题的令人满意的答案。本研究计划解决这些概念性问题。据推测，量子模拟器比经典计算机更强大，但与此同时，当试图找出模拟是否正确时，这构成了一个挑战。那么，如何才能最经济、最可行地证明量子器件的正确功能，同时采用经典和量子技术？那么，同样重要的是，对于哪些任务，量子模拟器比传统计算机更强大？这项建议提出了一项协调一致的方案来解决这些问题。特别是，它介绍了新的验证和认证工具，使用采样技术和交互式证明系统的量子认证创新工具。在几个方面，它从各种角度探讨了量子器件优于经典机器的性能问题，从对量子多体系统动力学的见解到量子采样问题的新思想，再到计算复杂性的新方法，以评估存在现实误差的模拟模拟器。

Quantum simulators promise to gain an understanding of the physical world at the microlevel that seems unattainable using numerical simulations on classical computers. Specifically promising from a physical perspective are so-called analog simulators, which allow to probe complex quantum dynamics under precisely controlled conditions in the laboratory. Indeed, in recent years, analog simulation has become an extraordinarily active field of research. Still, many conceptual questions are wide open; if the ultimate promise is to be fulfilled, a satisfactory answer to these questions has to be found. This research proposal addresses these conceptual questions. Presumably, quantum simulators are more powerful than classical computers, but at the same time this constitutes a challenge when trying to find out whether a simulation has been correct. So how can one most economically and feasibly certify the correct functioning of quantum devices, employing classical and quantum techniques? Then, equally important, for what tasks is a quantum simulator more powerful than a classical computer? This proposal suggests a concerted programme to address these points. In particular, it introduces novel validation and certification tools, innovating tools of quantum certification using sampling techniques and interactive proof systems. In several ways, it approaches the question of the superior performance of quantum devices over classical machines from a variety of perspectives, ranging from insights into the dynamics of quantum many-body systems out of equilibrium, through novel ideas on quantum sampling problems, to new methods in computational complexity to assess analog simulators in the presence of realistic errors.