Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses

The 30-second take

• What: The authors bound how hard it is to prepare low-energy states of dense quantum p-spin Hamiltonians by tracking Pauli-profile complexity, not just circuit light cones.
• Why it matters: If near-ground states of these spin glasses stay expensive even with extra qubits, some “quantum optimization will just work” stories get a complexity wall rather than a near-term product path.
• Who should care: Quantum complexity and algorithms researchers, people citing light-cone arguments, and anyone estimating resources for spin-glass or optimization state preparation.

What the paper actually did

The paper studies state-preparation complexity for dense quantum p-spin Hamiltonians on n qubits, beyond bounds that only use circuit light cones. The key quantity is effective profile complexity, from the metric entropy of Pauli profiles — expectations of all Pauli operators supported on exactly p qubits. Classes with uniformly bounded quadratic effective profile complexity stay separated from the ground-state energy by a positive multiple of √n for large enough fixed p. At subquadratic effective profile complexity, the class cannot beat a suitable benchmark at leading order, with product states as a universal benchmark. The proof adapts a nonsymmetric quantum de Finetti theorem (Berta et al.) and uses Gaussian process entropy bounds. Near-ground-state energy then requires Ω(n²/log n) one- and two-qubit gates, even with arbitrary discardable ancillas. The authors also give depth–width tradeoffs, entanglement-depth and MPS bond-dimension lower bounds, and obstructions for both orientations at every fixed level of Parham’s magic hierarchy with total circuit width O(n). For first-level reverse magic (shallow circuit then unrestricted Clifford), bounds still allow arbitrarily many clean ancillas at fixed shallow depth. A sharper benchmark shows Clifford+T circuits with o(n) T-gates have no leading-order energy advantage over product stabilizer states, even with unrestricted Cliffords and discardable ancillas.

What makes this disruptive

Light-cone arguments fail when later Cliffords can spread local observables across the system. By moving the bottleneck to Pauli-profile metric entropy, the paper still gets a quadratic-ish gate lower bound and a √n energy gap for bounded-complexity classes. That is a stronger “you cannot cheaply reach the ground state” statement for dense p-spin glasses, including leftover ancillas. The magic-hierarchy and o(n) T-gate results extend the wall beyond naive shallow circuits. For abundance, this is a negative result: some hard optimization/simulation capabilities stay elite. That is useful. It is not a construction of a better algorithm.

Why it matters (outside the lab)

Abundance lens: classically hard optimization and simulation are scarce; quantum devices are often sold as the path to making them default. This work says that for dense p-spin Hamiltonians, preparing near-ground states is still circuit-expensive under broad circuit classes. Horizon is long: infrastructure-scale, not a consumer default. Near-term use is to discipline resource estimates and light-cone folklore. Medium-term, the bounds are a map of which state-prep shortcuts are ruled out.

Limitations & open questions

These are complexity lower bounds for a specific Hamiltonian family (dense quantum p-spin), not a no-go for every optimization problem. Oracle-free, physically realized hardware may have structure the worst-case class does not. Product-state and stabilizer benchmarks are leading-order statements; finite-n gaps need the PDF. Magic-hierarchy results assume total width O(n) except where ancillas are explicitly allowed. A lower bound does not exhibit a matching algorithm. Preprint; check the de Finetti adaptation and Gaussian-process steps before treating constants as tight.