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)