4.6 Permutation-invariant mixed states and commutant compression
On this page · Permalink · Source line 1029
4.6.1 Why multiplicity can disappear without being discarded
On this page · Permalink · Source line 1035
The fully symmetric subspace is only one Schur–Weyl packet. A general permutation-invariant mixed state can occupy every Schur label while still admitting a polynomial classical description for fixed local dimension. The reason is that the exponentially large symmetric-group multiplicities occur as identity factors rather than independent dynamical coordinates.
Let \(S_n\) act on
by permuting tensor factors. Schur–Weyl duality gives
where \(S_n\) acts trivially on the first tensor factor and irreducibly on \(\mathcal V_\lambda\).
4.6.2 The permutation twirl
On this page · Permalink · Source line 1052
Define the twirling channel
Its image is the commutant of the permutation action.
Lemma 4.5: Invariant observables see only the twirl
If \(A\) commutes with every \(U_\pi\), then
for every density operator \(\rho\).
Proof
Using cyclicity of the trace and \(U_\pi^*AU_\pi=A\),
If a unitary \(U\) and acceptance operator \(M\) are permutation invariant, then \(U^*MU\) is invariant. Therefore the final probability depends on the input only through its twirl. This permits an observable-specific collapse even when the original pure input is not itself symmetric.
4.6.3 Exact commutant record
On this page · Permalink · Source line 1092
Let
Schur's lemma gives the following normal form.
Lemma 4.6: Permutation-invariant state normal form
A density operator \(\rho\) commutes with every permutation if and only if it can be written as
where \(p_\lambda\ge0\), \(\sum_\lambda p_\lambda=1\), and each \(\rho_\lambda\) is a density operator on \(\mathcal U_\lambda\) whenever \(p_\lambda>0\). The weights \(p_\lambda\) and the unnormalized blocks \(p_\lambda\rho_\lambda\) are unique. The normalized block \(\rho_\lambda\) is unique only when \(p_\lambda>0\) and is omitted when \(p_\lambda=0\).
The complete state record is therefore
The multiplicity dimension \(f_\lambda\) affects normalization and degeneracy, but no \(f_\lambda\times f_\lambda\) matrix needs to be stored.
A permutation-invariant unitary has the form
and a permutation-invariant measurement operator has the analogous form
The output probability is
4.6.4 Polynomial parameter bound
On this page · Permalink · Source line 1148
The number of partitions of \(n\) with at most \(d\) parts is bounded by the number of weak compositions:
The Weyl dimension formula gives
Therefore
Theorem 4.7: Schur-commutant collapse
Fix the local dimension \(d\). Consider a polynomial-time uniform family of permutation-invariant quantum circuits or channels on \(n\) qudits. Suppose:
the Schur-block record of the twirled input can be constructed in polynomial time;
the induced update on the invariant operator record in Equation (4.4) is computable to polynomial precision in polynomial time;
the final measurement is permutation invariant and its Schur blocks are efficiently computable.
Then the associated decision problem belongs to \(P\).
Proof
Permutation covariance keeps the density operator inside the commutant algebra. By Equation (4.8), that algebra has polynomial dimension for fixed \(d\). The hypotheses supply polynomial-time initialization, updates, and measurement on this record. Apply Theorem 6.1.
Derived theorem or corollary
For fixed local dimension, permutation-invariant mixed-state dynamics can be classically polynomial even when the state has support across exponentially large symmetric-group multiplicity spaces. Those multiplicities are exact identity factors in the invariant operator record.
4.6.5 Qubit corollary
On this page · Permalink · Source line 1191
For qubits, Schur labels are total spins \(j\). The carrier dimension is
and there are at most \(\lfloor n/2\rfloor+1\) labels. Hence
Corollary 4.8: Permutation-invariant qubit channels
A uniform permutation-covariant qubit channel family with efficiently computable total-spin block updates, efficiently available twirled input blocks, and a permutation-invariant measurement is classically simulable using \(O(n^3)\) density-matrix parameters, up to constant factors and numerical precision.
Collective Hamiltonians that are polynomial expressions in \(J_x,J_y,J_z\) are a basic test class because their total-spin matrices can be generated directly without constructing the full \(2^n\times2^n\) operator.
4.6.6 What this theorem does not cover
On this page · Permalink · Source line 1215
The theorem does not make an arbitrary local circuit easy. A gate acting on one selected pair generally fails to commute with all permutations. An arbitrary input may have Schur blocks that are difficult to compute from its succinct description. A non-invariant measurement can read information stored in multiplicity coordinates. Finally, allowing local dimension \(d\) to grow with \(n\) can make the commutant record superpolynomial.
The result is therefore a complete collapse theorem for a declared symmetry and access model, not a claim that Schur–Weyl decomposition alone solves generic many-body simulation.