Classical and quantum algorithms for many-body problems

The many-body problem is central to many fields, such as condensed-matter physics and chemistry, but also to combinatorial optimization, which is nothing but a classical many-body problem. This manuscript, written as part of an Habilitation à Diriger des Recherches, presents the various algorithmic approaches, both classical and quantum, to solving this problem. We begin by reviewing the main existing classical and quantum methods, focusing on their successes as well as their current limitations. In particular, we present the state-of-the-art in quantum methods, distinguishing between perfect and noisy processors. We then present recent work on combining classical and quantum algorithms to overcome the limitations inherent to both paradigms. In particular, we begin by showing how tensor networks, often used as reference tools to gauge the interest of quantum methods, can also be used to initialize a quantum computation, in addition to simulating it realistically. We then turn to the special case of fermionic problems. After describing a method based on natural orbitals for shortening, and thus making more reliable, quantum circuits to prepare fermionic states, we present a method based on slave spins for using a platform of Rydberg atoms to simulate lattice models of fermions. Finally, we show how these same Rydberg platforms can be used to solve combinatorial problems, and how decoherence influences the quality of the results obtained. This leads to the definition of a new utility metric for quantum processors, the Q-score.