Average-case quantum complexity from glassiness

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 and shallow variational algorithms. Using the replica trick, we also find that random 3-local Pauli Hamiltonians are quantumly hard and give strong 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.)