Genuine Quantum Algorithms Inspired by Thermodynamics and Natural Phenomena

forthcoming

"As low-noise medium-scale quantum devices are on the horizon, it is becoming increasingly important to find useful quantum algorithms that can be run on such devices. However, existing quantum algorithms typically only offer an advantage compared to advanced classical computers when run on large-scale quantum devices for rather long running times, urging us to find more effective quantum algorithms. This project aims to design new efficient Nature-inspired quantum algorithms and find new applications and use cases, through quantum generalisations of the Metropolis algorithm and Glauber dynamics, whose classical counterparts were also distilled from deeper understanding of physical models and thermodynamical processes, but turned out to be foundational in computer science through applications to a wide range of problems outside their original scope. The primary focus is on quantum algorithms related to open quantum systems and thermalisation. Such algorithms can be described by Quantum Markov Chains (QMC), which unify the powerful paradigms of classical randomized algorithms and traditional coherent quantum algorithms. Due to their rich, complex structure such processes have proven to be hard to construct and analyse. The PI's recent breakthroughs in designing detailed-balanced QMCs opened new ground in quantum algorithms design, and the PI intends to explore and exploit the resulting QMC algorithms and adapt them to the requirements of early quantum devices. The PI's interdisciplinary approach already led to the successful translation of the physics inspired ""Quantum Signal Processing"" protocol to a major unification of various quantum algorithms via ""Quantum Singular Value Transformation"" (QSVT) (which has been presented at STOC'19 and cited 750 times since). Further building on physics intuition and CS insights, this project aims to pave the way of QMC-based algorithms for advancements in quantum simulation, optimization and information processing."