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 Kliesch3 — 1Freie 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 supt∈ R<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