Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses

AI summary

Overview

Research area: Quantum information and many-body physics — circuit/state-preparation complexity lower bounds for random local Hamiltonians (quantum spin glasses).

Technical level: Advanced. The paper relies on metric entropy, Gaussian process theory, and a nonsymmetric quantum de Finetti theorem; the results are asymptotic theorems, not numerics.

Scope (one sentence): The paper introduces a general "profile complexity" framework for proving that restricted classes of quantum states (shallow circuits, bounded-entanglement states, MPS, magic-hierarchy circuits, Clifford+$T$ circuits) cannot reach the ground-state energy of the dense quantum $p$-spin Hamiltonian, even when arbitrary ancillas are allowed.

What This Paper Is About

Most existing quantum circuit lower bounds work by tracking light cones: in a shallow circuit, a local observable only depends on a small neighborhood of qubits, and this locality is used to rule out low-energy states. That reasoning breaks down whenever a circuit can spread local information across the whole system — for example, an unrestricted Clifford circuit placed at the end of a shallow circuit (reverse magic), or a general ansatz with long-range correlations such as matrix product states.

The authors ask: given a class $\mathcal{C}n$ of $n$-qubit states and the dense quantum $p$-spin Hamiltonian $H{n,p}$, how close can states in $\mathcal{C}_n$ get to the extremal energy? Their goal is a single, class-agnostic method that answers this without any locality assumption, and then to apply it to many state classes at once.

Key Contributions

1. A profile-based complexity measure. Instead of the full state, the authors track only the weight-$p$ Pauli profile $f_\rho(P) = \operatorname{Tr}(P\rho)$ over all weight-$p$ Pauli strings $\mathcal{P}_{n,p}$. Since the energy depends on the state only through this profile, the complexity of a state class can be measured by the metric entropy (covering numbers) of its set of profiles.

2. A general "local-profile complexity principle" (Theorem 1.2). Using an effective profile complexity $\Gamma_{n,p} = a_{n,p} + b_{n,p}\log(e B_{n,p} n)$ derived from a covering-number bound, the theorem gives (i) an order-$\sqrt{n}$ separation from the unrestricted optimum when $\Gamma_{n,p} \le L n^2$, and (ii) a benchmark comparison when $\Gamma_{n,p} = o(n^2)$.

3. A benchmark framework. The comparison in (ii) is against a "conditioning benchmark" class $\mathcal{B}_n$ (Definition 1.1); product states $\mathsf{prod}_n$ are shown to be a universal benchmark for every state class, and sharper benchmarks (e.g. product stabilizer states) are constructed for structured classes.

4. Applications across many state classes. Corollaries give lower bounds on circuit size, depth–width tradeoffs, entanglement depth, MPS bond dimension, both orientations of every fixed level of the magic hierarchy, and Clifford+$T$ circuits — all with arbitrary discardable ancillas in most cases.

Main Findings

• Gate count: Attaining near-ground-state energy requires $\Omega(n^2/\log n)$ one- and two-qubit gates, even with arbitrary discardable ancillas. Concretely, the ground-state separation holds whenever $G_n \le L n^2/\log n$, and the product-state comparison holds whenever $G_n = o(n^2/\log n)$ (Corollary 1.3).

• Depth–width tradeoff: With effective workspace $\widehat{M}_n = \min{M_n, n2^{D_n}}$, separation holds when $D_n \widehat{M}_n \le L n^2/\log n$. For circuits of width $O(n)$ this reaches depth $O(n/\log n)$; for width $O(n^\gamma)$ with $1 \le \gamma < 2$ the threshold is $O(n^{2-\gamma}/\log n)$. With arbitrary discardable ancillas, the product-state comparison holds for $D_n \le c\log_2 n$ with any fixed $c \in (0,1)$ (Corollary 1.4).

• Comparison to prior depth bounds: Earlier work proved an $\Omega_p(\log n)$ depth lower bound for sufficiently large fixed $p$; this paper strengthens it to $\Omega(n/\log n)$ for circuits on $O(n)$ qubits.

• Entanglement depth: For $b_n$-producible states, separation holds when $2^{b_n}/b_n \le L n/\log n$, and the product-state comparison when $2^{b_n}\log n/b_n = o(n)$. A near-ground state must therefore contain entangled components of essentially logarithmic size (Corollary 1.5).

• MPS bond dimension: For open-boundary MPS with bond dimension $\chi_n$, separation holds when $\chi_n^2 \log(n\chi_n) \le L n$. Near-ground states require bond dimension $\Omega(\sqrt{n/\log n})$. The authors state these are the first results showing low-energy states of the quantum $p$-spin model require asymptotically growing MPS bond dimension (Corollary 1.6).

• Magic hierarchy: For forward magic with total width $M_n = O(n)$, separation holds up to $D_n \le L n/\log n$; with arbitrarily many discardable ancillas the product-state comparison holds for $D_n \le c\log_2 n$ with $c \in (0,1/2)$. For reverse magic with $M_n = O(n)$, separation holds for $D_n \le L n/\log n$, and with arbitrarily many clean ancillas the same holds for every fixed depth $D$. Both orientations hold at every fixed level $k \ge 1$ for $M_n = O(n)$ and $D_n \le L n/\log n$ (Corollary 1.7). The required interaction order $p$ may depend on $D$ (and on $\kappa$).

• Clifford+$T$: For $\mathsf{cliffT}^{\mathrm{anc}}{n,t_n}$ with $t_n \le \kappa n$, the order-$\sqrt{n}$ ground-state separation holds. For $t_n = o(n)$, $\big(M{n,p}(\mathsf{cliffT}^{\mathrm{anc}}{n,t_n}) - M{n,p}(\mathsf{pstab}n)\big)/\sqrt{n} \to 0$, and for every $\varepsilon > 0$ there is $p\varepsilon$ such that for all fixed $p \ge p_\varepsilon$, $|M_{n,p}/\sqrt{n} - \sqrt{2\log 6}| \le \varepsilon$ with probability tending to one (Corollary 1.8). The constant $\sqrt{2\log 6}$ reflects the six single-qubit Pauli eigenstates.

• Benchmark sharpening: Since unrestricted stabilizer states and Clifford+$T$ states with sublinear $T$-count do not beat product stabilizer states at leading order, the long-range entanglement created by unrestricted Clifford circuits gives no leading-order energy advantage.

• Not reported: The paper does not report numerical experiments, simulation data, or explicit values for the constants $c_{p,L}$; it states only that such positive constants exist. Thresholds on $p$ are stated to be "sufficiently large fixed" and are not quantified.

Methodology in Plain English

The energy of a state under $H_{n,p}$ is a Gaussian random sum weighted by the state's weight-$p$ Pauli expectation values. So the random energies of an entire state class form a Gaussian process indexed by the class's set of profiles. The "size" of that index set — measured by how many small balls are needed to cover it (metric entropy) — controls how much the energy can fluctuate upward across the class.

The proof combines two ingredients. First, an entropy bound on the profile class yields a chaining-style bound on the Gaussian process. Second, a conditioning argument adapted from a nonsymmetric quantum de Finetti theorem shows that, after measuring a suitable $(1-\alpha)$ fraction of the qubits, the remaining local profile of any state resembles a convex mixture of benchmark states — this is what makes product states a universal benchmark. Putting these together turns a class-specific covering-number estimate into an energy lower bound, so each application reduces to a single entropy calculation rather than a new light-cone argument. Because no locality of the pulled-back observables is assumed, the method applies where light-cone arguments fail, such as reverse magic.

Why This Matters

The paper provides what the authors describe as the first general framework for energy lower bounds against qualitatively different restricted state classes in a bounded-locality Hamiltonian setting, and it removes the light-cone bottleneck that has limited prior lower bounds to logarithmic depth. It also answers, for the $p$-spin model, the request in Open Problem 4 of the magic-hierarchy work for bounds against the reverse orientation and higher levels, at fixed circuit width. It connects to the NLTS theorem and the quantum PCP program by exhibiting structured Hamiltonians whose low-energy states are hard to prepare.

Real-world applications (mostly indirect, via the theory of quantum algorithms and hardware):

• Variational quantum algorithms: bounds indicate which ansätze (shallow circuits, bounded-bond-dimension MPS, low-$T$-count Clifford circuits) cannot capture low-energy physics, guiding ansatz selection.
• Quantum simulation on near-term hardware: depth–width tradeoffs inform how much ancilla workspace and circuit depth are needed for ground-state preparation.
• Classical simulation and state learning: results on $t$-doped stabilizer states relate to simulability and to learning algorithms for almost-Clifford states.
• Hardware compilation: gate-count thresholds ($\Omega(n^2/\log n)$) indicate the scale at which compilation of low-energy state preparation becomes provably impossible for restricted circuits.

Industry relevance: Relevant to teams building variational/optimization workloads on quantum processors, to compiler and transpiler research where depth and ancilla budgets matter, and to groups studying quantum advantage and hardness of simulation.

Future Directions

• Beyond fixed width: the magic-hierarchy results require total circuit width $O(n)$; extending them to super-linear workspace is left open.
• Sharper thresholds in $p$: the required interaction order $p$ is only "sufficiently large fixed" and may depend on the depth constant $L$ or the $T$-gate density $\kappa$; quantifying this dependence is an open question.
• Tighter gate-count bounds: closing the gap between the $n^2/\log n$ threshold here and a possible $\Theta(n^2)$ bound.
• Other classes and Hamiltonians: whether the profile-entropy method extends to sparse or geometrically local Hamiltonians, and to further ansatz families beyond those treated (entanglement depth, MPS, magic hierarchy, Clifford+$T$).

Target Audience

Researchers in quantum information theory, quantum complexity theory, and many-body physics working on state-preparation complexity and circuit lower bounds; theoretical computer scientists interested in Gaussian process and de Finetti techniques; and advanced graduate students familiar with Pauli operators, stabilizer formalism, and asymptotic complexity arguments. Practitioners seeking hands-on algorithms or numerics will find little here, as the paper is purely theoretical.

Authors’ 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 $\sqrt 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.