Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses
Abstract
We introduce a method for studying state preparation complexity in dense quantum p-spin Hamiltonians on n qubits, going beyond bounds based only on circuit lightcones. The key input is the class's effective profile complexity, which is derived from the metric entropy of its Pauli profiles. These profiles record expectations of all Pauli operators supported on exactly p qubits. Classes with uniformly bounded quadratic effective profile complexity remain separated from the ground-state energy by a positive multiple of √n for sufficiently large fixed p. At subquadratic effective profile complexity, the class cannot outperform a suitable benchmark class at leading order, with product states providing a universal benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem of Berta et al. (arXiv:1810.12197) with Gaussian process entropy bounds. Applying this framework, we show that attaining near-ground-state energy requires Ω(n2/log n) one- and two-qubit gates, even with arbitrary discardable ancillas. We also obtain depth-width tradeoffs, entanglement-depth and matrix product state bond-dimension lower bounds, and obstructions for both orientations at every fixed level of Parham's magic hierarchy (arXiv:2504.19966), with total circuit width O(n). In first-level reverse magic, a shallow circuit is followed by an unrestricted Clifford circuit. The latter can spread local observables across the system, preventing a direct application of small-lightcone bounds. For this first-level class, our bounds also allow arbitrarily many clean ancillas at fixed shallow-circuit depth. A sharper benchmark shows that Clifford+T circuits with o(n) T-gates have no leading-order energy advantage over product stabilizer states, even with unrestricted Clifford operations and arbitrary discardable ancillas.
Related
- Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries
- A Universal Lower Bound for the Complexity of Gaussian-Divisible Spin Glasses
- A Simple Approach to the Complexity of Mean Field Ising Spin Glasses
- Beyond Typical Strings: Sampling the Complexity Landscape
- Quantum-compatible Riemannian conjugate gradient for ground-state preparation
BibTeX
@misc{alghattas2026beyond,
title = {{Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses}},
author = {Omar Al-Ghattas and David Gamarnik and Bobak T Kiani},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02166},
eprint = {2610.02166},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02166},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses
AU - Omar Al-Ghattas
AU - David Gamarnik
AU - Bobak T Kiani
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02166
UR - https://arxiv.org/abs/2610.02166
AB - We introduce a method for studying state preparation complexity in dense quantum p-spin Hamiltonians on n qubits, going beyond bounds based only on circuit lightcones. The key input is the class's effective profile complexity, which is derived from the metric entropy of its Pauli profiles. These profiles record expectations of all Pauli operators supported on exactly p qubits. Classes with uniformly bounded quadratic effective profile complexity remain separated from the ground-state energy by a positive multiple of √n for sufficiently large fixed p. At subquadratic effective profile complexity, the class cannot outperform a suitable benchmark class at leading order, with product states providing a universal benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem of Berta et al. (arXiv:1810.12197) with Gaussian process entropy bounds. Applying this framework, we show that attaining near-ground-state energy requires Ω(n^2/log n) one- and two-qubit gates, even with arbitrary discardable ancillas. We also obtain depth-width tradeoffs, entanglement-depth and matrix product state bond-dimension lower bounds, and obstructions for both orientations at every fixed level of Parham's magic hierarchy (arXiv:2504.19966), with total circuit width O(n). In first-level reverse magic, a shallow circuit is followed by an unrestricted Clifford circuit. The latter can spread local observables across the system, preventing a direct application of small-lightcone bounds. For this first-level class, our bounds also allow arbitrarily many clean ancillas at fixed shallow-circuit depth. A sharper benchmark shows that Clifford+T circuits with o(n) T-gates have no leading-order energy advantage over product stabilizer states, even with unrestricted Clifford operations and arbitrary discardable ancillas.
ER -