Circuit complexity lower bounds for quantum spin glasses

This paper investigates the circuit complexity of near-ground states for quantum p-spin glasses, a class of random, noncommuting many-body Hamiltonians. The central question is whether these states, which are known to be highly entangled and separated from the energy achievable by product states, can be prepared by shallow quantum circuits (i.e., circuits with low depth).

The authors analyze three regimes of the quantum p-spin model: the mean-field regime, the growing-average-degree regime, and the bounded-average-degree regime. To establish circuit-depth lower bounds, they move beyond simple union-bound arguments—which fail because the class of shallow circuits is too large—by focusing on the residual energy. They decompose the energy of a circuit-prepared state into a product-state component and a residual term representing non-product correlations. By leveraging the locality of quantum circuits (the backward light-cone structure), they show that the residual term has significantly lower variance and entropy, allowing them to prove that shallow circuits cannot achieve the near-ground state energy.

• In the mean-field and growing-average-degree regimes, any circuit preparing a state with energy close to the optimum must have a depth of at least Ω_p(log n).
• In the bounded-average-degree regime, for any fixed depth D, a sufficiently large degree prefactor ensures that no depth-D circuit can prepare a near-ground state.
• These results provide a probabilistic, non-code-based route to No Low-Energy Trivial States (NLTS)-like obstructions, contrasting with previous constructions that relied on quantum LDPC codes.