4.4 Permutation-symmetric circuits and Dicke coordinates
On this page · Permalink · Source line 898
4.4.1 The symmetric subspace
On this page · Permalink · Source line 903
Let the symmetric group \(S_n\) act by permuting the \(n\) tensor factors. The fully symmetric qubit subspace is spanned by the Dicke states
Its dimension is \(n+1\).
Derived theorem or corollary
If the initial state is permutation symmetric with efficiently computable Dicke coordinates, every gate preserves the fully symmetric subspace, the gate matrices in the Dicke basis are computable in polynomial time, and the final measurement is permutation invariant and efficient, then the circuit family lies in \(P\).
Theorem 4.2: Permutation-symmetric collapse
Under the hypotheses above, an \(n\)-qubit circuit can be simulated using an \((n+1)\)-component classical state vector and polynomial-time updates.
Proof
The projector onto the trivial \(S_n\) representation has rank \(n+1\). The Dicke basis is explicitly indexed by \(k=0,\ldots,n\). Apply Theorem 3.7.
4.4.2 Collective spin operators
On this page · Permalink · Source line 934
Define
The operators \(J_a\) preserve the symmetric subspace. We use the computational convention \(\sigma_z{\lvert 0\rangle}={\lvert 0\rangle}\) and \(\sigma_z{\lvert 1\rangle}=-{\lvert 1\rangle}\). Thus \(J_z{\lvert D_n^k\rangle}=(n/2-k){\lvert D_n^k\rangle}\). For the following occupation formulas define \(J_+=J_x-iJ_y\) and \(J_-=J_x+iJ_y\), so that the subscript records increasing or decreasing excitation number rather than magnetic quantum number. Then
Thus collective rotations and polynomial functions of collective spin admit banded or structured updates on \(n+1\) amplitudes.
4.4.3 Symmetric qudits
On this page · Permalink · Source line 953
For local dimension \(d\), the symmetric subspace has occupation-number basis
and dimension
For fixed \(d\), this is polynomial in \(n\).
Corollary 4.3: Fixed-local-dimension symmetric qudits
A uniform family of fully symmetric \(d\)-level circuits is classically polynomial-time simulable for fixed \(d\), provided its occupation-basis updates and measurement are polynomial-time computable.
4.4.4 What full symmetry excludes
On this page · Permalink · Source line 979
A generic two-qubit gate acting on one selected pair does not preserve the fully symmetric subspace. Symmetry is preserved by collective gates or by circuits arranged so that the total operation commutes with all permutations. A gatewise packet simulator requires gatewise invariance, or else it must combine several elementary gates into a symmetry-preserving layer and audit intermediate leakage.