DPG Phi
Verhandlungen
Verhandlungen
DPG

Berlin 2024 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

QI: Fachverband Quanteninformation

QI 22: Quantum Simulation I

QI 22.9: Vortrag

Donnerstag, 21. März 2024, 12:00–12:15, HFT-FT 101

Maximizing quantum expectation values over time is NEXP-hard — •Lennart Bittel1, Sevag Gharibian2, and Martin Kliesch31Freie Universität Berlin, Germany — 2Universität Paderborn, Germany — 3Technische Universität Hamburg, Germany

Understanding equilibration behavior of closed systems is an important but difficult problem. Intuitively, after some equilibration time, many-body systems typically transition to a steady state, in which expectation values become stationary. Sometimes, after long evolution times, however, a system can exit an equilibrium state again. Thus, a natural question is to ask how far out of equilibrium the long-term expectation value of an observable can be, i.e., to find the extremal value suptR<O(t)>. We first show that even for k-local Hamiltonians, approximating this quantity is NEXP-hard. Thus, no polynomial-time classical algorithm exists (unconditionally), and understanding equilibration behavior of closed systems can be extremely computationally difficult. We then show a similar result for estimating the ansatz error for a VQA setup, in which one can potentially reuse gate generators a superpolynomial number of times. This yields two arguably rare examples of physically motivated NEXP-hard problems. Finally, in terms of upper bounds, we show both problems are in EXPSPACE, i.e. solvable in exponential space, but potentially double-exponential time.

Keywords: Long term evolution; Complexity theory; NEXP; Equilibration

100% | Mobil-Ansicht | English Version | Kontakt/Impressum/Datenschutz
DPG-Physik > DPG-Verhandlungen > 2024 > Berlin