Substrate · Quantum-Advantage Thresholds

Neural-Network Quantum States Complexity Profile

The algorithmic boundary of neural-network quantum states modeled via graph theory.

A neural-network ansatz represents a quantum state's correlations; its classical tractability is set by the entanglement — and therefore the treewidth — it is forced to carry. Every profile below reads the same substrate through a different graph invariant and structural regime, and prices it with Ross’s Law.

Read the volume (PDF, 895 pp)

A neural-network quantum state — an RBM or deeper ansatz standing in for a wavefunction — is a wager that a many-body state’s correlations can be compressed into a small network of weights. The wager wins or loses on one quantity: how much entanglement the target state carries. Entanglement is treewidth wearing a physicist’s coat, so the question “can this ansatz represent this state efficiently?” is the same question as “is the correlation graph close to a tree?”

That makes neural quantum states the sharpest test of Ross’s Law outside a literal circuit: the ansatz is tractable exactly in the regime where the state is, and no clever architecture escapes a state whose treewidth grows with the system. The five invariants below each locate that boundary — a shadow regime where a compact network suffices, a mirror regime where no polynomial network can keep up, and the equilibrium band at the edge.

representation cost ≈ exp(Θ(tw(G)))Ross’s Law for ansätze: the parameters needed to represent a state faithfully scale with the treewidth of its correlation graph. Depth and width buy you the shadow regime; they cannot buy you the mirror.

Treewidth bounds

Treewidth of the correlation graph is the parameter budget in disguise — the width of the worst correlation cut the network must encode.

Shadow
tw(G) = O(1) — short-range, gapped correlations. A small RBM captures the state with parameters that barely grow.
Equilibrium
tw(G) = Θ(log N) — critical correlations. The ansatz still works but the parameter count climbs; this is where architecture choices decide success.
Mirror
tw(G) = Ω(N) — a maximally correlated state. No polynomial-size network represents it; the wager loses.

Graph degeneracy

Degeneracy is the polynomial pre-check on the correlation graph: the densest core of mutually-correlated degrees of freedom, computed without solving the representation problem itself.

Shadow
d(G) = O(1) — no dense correlation core; the state factorizes cleanly.
Equilibrium
d(G) = Θ(log N) — a slowly thickening core, the fingerprint of approaching criticality.
Mirror
d(G) = Ω(N) — an irreducible core certifying large treewidth and an intractable ansatz.

Volume-law entanglement

Here the bridge is literal, not analogical: the entanglement entropy across a cut is the log of the representational capacity the ansatz must spend there. Area-law states are shadow; volume-law states are mirror. This is the cleanest statement of the whole framework.

Shadow
S(ρ) ∝ ∂A — area law. Entanglement lives on the boundary; ground states of gapped local Hamiltonians sit here, and neural ansätze excel.
Equilibrium
S(ρ) ∝ log N — the logarithmic violation of critical 1D systems. Representable, but at growing cost.
Mirror
S(ρ) ∝ |A| — volume law. Typical excited and chaotic states; entanglement fills the region and no efficient representation exists.

Fiedler-value connectivity

The Fiedler value reads whether the correlation graph has a weak link the ansatz can factor through — a near-product structure to exploit.

Shadow
λ₂ → 0 — nearly separable subsystems. The state is close to a product; trivially represented.
Equilibrium
λ₂ = Θ(1/N) — weakly coupled blocks, a faint factorization the ansatz can lean on.
Mirror
λ₂ = Ω(1) — an expander of correlations. No subsystem decouples; the state is globally bound.

Bipartite treewidth

The bipartite cut is the entanglement stress test: split the degrees of freedom in two and measure the width the ansatz must carry across the worst bisection.

Shadow
twᵇ(G) = O(1) — the halves are nearly unentangled; a constant bond suffices.
Equilibrium
twᵇ(G) = Θ(√N) — the area-law scaling of a 2D region’s boundary; sub-exponential capacity.
Mirror
twᵇ(G) = Ω(N) — volume-law across every bisection. The ansatz needs exponential capacity and fails.

The same meter, four other substrates

A neural quantum state is one instance of the universal meter. The same five invariants read these too:

Tensor-Network ContractionVector Databases & RAGBiological ConnectomesSocial Clique Networks
The full matrix