Monomial stabilizer code[1]

Description

Code whose codespace is the joint \(+1\) eigenspace of a set of monomial unitary operators, i.e., unitary operators \(PD\) that are each a product of a permutation matrix \(P\) and a diagonal matrix \(D\) in a distinguished basis. The stabilizing operators need not commute. Codespaces are called M-spaces, and states admitted by one-dimensional codespaces are called M-states [1].

Monomial stabilizer descriptions exist for many states and codes outside of the Pauli stabilizer formalism. Examples include XP stabilizer codes [2], quantum-double codes, the ground space of the AKLT model, W and Dicke states, and coset states (i.e., CSS-type states) of finite Abelian groups [1]. Further examples include locally maximally entanglable (LME) states [3], states encoding output distributions of probabilistic classical circuits [4], and the Laughlin wavefunction at unit filling [1].

A monomial stabilizer group \(\mathcal{G}\) is an extension of the permutation group \(\mathcal{P}\) formed by the permutation parts of its elements by the normal subgroup formed by its diagonal elements. For example, the \(n\)-qubit Pauli group is an extension of its \(X\)-type permutation image by the diagonal subgroup generated by \(Z\)-type strings and phases.

The results below hold when the stabilizing operators generate a finite group \(\mathcal{G}\), which is the setting of the original formalism [1]. The defining joint-eigenspace condition applies verbatim to infinite groups, and many of the results naturally extend [1]. For compact stabilizer groups, averages over \(\mathcal{G}\) can be taken with respect to the Haar measure. For continuous configuration spaces, the distinguished basis becomes a generalized basis of delta-function normalized states, and joint eigenspaces can be spanned by non-normalizable states. In this way, the formalism accommodates the finite, compact, and sufficiently well-behaved locally compact Abelian (LCA) groups underlying general-group quantum-double codes, group-GKP codes, and stabilizer codes, with the LCA case including mixed stabilizer codes. For such \(\mathcal{G}\), the projector onto the codespace is the average of the elements of \(\mathcal{G}\). In other words, the codespace is the isotypic component of the trivial irrep of \(\mathcal{G}\), and the multiplicity of that irrep is the codespace dimension.

Every monomial stabilizer code with finite stabilizer group admits a canonical orthonormal basis, the orbit basis, containing one basis state per orbit of \(\mathcal{P}\) lying in the codespace support [1]. The orbit state determined by a distinguished-basis state \(|x\rangle\) in the support is \begin{align} |\psi_{x}\rangle=\frac{1}{\sqrt{|\mathcal{O}_{x}|}}\sum_{|y\rangle\in\mathcal{O}_{x}}\xi_{x}(y)|y\rangle~, \tag*{(1)}\end{align} where \(\mathcal{O}_{x}\) is the \(\mathcal{P}\)-orbit of \(|x\rangle\), and where \(\xi_{x}(y)\) are phases determined by the stabilizer group. An orbit lies in the support if and only if every stabilizer group element mapping an orbit representative to itself does so with unit phase [1]. As a result, the codespace dimension is the number of such orbits and is at most the total number of orbits of \(\mathcal{P}\).

Deciding whether the codespace of a monomial stabilizer code is nonzero is \(NP\)-hard, already for diagonal stabilizer generators acting on at most three qubits each [1]. Sampling the distribution underlying a codeword of a one-dimensional code and estimating codeword expectation values of single-qubit observables are \(NP\)-hard under randomized reductions, via the satisfiability problem with a promised unique satisfying assignment [1]. Efficient classical algorithms for sampling and for estimating expectation values of few-body observables exist whenever orbit membership, uniform orbit sampling, and the phases \(\xi_{x}(y)\) are efficiently computable [1]. Nearly all of the example families above satisfy these conditions [1].