Delineating the boundary between the computational power of quantum and classical devices

This project sets out to assess, make use of and verify the computational power of realistic quantum devices.

It comprehensively identifies quantum simulators and paradigmatic quantum devices that are computationally superior to classical supercomputers, based on presently available or plausible physical architectures.

In doing so, it explores the fine line that discriminates regimes featuring a quantum advantage from ones that are accessible to efficient classical simulation.

This naturally two-pronged approach is on the one hand concerned with (1) novel classical simulation tools for seemingly deeply quantum prescriptions and with identifying limitations of variational approaches and quantum simulation schemes.

On the other hand, (2) it identifies new practically minded applications of quantum devices that exhibit a computational speed-up over classical machines, with potentially game-changing applications emerging for learning tasks.

To achieve this goal, it digs deeply into computer science that provides sophisticated tools of computational complexity and of machine learning, and is instrumental in devising methods for the classical simulation of intricate quantum problems. At the same time, it draws on the physics of complex systems.

This proposal suggests an interdisciplinary effort by bringing together ideas of quantum information, condensed matter physics, complexity theory, machine learning, tensor network theory, and methods that are unusual in this context such as signal processing.

Individually, each objective substantially advances the respective field, but it is their combination that will permit a true breakthrough by delineating the delicate boundary between quantum and classical computations of synthetic quantum devices.