Seminar: Average-case quantum complexity from glassiness

Speaker: Alexander Zlokapa (MIT)

Venue & Time: Red Room / 11:30

Abstract: In the classical setting, glassiness characterizes many natural problems (e.g., random k-SAT) and underlies average-case hardness by obstructing a family of «stable» classical algorithms (e.g., constant-time Langevin dynamics). In this work, we develop analogous quantum results. Our techniques, based on quantum optimal transport, differ significantly from classical probabilistic approaches due to the sign problem in the absence of a known eigenbasis. We show that quantum glassiness obstructs stable quantum algorithms, including constant-time Lindbladian dynamics (even when starting from the maximally mixed state). Using the replica trick, we also find that random 3-local Pauli Hamiltonians are quantumly hard and give evidence that random k-local Hamiltonians are quantumly easy for sufficiently large constant k. This differs from the analogous classical (Ising, glassy phase for all k) and fermionic (SYK, never glassy for any k) k-local ensembles. (Talk based on arXiv:2510.08497.)