Average-Case Quantum Complexity from Glassiness

Explore the intersection of quantum complexity theory and glassiness in this 49-minute conference talk from IPAM's New Frontiers in Quantum Algorithms for Open Quantum Systems Workshop. Discover how glassiness, which characterizes many natural classical problems like random k-SAT and underlies average-case hardness by obstructing stable classical algorithms, extends to the quantum realm with significant differences from classical probabilistic approaches. Learn about novel techniques based on quantum optimal transport that address the sign problem in the absence of a known eigenbasis, and understand how quantum glassiness obstructs stable quantum algorithms, including constant-time Lindbladian dynamics even when starting from the maximally mixed state. Examine findings using the replica trick that demonstrate random 3-local Pauli Hamiltonians are quantumly hard, while gaining evidence that random k-local Hamiltonians become quantumly easy for sufficiently large constant k. Compare these quantum results with analogous classical Ising ensembles (glassy phase for all k) and fermionic SYK ensembles (never glassy for any k) to understand the unique characteristics of quantum k-local ensembles in complexity theory.