Source-linked AI summary
Behavioral Memory under Symmetry in One-Way Quantum Automata
Zeyu Chen
TL;DR
The paper asks how compact symmetry determines which quantum operator degrees of freedom become distinguishable behavioral memory and which force classical states. It answers with three filters—reachable–observable rank, dynamically mobile invariant coordinates, and threshold realization—and proves that fully mobile commutative algebras cost their dimension while noncommutative blocks cost one additional state. The theory also links preserved symmetry to polynomial or exponential memory scales and yields a Catalan law for half-filled fixed-weight modules.
Problem
Under compact symmetry, invariant operator dimension alone does not determine classical memory because coordinates may be frozen, unobservable to threshold tests, or already classical.
Method
The paper separates behavioral memory through exact reachable–observable Hankel rank, symmetry-commutant structural capacity, and strict-cutpoint stochastic realization.
Results
Fully mobile commutative invariant algebras cost their dimension, while noncommutative multiplicity blocks raise unrestricted strict-cutpoint cost by exactly one state; preserved symmetries can also yield polynomial or exponential scales.
Takeaways & Limitations
The commutant dimension and commutativity determine exact unrestricted state cost in the fully mobile case, while dynamics and readout decide which structural coordinates survive otherwise.
Takeaways & Limitations
The two-letter independent-sector-control result is an abstract global-control statement and need not be attainable with geometrically local or hardware-native gates.
Abstract
from arXiv · showhide
Under compact symmetry, observable behavior reduces to an invariant operator algebra, but its dimension is not yet classical memory: some coordinates are dynamically frozen, some invisible to threshold tests, and some already classical. We develop an operator-algebraic theory that separates these effects through three filters. For one automaton, behavior is the Hilbert--Schmidt pairing between prefix-reachable states and suffix-observable effects, whose rank equals the real Hankel rank without controllability or observability assumptions. Maximizing this invariant over a symmetry-constrained dynamical class gives a structural capacity controlled by the symmetry commutant: its center stores isotypic populations frozen by reversible dynamics, its traceless multiplicity blocks carry movable noncommutative coordinates, dissipation removes the unary spectral loss inside those blocks, and covariant mobility releases relative populations subject to component conservation. Operational realization then determines which surviving coordinates force probabilistic states. For a fixed nontrivial invariant readout, full mobility gives an exact dichotomy in worst-case state cost: a commutative invariant algebra costs exactly its dimension, whereas a noncommutative multiplicity block raises the unrestricted cost by exactly one state. Thus noncommutativity has a one-state worst-case classical price. The known four-letter quadratic-plus-one law at trivial symmetry is the fully mobile endpoint of this principle. Schur--Weyl duality further shows that different preserved symmetries on the same tensor-power Hilbert space can change the worst memory scale from polynomial to exponential, while fixed-weight modules give an exact Catalan law at half filling, with structural capacity equal to the Catalan count minus its central-sector correction.
1 Introduction
The paper develops a three-filter theory of behavioral memory under compact symmetry, separating exact instance rank, dynamically activatable operator coordinates, and the probabilistic-state cost of threshold recognition. It identifies commutativity as the full-mobility boundary between already-classical invariant memory and a one-state stochastic overhead.
- Operational realization: Fully mobile commutative invariant algebras have worst strict-cutpoint cost equal to their dimension, whereas a noncommutative multiplicity block adds exactly one state over unrestricted alphabets.The noncommutative endpoint requires at most five letters, or four when the readout is noncentral.
- Structural capacity: The symmetry commutant separates frozen isotypic populations in its center from movable traceless coordinates in multiplicity blocks.This structural filter asks which invariant operator directions the dynamics can actually write.
- Operational realization: Away from full mobility, strict-cutpoint cost lies between structural capacity M and M + 1, with scalar profiles attaining the lower endpoint and persistent noncommutative phases attaining the upper endpoint.For prescribed reversible readouts, visible orbit dimension yields the interval 2 + κ ≤ SC ≤ B + 1.
- Representation-theoretic consequences: Schur–Weyl duality shows that preserving permutation symmetry yields polynomial memory scale while preserving collective-unitary symmetry yields exponential scale on the same tensor-power Hilbert space.At half filling, fixed-weight permutation modules give a Catalan structural count minus the central-sector correction.
- Scope: The framework applies to strict-cutpoint language recognition by real PFAs and preserves threshold languages rather than numerical acceptance probabilities word by word.Other comparison classes, including bounded-error and hybrid quantum–classical models, require different invariants.
- Instance geometry: Behavioral memory is the Hilbert–Schmidt pairing rank between prefix-reachable states and suffix-observable effects, equal to real Hankel rank without controllability or observability assumptions.The construction quotients reachable states by directions invisible to all suffix effects.
3 Structural capacity: the center–commutator split
Structural capacity separates frozen central populations from movable traceless multiplicity coordinates in the symmetry commutant. Compact-group reduction makes these multiplicity spaces the carriers of word-dependent behavior, while reachability and observability determine which capacity is realized.
- Multiplicity-space reduction: Compact symmetry reduces equivariant behavior to sector multiplicity spaces, whose dimensions carry word-dependent acceptance behavior.The irreducible dimensions assemble the physical Hilbert space, but the multiplicities carry the reduced acceptance behavior.
- Saturation: Under independent SU(mλ) control, nonzero traceless components span all traceless Hermitian multiplicity blocks, and a nonzero central pairing adds one constant direction.The resulting pairing rank is 1 + νK, with the upper bound attained when the required state and effect components are present.
- Center–commutator split: The commutant center stores isotypic populations frozen by reversible conjugation, while its traceless multiplicity blocks contain the writable word-dependent directions.Within the reversible class, the writable part has dimension dimC[CK, CK].
- Saturation: Saturation requires both reachability and observability, so locked controls can still attain the structural cap when their multiplicity channels span the relevant operator modes.The accepting measurement can expose a smaller capacity than the full blockwise operator space.
4 Operational realization: finite and dynamic shattering
Operational realization converts visible operator coordinates into strict-cutpoint probabilistic state requirements through finite sign-rank and dynamic shattering. Binary control reaches the noncommutative capacity, while unary dynamics lose specific spectral directions.
- Operational conversion: Finite Jacobian shattering turns visible coordinates into strict signs, while codimension-one stochastic embedding converts linear memory into probabilistic states.Recurrent Markov-limit centering can force one additional state beyond finite sign-rank.
- Finite shattering: A complete sign matrix has sign-rank d, whereas its affine extension has sign-rank d + 1, yielding corresponding PFA state lower bounds.The PFA cutpoint rank is at most its number of states, transferring these sign-rank obstructions to probabilistic automata.
- Binary control: Two sector-preserving unitaries attain the full noncommutative capacity for every finite active profile, but this abstract global-control result need not hold under locality restrictions.Under geometrically local or hardware-native restrictions, exact instance and tangent criteria remain applicable, while the saturated profile law may fail to be attainable.
- Binary lower bounds: For every active profile, binary prepare–test constructions provide strict-cutpoint lower bounds, and rank-one readouts can obtain the same extra-state obstruction through curvature.The curved witness does not require a Markov limit or an infinite carrier orbit.
- Alphabet capacity: The threshold from one to two symbols is an exact noncommutative alphabet transition: a second noncommuting transition releases the Cartan directions lost in the unary case.Unary Hankel rank is bounded blockwise by the available spectral modes, while two symbols attain the broader capacity.
- Profile laws: The noncommutative commutant dimension controls the largest exact Hankel behavior and, up to universal constants, the worst strict-cutpoint probabilistic state cost.Balanced readouts expose a constant fraction of structural capacity, with at most one additional probabilistic state from the stochastic embedding.
5 Dissipative release: channels and central mobility
Dissipative covariant channels separate invariant operator coordinates into movable multiplicity directions and releasable central populations, yielding exact behavioral capacities and state-cost laws under mobility constraints.
- Central mobility: Reversible dynamics freeze central populations, while dissipation can make them writable through mobility partitions.Independent merges of conserved central components release relative population coordinates.
- Behavioral invariant: The Hilbert–Schmidt pairing between reachable states and observable effects gives the exact real Hankel rank without controllability or observability assumptions.Covariance confines behavior to the invariant algebra when at least one boundary is invariant.
- State cost: For component-conserving channels with structural capacity M, strict-cutpoint state cost lies in [M, M + 1].One input symbol already attains the full component capacity.
- Prescribed readout: Each readout-visible component contributes its trace-zero directions, while all component baselines contribute only one shared constant mode.Inactive or scalar readouts contribute no nonconstant observable direction.
C and TCRT
The section establishes binary and unrestricted-alphabet state-cost laws, including the exact quadratic-plus-one endpoint and finite strict-cutpoint witnesses.
- Full mobility: The full-mobility dichotomy gives cost DK for commutative invariant algebras and DK + 1 for noncommutative multiplicity blocks.The latter is exact for a fixed nontrivial invariant readout.
- Trivial symmetry: At trivial symmetry, fixed rank 1 ≤ r < N retains the unrestricted quadratic law N^2 + 1, with four input letters sufficient.The result extends the rank-one law to every nontrivial fixed rank.
- Witness complexity: Finite witnesses have prefix and suffix lengths at most MΠ,P − 1, with strict-cutpoint margins at least εMΠ,P −1/4.The margins may decrease with dimension.
6 Representation-theoretic consequence: Schur–Weyl inversion
Schur–Weyl duality shows that preserving different symmetries on the same tensor-power Hilbert space can produce polynomial or exponential behavioral-memory scales.
- Permutation symmetry: Permutation-equivariant automata have polynomial maximal Hankel rank and binary simulation cost at fixed local dimension.The commutant is the symmetric tensor power of End(C^d).
- Collective-unitary symmetry: Collective-unitary-equivariant automata have an exponential maximal Hankel rank and binary simulation cost for fixed d ≥ 2.The relevant scale is the Specht-factor commutant dimension.
- Symmetry inversion: The polynomial–exponential inversion occurs on the same physical Hilbert space and isolates preserved symmetry as the source of the worst-case memory change.The two automaton classes are distinct and generally non-nested.
- Classical memory bits: Indexing simulator states requires logarithmic memory bits on the permutation side and linear memory bits on the collective-unitary side.The stated scales are 3 log2 n + O(1) versus 2n − 3/2 log2 n + O(1).
7 Readout geometry and symmetry release
Readout geometry distinguishes total movable behavior from threshold-visible directions, while symmetry release enlarges both through block merging and subgroup restriction.
- Reversible capacity: For one active block with mλ = 2 and rλ = 1, the reversible binary state cost lies between 4 and 5.The interval is 4 = 2 + κGK(P) ≤ SCMO,(2) K,P,R(H) ≤ 5 = 2 + νP.
- Readout geometry: The accepting-orbit capacity κ measures the dimension of readout motion under available control, not the full structural behavior capacity.It is also identified with an intrinsic Fisher-rank quantity.
- Visible versus dark directions: The readout-visible directions are accepting–rejecting coherences, while same-outcome coherences and block-population directions remain dark to the two-outcome measurement.A dynamic witness can convert one common radial dark combination into an additional threshold coordinate.
- Block merging: Merging blocks releases cross-block Hermitian coherences and one relative population direction, but only the accepting–rejecting portion increases visible capacity.The increments are path independent on the partition lattice.
- Scope: Symmetry release is not uniformly useful to a fixed readout: capacity growth need not yield a fixed-language or task-performance gain without a finite sign witness.The gain for a particular automaton depends on its reachable–observable pairing.
8 Fixed-weight memory and the critical transition
Fixed-weight permutation modules convert symmetry-reduced operator capacity into a representation-theoretic memory count. Away from half filling endpoint sectors dominate, while half filling yields an exact Catalan law and a Gaussian critical transition.
- Representation-theoretic setup: Fixed-weight permutation modules realize structural capacity through squared dimensions of multiplicity-free Schur–Weyl sectors.The capacity is determined by the representation profile before transitions or accepting readouts are chosen.
- Probabilistic simulation: For sector-preserving binary automata, balanced accepting ranks attain the lower asymptotic order, matching universal upper bounds in the fixed-weight regimes.The resulting probabilistic cost has the same order as the structural capacity after the central correction.
- Macroscopic regime: For every fixed density α < 1/2, endpoint sectors remain geometrically dominant and preserve the full quadratic scale in Hilbert-space dimension.The mechanism fails at half filling because a growing sector window contributes on the same scale.
- Half filling: At half filling, the squared-sector-dimension sum is exactly the Catalan number C_n, while structural capacity is C_n − floor(n/2).The subtraction removes the central-sector correction.
- Half filling: At half filling, the memory scale is smaller than the naive quadratic scale by a factor of order √n.Balanced binary automata inherit the corresponding Catalan-order probabilistic simulation cost.
- Critical transition: When the distance from half filling is of order √n, the sector sum enters a Gaussian critical window interpolating between macroscopic and Catalan regimes.The three regimes are endpoint domination, Catalan accumulation, and critical-window interpolation.
9 Intermediate halting and nonhalting behavioral memory
Intermediate halting changes which operator coordinates carry behavior by accumulating acceptance and repeatedly projecting onto nonhalting corners. The resulting profile-dependent capacity and state cost are exact in broad covariant settings, but dynamic realization need not always reach the upper endpoint.
- Absorbing dynamics: Intermediate halting preserves absorbed acceptance while updating only the nonhalting block through absorbing Kraus channels.The construction is trace preserving and reproduces cumulative measure-many acceptance probabilities.
- Instance geometry: The measure-many continuation space remains the exact reachable–observable pairing, although absorption changes the operator coordinates carrying behavior.Thus the instance-geometric invariant survives the change from measure-once to measure-many dynamics.
- Structural capacity: Intermediate measurement does not release central isotypic coordinates, but surviving nonhalting block weights become dynamical coordinates.This closes the structural capacity once the halting profile is fixed.
- Profile laws: For a nonempty active profile, one input symbol can attain the exact profile capacity, while the probabilistic state cost is bounded by capacity plus one.An empty active profile has exact state cost one.
- Limitation: The compiled weak-leak construction does not automatically raise the measure-many interval to its upper endpoint because a persistent affine offset can prevent recurrent cutpoint crossing.This is identified as a genuine boundary of the dynamic lift.
- Boundary case: A scalar measure-many profile can attain the lower endpoint: one active label has exact state cost two rather than three.A phase-assisted upper-endpoint upgrade requires additional nonhalting structure and is not established here.
- Covariant mobility: General covariant channels replace labelwise restrictions with mobility components that can move initial weight among labels within each component.The resulting formula interpolates from the active-label law to 1 + D_non for one full mobility component.
10 Bridges and limits of operational realization
The paper connects instance geometry, structural capacity, and probabilistic state cost through explicit inequalities, while showing that readout geometry and alphabet size impose independent operational limits. These limits leave some fixed-readout and binary measure-many questions unresolved.
- Three bridges: The three layers measure different objects: exact Hankel rank for one instance, maximal activated operator space for a dynamics class, and threshold state cost.The stochastic embedding supplies the general upper bridge between these quantities.
- State-cost bridge: For nontrivial saturated or component-conserving measure-once classes and nonempty measure-many profiles, strict-cutpoint state cost lies between structural capacity M and M + 1.A recurrent noncommutative phase reaches the upper endpoint, while the scalar measure-many construction reaches the lower endpoint.
- Readout limitation: For prescribed reversible readouts, the lower obstruction is controlled by the accepting-projector orbit rather than total structural capacity.This task-visible geometry is where the filters communicate without identifying the quantities on either side.
- Readout limitation: An affine-complete reversible witness is limited by readout-orbit dimension, so full Hankel-capacity lower bounds may require a different sign matrix or invariant.The ceiling applies to every witness drawn from the readout orbit, not merely one construction.
- Quantitative boundary: For a rank-one block of dimension m, the orbit dimension is 2(m − 1) while numerical capacity is m^2, yielding only O(m log m) affine-complete certification.Balanced ranks with κ = Θ(m^2) remain open under this ceiling.
- Alphabet limitation: Alphabet restrictions prevent the present weak-leak compression from establishing a binary measure-many theorem for dimension at least two.The obstruction belongs to this architecture, leaving binary measure-many automata as a distinct semigroup problem.
- Scope: The state-count resource is PFA states; word length, gate depth, and hardware locality remain separate resources.The fixed-weight realization is a representation-sector statement rather than a shallow local implementation claim.
11 Conclusion
The paper presents symmetry-aware memory as a three-filter calculus: instance behavior comes from reachable–observable pairing, structural capacity from center–commutator and mobility, and classical cost from threshold realization. Its sharpest results show that symmetry can preserve classical populations, expose noncommutative coordinates, and change memory scale dramatically.
- Core conclusion: Symmetry reduction does not uniformly reduce memory because surviving coordinates can be frozen, invisible to readout, or already classical.The three-stage theory identifies these statuses through instance geometry, structural capacity, and operational state cost.
- Full mobility: Under full mobility, a commutative invariant algebra has worst state cost equal to its dimension, whereas a noncommutative multiplicity block adds exactly one state.The trivial-symmetry quadratic-plus-one law is the fully mobile endpoint.
- Representation-theoretic scale: Different Schur–Weyl symmetries on the same tensor-power Hilbert space produce polynomial versus exponential worst-case memory scales.At fixed weight, half filling gives a Catalan squared-sector sum and Catalan-minus-center structural capacity.
A Binary Lie generation
The proof uses frequency separation to isolate adjacent matrix edges with two generators, then propagates these local elements to generate the full traceless special-unitary algebra in every active sector.
- Frequency separation distinguishes all adjacent edge eigenvalues, enabling real interpolation to isolate each edge.The resulting Lagrange polynomials isolate one edge from all others.
- Each isolated edge yields its two off-diagonal quadratures and a traceless diagonal difference.These elements arise from iterated commutators of the two generators.
- Commutators propagate adjacent edge elements along each sector, generating su(Dα) whenever Dα ≥2.Blocks with Dα = 1 contribute only su(1) = {0}.
- Trace subtraction and zero diagonal entries exclude central u(1) directions from the generated algebra.
B Fisher geometry of the readout orbit
The readout orbit carries a positive-definite Hilbert–Schmidt geometry, and its dimension is analyzed through local asymptotics and endpoint-safe estimates.
- The projector tangent contains only accepting–rejecting off-diagonal blocks, which enter the spectral SLD calculation.
- The Hilbert–Schmidt form is positive definite on the orbit tangent space of dimension κG(P).
- The proof controls the interior orbit region using a local central limit theorem and mesh spacing 2/√n.
- Endpoint-safe expansions and Gaussian bounds control the discarded regions before taking n →∞, L →∞, and ε ↓0.
- The endpoint asymptotic yields the claimed function.
D Measure-many contraction and test constructions
The construction realizes prescribed contraction blocks and rank-one test directions using weak leaks, dense controls, and compiled measure-many channels while preserving exact threshold signs.
- Diagonalizable contractions with rank-one defect can be embedded as compressions of unitaries on one larger space.The singular-value decomposition supplies the compression realization.
- Distinct contraction eigenvalues give a complete product spectrum and nonzero mode coefficients for the compiled construction.
- Two nonleaking controls and one weak leak per label compile preparations and tests over at most |L| + 2 symbols.The covariant realization preserves complete positivity, trace preservation, covariance, and component conservation.
- Rank-one projections span Herm(Cn), providing finitely many directions for compiling arbitrary multiplicity-space tests.There are 2n^2 − n such projections.
- After choosing R, δ, and the dense-control error in sequence, the resulting finite sign matrix has the prescribed signs exactly.The approximation occurs only inside the construction; threshold signs remain exact.
- Aligned leaks produce survivor-weight grids, while a final continuously oriented leak fills intervals between grid values.For one-dimensional blocks, the grid approximates fixed targets with error O(δ).
E.1 Affine-complete shattering ceiling
The section derives a shattering ceiling from polynomial sign patterns, illustrates orbit-conservation non-saturation, and validates finite certificates without using numerical calculations as universal proof.
- Affine-complete shattering ceiling: Grassmannian charts convert readout threshold tests into real polynomials in κ orbit coordinates.After clearing denominators, the polynomial degree is bounded by the block readout parameters.
- Affine-complete shattering ceiling: Warren’s theorem bounds each chart’s sign patterns, yielding a global shattering inequality and the resulting logarithmic ceiling.
- Affine-complete shattering ceiling: A single-letter power test is monotone in the test length, so each preparation row can change threshold sign at most once within that architecture.
- Common-character covariance conserves label orbits, but the component bound need not be attained.For K = Z2 × Z2, the four labels form two transpositions and the resulting behavior has Hankel rank at most two despite a component bound of 3.
- Finite calculations check dimension and margin formulas, while universal capacity and state-cost theorems remain analytic rather than numerical.
- The Hamming-weight-two S4 module supplies a finite certificate with sector dimensions 1, 3, and 2 and orbit dimension 6.Its active Lie algebra has dimension 11 and its projector stabilizer has dimension 5.
- The same finite example has an intrinsic SLD Fisher metric of rank six with six equal nonzero eigenvalues.