Welcome to a talk by Sevag Gharibian, Junior Professor, Universität Paderborn, Germany.
The lecture will be held online.
The "quantum Cook-Levin Theorem" rigorously justified, assuming standard complexity theoretic conjectures, the long-standing physics intuition that studying quantum many-body systems is "hard": Indeed, the theorem says that estimating the ground state energy of such a system is QMA-complete, for QMA the quantum analogue of NP. However, a more natural physical problem had escaped the community's attention until recent years: How hard is it to simulate local measurements on ground states of many-body systems (denoted APX-SIM)? Indeed, this is arguably among the most fundamental questions facing experimentalists aiming to understand the low-temperature properties of physical systems. In this talk, we discuss a sequence of works which show that this problem is, perhaps surprisingly, even harder than QMA - it is P^QMA[log]-complete, for P^QMA[log] the class of decision problems solvable in polynomial time with access to logarithmically many queries to a QMA oracle. Along the way, we will see that this odd-looking class captures not only other physical problems such as estimating spectral gaps of local Hamiltonians, but that the APX-SIM problem remains hard even on ever-simpler-looking systems, such as the 2D Heisenberg interaction and 1D translationally invariant systems.
This talk covers a sequence of works, starting with one of Andris Ambainis, followed by joint works with (in alphabetical order) Johannes Bausch, Stephen Piddock, Justin Yirka, and James Watson.
22 January, 2021, 09:00
22 January, 2021, 10:00