I believe there is such a representation, as follows:

You need only consider operators which can be written as $\Omega = \sum_k \alpha_k \gamma_k$, where $\gamma_k = \sum_\ell P_\ell \big( \sigma_{k_1} \otimes \cdots \otimes \sigma_{k_N} \big)P_\ell^\dagger$ with $P_\ell$ being the operator corresponding to the $\ell^{\text{th}}$ permutation of qubits. Note that $\gamma_k$ is defined on the whole space, and is essentially a generalization of the number operator. $\gamma_k$ can be uniquely identified by each of the number of each kind of Pauli matrix it contains, and so is polynomial in the number of qubits. The same works for the case of qudits, though the degree of the polynomial will scale with the dimensionality of the local systems. For qubits, we have 3 relevant numbers: 1) $N_X$ the number of sites where the operator acts as $\sigma_X$, 2) $N_Y$ the number of sites where the operator acts as $\sigma_Y$ and 3) $N_Z$, the number of sites where the operator acts as $\sigma_Z$, subject to the constraint that $N_X + N_Y + N_Z \leq N$. So instead, we can relabel the $\gamma$ matrices as $\gamma_{N_X,N_Y,N_Z}$ for the two dimensional case.

Notice that the set of possible $\Omega$ form a group under multiplication, and that each element of the group has a polynomial description (up to approximation of the complex coefficients).

Thus:

Since the $\gamma$ operators form a basis for Hermitian matrices which are invariant under permutation of the local Hilbert spaces, they satisfy your first criterion.

Any stabilizing operator $\Omega$ can be described by a set of real numbers (or approximations there of), the number of which is polynomial in the number of subsystems and exponential in their local dimension, thus satisfying your second criterion.

Symmetric local unitaries can also be written in terms of a sum of $\gamma$ matrices (albeit it with an additional restriction on the values of $\alpha_k$), and thus by the group structure, the outcome can still be represented within this framework. When a unitary is applied, the stabilizers transform as $U \Omega U^\dagger$, which is efficiently computable if $U$ is symmetric given the reduced basis with which both $U$ and $\Omega$ can be expressed, satisfying your last criterion.

This post has been migrated from (A51.SE)