Eric Anschuetz

We show a relation between quantum learning theory and algorithmic hardness. We demonstrate that finding near-ground states of certain sparse disordered quantum systems is average-case hard for Lipschitz quantum algorithms if there exists an efficient, local learning algorithm---such as the classical shadows algorithm---for estimating the energy of a state of the system. A corollary of our result is that many standard quantum algorithms fail to find near-ground states of these systems, including short-time Lindbladian dynamics, short-time quantum annealing, phase estimation, and shallow-depth variational quantum algorithms. Our results are unconditional. To achieve this, we introduce a topological property of quantum systems that we call the quantum overlap gap property (QOGP). This property is only satisfied by systems with an efficient local learning algorithm for the energy. We prove that systems which exhibit this topological property in their low-energy space are intractable for quantum algorithms whose outputs are stable under perturbations to their inputs. We then prove that the QOGP is satisfied for a sparsified variant of the quantum p-spin model, giving the first known algorithmic hardness-of-approximation result for quantum algorithms in finding the ground state of a non-stoquastic, noncommuting quantum system. Our resulting lower bound for quantum algorithms optimizing this model using Lindbladian evolution matches (up to constant factors) the best-known time lower bound for classical Langevin dynamics optimizing classical p-spin models. For this reason we suspect that finding ground states of typical quantum p-spin models using quantum algorithms is, in practice, as intractable as the classical p-spin model is for classical algorithms. Inversely, we show that the Sachdev--Ye--Kitaev (SYK) model does not exhibit the QOGP, consistent with previous evidence that the model is rapidly mixing at low temperatures.

We provide a framework for average-case quantum complexity by showing that glassiness obstructs a natural family of quantum algorithms. Glassiness --- a phenomenon in physics characterized by a disordered, slow-mixing phase --- is known to imply hardness for stable classical algorithms; for example, constant-time Langevin dynamics or message-passing fail for random $k$-SAT and max-cut problems in a glassy parameter regime. We present comparable results in the quantum setting with the following contributions. \begin{itemize}[rightmargin=7em] \item \emph{Quantum optimal transport view of glassiness.} We show that the standard notion of quantum glassiness in physics implies that the Gibbs state is decomposed into clusters extensively separated in quantum Wasserstein distance. We prove this implies lower bounds on the quantum Wasserstein complexity of channels from non-glassy to glassy states. \item \emph{Structural argument for hardness.} We define \emph{stable quantum algorithms} in terms of Lipschitz temperature dependence. We prove that constant-time local Lindbladian evolution and shallow variational algorithms are stable and hence fail to capture the clustered geometry of the Gibbs state, yielding a geometrically interpretable algorithmic obstruction. Contrary to prior Lindbladian runtime lower bounds that only apply to evolution from worst-case initial states, our results hold even when starting from the maximally mixed state. \end{itemize} At a technical level, our techniques (based on channel complexity) differ significantly from classical probabilistic approaches due to the sign problem in the absence of a known eigenbasis. This allows our average-case hardness results to apply to non-commuting, non-stoquastic quantum Hamiltonians. As an example, we show the average-case hardness of random 3-local Hamiltonians: the ensemble of all 3-local Pauli strings with independent Gaussian coefficients. To obtain this result, we compute the full replica symmetry breaking solution of the general $p$-local Pauli Hamiltonian ensemble via the replica trick, a non-rigorous but widely used method in statistical physics. The system's phase diagram is richer than its classical (Ising $p$-spin) and fermionic (SYK) analogues, which either always or never have a glassy phase; instead, the Pauli ensemble has a glassy phase only below some constant value of $p$, confirming the phase diagram predicted by prior finite-size numerical analyses.

We study the performance of Decoded Quantum Interferometry (DQI) on typical instances of MAX-k-XOR-SAT when the transpose of the constraint matrix is drawn from a standard ensemble of LDPC parity check matrices. We prove that if the decoding step of DQI corrects up to the best known efficient decoding threshold for LDPC codes, then DQI is obstructed by a topological feature of the near-optimal space of solutions known as the overlap gap property (OGP). As the OGP is widely conjectured to exactly characterize the asymptotic performance of state-of-the-art classical algorithms, this result suggests that DQI has no quantum advantage in optimizing unstructured MAX-k-XOR-SAT instances for large k without significant asymptotic advances in efficient LDPC decoders. We also give numerical evidence supporting this conjecture by showing that approximate message passing (AMP)—a classical algorithm conjectured to saturate the OGP threshold—outperforms DQI on a related ensemble of MAX-k-XOR-SAT instances. Finally, we prove that depth-1 QAOA outperforms DQI at sufficiently large k under the same decoding threshold assumption. Our result follows by showing that DQI is approximately Lipschitz under the quantum Wasserstein metric over many standard ensembles of codes. We then prove that MAX-k-XOR-SAT exhibits both an OGP and a related topological obstruction known as the chaos property; this is the first known OGP threshold for MAX-k-XOR-SAT at fixed k, which may be of independent interest. Finally, we prove that both of these topological properties inhibit approximately Lipschitz algorithms such as DQI from optimizing MAX-k-XOR-SAT to large approximation ratio with substantial probability.