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.}