The complexity of complex quantum systems

• Applicant: Professor Dr. Jens Eisert
• Subject Area: Theoretical Condensed Matter Physics ; Optics, Quantum Optics and Physics of Atoms, Molecules and Plasmas
• Term: from 2017 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 390892736

• Final Report Year: 2024

Final Report Abstract

The physical world that we encounter in our everyday experience exhibits a remarkable degree of complexity and richness of phenomena, even though the interactions and rules giving rise to these phenomena can be simple. It has long been noted that there is a profound link between notions of computational complexity and ground state properties of local Hamiltonian models, in the focus of attention of the field of Hamiltonian complexity. Importantly, invoking the physical Church Turing thesis, one can relate the long equilibration times with the computational hardness of identifying the ground states of such models. Based on early steps in this direction, in this proposal, we have suggested that the link between computational complexity and the study of complex quantum systems runs much deeper. This project has suggested a concerted program of identifying the close links between: notions of computational complexity; and the study of interacting quantum many-body systems in condensed matter physics, in aspects of low-temperature physics, dynamical aspects and response features, notions of many-body localisation, and glassy dynamics. Viewed through the eyes of computational complexity, the problem of the classification of phases of matter will be revisited, relating to the notorious sign problem of Monte Carlo, suggesting the claim that phases of matter can large be captured in purely computational terms. The “big picture” underlying this research is the bold hypothesis that much of the understanding of how quantum many-body systems interacting with local interactions behave can be captured in terms of computer science, leading to new quantitative predictions.

Publications

• Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics. Physical Review Letters, 125(25).
  Haferkamp, J.; Hangleiter, D.; Bouland, A.; Fefferman, B.; Eisert, J. & Bermejo-Vega, J.
  
• Contracting projected entangled pair states is average-case hard. Physical Review Research, 2(1).
  Haferkamp, Jonas; Hangleiter, Dominik; Eisert, Jens & Gluza, Marek
  
• Dynamical structure factors of dynamical quantum simulators. Proceedings of the National Academy of Sciences, 117(42), 26123-26134.
  Baez, Maria Laura; Goihl, Marcel; Haferkamp, Jonas; Bermejo-Vega, Juani; Gluza, Marek & Eisert, Jens
  
• Easing the Monte Carlo sign problem. Science Advances, 6(33).
  Hangleiter, Dominik; Roth, Ingo; Nagaj, Daniel & Eisert, Jens
  
• Emergent Statistical Mechanics from Properties of Disordered Random Matrix Product States. PRX Quantum, 2(4).
  Haferkamp, Jonas; Bertoni, Christian; Roth, Ingo & Eisert, Jens
  
• Pinned quantum Merlin-Arthur: The power of fixing a few qubits in proofs. Physical Review A, 103(1).
  Nagaj, Daniel; Hangleiter, Dominik; Eisert, Jens & Schwarz, Martin
  
• Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates. Communications in Mathematical Physics, 397(3), 995-1041.
  Haferkamp, J.; Montealegre-Mora, F.; Heinrich, M.; Eisert, J.; Gross, D. & Roth, I.
  
• Linear growth of quantum circuit complexity. Nature Physics, 18(5), 528-532.
  Haferkamp, Jonas; Faist, Philippe; Kothakonda, Naga B. T.; Eisert, Jens & Yunger, Halpern Nicole
  
• Random quantum circuits are approximate unitary t-designs in depth O(nt5+o(1)). Quantum, 6, 795.
  Haferkamp, Jonas
  
• Resource theory of quantum uncomplexity. Physical Review A, 106(6).
  Yunger, Halpern Nicole; Kothakonda, Naga B. T.; Haferkamp, Jonas; Munson, Anthony; Eisert, Jens & Faist, Philippe