# Complexity of complex quantum systems and quantum algorithms

There is a remarkable connection between quantum many-body theory - the theory that captures the behavior exhibited by a large number of interacting particles - and complexity theory in computer science. Indeed, there are striking parallels between key objects of study: The Hamiltonians of quantum many-body physics resemble propositional formulae as they are the object of study in complexity theory. It has become clear that the connection runs deeper, and that a close formal link between equilibrium properties and satisfying assignments can be established. By a reading of the Church Turing thesis, one can link questions of computationally hard problems to physical properties, such as glassy systems taking a long time to cool to their ground state.

We are concerned with several ramifications of the link between complexity studies and the physics of complex quantum systems, beyond what is usually referred to as Hamiltonian complexity. We have been concerned with questions of computational complexity of Hamiltonian systems, open many-body systems, Markovianity, Gibbs state preparation and many-body localization. Some problems turn out not only to be computationally difficult, but even undecidable.

**Selected group publications**

- Easing the Monte Carlo sign problem

Science Advances 6, eabb8341 (2020) - Pinned QMA: The power of fixing a few qubits in proofs

Physical Review A 103, 012604 (2021) - On the quantum versus classical learnability of discrete distributions

Quantum 5, 417 (2021) - Contracting projected entangled pair states is average-case hard

Physical Review Research 1 (2019) - Closing gaps of a quantum advantage with short-time Hamiltonian dynamics

Physical Review Letters 125, 250501 (2020) - Dynamical structure factors of dynamical quantum simulators

PNAS 117, 26123-26134 (2020) - Architectures for quantum simulation showing a quantum speedup

Physical Review X 8, 021010 (2018) - Anticoncentration theorems for schemes showing a quantum speedup

Quantum 2, 65 (2018) - Quantum measurement occurrence is undecidable

Physical Review Letters 108, 260501 (2012) - Matrix product operators and states: NP-hardness and undecidability

Physical Review Letters 113, 160503 (2014) - Extracting dynamical equations from experimental data is NP-hard

Physical Review Letters 108, 120503 (2012) - Novel schemes for measurement-based quantum computation

Physical Review Letters 98, 220503 (2007) - Computational difficulty of global variations in the density matrix renormalization group

Physical Review Letters 97, 260501 (2006) - The complexity of relating quantum channels to master equations

Communications of Mathematical Physics 310, 383 (2012) - Area laws and efficient descriptions of quantum many-body states

New Journal of Physics 18, 083026 (2016) - Locality of temperature

Physical Review X 4, 031019 (2014) - A dissipative quantum Church-Turing theorem

Physical Review Letters 107, 120501 (2011) - Solving frustration-free spin systems

Physical Review Letters 105, 060504 (2010)