Complexity and order in approximate quantum error-correcting codes

The paper addresses how to meaningfully quantify and characterize approximate quantum error-correcting (AQEC) codes beyond the coarse criterion of vanishing error with system size. The central research question is: what quantitative AQEC parameters certify nontrivial many-body structure (e.g., high circuit complexity, long-range entanglement) across general connectivities, and where is a principled boundary between trivial and nontrivial AQEC subspaces? Motivated by the observation that trivial redundant encodings can yield vanishing average errors under random local noise, the authors seek refined, intrinsic code parameters. They introduce subsystem variance (a measure of fluctuation of reduced density matrices of code states relative to the code’s maximally mixed state) and connect it to standard AQEC imprecision. They then ask how small subsystem variance must be, as a function of code rate k/n and locality scale d, to force universal circuit complexity lower bounds for all states in the code. The work proposes O(k/n) (and in many physical settings, O(1/n)) as a meaningful boundary between acceptable and trivial AQEC codes, and explores implications for phases with topological order and for critical (CFT) systems.

The work builds on and contrasts with several strands of literature: - Exact QEC and stabilizer codes: canonical constructions and criteria (e.g., Knill-Laflamme conditions) that often aim for perfect recovery. - Approximate QEC (AQEC): earlier works established that small imprecision can dramatically extend correctability (e.g., decoding radius matching distance), but a general theory is fragmented across examples such as spin chains, covariant/coded symmetry settings, and quasi-exact codes. - Approximate Eastin-Knill and covariant codes: fundamental trade-offs between continuous symmetries and code performance, highlighting inherent polynomial/1/n-type limits in symmetric settings. - Circuit complexity and NLTS-style arguments: prior lower bounds for code Hamiltonian low-energy states inspire the backward-circuit and light-cone method adapted here to AQEC. - Many-body physics diagnostics: long-range entanglement and topological entanglement entropy (TEE) as hallmarks of topological order; area-law plus subleading constant (TEE) in 2D; Lieb-Robinson bounds for locality. The authors argue that existing AQEC notions (just requiring vanishing error) are too permissive (e.g., redundant encoding). Their framework unifies code-theoretic and complexity-theoretic perspectives and aligns with physical signatures in topological and critical systems.

Core constructs and steps: 1) Subsystem variance ε_G(C, d): For an ((n,k)) code C with maximally mixed state Γ on the code subspace, ε_G(C, d) is the worst-case trace-norm deviation ||σ_R − Γ_R||_1 over all code states σ and connected d-qubit regions R in adjacency graph G. This quantifies how much logical information is locally accessible and bounds deviations from Knill-Laflamme conditions. 2) AQEC inaccuracy ε̃(N, E): Using the channel purified distance between the effective logical channel (after noise N and optimal recovery) and the logical identity. For replacement (erasure/depolarizing/reset) channels on d-local regions, two-way bounds link ε_G(C, d) and ε̃: roughly, (¼) ε_G(C, d) ≤ ε̃ ≤ 2^{k/2} √ε_G(C, d), establishing that subsystem variance tightly characterizes AQEC imprecision in canonical noise models. 3) Circuit complexity definitions: C_G(|ψ⟩) is the minimum depth of 2-local circuits (with respect to adjacency graph G) preparing |ψ⟩ from |0⟩^{⊗n}; a δ-robust version C̃_G allows approximation within trace distance δ. Both all-to-all (complete graph) and geometric D-dimensional lattice circuits are considered; general graphs are treated via a light-cone size function f(t). 4) Main technique for lower bounds: Adapt and generalize the NLTS-style backward-circuit argument to AQEC. Assume a code state has shallow-depth preparation so each qubit’s influence is confined to a light cone. Apply the inverse circuit to the maximally mixed code state Γ; small subsystem variance at the light-cone scale makes local marginals nearly product, bounding global entropy by sums of local entropies. This can contradict S(Γ) = k when ε_G is sufficiently small relative to k/n and the light-cone cover number, forcing depth to be large. 5) General theorems: Conditions of the form H2(ε_G(C,d)/2 + δ/2) < k/n (binary entropy H2) imply code-space-wide circuit depth lower bounds that scale with d and geometry. Results are presented for all-to-all connectivity and for D-dimensional lattices, and extended to arbitrary graphs via the inverse light-cone size f^{-1}(d). 6) Physical applications: - Topological order/TEE: Use Markov entropy decomposition to relate k to a signed sum of subregion entropies where area-law terms cancel, leaving TEE minus corrections controlled by ε_G(C,d). If ε_G = o(1/n) on linear-size regions, one obtains nontrivial TEE lower bounds for all code states. - Critical systems/CFT: Via state-operator correspondence and scaling of one-point functions of primary operators, estimate ε_G ~ Θ(n^{-Δ/D}) up to polylog(n) factors for operators of size O(log log n). This yields polynomial AQEC error exponents tied to the minimal scaling dimension Δ. 7) Examples: Analyze ETH spin-chain codes, approximate LDPC codes from spacetime Hamiltonians, Heisenberg chain codes, CFT codes, and momentum codes (with fragmentation) to illustrate parameter regimes and tightness.

- Subsystem variance as an intrinsic AQEC parameter: It bounds violations of Knill-Laflamme and is quantitatively equivalent (up to known factors) to AQEC inaccuracy for replacement channels. Thus ε_G(C,d) robustly characterizes AQEC precision. - Universal complexity lower bounds from small ε_G: If H2(ε_G(C,d)/2 + δ/2) < k/n (with ε + δ < 1/2), then every state in the code subspace has nontrivial circuit depth lower bounds. This applies to all-to-all circuits and to geometric circuits on D-dimensional lattices and general graphs. In particular, an O(k/n) scaling of ε_G marks the approximate boundary between trivial and nontrivial AQEC subspaces. For superconstant d, Corollary 3 implies superconstant circuit complexity when H2(ε_G/2) < k/n, e.g., if k = o(n) with ε_G = õ(1/n) or if k = Ω(n) with ε_G = o(1). - Phase diagram intuition: The work identifies a “nontrivial” regime (ε_G below ≈ O(k/n)) where complexity lower bounds hold for all code states, versus an “unboundable” regime where the method does not apply. The ~1/n scaling emerges repeatedly as a physically meaningful threshold. - Topological order and TEE: In 2D area-law settings, if ε_G = o(1/n) on linear-size contractible regions, then all code states possess nonzero TEE. A quantitative lower bound γ ≥ k/2 is achievable (e.g., in abelian topological order) under d > n/4 or with local recoverability (via Expansion Lemma), reinforcing that TEE and long-range entanglement are robust up to ~1/n AQEC error. - Critical systems/CFT codes: For low-energy CFT code spaces on S^D, ε_G scales polynomially with system size: ε_G = Θ(n^{-Δ/D}), where Δ is the minimal scaling dimension. If Δ > D (so ε_G = õ(1/n)), then every CFT code state has superconstant all-to-all complexity. The threshold Δ = D is tied to conserved currents (global symmetries), aligning the ~1/n boundary with symmetry constraints and approximate Eastin-Knill phenomena. - Examples and tightness: • Redundant encodings can achieve vanishing errors of order O(√(dk/n)) under random erasures, showing that merely vanishing error is too weak a criterion. • Heisenberg ferromagnet ground-space codes have ε_G ≳ Ω(1/n) at d = O(log n), placing them outside the nontrivial regime, consistent with containing product states. • Momentum codes: the full code (k ~ log n) has nonvanishing ε_G, but fragmenting into k=1 codes yields ε_G = o(1) for d = o(n^{1/3}), enabling complexity bounds for eigenstates and selected superpositions. • Good approximate quantum LDPC constructions (from spacetime Hamiltonians) inhabit the nontrivial regime with polylogarithmic errors. Overall, the analysis supports proposing O(k/n)—often O(1/n)—as the operative threshold for nontrivial AQEC codes and associated complexity.

The findings answer the motivating question by providing a principled, quantitative condition—small subsystem variance relative to code rate and light-cone scale—that uniformly implies nontrivial circuit complexity for all states in a code. This links AQEC precision to intrinsic computational structure in many-body systems, independently of a specific Hamiltonian. The results: - Clarify the relation among code properties (TQO-like conditions), long-range entanglement, and TEE: exponentially small error and macroscopic distance are not necessary for long-range entanglement; ε_G ≲ O(1/n) with superconstant d suffices. Conversely, trivial TEE in 2D area-law states rules out ε_G = o(1/n) on linear regions. - Illuminate critical systems: CFT low-energy sectors are intrinsically AQEC with polynomial error, and crossing the Δ = D threshold yields intrinsic all-to-all complexity. This dovetails with expectations from holography (e.g., large Δ/corresponding to large central charge and bulk masses), hinting that AQEC parameters may diagnose features relevant to gravity duals. - Provide a framework for circuit lower bounds: The subsystem-variance-based conditions yield general, geometry-aware lower bounds and a converse: the existence of low-complexity states in a code enforces lower limits on ε_G. - Identify “marginal order”: Systems near the ~1/n precision boundary (often enforced by symmetries) can display nontrivial but fragile order distinct from gapped topological order. This helps differentiate classes of quantum order and their stability properties. These insights unify disparate observations across QEC and physics, offering both conceptual clarity and practical tools for complexity lower bounds in many-body systems.

This work proposes subsystem variance as a fundamental AQEC parameter and establishes quantitative thresholds—scaling roughly as O(k/n), often O(1/n)—below which code subspaces necessarily exhibit nontrivial circuit complexity for all code states across both all-to-all and geometric settings. The framework bridges AQEC precision with computational complexity and physical order, providing rigorous connections to long-range entanglement and TEE in topologically ordered systems, and revealing intrinsic polynomial AQEC errors in CFT code spaces with consequences for holography. Key contributions include: two-way bounds between subsystem variance and AQEC inaccuracy, general circuit lower bounds via light-cone/entropy arguments, TEE robustness under o(1/n) errors, and ε_G ~ n^{-Δ/D} scaling for CFTs. Future directions suggested include: refining constants and graph-dependent factors in the bounds; exploring codes with Δ > D CFTs and their potential gravity duals; probing symmetry constraints via AQEC parameters; extending the theory to continuous variables, fermions, mixed states, and broader noise models; and leveraging the framework to prove lower bounds for specific physically motivated states and Hamiltonians.

- The principal circuit lower bounds are sufficient conditions tied to subsystem variance and may not be necessary; there can be codes outside the stated regimes that still have high complexity. - Several bounds (e.g., relating ε_G to ε̃, and geometric complexity constants) include dimension- and k-dependent factors (e.g., 2^{k/2}) and polylogarithmic overheads; tight constants may be improved. - Replacement channels are a canonical but restricted noise class for which the tight two-way ε_G–ε̃ bounds are proven; extensions to general noise require additional assumptions or looser bounds. - Some main-text theorem statements contain simplified forms; refined statements with sharper dependencies and full proofs are in the appendices, indicating technical subtleties in exact exponents and constants. - The CFT analysis relies on scaling arguments (state-operator correspondence and one-point functions) and assumes that small-size operators can be approximated by products of local operators up to polylog factors; rigorous control of all subleading terms is left to future work. - Applications to specific models (e.g., momentum codes, string-net with tension) illustrate phenomena but do not exhaustively classify all parameter regimes or noise models.