What is the largest number of stabilizers a pure state can have?

What is the largest number of stabilizers a pure state can have? Elaborately put:

Let $$P(n)$$ denote the Pauli group. Given an arbitrary pure state $$|\psi\rangle$$, what is the upper limit on how many unitary matrices $$U_i \in P(n)$$ there can be such that $$U_i|\psi\rangle = |\psi\rangle$$?

An exact reference and/or a proof is very, very much appreciated.

Every $$n$$-qubit pure quantum state has at most $$2^n$$ stabilizers. There are at least two approaches to proving this bound. One makes explicit use of the language of symplectic bilinear forms and the other eschews it while using essentially the same ideas. Below, I write out the former including a short summary of the relevant definitions and the key lemma from symplectic linear algebra. For the latter, see Proposition $$10.5$$ on page $$458$$ in Nielsen & Chuang. Note that the connection to the symplectic linear algebra is used throughout literature and therefore it is useful to know it.

Summary

The proof works by mapping the Pauli group $$P(n)$$ into a symplectic vector space $$\mathbb{Z}_2^{2n}$$. Due to the way the symplectic form on $$\mathbb{Z}_2^{2n}$$ is defined, abelian subgroups of $$P(n)$$, such as any stabilizer group, are mapped into isotropic subspaces. Symplectic linear algebra then puts an upper bound on the dimension of those subspaces which translates into an upper bound on the order of abelian subgroups of $$P(n)$$.

Background in symplectic linear algebra

Let $$V$$ be a finite dimensional vector space over field $$K$$. A function $$\langle.,.\rangle:V\times V\to K$$ which is

• linear in both arguments,
• alternating, i.e. $$\langle u,u\rangle = 0$$ for all $$u\in V$$ and
• non-degenerate, i.e. $$\langle u,v\rangle = 0$$ for all $$v\in V$$ implies that $$u=0$$

is called a symplectic bilinear form. A subspace $$W\subset V$$ is called isotropic if $$\langle u,v\rangle=0$$ for all $$u,v\in W$$. In a fixed basis $$v_1,\dots,v_{2n}$$ the symplectic bilinear form can be represented as a matrix

$$\Omega = \begin{bmatrix} \langle v_1,v_1\rangle & \dots & \langle v_1,v_{2m}\rangle \\ \dots & \dots & \dots \\ \langle v_{2m},v_1\rangle & \dots & \langle v_{2m},v_{2m}\rangle \\ \end{bmatrix}.\tag1$$

It is easy to show that non-degeneracy of $$\langle.,.\rangle$$ implies non-singularity of $$\Omega$$. The key result from symplectic linear algebra needed to establish the upper bound on the number of stabilizers of a pure state is the following

Lemma Let $$V$$ be a $$2m$$-dimensional$$^1$$ symplectic vector space. Let $$W$$ be an isotropic subspace of $$V$$. The dimension of $$W$$ is at most $$m$$.

Proof Suppose that $$\dim W = k > m$$ and let $$w_1,\dots,w_k$$ be a basis of $$W$$. Extend it to a basis $$w_1,\dots,w_k,v_{k+1},\dots,v_{2m}$$ of $$V$$. In this basis

$$\Omega = \begin{bmatrix} 0 & \dots & 0 & \omega_{1,k+1} & \dots & \omega_{1,2m} \\ \dots & & \dots & \dots & & \dots \\ 0 & \dots & 0 & \omega_{k,k+1} & \dots & \omega_{k,2m} \\ \omega_{k+1,1} & \dots & \omega_{k+1,k} & \omega_{k+1,k+1} & \dots & \omega_{k+1,2m} \\ \dots & & \dots & \dots & & \dots \\ \omega_{2m,1} & \dots & \omega_{2m,k} & \omega_{2m,k+1} & \dots & \omega_{2m,2m} \\ \end{bmatrix}\tag2$$

which has rank at most $$4m-2k < 2m$$. The contradiction means that $$\dim W \le m$$.$$\square$$

Upper bound on the number of stabilizers

Claim For a pure state $$|\psi\rangle$$ of $$n$$ qubits, let $$S_\psi:=\{U\in P(n)\,|\,U|\psi\rangle=|\psi\rangle\}$$ be the set of all Pauli operators that stabilize $$|\psi\rangle$$. Then

$$|S_\psi|\le 2^n.\tag3$$

Proof Every $$U\in P(n)$$ can be written uniquely as

$$U=a\bigotimes_{k=1}^nX^{x_k}Z^{z_k}\tag4$$

with $$a\in\{\pm 1, \pm i\}$$ and $$x_k,z_k\in\mathbb{Z}_2$$. Define $$h:P(n)\to\mathbb{Z}_2^{2n}$$ by

$$h(U):=x_1\dots x_nz_1\dots z_n.\tag5$$

Writing for brevity $$[x,z]:=x_1\dots x_nz_1\dots z_n$$ with $$x,z\in\mathbb{Z}_2^n$$ define $$\langle.,.\rangle:\mathbb{Z}_2^{2n}\times\mathbb{Z}_2^{2n}\to\mathbb{Z}_2$$ by

$$\langle [x,z], [x',z']\rangle:=x^Tz' + x'^Tz.\tag6$$

It is easy to check that $$(6)$$ defines a symplectic bilinear form. Its significance lies in the observation that $$U,V\in P(n)$$ commute if and only if $$\langle h(U),h(V)\rangle = 0$$.

Now, $$S_\psi$$ is an abelian subgroup of $$P(n)$$, so the image $$h[S_\psi]$$ is an isotropic subspace of $$\mathbb{Z}_2^{2n}$$ and by the lemma above $$\dim h[S_\psi]\le n$$. Therefore, $$|h[S_\psi]|\le 2^n$$. Finally, even though $$h$$ is a four-to-one map, exactly one of the four operators in the preimage $$h^{-1}[u]$$ of $$u\in h[S_\psi]$$ is in $$S_\psi$$. Therefore, $$|S_\psi|\le 2^n$$.$$\square$$

Saturation of the bound

The computational basis state $$|00\dots 0\rangle$$ is stabilized by all tensor products of Pauli $$Z$$ and identity, i.e.

$$S(|00\dots 0\rangle) = \left\{\bigotimes_{k=1}^n Z^{u_k}\,\Big|\,u_1u_2\dots u_n\in\mathbb{Z}_2^n\right\}.\tag7$$

Since $$|S(|00\dots 0\rangle)|=|\mathbb{Z}_2^n|=2^n$$, we see that the upper bound $$(3)$$ is saturated. The states that saturate the bound are called stabilizer states.

$$^1$$ It can be shown that a symplectic vector space is even-dimensional. However, we do not need this result here since the symplectic vector space we use is even-dimensional by construction.

• Shouldn't the plus in (6) be replaced by a minus? Otherwise we get a symmetric form instead of an alternating one. Dec 21 '21 at 12:00
• In general yes, but over $\mathbb{Z}_2$ there is no difference. Dec 21 '21 at 16:33

TL/DR

The dimension of the stabilizer $$\mathcal{S}$$ is $$2^{n}$$ because there are exactly $$n$$ generators to make the dimension of the stabilizer's eigenspace exactly $$1$$. Then, each element in $$\mathcal{S}$$ is a unique combination of the generators for a total of $$2^{n}$$ combinations.

Long version

It's easy to show that the stabilizer $$\mathcal{S}$$ forms a group. Let $$\{G_{i}\}_{i=1}^{k}$$ form a set of generators.

Note that, since $$G_{i}$$ are generators and their self-inverses, no product of different $$G_{i}$$ can be the identity. Moreover, the stabilizer is abelian so all the generators commute. This means that we can write any element $$S_{\vec{l}}$$ in $$\mathcal{S}$$ as a (unique) product of its generators:

$$\begin{equation} S_{\vec{l}} = G_{1}^{l_{1}}G_{2}^{l_{2}}\dots G_{k}^{l_{k}}, \end{equation}$$ where $$\vec{l}$$ is a binary vector of length $$k$$ that has $$\vec{l}_{i} = 1$$ if $$G_{i}$$ is 'part' of $$S_{\vec{l}}$$. There are $$2^{k}$$ such vectors (i.e. each generator can be 'turned on' or 'turned off'), so there are $$2^{k}$$ elements in $$\mathcal{S}$$.

So what is $$k$$? The projector upon all the $$+1$$ eigenspaces is of the form $$\Pi_{i}\frac{I+G_{i}}{2}$$, which we can rewrite by noting that this gives every possible combination of products of the generators: $$\begin{equation} \begin{split} \Pi^{k}_{i}\Big(\frac{I+G_{i}}{2}\Big) &= \frac{1}{2^{k}}\sum_{\vec{l}}G_{1}^{l_{1}}G_{2}^{l_{2}}\dots G_{k}^{l_{k}}\\ &= \frac{1}{2^{k}}\sum_{S\in\mathcal{S}}S \end{split} \end{equation}$$

The stabilizer uniquely defines $$|\psi\rangle$$ as the shared $$+1$$ eigenspace, and this thus should have dimension $$d = 1$$. The dimension of a projector $$\Pi$$'s space is $$\mathrm{tr}\big[\Pi\big]$$, so we get: $$\begin{equation} \begin{split} d &= \mathrm{tr}\Big[\frac{1}{2^{k}}\sum_{S\in\mathcal{S}}S\Big] \\ &= \frac{1}{2^{k}}\sum_{S\in\mathcal{S}}\mathrm{tr}\big[S\big] \\ &= \frac{1}{2^{k}}\mathrm{tr}\big[I\big] + \frac{1}{2^{k}}\sum_{S\in\mathcal{S}\setminus I}\mathrm{tr}\big[S\big] \\ &= \frac{1}{2^{k}}2^{n} + 0 = 2^{n-k}, \end{split} \end{equation}$$ where I made us of the fact that the trace is linear, and that every non-identity Pauli is traceless. Hence, $$1=d=2^{n-k}$$ leads to there being $$k=n$$ generators, for a total of $$2^{k} = 2^{n}$$ elements in the $$\mathcal{S}$$.

Note that this also means that every stabilizer state has exactly this many elements in it's stabilizer.