Finite set of invariants to characterize local Clifford equivalence of stabilizer states
Maarten Van den Nest
The classification of stabilizer states under local Clifford (LC) equivalence is of particular importance in quantum error-correction and measurement-based quantum computation. Two stabilizer states are called LC equivalent if there exists a local Clifford operation which maps the first state to the second. We present a finite set of invariants which completely characterizes the LC equivalence class of any stabilizer state. Our invariants have simple descriptions within the binary framework in which stabilizer states are usually described.
cliff_inv_graph_prl2.tex
\documentclass[floatfix,showpacs,amsmath,twocolumn]{revtex4}
\usepackage{amssymb}
%\documentclass[12pt,fleqn]{article}
%\usepackage{a4wide,epsfig,amssymb}
%\topmargin 0cm  \textwidth 15cm \textheight 24cm
\parskip 0mm

%\pagestyle{empty}
\newcommand{\trace}{\mathop{\rm Tr}\nolimits}
\newcommand{\vek}{\mathop{\rm vec}\nolimits}
\newcommand{\diag}{\mathop{\rm diag}\nolimits}
\newcommand{\rank}{\mathop{\rm rank}\nolimits}
\newcommand{\ran}{\mathop{\rm ran}\nolimits}
\newcommand{\kerc}{\ker^\perp}
%\newcommand{\cl}{\mathop{\rm cl}\nolimits}
%\newcommand{\conv}{\mathop{\rm co}\nolimits}
%\newcommand{\conc}{\mathop{\rm conc}\nolimits}
\newcommand{\bra}[1]{\langle#1|}
\newcommand{\ket}[1]{|#1\rangle}
\newcommand{\inpr}[2]{\langle#1|#2\rangle}
\newcommand{\Nabla}{\nabla}
% \newcommand{\qed}{\hfill$\square$\par\vskip12pt} % is already in CMP style
% convention: otimes, oplus for A-B
% ktimes, kplus for I-II
\newcommand{\kplus}{\boxplus}
%\newcommand{\ktimes}{\otimes}
\newcommand{\ktimes}{\boxtimes}
\newcommand{\cB}{{\cal B}}
\newcommand{\cE}{{\cal E}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cG}{{\cal G}}
\newcommand{\cT}{{\cal T}}
\newcommand{\cH}{{\cal H}}
\newcommand{\cI}{{\cal I}}
\newcommand{\cL}{{\cal L}}
\newcommand{\cP}{{\cal P}}
\newcommand{\cS}{{\cal S}}
\newcommand{\cU}{{\cal U}}

\newcommand{\fE}{{\mathfrak E}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\R}{{\mathbb{R}}}
%\newcommand{\identity}{{\openone}}
\newcommand{\identity}{{\mathbb{I}}}

\def\be{\begin{eqnarray}}
\def\ee{\end{eqnarray}}
\def\bee{\begin{eqnarray*}}
\def\eee{\end{eqnarray*}}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{lem}{Lemma}
\newtheorem{conj}{Conjecture}
\newtheorem{prop}{Proposition}
\newtheorem{defn}{Definition}
          \def\pf{\medbreak\noindent{\bf Proof:}\enspace}
          \def\lanbox{{$\, \vrule height 0.25cm width 0.25cm depth 0.05mm \,$}}
          \def\iff{\Longleftrightarrow}
          \def\half{{\textstyle \frac{1}{2}}}
          \def\tr{\hbox{Tr}}
          \def\fm{\lfloor m \rfloor}
        \def\Hil{{\cal H}}
\def\class{{\rm Class}}
\def\shan{{\rm Shan}}
\def\holv{{\rm Holv}}
\def\img{{\rm Image}}
\def\wh{\widehat}
\def\ds{\displaystyle}
   \def\ts{\textstyle}
\def\bra{\langle}
\def\ket{\rangle}
\def\kb{ \ket \bra }
\def\dg{\dagger}
\def\ot{\otimes}
%\def\trho{ \tilde{\rho} }
\def\lraw{\leftrightarrow}
\def\raw{\rightarrow}
\def\wh{\widehat}
\def\whm{\wh{\mu}}
\def\whn{\wh{\nu}}
\def\half{{\textstyle \frac{1}{2}}}
\def\frth{{\textstyle \frac{1}{4}}}
\def\PE{ {\rm ProbErr} }
\def\MPE{ {\rm MinProbErr} }
\def\dtsig{{\mathbf \cdot \sigma}}
\def\bu{{\bf u}}
\def\bv{{\bf v}}
\def\bw{{\bf w}}
\def\nl{\newline}
\def\Tr{{\rm Tr}}


\begin{document}


\title{Finite set of invariants to characterize local Clifford equivalence of stabilizer states}

\author{Maarten Van den Nest}
\email{maarten.vandennest@esat.kuleuven.ac.be} \author{Jeroen Dehaene}\author{Bart De Moor}
 \affiliation{Katholieke Universiteit Leuven, ESAT-SCD, Belgium.}%Lines break automatically or can be forced with \\
\date{\today}
%\maketitle
\begin{abstract}
The classification of stabilizer states under local Clifford (LC) equivalence is of particular
importance in quantum error-correction and  measurement-based quantum computation. Two stabilizer
states are called LC equivalent if there exists a local Clifford operation which maps the first
state to the second. We present a finite set of invariants which completely characterizes the LC
equivalence class of any stabilizer state. Our invariants have simple descriptions within the
binary framework in which stabilizer states are usually described.
\end{abstract}
\pacs{03.67.-a}

 \maketitle

%\section{Introduction}

Stabilizer states constitute a class of multipartite pure quantum states which is of considerable
interest in quantum information theory (QIT) and quantum computing (QC). A stabilizer state on $n$
qubits is defined as a simultaneous eigenvector of a maximal set of commuting observables in the
Pauli group, where the latter is the group generated by all $n$-fold tensor products of the Pauli
matrices and the identity. To name but two of their presently most prominent applications,
stabilizer states firstly appear as codewords of quantum stabilizer codes in the theory of quantum
error-correction \cite{Gott}, and, secondly, they are the resources for QC in a computation model
where only single-qubit measurements are performed (the one-way quantum computer \cite{1wayQC}). In
order to understand the role of stabilizer states in these and other QIT and QC tasks, the
mathematical and physical properties of these states have recently been studied in a number of
accounts \cite{entgraphstate, graphbriegel, localcliffgraph,invar_stab, alg_codes, val_bond}.
%hein, asschauer, frank
One central problem in this research is the classification of stabilizer states under local unitary
(LU) equivalence. Indeed, next to the natural relevance of this issue in the study of the
entanglement properties of stabilizer states, it is also of particular importance both in the
development of the one-way quantum computer and in the coding theoretic aspect of stabilizer
states. In this paper we consider a restricted version of LU equivalence of stabilizer states, in
that we consider only those local unitary operations which belong to the local Clifford group (LC).
The local Clifford group consists of all local unitary operators which map the Pauli group to
itself under conjugation. We will call two stabilizer states LC equivalent if there exists a local
Clifford operator which maps the first state to the second.

The restriction of considering LC equivalence rather than general LU equivalence has two main
motivations. Firstly, the problem of general LU equivalence is difficult and it is therefore
appropriate to first consider a more manageable subproblem, for which LC equivalence is a suitable
candidate - given the very explicit connections between stabilizers states, the Pauli group and the
(local) Clifford group. Secondly, this so-called 'subproblem' might in fact not be a subproblem at
all, as the natural question exists whether every two LU equivalent stabilizer states are
necessarily LC equivalent. Although this question is to date unanswered in general, our work
\cite{LU_LC}, following work performed in Ref. \cite{RainsMin2},  shows that this assertion is at
least true for some interesting subclasses of stabilizer states and a positive answer to this
question is widely believed.


In the following we study LC invariants of stabilizer states, i.e. functions in the entries of a
stabilizer state which take on equal values in LC equivalent states. We construct a finite
\emph{complete set} of invariants, which characterizes the LC equivalence class of any stabilizer
state. Such a study of LC invariants primarily serves to obtain a characterization of LC
equivalence classes of stabilizer states and to gain insight in the structure of these classes, and
to a lesser extent to obtain algorithms which can recognize LC equivalence of two given states.
Indeed, an efficient algorithm to recognize LC equivalence of stabilizer states has recently been
presented in our earlier work and there is little hope that equally efficient algorithms can be
constructed on the basis of invariants (see below). Therefore, we believe that the main merit of
the present result is, firstly, that it gives a \emph{finite} characterization of the LC
equivalence class of any stabilizer state and, secondly, that our invariants exhibit a very
transparent structure in terms of the stabilizer formalism.

Let us now start by recalling the basic notions concerning stabilizer states and the local Clifford
group. A stabilizer state $|\psi\rangle$ on $n$ qubits is the unique simultaneous eigenvector with
eigenvalue 1 of a set of $n$ commuting and independent observables in the Pauli group ${\cal G}_n$.
The latter consists of all operators of the form
$\alpha\sigma_{a_1}\otimes\dots\otimes\sigma_{a_n},$ where $\alpha\in\{ \pm1, \pm i\}$ is an
overall phase factor and $\sigma_{a_i}$ is either the $2\times 2$ identity matrix or one of the
Pauli matrices $\sigma_{x}$, $\sigma_y$, $\sigma_z$, for every $i=1, \dots, n$. The stabilizer
${\cal S}(\psi)$ of $|\psi\rangle$ is the set of all Pauli operators which have $|\psi\rangle$ as
an eigenvector with eigenvalue 1.
%Graph states are special cases of stabilizer states. In particular,   a graph state
%$|G\rangle$ on $n$ qubits is stabilized by $n$ correlation operators $K_j$ $(j=1, \dots, n)$ of the
%specific form \be K_j=\sigma^{(j)}_x \prod_{k=1}^n \left(\sigma_z^{(k)}\right)^{\theta_{kj}},\ee
%where $\sigma^{(i)}_x, \sigma^{(i)}_y, \sigma^{(i)}_z$ are the Pauli matrices which act on the
%$i$th copy of $\Bbb{C}^2$ and where the coefficients $\theta_{kj}\in\{0,1\}$ are the entries of a
%symmetric $n\times n$ matrix $\theta$. This matrix $\theta$ is the adjacency matrix of a simple
%graph $G$ on the vertex set $\{1, \dots, n\}$ \footnote{A simple graph $G$ has no loops or multiple
%edges. Therefore, it can be described by a $n\times n$ symmetric matrix $\theta$ where
%$\theta_{ij}$ is equal to 1 whenever there is an edge between vertices $i$ and $j$ and zero
%otherwise. As $G$ has no loops, $\theta_{ii}=0$ for every $i=1, \dots, n$}.
%Note that any
%stabilizer states is LC equivalent to some graph state \cite{stabgraphcode, graph_grassl}.
It is well known (see e.g. \cite{QCQI}) that the stabilizer formalism has an equivalent formulation
in terms of algebra over the field $\mathbb{F}_2=$ GF(2), where arithmetic is performed modulo 2.
The heart of this binary representation is an encoding of the Pauli matrices by pairs of bits,
writing $\sigma_0=\sigma_{00}$, $\sigma_x=\sigma_{01}$, $\sigma_z=\sigma_{10}$ and
$\sigma_y=\sigma_{11}$ and subsequently \be\sigma_{w_1w_1'}\otimes\dots\otimes\sigma_{w_n w_n'}=:
\sigma_{(w,w')}, \ee where $w:=(w_1, \dots, w_n),\ w':=(w_1', \dots, w_n')\in\mathbb{F}_2^{n}$ are
$n$-dimensional binary vectors. Note that the information about the $i$th qubit is distributed over
the $i$th components of the vectors $w$ and $w'$. Identifying every Pauli operator in an $n$-qubit
stabilizer ${\cal S}(\psi)$ with its $2n$-dimensional binary index vector, one can show that ${\cal
S}(\psi)$ corresponds to an $n$-dimensional self-dual linear subspace $S_{\psi}$ of
$\Bbb{F}_2^{2n}$; the self-duality of this subspace is with respect to a symplectic inner product
on $\Bbb{F}_2^{2n}$.
%$<\cdot, \cdot>$ defined
%by $< u, v>:= u^T P v$, where $u,v\in\Bbb{F}_2^{2n}$ and \be P = \left[
%\begin{array}{cc} 0 & I \\ I& 0 \end{array} \right].\ee
%The binary stabilizer subspace is usually presented in terms of a full rank $2n\times n$ generator
%matrix $S$, the columns of which form a basis of the subspace.
%This generator matrix satisfies$S^TPS=0$ from the self-duality of the space.
%The entire binary stabilizer space, which we denote
%by $S_{\psi}$, is the column space of $S$.
%i.e., it is equal to
%\begin{equation}
%S_{\psi}:=\left\{ Sx\ |\ x\in\Bbb{F}_2^{n}\right\}.
%\end{equation}
%It is clear that there is a lot of freedom in choosing the generator matrix of a stabilizer, as
%multiplying $S$ to the right with a nonsingular $n\times n$ matrix $R$ yields a new generator
%matrix $SR$.
%It can easily be shown that a graph state with adjacency matrix $\theta$ has a generator matrix $ S
%=[ \theta\ |\ I]^T $.

The Clifford group ${\cal C}_1$ on one qubit is the group of all $2\times 2$ unitary operators
which map $\sigma_u$ to $\alpha_u\sigma_{\pi(u)}$ under conjugation, where $u=x,y,z$, for some
$\alpha_u=\pm 1$ and  some permutation $\pi$ of $\{x,y,z\}$. The local Clifford group ${\cal
C}_n^l$ on $n$ qubits is the $n$-fold tensor product of ${\cal C}_1$ with itself. In the binary
stabilizer framework, local Clifford operations $U\in {\cal C}_n^l$ correspond to nonsingular
$2n\times 2n$ binary matrices $Q$ of the block form
\be Q = \left [ \begin{array}{cc} A&B\\
C&D \end{array}\right],\ee where the $n\times n$ blocks $A, B, C, D$ are diagonal
\cite{localcliffgraph}. We denote the diagonal entries of $A, B, C, D$ by
 $a_i$, $b_i$, $c_i$, $d_i$, respectively. The $n$  submatrices \be Q_i:=\left [
\begin{array}{cc} a_i & b_i
\\ c_i& d_i\end{array} \right ]\in GL(2,\Bbb{F}_2)\ee correspond to the tensor factors of $U$.
We denote the group of all such $Q$ by $C^l_n$. In the binary stabilizer framework, two $n$-qubit
stabilizer states $|\psi\rangle$, $|\psi'\rangle$ are LC equivalent if and only if there exists an
operator $Q\in C_n^l$ such that $QS_{\psi}=S_{\psi'}$, i.e., $Q$ maps the space $S_{\psi}$ to the
space $S_{\psi'}$.

Finally, let us recall the definition of \emph{support} in this context of stabilizers, which will
be of considerable importance in the following. The support supp$(v)$ of any vector $v\in
\Bbb{F}_2^{2n}$ is the set \be\label{supp} \mbox{supp}(v) &=& \{i\in \{1, \dots, n\}\ |\
(v_i,v_{n+i})\neq(0,0)\}\nonumber.\ee Note that supp$(v)$ contains exactly those $i\in\{1, \dots,
n\}$ such that the $i$th tensor factor of $\sigma_v$ differs from the identity.

We are now in a position to state the first result of this paper. In theorem 1 a finite set of
invariants which characterizes the LC equivalence class of any stabilizer state, is presented.
\begin{thm}
Let $|\psi\rangle$ be a stabilizer state on $n$ qubits. Let $r\in\Bbb{N}_0$ and consider subsets
$\omega^k$, $\omega^{kl}\subseteq\{1, \dots, n\}$ for every $ k,l\in\{1, \dots, r\}$ with $k<l$.
Denote $\Omega := (\omega^1, \omega^2, \dots, \omega^{12}, \omega^{13}, \dots)$ and let ${\cal
T}_{n,r}^{\Omega}(\psi)$ be the set consisting of all tuples $(v^1, \dots, v^r)\in
S_{\psi}\times\dots\times S_{\psi}$ satisfying \be\label{thm1} \mbox{ supp}(v^{k})= \omega^{k},\
\mbox{\ supp}(v^{k}+ v^{l})= \omega^{kl}.\ee Then (i) $|{\cal T}_{n,r}^{\Omega}(\psi)|$ is an LC
invariant and (ii) the LC equivalence class of $|\psi\rangle$ is completely determined by the
values of all invariants $|{\cal T}_{n,n}^{\Omega}(\psi)|$ (i.e. where $r=n$).
\end{thm}
{\it Proof: } Statement (i) is trivial. To prove (ii), let $|\psi\rangle$ and $|\psi'\rangle$ be
two stabilizer states on $n$ qubits such that $|{\cal T}_{n,n}^{\Omega}(\psi)| = |{\cal
T}_{n,n}^{\Omega}(\psi')|$ for every tuple $\Omega$ as defined above. We will show that this
implies that $|\psi\rangle$ and $|\psi'\rangle$ are LC equivalent. Fix a basis $\{v^1, \dots,
v^n\}$ of $S_{\psi}$ and define the tuple of sets $\Omega_*=(\omega_*^1,\dots, \omega_*^{12},
\dots)$  such that \be\label{thm1'} \omega_*^{k}=\mbox{ supp}(v^{k}) ,\ \omega_*^{kl}=\mbox{\
supp}(v^{k}+ v^{l}) ,\ee for every $k,l=1, \dots, n$ with $k<l$. It follows that $|{\cal
T}_{n,n}^{\Omega_*}(\psi)|$ is nonzero, and therefore $|{\cal T}_{n,n}^{\Omega_*}(\psi')|$ is
nonzero as well, since these numbers are equal by assumption. Therefore, there exist vectors $w^1,
\dots, w^n\in S_{\psi'}$ such that \be\label{thm1''} \mbox{ supp}(w^{k})= \omega_*^{k},\ \mbox{\
supp}(w^{k}+ w^{l})= \omega_*^{kl},\ee for every $k,l$.
%We now use thefollowing lemma:
%\begin{lem}
%Let $r\in\Bbb{N}_0$. Consider subsets $\omega^k$, $\omega^{kl}\subseteq\{1, \dots, n\}$ as before
%and let $(v^1, \dots, v^r)$, $(w^1, \dots, w^r)\in(\mathbb{F}_2^{2n})^{\times r}$. Then there
%exists an operator $Q\in C_n^l$ such that $Qv^k=w^k$, for every $k=1, \dots, r$, if and only if
%\be\label{lemma}
% \mbox{ supp}(v^{k}) &=&  \mbox{ supp}(w^{k})\nonumber\\
% \mbox{\ supp}(v^{k}+ v^{l})&=& \mbox{\ supp}(w^{k}+ w^{l}),\ee for every $k, l\in\{1, \dots, r\}$,
% $k<l$.
%\end{lem}
%{\it Proof: } One of the implications is trivial. To prove the reverse statement, fix two
%$r$-tuples $(v^1, \dots, v^r)$, $(w^1, \dots, w^r)$ of vectors and suppose that (\ref{lemma})
%holds.
Expressions (\ref{thm1'}) and ({\ref{thm1''}}) show that \be (v^{k}_{i}, v^{k}_{n+i}) = (0,0)
&\mbox{ iff }& (w^{k}_i,w^{k}_{n+i}) = (0,0)\nonumber\\ (v^{k}_i,v^{k}_{n+i}) =
(v^{l}_i,v^{l}_{n+i}) &\mbox{ iff }& (w^{k}_i,w^{k}_{n+i}) = (w^{l}_i,w^{l}_{n+i})\nonumber,\ee for
every $i,\ k,\ l=1, \dots, n$. This implies the existence of $n$
operators $Q_i\in GL(2, \mathbb{F}_2)$ such that \be Q_i \left[ \begin{array}{c} v^{k}_i\\
v^{k}_{n+i}\end{array}\right] = \left[ \begin{array}{c} w^{k}_i\\
w^{k}_{n+i}\end{array}\right]\ee for every $i,\ k =1, \dots, n$, and the operators $Q_i$
consequently constitute an operator $Q\in C_n^l$ such that $Qv^k = w^k$ for every $k=1, \dots, n$.
Therefore, the space $QS_{\psi}$ is spanned by the vectors $w^1, \dots, w^n$. Moreover, these
vectors are linearly independent, as they are the images of a linearly independent set under an
invertible linear transformation. Therefore, $\{w^1, \dots, w^n\}$ is a basis of $S_{\psi'}$ (since
the latter is an $n$-dimensional vector space) and we obtain $QS_{\psi} = S_{\psi'}$. This proves
the theorem. \hfill $\square$

Let us briefly discuss this result.  The invariants in theorem 1 are presented as cardinalities of
certain subsets of $S_{\psi}\times\dots\times S_{\psi}$, which are defined in terms of simple
constraints on the supports of their elements. Note that for $r=1$ these invariants simply count
the number of elements in the stabilizer with a prescribed support, i.e., for every
$\omega\subseteq\{1, \dots, n\}$ one has an invariant \be\label{equal}|\{ v\in S_{\psi}\ |\
\mbox{supp}(v)=\omega\}|. \ee These invariants are in fact 'local versions' of the so-called
\emph{weight distribution} of a stabilizer, a well known concept in quantum (and classical) coding
theory which is e.g. used to produce bounds on how good codes can be (see e.g. \cite{Shor_Lafl}).
Our invariants for $r\geq 2$ are in this respect generalizations of this well known notion.

While the structure of the invariants in theorem 1 is indeed very transparent, a direct calculation
of the numbers $|{\cal T}_{n,r}^{\Omega}(\psi)|$ is likely to be hard. It is in this context
interesting to consider the following variant of theorem 1, which presents an alternative complete
family of LC invariants:
\begin{thm}
Using the same notations as in theorem 1, let ${\cal V}_{n,r}^{\Omega}(\psi)$ be the vector space
consisting of all tuples $(v^1, \dots, v^r)\in S_{\psi}\times\dots\times S_{\psi}$ satisfying
\be\label{thm2} \mbox{ supp}(v^{k})\subseteq \omega^{k},\ \mbox{\ supp}(v^{k}+ v^{l})\subseteq
\omega^{kl}.\ee Then (i) the dimension of ${\cal V}_{n,r}^{\Omega}(\psi)$ is an LC invariant and
(ii) the LC equivalence class of $|\psi\rangle$ is completely determined by the values of all
invariants dim$({\cal V}_{n,n}^{\Omega}(\psi))$.
\end{thm}
{\it Proof: } Statement (i) is again trivial. We now prove (ii). Let $\omega\subseteq\{1, \dots,
n\}$ and define the functions $\delta_{\omega}, \epsilon_{\omega}: \Bbb{F}_2^{2n}\to \Bbb{C}$,
respectively,  by $\delta_{\omega}(w) = 1$ if supp$(w)=\omega$ and $\delta_{\omega}(w) = 0$
otherwise, and $\epsilon_{\omega}(w) = 1$ if supp$(w)\subseteq\omega$ and $\epsilon_{\omega}(w) =
0$ otherwise.
%\begin{itemize}
%\item[] $\delta_{\omega}(w) = 1$ if supp$(w)=\omega$ and $\delta_{\omega}(w) = 0$ otherwise
%\item[] $\epsilon_{\omega}(w) = 1$ if supp$(w)\subseteq\omega$ and $\epsilon_{\omega}(w) = 0$
%otherwise. \end{itemize}
It is then straightforward to show the following relations: \be\label{relations1}
&&\epsilon_{\omega} = \sum_{\omega'\subseteq\omega} \delta_{\omega'}\nonumber\\
&&\delta_{\omega}=(-1)^{|\omega|}\sum_{\omega'\subseteq\omega}(-1)^{|\omega'|}\
\epsilon_{\omega'},\ee the first of which is trivial and the second of which can be verified using
straightforward combinatorics. Letting $\Omega$ be a tuple of sets
$\omega^k,\omega^{kl}\subseteq\{1, \dots, n\}$, with $k, l=1, \dots, r$ and $k<l$, it follows that
\be &&|{\cal T}_{n,r}^{\Omega}(\psi)| = \sum \left\{\prod_k \delta_{\omega^k}(v^k)\right\}
\left\{\prod_{k<l} \delta_{\omega^{kl}}(v^k+v^l)\right\}\nonumber\\
&&|{\cal V}_{n,r}^{\Omega}(\psi)| = \sum \left\{\prod_k \epsilon_{\omega^k}(v^k)\right\}
\left\{\prod_{k<l} \epsilon_{\omega^{kl}}(v^k+v^l)\right\}\nonumber,\ee where the sums run over all
$r$-tuples $(v^1, \dots, v^r)\in S_{\psi}^{\times r}$. Using (\ref{relations1}) one finds that
every invariant $|{\cal T}_{n,r}^{\Omega_0}(\cdot)|$ is a linear combination of the invariants
$\{|{\cal V}_{n,r}^{\Omega}(\cdot)|\}_{\Omega}$ with constant coefficients (and vice versa). The
proof then readily follows after applying theorem 1 and noting that the dimension of any vector
space ${\cal V}$ over $\mathbb{F}_2$ is given by dim$({\cal V})= \log_2 |{\cal V}|$. \hfill
$\square$

The main advantage of the invariants dim$({\cal V}_{n,r}^{\Omega}(\psi))$ over the $|{\cal
T}_{n,r}^{\Omega}(\psi)|$'s is that in the former case one is dealing with (dimensions of) vector
spaces, which are much more manageable from a computational point of view. Let us illustrate this
with a simple example: take $\omega\subseteq\{1, \dots, n\}$ as before and consider the invariant
\be\label{subset}|\{ v\in S_{\psi}\ |\ \mbox{supp}(v)\subseteq\omega\}|, \ee which is the
counterpart of (\ref{equal}) in theorem 2. This invariant can indeed be calculated efficiently as
follows: let $v^1, \dots, v^n$ be a basis of $S_{\psi}$ and let $S=[v^1| \dots| v^n]$ be the
$2n\times n$ binary matrix which has the vectors $v^j$ as its columns (the matrix S is generally
referred to as a \emph{generator matrix} of the stabilizer). Denoting by $S_i^T$ the $2\times n$
submatrix of $S$ which is obtained by assembling the $i$th and the $(n+i)$th row of $S$, for every
$i=1, \dots, n$, one readily verifies that the invariant (\ref{subset}) is equal to the corank
(i.e. the dimension of the kernel) over $\mathbb{F}_2$ of the matrix $S_{\omega}:=
(S^T_j)_{j\in\bar\omega}$, where $\bar\omega$ denotes the complement of $\omega$ in $\{1, \dots,
n\}$. Note that the calculation of the (co)rank of a matrix over any field indeed requires only a
polynomial number of operations in the dimensions of this matrix. This shows that the invariant
(\ref{subset}) can easily be calculated when a generator matrix of the stabilizer is known (note
that a stabilizer state in indeed usually presented in terms of a generator matrix). A
straightforward continuation of the above argument shows that, e.g. for $r=2$, an invariant
dim$({\cal V}_{n,2}^{\Omega}(\psi))$, where $\Omega=(\omega^1, \omega^2, \omega^{12})$ with
$\omega^1, \omega^2, \omega^{12}\subseteq\{1, \dots, n\}$, is equal to the corank
of the matrix \be \left[\begin{array}{cc} S_{\omega^1}& \cdot\\\cdot& S_{\omega^2}\\
S_{\omega^{12}} & S_{\omega^{12}}\end{array}\right],\ee and analogous results hold for arbitrary
degrees. This shows that the invariants dim$({\cal V}_{n,r}^{\Omega}(\psi))$ can indeed be
evaluated efficiently; moreover, the information needed to perform the calculation (i.e., the
matrices $S_{\omega}$) can easily be extracted from a generator matrix of the stabilizer.

There is in fact a close relationship between the LC invariants dim$({\cal
V}_{n,r}^{\Omega}(\psi))$ and the polynomial LU invariants  that we considered in
\cite{invar_stab}. In both cases, invariants correspond to dimensions of certain subspaces of
$S_{\psi}\times\dots\times S_{\psi}$ that are defined in terms of constraints on the supports of
their elements. In fact, if $r$ equals 1 or 2 then the LC invariants in theorems 1 and 2 are also
LU invariants; in other words, the invariants dim$({\cal V}_{n,r}^{\Omega}(\psi))$ and $|{\cal
T}_{n,r}^{\Omega}(\psi)|$ take on equal values on LU equivalent stabilizer states. This property is
well known (see e.g. \cite{RainsQWE}) for the invariants (\ref{equal}) and (\ref{subset}),
corresponding to $r=1$. In order to prove this assertion for $r=2$, let
$\Psi=|\psi\rangle\langle\psi|$ be (the projector associated with) a stabilizer state and take
$\Omega=(\omega^1, \omega^2, \omega^{12})$. Then one can readily verify that $|{\cal
V}_{n,2}^{\Omega}(\psi)|$ is, up to a multiplicative constant,  equal to \be \mbox{ Tr
}\left\{(\mbox{Tr}_{\bar\omega^1} \Psi)\ (\mbox{Tr}_{\bar\omega^2} \Psi)\
(\mbox{Tr}_{\bar\omega^{12}} \Psi)\right\},\ee which is manifestly invariant under the action of
local unitary operators (the operation Tr$_{\omega}$ denotes tracing out all qubits in the set
$\omega$). Moreover, this also shows that every $|{\cal T}_{n,2}^{\Omega}(\psi)|$ is an LU
invariant, as it can be written as a linear combination with constant coefficients of the $|{\cal
V}_{n,2}^{\Omega}(\psi)|$'s. Summarizing the current discussion, if $r$ equals 1 or 2 then the
invariants dim$({\cal V}_{n,r}^{\Omega}(\psi))$ and $|{\cal T}_{n,r}^{\Omega}(\psi)|$ take on equal
values on LU equivalent stabilizer states. It is clear that this result is very interesting in
relation with the problem whether LC equivalence and LU equivalence of stabilizer states are
identical notions.

Finally, we wish to note that the two main results in this paper are to be regarded as \emph{upper
bounds} on the maximal $r$ which needs to be considered in order to obtain a complete set of
invariants. Indeed, it is likely that only invariants corresponding to (substantially) lower $r$
need to be considered in order to recognize LC equivalence between two stabilizer states. One
indication for this conjecture is the proof of theorem 1, which shows that all the information of
the LC equivalence class of a given state $|\psi\rangle$ is in fact contained within a single
invariant $|{\cal T}_{n,n}^{\Omega_*}(\psi)|$. A second state $|\psi'\rangle$ is LC equivalent to
$|\psi\rangle$ if and only if \be |{\cal T}_{n,n}^{\Omega_*}(\psi)|=|{\cal
T}_{n,n}^{\Omega_*}(\psi')|, \ee (in fact, even $|{\cal T}_{n,n}^{\Omega_*}(\psi')|>0$ is
sufficient) and the information in all other invariants is in fact redundant. It is not unlikely
that there exist smaller complete lists of invariants (i.e. of smaller $r$) which exhibit less
redundancies. Secondly, our work shows examples of LC equivalence classes which are indeed
characterized by invariants of small $r$: e.g., any stabilizer state is LC equivalent to the GHZ
state on $n$ qubits if and only if the values of the invariants (\ref{subset}) coincide for both
states \cite{LU_LC}. We are therefore led to believe that the results in theorems 1 and 2 can in
principle be improved - if not for all stabilizer states then at least for some interesting
subclasses of states. It is in this context interesting to point out that it has been conjectured
and later disproved in a graph theoretical context that the list of LC invariants (\ref{subset})
are sufficient to characterize the LC equivalence class of all stabilizer states \cite{Bouchet,
entgraphstate}. Therefore, invariants where $r$ is at least 2 must be taken into account. It is to
date not clear whether also higher $r$ are to be considered.

Summarizing this paper, we have characterized LC equivalence classes of stabilizer states by means
of a finite set of invariants. Our invariants have simple descriptions within the binary stabilizer
framework, in that they are equal to dimensions of certain subspaces of $S_{\psi}\times\dots\times
S_{\psi}$. Furthermore, we discussed the link with existing families of LU invariants.



\begin{acknowledgments}

This research is supported by several funding agencies: Research Council KUL: GOA-Mefisto 666,
GOA-Ambiorics, several PhD/postdoc and fellow grants; Flemish Government: -   FWO: PhD/postdoc
grants, projects, G.0240.99 (multilinear algebra), G.0407.02 (support vector machines), G.0197.02
(power islands), G.0141.03 (Identification and cryptography), G.0491.03 (control for intensive care
glycemia), G.0120.03 (QIT), G.0452.04 (QC), G.0499.04 (robust SVM), research communities (ICCoS,
ANMMM, MLDM); -   AWI: Bil. Int. Collaboration Hungary/ Poland; -   IWT: PhD Grants, GBOU (McKnow)
Belgian Federal Government: Belgian Federal Science Policy Office: IUAP V-22 (Dynamical Systems and
Control: Computation, Identification and Modelling, 2002-2006), PODO-II (CP/01/40: TMS and
Sustainibility); EU: FP5-Quprodis;  ERNSI; Eureka 2063-IMPACT; Eureka 2419-FliTE; Contract
Research/agreements: ISMC/IPCOS, Data4s, TML, Elia, LMS, IPCOS, Mastercard; QUIPROCONE; QUPRODIS.
\end{acknowledgments}


\bibliographystyle{unsrt}
%\bibliography{localequivgraph}
\bibliography{cliff_inv_graph_prl2}




\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

















Let us now investigate the structure of the sets ${\cal T}_{n,r}^{\gamma}(\psi)$ in more detail.
Consider e.g. the case of smallest nontrivial degree, i.e. $r=2$. %\footnote{If $r=1$ then there is
%only one invariant, namely Tr$(\rho)$, which is equal to 1 when evaluated in a normlized state.}.
There are two orbits in ${\cal O}_2$,
namely $\Gamma=\{(0,0;0,0)\}$ and \begin{eqnarray}\Gamma'&=&\{(0,0;1,1), (1,1;0,0), (1,1;1,1)\}\nonumber\\
&=& \{w\in \Bbb{F}_2^4| (w_1, w_3) = (w_2, w_4) \neq (0,0)\}.\nonumber\end{eqnarray} Let
$\gamma=(\Gamma_1, \dots, \Gamma_n)$ be an $n$-tuple  of orbits $\Gamma_i\in {\cal O}_2$ and let
$\omega$ be the subset of $\{1, \dots, n\}$ which consists of all $i$ such that $\Gamma_i =
\Gamma'$. It can easily be verified that any couple $(w^{1}, w^{2})\in \Bbb{F}_2^{2n}\times
\Bbb{F}_2^{2n}$ satisfies \be (w^{1}_i, w^{2}_i, w^{1}_{n+i}, w^{2}_{n+i})\in \Gamma_i\ee for every
$i=1, \dots, n$ if and only if $w^{1}=w^{2}=:w$ and supp$(w)= \omega$; here, the \emph{support}
supp$(v)$ of any vector $v\in \Bbb{F}_2^{2n}$ is the set \be\label{supp} \mbox{supp}(v) &=& \{i\in
\{1, \dots, n\}\ |\ (v_i,v_{n+i})\neq(0,0)\}\nonumber.\ee Note that supp$(v)$ contains exactly
those $i\in\{1, \dots, n\}$ such that the $i$th tensor factor of $\sigma_v$ differs from the
identity. Letting $\Psi$ be an $n$-qubit stabilizer state with generator matrix $S$, the above
leads to \be T_{n,2}^{\gamma}(\psi)= \{(w,w) \in S_{\psi}^{\times 2}\ |\ \mbox{ supp}(w)=\omega \}
\ee and therefore \be\label{suppinv} p_{n,2}^{\gamma}(\Psi)= |T_{n,2}^{\gamma}(\psi)| = |\{w \in
S_{\psi}\ |\ \mbox{ supp}(w)= \omega\}|.\ee This shows that every invariant
$p_{n,2}^{\gamma}(\Psi)$ of degree 2 simply counts the number of vectors in ${\cal S}$ with support
equal to the set $\omega$.

The above example relates invariants $p_{n,2}^{\gamma}(\Psi)$ to cardinalities of subsets of
$S_{\psi}$, where these subsets are defined through simple constraints on the supports of their
elements. This translation clearly adds to the insight in the structure of the invariants
$p_{n,2}^{\gamma}(\Psi)$. Interestingly, such a formulation in terms of supports can be obtained
for all degrees:

\begin{thm} Let $\Psi$ be an $n$-qubit stabilizer state. Let $r\in\Bbb{N}_0$
and let $\gamma=(\Gamma_1, \dots, \Gamma_n)\in{\cal O}_r^n$. Then there exist unique sets
$\omega^{j},\ \omega^{jk}\subseteq \{1, \dots, n\}$, where $j, k\in\{1,\dots, r\}$ and $j<k$, such
that ${\cal T}_{n,r}^{ \gamma}(\psi)$ consists of all $r$-tuples $(w^{1} ,\dots, w^{r})\in
S_{\psi}^{\times r}$  satisfying \be \mbox{ supp}(w^{j})=  \omega^{j},\ \mbox{\ supp}(w^{j}+
w^{k})= \omega^{jk}\ee
%\begin{eqnarray}
%&&\mbox{ supp}(w^{j})=  \omega^{j} \label{supps1}\\
%&&\mbox{\ supp}(w^{j}+ w^{k})= \omega^{jk},\label{supps2}
%\end{eqnarray}
for every $j, k$.
\end{thm}
{\it Proof:} This result immediately follows from (\cite{inv_cliff}, theorem 3). \hfill $\square$

Note that an explicit construction of the sets $\omega^{j},\ \omega^{jk}$ can be found in Ref.
\cite{inv_cliff}.


As a first result of this paper, we evaluate the polynomials $p_{n,r}^{\gamma}$ in an arbitrary
stabilizer state.

\begin{thm}  Let $\Psi=|\psi\rangle\langle\psi|$ be (the projector associated with) a stabilizer state on
 $n$ qubits. Let $r\in
\Bbb{N}_0$ and consider an $n$-tuple $\gamma=(\Gamma_1, \dots, \Gamma_n)\in {\cal O}_r^n$. Then $
p_{n,r}^{\gamma}(\Psi)$ is equal to the cardinality of the set
\begin{eqnarray}\label{theorem4}
&&{\cal T}_{n,r}^{ \gamma}(\psi):= \{ (w^{1},\dots, w^{r})\in\ S_{\psi}\times\dots\times\ S_{\psi}
|\quad
 \nonumber\\&&\mbox{\quad } (w^{1}_i,\ \dots,\ w^{r}_i, w^{1}_{n+i}\dots,w^{r}_{n+i})\in \Gamma_i
 \mbox{\ for every } i\}.\nonumber
\end{eqnarray}\end{thm}

{\it Proof}: Denoting by ${\cal S}(\psi)$ the stabilizer of the state $|\psi\rangle$, one has
\be\label{psi} \Psi = \frac{1}{2^n} \sum_{M\in {\cal S}(\psi)} M=\frac{1}{2^n}\sum_{w\in S_{\psi}}
\alpha_{w} \sigma_{w},\ee where $\alpha_{w}=\pm 1$ is for every $w\in S_{\psi}$ an overall phase
factor. Now, consider an $n$-tuple of orbits $\gamma=(\Gamma_1, \dots, \Gamma_n)\in {\cal O}_r^n$.
Using (\ref{psi}), the invariant $p_{n,r}^{ \gamma}(\Psi)$ is equal to
\begin{equation}\label{trace}
\frac{1}{2^{nr}} \sum\ \{\prod_{j=1}^r \alpha_{w^{j}}\}
 \mbox{ Tr}\left(A_{\gamma}\ \sigma_{w^{1}} \otimes
\dots\otimes  \sigma_{w^{r}}\right),
\end{equation}
where the sum is taken over all $(w^{1},\dots, w^{r})\in S_{\psi}^{\times r}$. Note that the trace
in (\ref{trace}) is equal to $2^{nr}$ if $(w^{1},\dots, w^{r})$ belongs to the set ${\cal
T}_{n,r}^{ \gamma}(\psi)$ and is equal to zero otherwise. Indeed, this simply follows from the
identity
\[\mbox{Tr} (\sigma_w\sigma_{w'}) = \left\{ \begin{array}{cc}2^r & \mbox{ if }  w=w'\\
0 &\mbox{ otherwise,}\end{array} \right.\] for every $w,w'\in \mathbb{F}_2^{2r}$. We now argue that
the product of phases $\prod_{j=1}^r \alpha_{w^{j}}$ is equal to 1 for every $(w^{1},\dots, w^{r})
\in {\cal T}_{n,r}^{ \gamma }(\psi)$; a proof of this assertion will complete the proof of the
theorem. Firstly, it follows from the definitions of ${\cal T}_{n,r}^{ \gamma }(\psi)$, ${\cal
O}_r$ and ${\cal V}_r$, that $\tilde w:= \sum_{j=1}^r w^{j} = 0$ for every $(w^{1},\dots, w^{r})
\in {\cal T}_{n,r}^{ \gamma }(\psi)$. We then apply the following trick: consider the stabilizer
generated by the $r$ operators $M_j:= \alpha_{w^{j}} \sigma_{w^{j}}$. It follows from $\tilde w=0$
that $\prod_{j=1}^r M_j = \alpha I_n$ for some phase factor $\alpha=\pm 1$. In fact, one must have
$\alpha=1$, since a stabilizer cannot contain the element $-I$ (see e.g. \cite{QCQI}), and we
conclude that
\begin{equation}\label{prod1}
\prod_{j=1}^r M_j =\prod_{j=1}^r \alpha_{w^{j}} \sigma_{w^{j}} = I,
\end{equation}
where $I$ is the identity matrix on $n$ qubits. The same argument can be applied to the stabilizer
generated by the $r$ operators $M_j':=\sigma_{w^{j}}$, yielding
\begin{equation}\label{prod2}
\prod_{j=1}^r M_j'=\prod_{j=1}^r \sigma_{w^{j}}  = I
\end{equation}
and the result $\prod_{j=1}^r \alpha_{w^{j}}=1$ follows from a comparison of (\ref{prod1}) and
(\ref{prod2}). This ends the proof. \hfill $\square$

This result shows that the invariants $p_{n,r}^{\gamma}(\Psi)$ correspond tot the cardinalities of
certain subsets of $S_{\psi}\times\dots\times S_{\psi}$ ($r$ times). Using theorem 1, we can now
pinpoint a finite set of invariants which characterizes the LC equivalence class of any stabilizer
state:

\begin{cor} The LC equivalence class of any  stabilizer state $\Psi$ on $n$ qubits is completely determined
by the invariants $p_{n,n+1}^{\gamma}(\Psi)$ of degree $n+1$.\end{cor}

{\it Proof}: Let $|\psi\rangle$, $|\psi'\rangle$ be two  stabilizer states on $n$ qubits such that
the the invariants $p_{n,n+1}^{\gamma}$ take on equal values on for both states. We will show that
this implies that $|\psi\rangle$ and $|\psi'\rangle$ are LC equivalent. Let $s^{1}, \dots, s^n
\in\mathbb{F}_2^{2n}$ be a basis of $S_{\psi}$. Defining $s^{n+1}:=\sum_{j=1}^n s^{j}$ and
 $S_k := (s^{1}_k,\ \dots,\ s^{n+1}_k)$ for every $k=1, \dots, 2n$, one has $(S_i, S_{n+i})\in {\cal V}_{n+1}$ %\be (s^{1}_i,\
%\dots,\ s^{n+1}_i, s^{1}_{n+i}\dots,s^{n+1}_{n+i})\in {\cal V}_{n+1}\ee
for every $i=1, \dots, n$ and therefore there exists a unique $n$-tuple $\gamma_*=(\Gamma_1, \dots,
\Gamma_n)\in{\cal O}_{n+1}^n$ such that
\begin{equation}\label{cor3}(s^{1}, \dots, s^{n+1})\in {\cal T}_{n,n+1}^{\gamma_*}(\psi).\end{equation}
This implies that $p_{n,n+1}^{\gamma_*}(\Psi)>0$. As $p_{n,n+1}^{\gamma_*}(\Psi) =
p_{n,n+1}^{\gamma_*}(\Psi')$ from our assumption, one has $p_{n,n+1}^{\gamma_*}(\Psi')= |{\cal
T}_{n,n+1}^{\gamma_*}(\psi')|>0$ and consequently there exists a $(n+1)$-tuple
\begin{equation}\label{cor3'}(t^{1}, \dots, t^{n+1})\in {\cal T}_{n,n+1}^{\gamma_*}(\psi').\end{equation}
Denoting $T_k := (t^{1}_k,\ \dots,\ t^{n+1}_k)$ for every $k=1, \dots, 2n$, it follows from
(\ref{cor3}) and (\ref{cor3'}) that the vectors $(S_i, S_{n+i})$  and $(T_i, T_{n+i})$ lie on the
same orbit $\Gamma_i$, for every $i=1, \dots, n$.
%\be\label{s}(s^{1}_i,\ \dots,\ s^{n+1}_i, s^{1}_{n+i}\dots,s^{n+1}_{n+i})\ee and
%\be\label{w}(t^{1}_i,\ \dots,\ t^{n+1}_i, t^{1}_{n+i}\dots,t^{n+1}_{n+i})\ee
This implies the existence of $n$ operators $Q_i\in GL(2, \Bbb{F}_2)$  such that $Q_i$ maps the
vector $(S_i, S_{n+i})$ %(\ref{s})
to $(T_i, T_{n+i})$
%(\ref{w})
according to the action (\ref{action}), for every $i=1, \dots, n$. Therefore, the matrices $Q_i$
constitute an operator $Q\in C_n^l$ such that $Qs^{j}= t^{j}$ for every $j=1, \dots, n$, which
yields \be Q S_{\psi}&=& \mbox{span}\{Qs^{1}, \dots, Qs^{n}\}\nonumber\\ &=& \mbox{ span}\{t^{1},
\dots, t^{n}\} \nonumber.\ee Moreover, the set $\{t^{1}, \dots, t^{n}\}$ is linearly independent,
being the image of a linearly independent set under an invertible linear transformation $Q$. It
follows that this set is a basis of $S_{\psi'}$ (since $S_{\psi'}$ is an $n$-dimensional vector
space) and we conclude that $Q S_{\psi} = S_{\psi'}$. This proves the lemma. \hfill $\square$



As mentioned above, we will study LC invariants of stabilizer states using a former result of ours,
which is a construction of a generating set of the invariant algebra of ${\cal C}_n^l$
\cite{inv_cliff}. To obtain this generating set, we adopted the standard approach of considering
homogeneous polynomial invariants degree by degree and constructing for every positive integer $r$
a basis of the space of invariants of degree $r$. %More explicitly, for every $r$ we considered the
%set of polynomials $F(\rho)$ of degree $r$, where $\rho=(\rho_{ij})$ is a $2^n\times 2^n$ matrix of
%variables $\rho_{ij}$, satisfying $F(U\rho U^{\dagger}) = F(\rho)$ for every $U\in {\cal C}_n^l$.
%Such a set of polynomials is, for fixed degree $r$, a complex vector space; therefore, a generating
%set of the entire invariant algebra is obtained by constructing bases of these spaces for each $r$.
The union of all such bases then yields an (infinite) generating set of the invariant algebra. We
will now repeat the details of this result. Let $r\in \mathbb{N}_0$ and let a matrix $R\in GL(2,
\Bbb{F}_2)$ act on $\Bbb{F}_2^{2r}$ by sending a vector
$u\in \Bbb{F}_2^{2r}$ to $u^R$, defined by \be\label{action}\left[\begin{array}{c} u^R_j\\
u^R_{r+j}
\end{array}\right]=R \left[\begin{array}{c} u_j\\ u_{r+j} \end{array}\right],\ee for every $j=1,
\dots, r$, where $u=(u_1, \dots, u_{2r})$. The orbit $\Gamma_u$ of $u$ under this action is the set
\be \Gamma_u= \{u^R\ |\ R\in GL(2, \Bbb{F}_2)\}.\ee Secondly, let the vector space ${\cal V}_r$
consist of all $u\in\Bbb{F}_2^{2r}$ such that $\sum_{j=1}^r u_j=\sum_{j=1}^r u_{r+j} = 0$ and
consider the set ${\cal O}_r$ of orbits $\Gamma_u$ of all vectors $u\in{\cal V}_r$. For every
$n$-tuple $\gamma=(\Gamma_1, \dots, \Gamma_n)$ of orbits $\Gamma_i\in{\cal O}_r$ we define a
$2^{nr}\times 2^{nr}$ complex matrix $ A_{\gamma}:=\sum\ \sigma_{w^{1}} \otimes\dots\otimes
\sigma_{w^{r}}, $ where the sum runs over all ordered $r$-tuples $(w^{1},\dots, w^{r})\in
(\Bbb{F}_2^{2n})^{\times r}$ such that \be(w_i^{1},\dots, w_i^{r},w_{n+i}^{1},\dots,
w_{n+i}^{r})\in \Gamma_i,\ee for every $i=1, \dots,n$. Finally, every matrix $A_{\gamma}$ defines a
homogeneous polynomial $p_{n,r}^{\gamma}$ of degree $r$ through \be\label{p_{n,r}}
p_{n,r}^{\gamma}(\rho):=\mbox{Tr }(A_{\gamma}\cdot \rho^{\otimes r}),\ee where $\rho=(\rho_{ij})$
is a $2^n\times 2^n$ matrix of variables $\rho_{ij}$. We proved that the polynomials
$\{p_{n,r}^{\gamma}\}_{\gamma}$ form a generating set of the vector space of invariants of ${\cal
C}_n^l$ of degree $r$. What is more, a method was presented of pinpointing a linearly independent
set of polynomials within the set $\{p_{n,r}^{\gamma}\}_{\gamma}$, yielding a basis of invariants
for every degree (the reader is referred to \cite{inv_cliff} for the details of this construction).
The union of all these bases yields a generating set of the invariant algebra of ${\cal C}_n^l$.

To illustrate this correspondence between LC and LU invariants of low degrees, let us again
consider the invariants of degree two. Recall that the invariants of the form \be A_{\omega}(S):=
|\{w \in S_{\psi}\ |\ \mbox{ supp}(w)= \omega\}|,\ee where $\omega\subseteq\{1, \dots, n\}$ form a
set of basic invariants of degree 2. Interesting variants of the functions $A_{\omega}$ are the
functions $B_{\omega}$, defined by \be B_{\omega}(S) = |\{w \in S_{\psi}\ |\ \mbox{
supp}(w)\subseteq \bar\omega\}|,\ee which are in fact the LU invariants of degree 2 which appeared
in \cite{invar_stab} (see also [Rains][hein]). The $A_{\omega}$'s and the $B_{\omega}$'s are
related through the following identities: \be\label{relations}
&&B_{\omega} = \sum_{\omega'\supseteq\omega} A_{\omega'}\nonumber\\
&&A_{\omega}=(-1)^{|\omega|}\sum_{\omega'\supseteq\omega}(-1)^{|\omega'|}\ B_{\omega'},\ee which
are easily verified. Note that the second identity in (\ref{relations}) shows that $A_{\omega}$
takes on equal values on LU equivalent stabilizers states. Moreover, (\ref{relations}) shows that,
for a given $S$, knowledge of the set of all numbers $A_{\omega}(S)$ implies knowledge of the set
of $B_{\omega}(S)$'s and vice versa; therefore, these two lists of invariants contain the same
information. Note that $B_{\omega}(S)$ is much more easily evaluated than $A_{\omega}(S)$. Indeed,
the set $\{w \in S_{\psi}\ |\ \mbox{ supp}(w)\subseteq \bar\omega\}$ is a linear subspace of
$S_{\psi}$, the cardinality of which can easily be calculated via a calculation of the rank over
$\mathbb{F}_2$ of the submatrix $S_{\omega} $ of $S$, defined as follows: letting $S_i^T$ denote
the $i$th row of $S$, for every $i=1, \dots, 2n$, the matrix $S_{\omega}$ is obtained by assembling
all rows $S_j$ with $j\in\omega$ or $j-n\in\omega$. It then easily follows that \be\log_2
B_{\omega}(S)=n - \mbox{ rank}_{\Bbb{F}_2} (S_{\omega}).\ee If $S=[\theta\ I]^T$ is the generator
matrix of a graph state $|G\rangle$ with adjacency matrix $\theta$, then $B_{\omega}(S)$ is a
function the rank of the off-diagonal submatrix $\theta_{\omega}:= (\theta_{ij})_{i\in\omega,
j\in\bar\omega}$ as follows: \be\log_2 B_{\omega}(S)=n - |\omega| -\mbox{ rank}_{\Bbb{F}_2}
(\theta_{\omega}).\ee For a fixed graph $G$ with adjacency matrix $\theta$, the function
\be\omega\subseteq\{1, \dots, n\}\mapsto \mbox{ rank}_{\Bbb{F}_2} (\theta_{\omega})\ee is known in
graph theory as the \emph{connectivity function} of $G$ []. It follows from the above that the
connectivity function of a graph contains all the information about its LC (and LU) invariants of
degree 2 of its associated graph state.

As for degree 3, a similar exercise can be done.

%For each $w\in \Bbb{F}_2^{2r}$, define the sets
%\begin{eqnarray}
%\eta_{0}(w)&=&\{j|\ (w_j, w_{n+j})=(0,0) \},\nonumber\\
%\eta_{x}(w)&=&\{j|\ (w_j, w_{n+j})=(0,1) \},\nonumber\\
%\eta_{y}(w)&=&\{j|\ (w_j, w_{n+j})=(1,1) \},\nonumber\\
%\eta_{z}(w)&=&\{j|\ (w_j, w_{n+j})=(1,0) \}.\nonumber
%\end{eqnarray}
%Then any orbit $\Gamma$ of the action (\ref{action}) can completely be described by
%\begin{itemize}
%\item[(a)] a set $\eta_{0}(\Gamma)\subseteq\{1, \dots, r\}$ and
%\item[(b)] a \emph{partition} ${\cal P}(\Gamma)=\{\eta_1, \eta_2, \eta_3\}$
%of $\{1, \dots, r\}\setminus\eta_{0}(\Gamma)$ into three (possibly empty) subsets,
%\end{itemize}
%such that $w\in \Gamma$ if and only if $\eta_{0}(w) = \eta_0(\Gamma)$ and $\{\eta_{x}(w),
%\eta_{y}(w), \eta_{z}(w)\}$ $= {\cal P}(\Gamma)$. Let $\Psi$ be an $n$-qubit stabilizer state with
%generator matrix $S$. Let $r\in\Bbb{N}_0$ and let $\gamma=(\Gamma_1, \dots, \Gamma_n)\in{\cal
%O}_r^n$. For every $j, k\in\{1,\dots, r\}$, $j<k$, define the sets $\omega^{(j)}$ and
%$\omega^{(jk)}$ by
%\begin{eqnarray}
%&\omega^{(j)}&= \{i\in \{1, \dots, n\}\ |\ j\in \eta_0(\Gamma_i)\}^c\label{omegas1}\nonumber\\
%&\omega^{(jk)} &= \{i\in \{1, \dots, n\}\ |\ j, k \in \eta_0(\Gamma_i)\mbox{ or j and k}\nonumber\\
%&&\mbox{\quad belong to the same  subset of } {\cal P}(\Gamma_i) \}^c,\label{omegas2}
%\end{eqnarray} where the superscript $^c$ denotes taking the complement in the set $\{1, \dots,
%n\}$. It then directly follows from (\cite{inv_cliff}, theorem 3) that ${\cal T}_{n,r}^{
%\gamma}(S)$ consists of all $r$-tuples $(w^{(1)} ,\dots, w^{(r)})\inS_{\psi}^{\times r}$
%satisfying (\ref{supps1})-(\ref{supps2}). This ends the proof.

As a second result, we will show how the invariants $I_{r, \gamma}(\rho_{\cal S})$ can be
characterized in an alternative way than in theorem 4. Let us first recall that the \emph{support}
supp$(M)$ of any $M=\alpha\ v_1 \otimes \dots \otimes v_n\in{\cal G}_n$ is defined by the subset of
those $i\in\{1,\dots,n\}$ such that $v_i\neq\sigma_0$ and that the support of a vector
$v\in\Bbb{F}_2^{2n}$ is defined in accordance with the binary description of the Pauli group, i.e.,
supp$(v)$ is the subset of those $i\in\{1,\dots,n\}$ such that $(v_i, v_{n+i})\neq (0,0)$. This
concept of \emph{support} of a codeword, and the directly related notion of \emph{weight}, which
will appear below when we deal with global invariants, is of central importance in coding theory,
as the error-correcting capabilities of a code is directly related to the weight distribution of
its codewords. We now show how the sets ${\cal T}_{r, \gamma}(S)$ can be described in terms of
supports. First, consider the case of smallest nontrivial degree, i.e. $r=2$. Then we are dealing
with the action of $GL(2, \Bbb{F}_2)$ on $\Bbb{F}_2^4$. In this case there are two orbits in ${\cal
O}_2$, namely
$\Gamma=\{(0,0;0,0)\}$ and \begin{eqnarray}\Gamma'&=&\{(0,0;1,1), (1,1;0,0), (1,1;1,1)\}\nonumber\\
&=& \{(u,v)\in \Bbb{F}_2^4| (u_1, v_1) = (u_2, v_2) \neq (0,0)\}.\nonumber\end{eqnarray} Now,
consider an $n$-tuple $\gamma=(\Gamma_1, \dots, \Gamma_n)$ of orbits $\Gamma_i\in {\cal O}_2$. Let
$\omega$ be the subset of $\{1, \dots, n\}$ which consists of all $i$ such that $\Gamma_i =
\Gamma'$ (note that every $\gamma$ corresponds uniquely to such a set). Therefore, the set ${\cal
T}_{2, \gamma}(S)$ consists of all couples $(y^{(1)}, y^{(2)})\in S_{\psi}\times S_{\psi}$
satisfying
 \begin{eqnarray}\label{degree2'}&(y^{(1)}_i, y^{(1)}_{n+i}) = ( y^{(2)}_{i}, y^{(2)}_{n+i})\neq (0, 0)& \mbox{ for every } i\in \omega\nonumber\\
&(y^{(1)}_j, y^{(1)}_{n+j}) = ( y^{(2)}_{j}, y^{(2)}_{n+j})= (0, 0)& \mbox{ for every }j\in\omega^c
,\nonumber
\end{eqnarray} where $\omega^c$ is the complement of $\omega$ in $\{1, \dots, n\}$. This
implies that $|{\cal T}_{2, \gamma}(S)| = I_{2, \gamma}(\rho_{\cal S})$ is equal to the cardinality
of the set
\[\{y\in S_{\psi}| \mbox{ supp}(y)= \omega \}.\]
As for general degree $r$, an analogous but more complex argument can be made. Let us first study
the structure of the orbits of the action of $GL(2, \Bbb{F}_2)$ on $\Bbb{F}_2^{2r}$ in more detail.
For each $(u,v)\in \Bbb{F}_2^{2r}$, define the sets
\begin{eqnarray}
\eta_{00}(u,v)&=&\{j|\ (u_j, v_j)=(0,0) \},\nonumber\\
\eta_{01}(u,v)&=&\{j|\ (u_j, v_j)=(0,1) \},\nonumber\\
\eta_{10}(u,v)&=&\{j|\ (u_j, v_j)=(1,0) \},\nonumber\\
\eta_{11}(u,v)&=&\{j|\ (u_j, v_j)=(1,1) \}.\nonumber
\end{eqnarray}
Then two vectors $(u,v)$, $(u',v')\in \Bbb{F}_2^{2r}$ belong to the same orbit if and only if
$\eta_{00}(u,v)=\eta_{00}(u',v')$ and there exists a permutation $\pi$ of $\{01, 10, 11\}$ such
that $\eta_{01}(u',v')=\eta_{\pi(01)}(u,v)$, $\eta_{10}(u',v')= \eta_{\pi(10)}(u,v),$ and $
\eta_{11}(u',v')= \eta_{\pi(11)}(u,v).$ This implies that any orbit $\Gamma$ can completely be
described by a set $\eta_{0}(\Gamma)$ and a \emph{partition} ${\cal P}(\Gamma) = \{\eta_1, \eta_2,
\eta_3\}$ of $\{1, \dots, r\}\setminus\eta_{00}$ into three subsets, such that $(u, v)\in \Gamma$
if and only if $\eta_{00}(u,v) = \eta_0(\Gamma)$ and
\begin{equation}
\{\eta_{01}(u,v), \eta_{10}(u,v), \eta_{11}(u,v)\} = {\cal P}(\Gamma)
\end{equation}
Furthermore, it will be convenient to consider, for every orbit $\Gamma$,  an equivalence relation
$\sim_{\Gamma}$ on the set $\{1, \dots, r\}$, defined by $j \sim_{\Gamma} k$ if $j$ and $k$ belong
to the same subset $\eta_a$, for some $a\in\{0, 1, 2, 3\}$.

Now, let $\gamma=(\Gamma_1, \dots, \Gamma_n)$ be an $n$-tuple of orbits $\Gamma_i\in {\cal O}_r$.
For every $j, k\in\{1,\dots, r\}$, $j<k$, define the sets $\omega^{(j)}$ and $\omega^{(jk)}$ by
\begin{eqnarray}
\omega^{(j)}&=& \{i\in \{1, \dots, n\}\ |\ j\in \eta_0(\Gamma_i)\}\nonumber\\
\omega^{(jk)} &=& \{i\in \{1, \dots, n\}\ |\ j\sim_{\Gamma_i} k\}.
\end{eqnarray}
We can then state the following result:

\textbf{Theorem 5} {\it Let $\rho_{\cal S}$ be a stabilizer code on $n$ qubits with generator
matrix $S$. Let $r\in \Bbb{N}$, $r\geq 2$, and consider an $n$-tuple $\gamma=(\Gamma_1, \dots,
\Gamma_n)$ of orbits $\Gamma_i\in {\cal O}_r$. For every $j, k\in\{1,\dots, r\}$, $j<k$, let the
sets $\omega^{(j)}$ and $\omega^{(jk)}$ be defined as before. Then $I_{r, \gamma}(\rho_{\cal S})$
is equal to the number of ordered $(r-1)$-tuples $(y^{(1)},\dots, y^{(r-1)})\in\ S_{\psi}^{\times
(r-1)}$ such that
\begin{eqnarray}\label{theorem5}
&&\mbox{ supp}(y^{(j)})= \omega^{(j)} \nonumber\\
&&\mbox{\ supp}(y^{(j)}+ y^{(k)})= \omega^{(jk)},
\end{eqnarray}
for every $j, k\in\{1,\dots, r-1\}$, $j<k$.}

{\it Proof:} It immediately follows from the definition of the sets $\omega^{(j)}$ and
$\omega^{(jk)}$ and the definition of the support of a codeword that the set ${\cal T}_{r,
\gamma}(S)$ consists of all $r$-tuples $(y^{(1)},\dots, y^{(r)})\in\ S_{\psi}^{\times r}$ such that
$\mbox{ supp}(y^{(j)})= \omega^{(j)}$ and  $\mbox{supp}(y^{(j)}+ y^{(k)})= \omega^{(jk)}$, for
every $j, k\in\{1,\dots, r\}$, $j<k$.  Moreover, $y^{(1)}+\dots+ y^{(r)}=0$ for all of these
tuples, and therefore the vector $y^{(r)}$ is completely determined by the $(r-1)$-tuple
$(y^{(1)},\dots, y^{(r-1)})$.  Consequently, it is unnecessary to consider this vector  in order to
calculate the cardinality of ${\cal T}_{r, \gamma}(S)$. This proves the result. \hfill $\square$






%\subsection{Generalized weights and global invariants}

\section{Discussion}
%mogelijk minder dan graad k+1
%algoritmes
%self-dual codes (link met vorige werk, algoritme, link met 1way QC en entanglement)
%local clifford versus local unitary


In this section, we present an extensive discussion of the results gathered in section IV.

We have shown that the polynomials $\{I_{k+1, \gamma}\}_{\gamma}$ of degree $k+1$ form a finite set
of ${\cal O}( 4^{nk})$ local invariants which separate the orbits of the set of $[n,k]$ stabilizer
codes, i.e., the local Clifford equivalence class of any $[n,k]$ code is completely determined by
the values of these invariants. In order to obtain a complete set of \emph{global invariants} from
the local Clifford invariants $I_{r, \gamma}(\rho_{\cal S}) = |{\cal T}_{r, \gamma}(S)|$, it is
sufficient to average every local invariant over all possible permutations of the qubits. We then
obtain a global invariant as follows:
\begin{equation}\label{global}\sum_{\Pi} |{\cal T}_{r, \gamma}(\bar\Pi S)|,\end{equation} where the
sum is taken over all $n\times n$ permutation matrices $\Pi$ and $\bar\Pi$ is defined as in
(\ref{pi}). Such a global invariant is specified by a set of $m\leq n$ orbits $\Gamma_1, \dots,
\Gamma_m \in {\cal O}_r$ and a set of strictly positive integers $a_1, \dots, a_m$ satisfying
$\sum_{i=1}^m a_i = n$, and the invariant counts the number of $r$-tuples $(y^{(1)},\dots,
y^{(r)})\in S_{\psi}^{\times r}$ such that \[\left|\{i| (y^{(1)}_i, \dots, y^{(r)}_i,
y^{(1)}_{n+i}\dots,y^{(r)}_{n+i})\in \Gamma_i\}\right| = a_i,\] for every $i=1, \dots, m$.
Considering e.g. the case $r=2$, we find that the set of invariants (\ref{global}) constitutes the
weight distribution of the code $\rho_{\cal S}$, i.e., each invariant counts the number of
codewords $y\in S_{\psi}$ such that the weight of $y$ is equal to $d$, for some $d=0, \dots, n$.
This most easily follows from the discussion below corollary 3. The global invariants of arbitrary
degree are generalized notions of 'weight'.

The argument made in corollary 3 suggests an algorithmic way of deciding whether two given
stabilizer codes are locally equivalent. Suppose that two $[n, k]$ codes $\rho_{\cal S}$ and
$\rho_{{\cal S}'}$  with generator matrices $S$ and $S'$, respectively, are given. In order to
detect local Clifford equivalence of these codes, one can proceed as follows: denoting by $s^{(j)}$
the $j$th column of $S$, for every $j=1, \dots, k$, and defining $s^{(k+1)}:=\sum_{j=1}^k s^{(j)}$,
determine the unique $n$-tuple $\gamma_*=(\Gamma_1, \dots, \Gamma_n)$ of orbits $\Gamma_i\in {\cal
O}_{k+1}$ such that
\begin{equation}(s^{(1)}, \dots, s^{(k+1)})\in {\cal T}_{k+1, \gamma_*}(S).\end{equation}
Then calculate $I_{r, \gamma*}(\rho_{{\cal S}'})$; it follows that the codes are locally equivalent
under the Clifford group if and only if $I_{r, \gamma}(\rho_{{\cal S}'})$ is nonzero. While this
approach is straightforward to implement, the last step in the algorithm - i.e., determining
whether $I_{r, \gamma}(\rho_{{\cal S}'})$ is nonzero - may be computationally hard. However, note
that for \emph{self-dual} codes, which are the class of $[n, n]$ codes for arbitrary $n$, there
does exist an efficient algorithm to detect local Clifford equivalence (based on a different
approach) []. Therefore, it not impossible that fast algorithmic ways to determine local Clifford
equivalence of general codes exist,(al dan niet) based on the invariant based approach suggested
above.

Finally, we wish to point out the following unsolved problem: suppose two (locally) equivalent
stabilizer codes are given, where the definition of equivalence is to be taken in the general sense
(i.e., considering the entire local unitary group and not merely the local Clifford group). Are
these codes that necessarily (locally) equivalent under the Clifford group?

\section{Conclusion}

We have investigated the global and local equivalence of stabilizer codes. First, we have
considered the invariants of the local Clifford group in detail and, as a result, we derived for
each degree a generating set of homogenous invariants. We then studied these invariants with
respect to the stabilizer formalism, and proved that the Clifford equivalence class of any $[n, k]$
code is completely determined by the values of the invariants of degree $k+1$. We finally presented
a translation of the invariants into the binary description of the stabilizer formalism.




















The Pauli group ${\cal G}_n$ on $n$ qubits consists of all $4\times 4^n$ $n$-fold tensor products
of the form $\alpha\ v_1 \otimes v_2\otimes \dots \otimes v_n$, where $\alpha \in \{ \pm 1, \pm
i\}$ is an overall phase factor and the $2 \times 2$-matrices $v_i$ $(i=1,\dots, n)$ are either the
identity $\sigma_0$ or one of the Pauli matrices \[ \sigma_x= \left(
\begin{array}{cc}0 & 1\\1 & 0 \end{array}\right),\ \sigma_y = \left(
\begin{array}{cc}0 & -i\\i & 0 \end{array}\right),\ \sigma_z=\left(
\begin{array}{cc}1 & 0\\0 & -1 \end{array}\right).  \]

An $n$-qubit stabilizer ${\cal S}$ in the Pauli group is an abelian subgroup of ${\cal G}_n$ which
does not contain $-I_n$ or $\pm i I_n$, where $I_n$ is the $2^n\times 2^n$ identity matrix.
Equivalently, ${\cal S}$ is generated by $k\leq n$ commuting, independent and Hermitian observables
$M_i \in {\cal G}_n$ ($i=1, \dots, k$). Here "independent" means that no product of the form
$M_1^{x_1}\dots M_k^{x_k}$, where $x_i \in \{0,1\}$, yields the identity except when all $x_i$ are
equal to zero. The $[n, k]$ stabilizer code associated with ${\cal S}$ is the joint eigenspace
belonging to eigenvalue one of the $2^k$ operators $M\in {\cal S}$. There is a one-to-one
correspondence between the code associated with ${\cal S}$ and the matrix
\begin{equation}\label{rho_S}\rho_{\cal S}=\frac{1}{2^n}\sum_{M\in {\cal S}}M,\end{equation} as this operator is (up to a
multiplicative constant) the projection operator which projects on the code space. Note that the
normalization is chosen such as to yield Tr$(\rho_{\cal S})=1$.

It is well known that the stabilizer formalism has an equivalent formulation in terms of binary
linear algebra (for literature on this subject, see e.g. \cite{Gott, QCQI}). Employing the mapping
\begin{eqnarray}
\sigma_0=\sigma_{00} &\mapsto& (0,0)\nonumber\\
\sigma_x=\sigma_{01} &\mapsto& (0,1)\nonumber\\
\sigma_z=\sigma_{10} &\mapsto& (1,0)\nonumber\\
\sigma_y=\sigma_{11} &\mapsto& (1,1),
\end{eqnarray}
the elements of ${\cal G}_n$ can be represented as $2n$-dimensional binary vectors as follows:
\[\sigma_{u_1v_1}\otimes\dots\otimes\sigma_{u_nv_n}=\sigma_{(u,v)} \mapsto  (u,v) \in \Bbb{F}_2^{2n},\]
where $(u,v)=(u_1, \dots, u_n, v_1, \dots,v_n)$. This parameterization establishes a group
homomorphism between ${\cal G}_n, \cdot$ and $\Bbb{F}_2^{2n},+$ (which disregards the overall
phases of Pauli operators). In this binary representation, two Pauli operators $\sigma_a$ and
$\sigma_b$, where $a, b \in \Bbb{F}_2^{2n}$, commute if and only if $a^T P b = 0$, where the
$2n\times 2n$ matrix
\[P = \left[
\begin{array}{cc} 0 & I \\ I& 0 \end{array} \right]\]
 defines a symplectic inner product on $\Bbb{F}_2^{2n}$. Therefore, an $[n,k]$ stabilizer code corresponds to a $k$-dimensional linear subspace of $\Bbb{F}_2^{2n}$ which is
self-orthogonal with respect to this symplectic inner product, i.e., $a^T P b = 0$ for every $a, b$
in this subspace. Given a set of generators of the stabilizer, we assemble their binary
representations as the columns of a full rank $2n\times k$ matrix $S$, which is referred to as a
generator matrix of the stabilizer subspace. This generator matrix satisfies $S^TPS=0$ from the
symplectic self-orthogonality property. The entire binary stabilizer subspace (or \emph{code
space}) $S_{\psi}$ is the column space of $S$.




The Clifford group ${\cal C}_1$ on one qubit is the normalizer of ${\cal G}_1$ in $U(2)$, i.e. it
is the subgroup of $2\times 2$ unitary operators which map ${\cal G}_1$ to itself under
conjugation. The local Clifford group ${\cal C}_n^l:={\cal C}_1^{\otimes n}$ on $n$ qubits is the
$n$-fold tensor product of ${\cal C}_1$ with itself. When disregarding the overall phases of the
elements in ${\cal G}_1$, it is easy to see there exists a one-to-one correspondence between the
one-qubit Clifford operations and the 6 possible invertible linear transformations of
$\Bbb{F}_2^{2}$, since each one-qubit Clifford operator performs one of the 6 possible permutations
of the Pauli matrices and leaves the identity fixed.  Generalizing to $n$-qubit local Clifford
operations, it follows that each $U\in {\cal C}_n^l$ corresponds to a $2n\times 2n$ binary matrix
$Q $ of the block form
\[Q = \left [ \begin{array}{cc} A&B\\
C&D \end{array}\right],\] where the $n\times n$ matrices $A, B, C, D$ are diagonal. We denote the
diagonal entries of $A, B, C, D$, respectively, by
 $a_i$, $b_i$, $c_i$, $d_i$, respectively. The $n$ submatrices \[Q^{(i)}:=\left [
\begin{array}{cc} a_i & b_i
\\ c_i& d_i\end{array} \right ]\in GL(2, \Bbb{F}_2)\] correspond to the tensor factors of $U$.
The set $C^l_n$ of all such $Q$ is a matrix group isomorphic to $GL(2, \Bbb{F}_2)^{\oplus n}$.



Two stabilizer codes $\rho_{\cal S}$, $\rho_{{\cal S}'}$ are called (globally) equivalent under the
Clifford group if there exists an operator $U\in {\cal C}_n^l$ such that $U\rho_{\cal S}
U^{\dagger}$ is equal to $\rho_{{\cal S}'}$ up to a permutation of the $n$ qubits. The codes are
called locally equivalent under the Clifford group if $U\rho_{\cal S} U^{\dagger}=\rho_{{\cal
S}'}$, without any additional permutation. Denoting the generator matrices of $\rho_{\cal S}$ and
$\rho_{{\cal S}'}$ by $S$ and $S'$, respectively, one easily verifies that local Clifford
equivalence occurs if and only if there exists $Q\in C^l_n$ such that
\begin{equation}\label{QSR1}
{\cal C}_{QS} = {\cal C}_{S'}.
\end{equation} To see this, simply note that $U\rho_{\cal S}U^{\dagger}=\rho_{{\cal S}'}$
for some $U\in {\cal C}_n^l$ if and only $U{\cal S}U^{\dagger}={\cal S}'$. Global Clifford
equivalence occurs whenever there exists an $n\times n$ permutation matrix $\Pi$ such that ${\cal
C}_{ (\bar\Pi Q) S} = {\cal C}_{S'}$,
where the $2n\times 2n$ matrix $\bar \Pi$ is defined as \begin{equation}\label{pi}\bar\Pi = \left [ \begin{array}{cc} \Pi&0\\
0&\Pi \end{array}\right].\end{equation}





















\section{The invariants of the local Clifford group}

Let $\rho$ be an arbitrary $2^n\times 2^n$ matrix. In this section, we study the algebra of
polynomial functions $F(\rho)= F(\rho_{11}, \rho_{12}, \dots, \rho_{2^n2^n})$, in the coefficients
$\rho_{ij}$, which remain invariant under the substitutions $\rho\to U\rho U^{\dagger}$, for every
$U\in {\cal C}_n^l$. Note that it is sufficient to consider homogeneous polynomials in order to
obtain a generating set of this algebra, since each invariant polynomial can be written as a sum of
its homogeneous components, each of which is an invariant as well.  Any homogeneous polynomial
$F(\rho)$ of degree $r$ can be written as a trace
\[F(\rho)=\mbox{Tr }(A_F\cdot \rho^{\otimes r})\] for some $2^{nr}\times 2^{nr}$ matrix $A_F$. To see this, simply note
that the tensor product $\rho^{\otimes r}$ contains all monomials of degree $r$ in the entries
$\rho_{ij}$.  The coefficients of these monomials in the polynomial $F$ are encoded in the entries
of $A_F$. Note, however, that the correspondence $F \leftrightarrow A_F$ is not one-to-one. It can
easily be verified that $F(\rho)$ is an invariant of ${\cal C}_n^l$ if and only if there exists an
$A_F$ such that
\begin{equation}\label{F}
U^{\otimes r}A_F (U^{\otimes r})^{\dagger} =A_F
\end{equation} for every $U\in {\cal C}_n^l$. Therefore, the study of invariant homogeneous
polynomials of fixed degree $r$ is transformed to the study of the algebra ${\cal A}_{r}^{(n)}$ of
matrices $A_F$ which satisfy (\ref{F}). Our goal is to construct a basis of matrices which linearly
generates this algebra. This will yield a generating set of homogeneous invariants of degree $r$
\footnote{This set will however not be linearly independent in general, due to fact that the
description of an invariant $F(\rho)$ by a trace $\mbox{Tr }(A_F\cdot \rho^{\otimes r})$ is
non-unique.}. First we consider the simplest case of one single qubit, i.e. $n=1$, and then we move
to the general case of arbitrary $n$.

\subsection{One qubit}

Let $r\in \Bbb{N}_0$ and let ${\cal R}_r$ be the averaging operator which maps a $2^r\times 2^r$
matrix  $A$ to
\[{\cal R}_r(A) := \frac{1}{|{\cal C}_1|}\sum_{U\in {\cal C}_1} U^{\otimes r}A (U^{\otimes
r})^{\dagger}.\] Note that that ${\cal R}_r$ is the orthogonal projector onto the subspace ${\cal
A}_r^{(1)}$. Therefore, a spanning (though in general nonminimal) set of ${\cal A}_r^{(1)}$ is
obtained by fixing a vector space basis of the set of $2^r\times 2^r$ matrices and calculating its
image under ${\cal R}_r$. In this context, a natural choice for such a basis is the set
$\{\sigma_{(u, v)}|\ u,v\in \Bbb{F}_2^r\}$ of $r$-qubit Pauli operators. We calculate the images
${\cal R}_r\left(\sigma_{(u,v)}\right)$ in lemma 1.

\textbf{Lemma 1} {\it Let $Q\in GL(2, \Bbb{F}_2)$ act on $\Bbb{F}_2^{2r}$ by sending
a vector $(u, v)$, where $u, v\in \Bbb{F}_2^{r}$, to $(\bar u, \bar v)$, defined by \[\left[\begin{array}{c}\bar u_j\\
\bar v_j
\end{array}\right]=Q \left[\begin{array}{c} u_j\\ v_j \end{array}\right],\] for every $j=1,
\dots, r$, where $u_j, v_j,\bar u_j,\bar v_j$, respectively, are the components of $u, v,\bar
u,\bar v$, respectively. Let the vector space ${\cal V}_r$ consist of all $(u, v)\in\Bbb{F}_2^{2r}$
such that
\[\sum_{j=1}^r (u_j,v_j) = (0,0).\] Fix a vector $(u_0,v_0)\in\Bbb{F}_2^{2r}$ and let
$\Gamma$ denote its orbit under the above action. Then
\[{\cal
R}_r\left(\sigma_{(u_0,v_0)}\right)=
\left\{ \begin{array}{cc}\lambda \sum_{(u, v)\in \Gamma} \sigma_{(u, v)} & \mbox{ if }  (u_0,v_0)\in {\cal V}_r\\
0 &\mbox{ otherwise,}\end{array} \right. \] where $\lambda$ is a constant.}

{\it Proof:} First, for arbitrary $(u, v)\in \Bbb{F}_2^{2r}$, define the integers $n_x(u, v),
n_y(u,v), n_z(u, v)$ by
\begin{eqnarray}
n_x(u, v)&=&|\{j|\ (u_j,v_j)=(0,1) \}|,\nonumber\\
n_y(u, v)&=&|\{j|\ (u_j,v_j)=(1,1) \}|,\nonumber\\
n_z(u, v)&=&|\{j|\ (u_j,v_j)=(1,0) \}|.\nonumber
\end{eqnarray}
Secondly, let $U\in {\cal C}_1$ be an arbitrary Clifford operation. Then there exists coefficients
$\alpha_{ab}=\pm 1$ and an operator  $Q\in GL(2, \Bbb{F}_2)$ such that
$U\sigma_{(a,b)}U^{\dagger}=\alpha_{ab}\sigma_{Q(a,b)}$ for every $(a,b)\in\{(0,1), (1,0),
(1,1)\}$. Moreover, since $\sigma_{(0,1)}\sigma_{(1,0)}\sim\sigma_{(1,1)}$, the identity
$\alpha_{01}\alpha_{10}\alpha_{11}=1$ holds. Now, fix $(u_0, v_0) \in \Bbb{F}_2^{2r}$ and let
$\Gamma$ denote its orbit under the action of $GL(2, \Bbb{F}_2)$. Then $U^{\otimes r}$ maps
$\sigma_{(u_0,v_0)}$ to
\begin{eqnarray}
&&\alpha_{01}^{n_x}\alpha_{10}^{n_z}\alpha_{11}^{n_y}\ \sigma_{(\bar u_0,\bar v_0)}=
\alpha_{01}^{n_x+n_y}\alpha_{10}^{n_z + n_y}\ \sigma_{(\bar u_0,\bar v_0)}
\end{eqnarray}
under conjugation, where we have used the notation $n_x:= n_x(u_0, v_0)$ etc. and where $(\bar u_0,
\bar v_0)\in \Gamma$ is the image of $(u_0,v_0)$ under the action of $Q$ (cfr. definition above).
The crucial observation is now that the coefficient of $\sigma_{(\bar u_0,\bar v_0)}$ is always
positive (and thus equal to 1) if and only if both the numbers $n_x+n_y$ and $n_z+n_y $ are even.
Note that this occurs if and only if $n_x, n_y $ and $n_z$ are all even or all odd or,
equivalently, if and only if $(u_0,v_0)\in {\cal V}_r$, as one can readily verify. Therefore, we
have
\[{\cal R}_r\left(\sigma_{(u_0,v_0)}\right)= \sum_{(u, v)\in \Gamma} \lambda_{(u, v)}\sigma_{(u,
v)},\] for some coefficients $\lambda_{(u, v)}\in \Bbb{R}$, which are all strictly positive if and
only if $(u_0,v_0)\in {\cal V}_r$. Moreover, $\lambda_{(u, v)} =\lambda_{(u', v')}\equiv \lambda$
for every $(u, v), (u',v')\in \Gamma$. This follows from the property that ${\cal
R}_r\left(\sigma_{(u_0,v_0)}\right)$ must remain invariant under conjugation by every operator
$U^{\otimes r}$. If $(u_0,v_0)\notin {\cal V}_r$, one can easily see that the different terms in
the sum ${\cal R}_r\left(\sigma_{(u_0,v_0)}\right)$ interfere such as to yield zero. This ends the
proof. \hfill $\square$

Using the result in lemma 1, we can now construct a basis of ${\cal A}_r^{(1)}$:
%\textbf{Definition 1} {\it Let the action of $GL(2, \Bbb{F}_2)$ on $\Bbb{F}_2^{2r}$ and the vector
%space ${\cal V}_r$ be defined as in lemma 1. We denote by ${\cal O}_r$ the set of all orbits
%$\Gamma$ of the elements in ${\cal V}_r$. Note that $\Gamma\subseteq {\cal V}_r$ for every
%$\Gamma\in {\cal O}_r$.}

\textbf{Theorem 1} {\it Let $r\in \Bbb{N}$ and $r\geq 2$. Let the action of $GL(2, \Bbb{F}_2)$ on
$\Bbb{F}_2^{2r}$ and the vector space ${\cal V}_r$ be defined as in lemma 1. Denote by ${\cal O}_r$
the set of all orbits $\Gamma$ of the elements in ${\cal V}_r$ (note that ${\cal O}_r$ forms a
partition of ${\cal V}_r$).
%Note that $\Gamma\subseteq {\calV}_r$ for every $\Gamma\in {\cal O}_r$.
For every $\Gamma\in {\cal O}_r$, define the matrix
\[A_{\Gamma}:= \sum_{(u, v)\in \Gamma} \sigma_{(u, v)}.\] Then the set $\{A_{\Gamma}\}_{\Gamma\in
{\cal O}_r}$ is a vector space basis of ${\cal A}_r^{(1)}$. The dimension $|{\cal O}_r|$ of ${\cal
A}_r^{(1)}$ is equal to \begin{equation}\label{dim}\frac{1}{3}(2^{2r-3} + 3\cdot 2^{r-2} +
1).\end{equation}}

{\it Proof:} It follows  from the result in lemma 1 and the argumentation above lemma 1 that the
matrices $A_{\Gamma}$ linearly generate the algebra ${\cal A}_{ r}^{(1)}$. The linear independence
of the $A_{\Gamma}$'s is implied the linear independence of the Pauli operators. Therefore, we can
conclude that the $A_{\Gamma}$'s are indeed a basis of ${\cal A}_{ r}^{(1)}$. In order to calculate
the dimension $|{\cal O}_r|$ of ${\cal A}_{r}^{(1)}$, we use the Cauchy-Frobenius orbit-counting
lemma [], which states that the number of orbits of a finite group $G$ acting on a set $X$ is equal
to the average number of fixed points, i.e., the number of orbits is equal to
\begin{equation}\label{fix}\frac{1}{|G|} \sum_{g\in G} |\mbox{Fix}(g)|,\end{equation} where $|\mbox{Fix}(g)|$ is the number
of fixed points in the set $X$ of the group element $g$. Let us therefore calculate the number of
fixed points of an arbitrary matrix $Q\in GL(2, \Bbb{F}_2)$ acting on ${\cal V}_r$. Firstly, it is
trivial that the identity has $|{\cal V}_r|=4^{r-1}$ fixed points.  Secondly, there are three
elements in $GL(2, \Bbb{F}_2)$ of order two. Consider e.g. the matrix \[ Q_0=\left[
\begin{array}{cc}0 & 1\\1 & 0 \end{array}\right].\] When acting on $\Bbb{F}_2^2$, this operator fixes exactly two
vectors, namely (0,0) and (1,1). Therefore, when $Q_0$ acts on ${\cal V}_r$, the set Fix$(Q_0)$
consists of all vectors of the form \begin{eqnarray} \alpha_1 (1, 0,\dots, 0;\ 1, 0, \dots,0)\ +\
\alpha_2(0, 1,\dots, 0;\ 0, 1, \dots,0)  \nonumber\\+\ \dots\ +\  \alpha_r (0, 0,\dots 1;\ 0, 0,
\dots,1), \mbox{\qquad}
\end{eqnarray}
where $\alpha_i\in \{0,1\}$ for every $i=1, \dots, r$ and where exactly an even number of
$\alpha_i$'s are nonzero. Therefore, the cardinality of $\mbox{Fix}(Q_0)$ is equal to the number of
even subsets of $\{1, \dots, r\}$, i.e. $|\mbox{Fix}(Q_0)|=2^{r-1}$. Note that an analogous
argument holds for the other two matrices of order two. Finally, there are two elements in $GL(2,
\Bbb{F}_2)$ of order three, which fix only the zero vector. Gathering these results in the formula
(\ref{fix}), we find that the number $|{\cal O}_r|$ of orbits  is equal to \[\frac{1}{6}(4^{r-1} +
3\cdot 2^{r-1} + 2),\] which yields the result. \hfill $\square$


\textbf{Corollary 1} {\it The polynomials $\mbox{Tr }(A_{\Gamma}\cdot \rho^{\otimes r}),$ in the
variables $\rho_{ij}$ (i, j = 1, 2), where $\Gamma$ ranges over all orbits in ${\cal O}_r$,
linearly generate the space of homogeneous invariants of ${\cal C}_1$ of degree $r$.}

\subsection{Multiple qubits}

As for arbitrary $n$, the above results can immediately be used to construct a basis of ${\cal
A}_{r}^{(n)}$. To see this, let us first consider the algebra of $2^{nr}\times 2^{nr}$ matrices $A$
which satisfy \[U_1^{\otimes r}\otimes\dots\otimes U_n^{\otimes r} A (U_1^{\otimes
r}\otimes\dots\otimes U_n^{\otimes r})^{\dagger} = A,\] for every $U_1, \dots, U_n\in {\cal
C}_n^l$. It is straightforward to show that this algebra is the $n$-fold tensor product of ${\cal
A}_{r}^{(1)}$ with itself. Therefore, a basis of this algebra is given by the matrices
$A_{\Gamma_1}\otimes\dots\otimes A_{\Gamma_n}$, where $\Gamma_i$ ranges over all orbits in ${\cal O
}_r$, for every $i=1, \dots, n$. In order to obtain a basis of ${\cal A}_{ r}^{(n)}$, one simply
needs to conjugate this basis with the permutation matrix $P$, defined by
\begin{eqnarray}&&P\ | i_{11}\dots i_{1r}; i_{21}\dots i_{2r};\dots; i_{n1}\dots i_{nr}\rangle
\nonumber\\ & & = | i_{11}\dots i_{n1}; i_{12}\dots i_{n2};\dots; i_{1r}\dots
i_{nr}\rangle,\end{eqnarray} since this matrix performs the appropriate permutation of tensor
factors, mapping $U_1^{\otimes r}\otimes\dots\otimes U_n^{\otimes r}$ to $(U_1\otimes\dots\otimes
U_n)^{\otimes r}$ under conjugation. We therefore arrive at the following theorem:

\textbf{Theorem 3} {\it Let $r\in \Bbb{N}$ and $r\geq 2$. For every $n$-tuple $\gamma=(\Gamma_1,
\dots, \Gamma_n)$ of orbits $\Gamma_i\in {\cal O}_r$, define the matrix \[A_{\gamma}:= P
A_{\Gamma_1}\otimes\dots\otimes A_{\Gamma_n}P^T.\] Then the set $\{ A_{\gamma}\}_{\gamma}$, where
$\gamma$ ranges over all $n$-tuples of orbits, forms a vector space basis of ${\cal A}_{ r}^{(n)}$.
The dimension of ${\cal A}_{n, r}$ is equal to $|{\cal O}_r|^n$.}

\textbf{Corollary 2} {\it The polynomials $I_{r, \gamma}$, defined by
\begin{equation}\label{inv}
I_{r, \gamma}(\rho):= \mbox{ Tr }(A_{\gamma} \cdot \rho^{\otimes r}),
\end{equation}
where $\rho\in M_{2^n}(\Bbb{C})$, linearly generate the space of homogeneous invariants of degree
$r$ of the local Clifford group ${\cal C}_n^l$.}








The theory of quantum error-correcting codes constitutes a vital ingredient in the realization of
quantum computing, as these codes protect the vulnerable information stored in a quantum computer
from the destructive effects of decoherence. The most widely known class of error-correcting codes
is that of the stabilizer codes, studied extensively in e.g. \cite{Gott,codeGF4, QCQI}. An
$n$-qubit stabilizer code is defined as a simultaneous eigenspace of a set of commuting observables
in the Pauli group, where the latter consists of all $n$-fold tensor products of the Pauli matrices
and the identity. Equivalently, a code is described by the projector operator on this eigenspace.
In the characterization of the the error-correcting capabilities of quantum codes, two equivalence
relations arise naturally on the set of corresponding projectors: two $n$-qubit quantum codes
described by projectors $\rho$ and $\rho'$ are called \emph{globally equivalent}, or just
\emph{equivalent}, if there exists a local unitary operator $U\in U(2)^{\otimes n}$ such that
$U\rho U^{\dagger}$ is equal to $\rho'$ modulo a permutation of the $n$ qubits. If $U\rho
U^{\dagger}=\rho'$, without any additional permutation, the codes are called \emph{locally
equivalent}. As globally equivalent codes have exactly the same error-correcting capabilities and
vice versa, global equivalence is in fact the true equivalence of quantum codes. However, the
structure of local equivalence is more transparent and insight in this matter already provides a
lot of information about the structure of quantum codes. Therefore, much of the relevant literature
tackles local equivalence and we will do the same in the following.

This paper is concerned with the characterization of the local equivalence class of a stabilizer
code $\rho$ by means of local \emph{invariants}. These are complex functions $F(\rho)$ which remain
invariant under the action of all local unitary transformations, i.e., \[F(\rho)=F(U\rho
U^{\dagger})\] for every $U\in U(2)^{\otimes n}$. In studying invariants, the general goal is to
look for a minimal set of invariants which characterizes the local equivalence class of any given
code. To obtain such a minimal complete set, it is well known \cite{pol_inv_suff} that it is
sufficient to consider functions $F$ which are polynomials in the entries of $\rho$.  These
polynomial invariants form an algebra over $\Bbb{C}$, as linear combinations and products of
invariants remain invariants. Interestingly, the invariant algebra of $U(2)^{\otimes n}$ is
finitely generated \cite{finit_gen} and therefore the existence of a \emph{finite} complete set of
polynomial invariants is guaranteed. Although the problem of pinpointing such a finite set is to
date unanswered, progress has been made in the past years in constructing complete though infinite
families of invariants. A natural approach is to consider homogeneous invariants, since any
invariant can be written as a sum of its homogeneous components, each of which needs to be an
invariant as well.  As the set of homogeneous invariants of fixed degree has the structure of a
vector space, one wishes to construct a basis of this vector space degree per degree in order to
obtain a generating (yet infinite) set of the invariant algebra. Grassl et al. \cite{invarqubit}
achieve this goal, using earlier work of Rains \cite{RainsPol}. Their study of local invariants is
general in the sense that is does not merely regard (projectors associated with) quantum codes, but
in fact arbitrary $n$-qubit density operators $\rho$. Closer inspection of their basic invariants
when dealing with stabilizer codes is certainly appropriate, given the very specific structure of
these codes and their associated projectors. Indeed, the stabilizer formalism has an equivalent
formulation in terms of algebra over GF(2) and in this framework any stabilizer code of length $n$
and dimension $k$ is essentially described by an $2n\times k$ binary matrix, called the generator
matrix of the code. It is therefore natural to ask what the structure of the basic invariants is in
relation to this binary description. In the present paper we resolve this issue: it is shown that
the invariants of Grassl et al. are in a one-to-one correspondence with the dimensions of certain
linear subspaces over GF(2) which depend solely on the binary matrix description of a code. Hence,
a complete translation of the invariants into the binary stabilizer framework is obtained.

We wish to point out that the relevance of this investigation stretches beyond the domain of
quantum coding theory: stabilizer codes with rank one projectors correspond to the class of pure
states generally known as stabilizer states.  The problem of recognizing local unitary equivalence
of stabilizer states is of importance in the study of multipartite entanglement
\cite{entgraphstate, localcliffgraph} and in the development of the one-way quantum computer, a
measurement-based model of quantum computation which uses a stabilizer state as a universal
resource \cite{1wayQC}.

It is appropriate to point out the relevance of self-dual codes. The code space of a self-dual code
is one-dimensional or, equivalently, $\rho_{\cal S}= |\psi\rangle\langle\psi|$ for some pure state
$|\psi\rangle$. The states $|\psi\rangle$ obtained in this way are known in the literature as
\emph{stabilizer states}. The problem of recognizing local (Clifford) equivalence of stabilizer
states is of importance in a number of applications in quantum information theory and quantum
computing [] []. Due to the special structure of self-dual codes, some additional results on local
Clifford equivalence exist: firstly, it is well known that every self-dual code is equivalent under
the Clifford group to a code with a generator matrix of the form
\[S = \left [ \begin{array}{c} \theta\\
I \end{array}\right], \] where $\theta$ is a symmetric matrix with zero diagonal []. As such a
matrix corresponds naturally to the adjacency matrix of a (simple) graph, these codes are called
\emph{graph codes}. Secondly, the action of local Clifford operations on such self-dual graph codes
is related to a graph transformation rule known in graph theory as \emph{local complementation} [].
The local complement $g_i(G)$ of a graph $G$ at one of its vertices $i$ is defined by its adjacency
matrix $g_i(\theta)$ as follows:
\begin{equation}\label{localcomp}g_i(\theta) = \theta + \theta_i\theta_i^T + \Lambda,\end{equation}
where $\theta$ is the adjacency matrix of $G$, $\theta_i$ is its $i$th column and $\Lambda$ is a
diagonal matrix such as to yield zeros on the diagonal of $g_i(\theta)$. Addition in
(\ref{localcomp}) is to be performed modulo two. In graph theoretical terminology, $g_i(G)$ is
obtained by replacing the subgraph of $G$ induced by the neighborhood of $i$ by its complement. Two
self-dual graph codes are locally equivalent under the Clifford group if and only if there exists a
sequence of local complementations which relates their associated graphs. The codes are globally
equivalent iff their graphs are related by a sequence of local complementations, modulo graph
isomorphism.


\appendix
\section{}

\textbf{Proposition}: {\it (i) The orbit of the $n$-qubit GHZ state under local Clifford operations
contains exactly the following $n+1$ graph states:

\vspace{3cm}

where the example is given for $n=5$ and generalization is straightforward. (ii) An $n$-qubit graph
state with adjacency matrix $\theta$ is equivalent to the GHZ state iff $\mbox{rank }\theta_{\{i\}}
= 1 = \mbox{rank }\theta_{\{i, j\}}$ for all $i, j \in \{1, \dots, n\}$. (iii) An $n$-qubit
stabilizer state $|\psi\rangle$ is equivalent to the GHZ state iff it has local ranks
$r_{\{i\}}=2=r_{\{i, j\}}$ for all $i, j \in \{1, \dots, n\}$.}


\textit{Proof}: Statement (i) is an immediate corollary of Theorem*. We now prove statement (ii).
Let $\theta$ be an $n$-qubit graph state with $\mbox{rank }\theta_{\{i\}} = 1 = \mbox{rank
}\theta_{\{i, j\}}$ for all $i, j \in \{1, \dots, n\}$. Then $\theta$ has a nonzero entry, which we
can assume to be $\theta_{12}=1$ (if necesarry after relabelling the qubits). Firstly, we observe
that it is impossible that $\theta_{1j}=0 =\theta_{2j}$ for any $j$: for, if this is the case, then
the property $\mbox{rank }\theta_{\{1, j\}}=1$ would imply that $\theta_{\{j\}} = (0 \dots 0)$,
which is a contradiction. We now make a distinction between the following cases:

{\it Case 1}: let there be a $j_0$ such that $\theta_{1j_0}=1$ and $\theta_{2j_0}=0$. The property
$\mbox{rank }\theta_{\{1, 2\}}=1$ then implies that $\theta_{2j}=0$ for all $j \neq 1$. Since
$\theta_{1j}$ and $\theta_{2j}$ cannot be simultaneously zero, it follows that $\theta_{1j}=1$ for
all $j \neq 1$. Finally, considering the property $\mbox{rank }\theta_{\{1, j\}}=1$ for all $j$ we
conclude that $\theta_{ij} = 1$ iff $i$ or $j$ are equal to 1 and $\theta_{ij} = 0$ otherwise,
yielding the graph (*).

{\it Case 2}: if there is a $j_0$ such that $\theta_{2j_0}=1$ and $\theta_{1j_0}=0$ then a
permutation of qubits 1 and 2 brings us back to case 1.

{\it Case 3}: finally, let there be a $j_0$ such that $\theta_{1j_0}=1$ and $\theta_{2j_0}=1$. A
similar reasoning as in the previous cases proves that $\theta$ is the state (*).

(iii) This is an immediate corollary of (ii), lemma* and the fact that each stabilizer state is
equivalent to a graph state. \hfill $\square$


\textbf{Lemma} {\it Consider the natural action of $GL(2, \Bbb{F}_2)$ on $\Bbb{F}_2^{2r}$, where
$Q\in GL(2, \Bbb{F}_2)$ maps $u=(u_1, \dots, u_r)\in\Bbb{F}_2^{2r}$ to $u^Q := (Q u_1, \dots, Q
u_r)$, where $u_j\in \Bbb{F}_2^2$ for every  $j=1, \dots, r$. For each $u\in \Bbb{F}_2^{2r}$,
define the sets
\begin{eqnarray}
\omega_{00}(u)&=&\{j|\ u_j=(0,0) \},\nonumber\\
\omega_{01}(u)&=&\{j|\ u_j=(0,1) \},\nonumber\\
\omega_{10}(u)&=&\{j|\ u_j=(1,0) \},\nonumber\\
\omega_{11}(u)&=&\{j|\ u_j=(1,1) \}.\nonumber
\end{eqnarray}
Then two vectors $u, u'\in \Bbb{F}_2^{2r}$ belong to the same orbit under the above action if and
only if (i) $\omega_{00}(u)=\omega_{00}(u')$ and (ii) there exists a permutation $\pi$ of $\{01,
10, 11\}$ such that
\begin{eqnarray}\label{orbit}\omega_{01}(u')= \omega_{\pi(01)}(u),\nonumber\\
\omega_{10}(u')= \omega_{\pi(10)}(u),\nonumber\\
 \omega_{11}(u')=
\omega_{\pi(11)}(u).\nonumber\end{eqnarray} Equivalent to condition (ii), the sets $\{\omega_{01},
\omega_{10}, \omega_{11}\}$ and $\{\omega_{01}', \omega_{10}', \omega_{11}'\}$ form the same
partition of $\bar\omega_{00}$, where the set $\bar\omega_{00}$ is the complement of $\omega_{00}$
in $\{1, \dots, r\}$.}

We are now ready to introduce the generalized weight polynomials. We will first give a formal
definition and then investigate the properties of these polynomials. Let $\rho_{\cal S}$ be an $[n,
k]$ stabilizer code with  binary code space $S_{\psi}$. Fix $d\in \Bbb{N}_0$ and consider the
natural action of $GL(2, \Bbb{F}_2)$ on $(\Bbb{F}_2^2)^d$, where a nonsingular matrix $F$ over
$\Bbb{F}_2$ sends a vector $(u_1, v_1, \dots, u_d, v_d)\in \Bbb{F}_2^{2d}$ to $(\bar u_1, \bar v_1,
\dots, \bar u_d, \bar v_d)$, defined by
\[\left[\begin{array}{c}\bar u_i\\ \bar v_i
\end{array}\right]=F \left[\begin{array}{c} u_i\\ v_i \end{array}\right]\] for every $i=1, \dots, d$.
The set of all orbits of this group action is a partition of $\Bbb{F}_2^{2d}$. Every orbit $\Gamma$
defines a function on $S_{\psi}^d= S_{\psi} \times\dots\times S_{\psi}$ ($d$ times) as follows:
\[\Gamma(y^{(1)}, \dots, y^{(d)}) = \left|\left\{i\ |\ (y^{(1)}_i, y^{(1)}_{n+i}, \dots,
y^{(d)}_i, y^{(d)}_{n+i})\in \Gamma\right\}\right| , \] for every ordered $d$-tuple $(y^{(1)},
\dots, y^{(d)})\in S_{\psi}^d$. Introducing for every orbit $\Gamma$ a variable $x_{\Gamma}$, the
$d$-th weight polynomial $W_n^{(d)}(\{x_{\Gamma}\})$ is defined as follows:
\[W_n^{(d)}(\{x_{\Gamma}\}) = \sum_{(y^{(1)}, \dots,\
y^{(d)})\in\ S_{\psi}^d} \prod_{\Gamma}\ x_{\Gamma}^{\Gamma(y^{(1)}, \dots,\ y^{(d)})}.\]

Firstly, note that the generalized weight polynomials are indeed generalizations of the standard
weight enumerator. If $d=1$ then we are dealing with the natural linear action of $GL(2,
\Bbb{F}_2)$ on $\Bbb{F}_2^2$. In this case there are two orbits, namely $\Gamma_0=\{(0,0)\}$ and
$\Gamma_1=\{(0,1), (1,0), (1,1)\}$, as the zero vector remains fixed under linear transformations
and any nonzero vector can be mapped to any other nonzero vector by some invertible linear
transformation. Introducing the variables $x := x_{\Gamma_0}$ and $y := x_{\Gamma_1}$, we recover
the standard weight enumerator
\[W_n^{(1)}(x, y) = \sum_{i=1}^n A_i x^{n-i}y^i,\] where $A_i$ is the number of codewords
 with weight equal to $i$. As for general $d$, the properties of the generalized weight polynomials
 are stated and proven in the following theorem:

\textbf{Theorem 1} {\it Let $n, d\in \Bbb{N}_0$. The $d$-th generalized weight polynomial
$W_n^{(d)}$ is a homogeneous polynomial of degree $n$ in $\frac{1}{3}\ (2^{2d-1} + 3\cdot 2^{d-1} +
1)$ variables $x_{\Gamma}$. Moreover, any $[n, k]$ stabilizer code is completely determined  by its
$k$-th generalized weight enumerator up to ${\cal C}_n^l$-equivalence.}

{\it Proof:} It is immediately clear that all generalized weight polynomials are homogeneous of
degree $n$. In order to count the number of variables $x_{\Gamma}$, we use the Cauchy-Frobenius
orbit-counting lemma [], which states that the number of orbits of a group acting on a set is equal
to the average number of fixed points. In the case of $GL(2, \Bbb{F}_2)$ acting on
$(\Bbb{F}_2^2)^d$, an easy calculation shows that there are
\[\frac{1}{|GL(2, \Bbb{F}_2)|}\ (4^{d} + 3\cdot 2^{d} + 2)\] orbits $\Gamma$. Using
$|GL(2, \Bbb{F}_2)| = 6$ the result easily follows. We now prove the final assertion. First, note
that the polynomials $W_n^{(d)}$ are by definition equal for (globally) ${\cal C}_n^l$-equivalent
codes, for every $d\in\Bbb{N}_0$. The reverse statement is proven as follows: suppose that two
$[n,k]$ codes $\rho_{\cal S}$ and $\rho_{{\cal S}'}$, with generator matrices $S$, $S'$ and binary
code spaces $S_{\psi}$ and ${\cal C}_{S'}$, respectively,  have the same $k$-th weight enumerator
$W_n^{(k)}$. Letting $S^{(i)}$ denote the $i$th column of $S$, for every $i=1, \dots, k$, we fix
the ordered $k$-tuple $(S^{(1)}, \dots, S^{(k)})\in S_{\psi}^k$.  This $k$-tuple corresponds to a
monomial in $W_n^{(k)}$ and, as $W_n^{(k)}$ is the $k$-th weight enumerator of $\rho_{{\cal S}'}$
as well, there exists a $k$-tuple $(y^{(1)}, \dots, y^{(k)})$ of vectors $y^{(i)}\in{\cal C}_{S'}$
which corresponds to the same monomial. Equivalently, there is a transformation $Q\in C_n^l$ and an
$n\times n$ permutation matrix $\Pi$ such that $y^{(i)} = (\bar\Pi Q) S^{(i)}$ for every $i=1,
\dots, k$, where $\bar\Pi$ is defined as in (\ref{pi}). It follows that the set $\{y^{(1)}, \dots,
y^{(k)}\}$ is a basis of ${\cal C}_{S'}$, being the image of a basis under an invertible linear
transformation $\bar\Pi Q$. Therefore ${\cal C}_{ (\bar\Pi Q) S} = {\cal C}_{S'}$, which is the
desired result.
 \hfill $\square$

%Note that...

In order to compute the polynomials $W_n^{(d)}$ for a given code, one needs an operational
criterion to recognize which orbit $\Gamma$ an arbitrary vector in $\Bbb{F}_2^{2d}$ belongs to. To
this end, let us characterize when two vectors $(u,v)=(u_1, v_1, \dots, u_d, v_d)$ and $(u', v'
)=(u_1', v_1', \dots, u_d', v_d')$ lie on the same orbit under the action of $GL(2, \Bbb{F}_2)$.
Firstly, it is immediately clear that the sets $\omega_{00}=\{i|\ (u_i,v_i)=(0,0) \}$ and
$\omega_{00}'=\{i| (u_i',v_i')=(0,0) \}$ must be equal, %in order for $(u,v)$ and $(u'v')$ to lie on
%the same orbit,
as the zero vector $(0,0)$ is fixed under any linear transformation. Moreover, defining
\begin{eqnarray}
\omega_{01}&=&\{i|\ (u_i,v_i)=(0,1) \},\nonumber\\
\omega_{10}&=&\{i|\ (u_i,v_i)=(1,0) \},\nonumber\\
\omega_{11}&=&\{i|\ (u_i,v_i)=(1,1) \},\nonumber
\end{eqnarray}
and $\omega_{01}'$, $\omega_{10}'$, $\omega_{11}'$ analogously for $(u', v')$, there must exist a
permutation $\pi$ of $\{01, 10, 11\}$ such that
\begin{equation}\label{orbit}\omega_{01}'= \omega_{\pi(01)},\ \omega_{10}'= \omega_{\pi(10)},\
\omega_{11}'= \omega_{\pi(11)}.\end{equation} To see this, simply note that any invertible linear
operation over $\Bbb{F}_2$ is in a one-to-one correspondence with such a permutation $\pi$.
Equivalently to (\ref{orbit}), we can state that the sets $\{\omega_{01}, \omega_{10},
\omega_{11}\}$ and $\{\omega_{01}', \omega_{10}', \omega_{11}'\}$ form the same partition of
$\bar\omega_{00}$, where $\bar\omega_{00}$ is the complement of $\omega_{00}$ in $\{1, \dots, d\}$.
It is now readily verified that equality of these two partitions plus equality of the sets
$\omega_{00}$ and $\omega_{00}'$ are also sufficient conditions for $(u,v)$ and $(u',v')$ to lie on
the same orbit. Summarizing, any orbit $\Gamma$ is completely determined by specifying a set
$\omega_{00}(\Gamma)\subseteq\{1, \dots, d\}$ and a partition ${\cal P}(\Gamma) = \{\omega_{01},
\omega_{10}, \omega_{11}\}$ of $\bar\omega_{00}$. This characterization can be used to calculate
the generalized weight polynomials of a given code.

%{\it Example.} Consider the $[4, 4]$ code with $8\times 4$ generator matrix \[S=\left[
%\begin{array}{c}\theta\\ I \end{array}\right],\] where $\theta$ is the symmetric $4\times 4$ matrix
%which has all ones, except for the diagonal entries, which are zero.
%\[\theta = \left[
%\begin{array}{cccc} 0&1&1&1\\ 1&0&1&1\\1&1&0&1\\1&1&1&0\\ \end{array}\right].\]

\section{Equivalence versus ${\cal C}_n^l$-equivalence}

%{\it  Quantum error-correction.}
The following important remark is called for: it is clear that the notion of Clifford equivalence
of stabilizer codes is intrinsically contained within the definition of the weight polynomials.
Moreover, these polynomials contain all the information about the ${\cal C}_n^l$-equivalence class
of any given code, as we have shown in theorem 1. However, in quantum coding theory one is
interested in equivalence under all unitaries in $U(2)^{\otimes n}$ and therefore it seems that the
generalized weight polynomials contain in this respect too much information. This issue (sluit aan)
with the to date unanswered question whether equivalent stabilizer codes are necessarily ${\cal
C}_n^l$-equivalent. Note that a positive answer to this question would neutralize the above remark.
From a somewhat opposite point of view, the generalized weight polynomials could in fact be used to
settle this question. Indeed, should one be able to prove that the coefficients of the generalized
weight polynomials are invariants under equivalence, it would follow that any  two equivalent codes
are necessarily ${\cal C}_n^l$-equivalent. Note that the coefficients of the standard weight
enumerator ($d=1$) are indeed invariants under equivalence [][]. We show below that the same
assertion holds for the case $d=2$. However, a proof (or counterexample) for general $d$ has to
date not been found and we leave this as an open problem.
%\textbf{Open problem:} {\it Are the coefficients of the generalized weight polynomials invariants
%under equivalence? }
Let us now show that the coefficients of the polynomials $W_n^{(2)}$ are indeed invariants.

\textbf{Theorem 2} {\it  The coefficients of the weight polynomials $W_n^{(2)}$ are invariants
under equivalence.}

{\it Proof: }

\section{Self-dual codes}

{\it Self-dual codes.} Of particular interest in quantum information theory are {self-dual}
stabilizer codes, which are $[n, n ]$ codes. The associated projectors of such codes are
one-dimensional and therefore correspond to pure multiqubit states, known in the literature as
stabilizer states. Stabilizer states have been employed in numerous applications [][][][]. As most
applications use in some way the entanglement present in these states, it is sensible to
investigate what the nonlocal properties of this class of states are. Hein [] Note that ...
Moreover, eindig aantal invarianten... Note that also in this context the question involving
equivalence versus ${\cal C}_n^l$-equivalence is relevant.
%{\it  Quantum computing.}
An important application of stabilizer states is the so-called \emph{one-way quantum computer},
which is a  measurement-based model for quantum computation which uses a stabilizer state (namely
the cluster state) as a universal resource. In this model, a computation is implemented by a series
of one-qubit measurements on this state. Moreover, the Clifford part of a computation transforms
this cluster state to a different stabilizer state and states which are related by a local Clifford
transformation correspond to the same (Clifford part of the) computation. In other words, these
computations naturally correspond to ${\cal C}_n^l$-equivalence classes of self-dual stabilizer
codes and the generalized weight polynomials therefore provide a suitable description thereof.

%{\it Graph theory.}

%{\it Invariant theory.}

Let us first state some preliminaries.  For simplicity, we restrict ourselves to qubit codes, but
generalizations to higher dimensional systems are immediate. The Pauli group ${\cal G}_n$ on $n$
qubits consists of all $4\times 4^n$ $n$-fold tensor products of the form $\alpha\ v_1 \otimes
v_2\otimes \dots \otimes v_n$, where $\alpha \in \{ \pm 1, \pm i\}$ is an overall phase factor and
the $2 \times 2$-matrices $v_i$ $(i=1,\dots, n)$ are either the identity $\sigma_0$ or one of the
Pauli matrices $\sigma_x$, $\sigma_y$, $\sigma_z$. An $[n, k]$
 \emph{stabilizer code} is a joint eigenspace belonging to eigenvalue 1 of $k\leq n$
commuting, independent and Hermitian observables $M_i \in {\cal G}_n$. Here "independent" means
that no product of the form $M_1^{x_1}\dots M_k^{x_k}$, where $x_i \in \{0,1\}$, yields the
identity except when all $x_i$ are equal to zero. The multiplicative group ${\cal S}$ generated by
the operators $M_i$ is called the stabilizer of the code. Note that here is a one-to-one
correspondence between the code associated with ${\cal S}$ and the matrix
%\begin{equation}\label{rho_S}
$\rho_{\cal S}=\frac{1}{2^n}\sum_{M\in {\cal S}}M,$
%\end{equation}
as this operator is (up to a multiplicative constant) the projection operator which projects on the
code space. The \emph{Clifford group} ${\cal C}_1$ on one qubit is the normalizer of ${\cal G}_1$
in $U(2)$, i.e., it is the group of all $2\times 2$ unitary operators which map $\sigma_u$ to
$\alpha_u\sigma_{\pi(u)}$ under conjugation, where $u=x,y,z$, for some $\alpha_u=\pm 1$ and some
permutation $\pi$ of $\{x,y,z\}$. The $n$-qubit local Clifford group ${\cal C}_n^l$ is the $n$-fold
tensor product of ${\cal C}_1$ with itself.

It is well known (see e.g. \cite{QCQI}) that the stabilizer formalism has an equivalent formulation
in terms of binary linear algebra. In this binary formulation, an $[n,k]$ stabilizer code %${\cal S}$
 corresponds to a $k$-dimensional self-orthogonal linear subspace of $\Bbb{F}_2^{2n}$. Here
$\Bbb{F}_2$ is the finite field of two elements (0 and 1), where arithmetics are performed modulo
2. The self-orthogonality of the subspace is with respect to a symplectic inner product $<\cdot,
\cdot>$ defined by $< u, v>:= u^T P v$, where $u,v\in\Bbb{F}_2^{2n}$ and \[P = \left[
\begin{array}{cc} 0 & I \\ I& 0 \end{array} \right].\]
The binary stabilizer subspace is usually  presented in terms of a full rank $2n\times k$ generator
matrix $S$, the columns of which form a basis of the subspace \footnote{In fact, ...}. This
generator matrix satisfies $S^TPS=0$ from the self-orthogonality of the space. The entire binary
stabilizer space (or binary code space), which we denote by $S_{\psi}$, is the column space of $S$.
%i.e., it is equal to
%\begin{equation}
%S_{\psi}:=\left\{ Sx\ |\ x\in\Bbb{F}_2^{n}\right\}.
%\end{equation}
%It is clear that there is a lot of freedom in choosing the generator matrix of a stabilizer, as
%multiplying $S$ to the right with a nonsingular $n\times n$ matrix $R$ yields a new generator
%matrix $SR$.

In the binary framework, local Clifford operations $U\in {\cal C}_n^l$ correspond to nonsingular
$2n\times 2n$ binary matrices $Q$ of the block form
\[Q = \left [ \begin{array}{cc} A&B\\
C&D \end{array}\right],\] where the $n\times n$ blocks $A, B, C, D$ are diagonal. We denote the
diagonal entries of $A, B, C, D$, respectively, by
 $a_i$, $b_i$, $c_i$, $d_i$, respectively. The $n$ nonsingular submatrices \[\left [
\begin{array}{cc} a_i & b_i
\\ c_i& d_i\end{array} \right ]\] correspond to the tensor factors of $U$. The set $C^l_n$ of all such $Q$
is a multiplicative matrix group isomorphic to $GL(2, \Bbb{F}_2)^{\oplus n}$. It follows that two
stabilizer codes $\rho_{\cal S}$, $\rho_{{\cal S}'}$ with generator matrices $S$, $S'$,
respectively, are locally ${\cal C}_n^l$-equivalent  if and only if there exists $Q\in C^l_n$ such
that ${\cal C}_{QS} = {\cal C}_{S'}$. To see this, simply note that $U\rho_{\cal
S}U^{\dagger}=\rho_{{\cal S}'}$ for some $U\in {\cal C}_n^l$ if and only $U{\cal
S}U^{\dagger}={\cal S}'$. Global ${\cal C}_n^l$-equivalence occurs whenever there exists an
$n\times n$ permutation matrix $\Pi$ such that ${\cal C}_{ (\bar\Pi Q) S} = {\cal C}_{S'}$,
where the $2n\times 2n$ matrix $\bar \Pi$ is defined as \begin{equation}\label{pi}\bar\Pi = \left [ \begin{array}{cc} \Pi&0\\
0&\Pi \end{array}\right].\end{equation}


Consequently, in the past years the theory of quantum error-correcting codes has been developed
with substantial success.
%The most widely known and studied class of quantum codes is
%that of the stabilizer codes, which are constructed on the basis of abelian subgroups of the Pauli
%group.
The \emph{weight enumerator} of a code is a celebrated polynomial, both in classical as in quantum
coding theory, the coefficients of which describe the weight distribution of the code. Shor and
Laflamme showed that weight enumerators are powerful tools to explore the structure of quantum
codes, as they can be used to obtain bounds on how good quantum codes can be and to test whether
possible good codes exist [].

In this paper we introduce a family of polynomials which are generalizations of the standard
quantum weight enumerator. These polynomials are analogons of the \emph{generalized weight
polynomials} in classical coding theory, which were introduced by Runge []. This author studied
such polynomials in the context of modular forms and showed that the algebra generated by the
weight polynomials of a certain subclass of codes (the doubly-even self-dual codes) is in fact the
invariant algebra of the Clifford group. This is a generalization of a central result in classical
coding theory, known as Gleason's theorem []. The relation between classical weight polynomials and
invariant theory has subsequently been investigated in more detail by Nebe, Rains, Sloane and
others [][][] and there appears to be a very deep connection between these fields in mathematics.
What is more, the appearance of the Clifford group in this context is remarkable, as this group is
so typical of a quantum setting rather than a classical one, and it is in fact unclear whether this
is a mere coincidence or a manifestation of some deeper result [].

In light of the above considerations, we introduce below the concept of generalized weight
polynomials for quantum stabilizer codes, both as . Indeed, we motivate below that the quantum
generalized weight polynomials are of potential interest in quantum computing, multipartite
entanglement theory and graph theory.




\textbf{Corollary 2} {\it The Molien function $\Phi^{(n)}(z)$ of the group $\{U\otimes\bar U\ |\
U\in {\cal C}_n^l\}$ is
\begin{eqnarray}
\Phi^{(n)}(z) = 1 + z + \sum_{r=2}^{\infty}\ (2^{2r-3} + 3\cdot 2^{r-2} + 1)^n
\frac{z^r}{3^n}\nonumber.\end{eqnarray} A closed form of $\Phi^{(n)}(z)$ can be obtained using the
recursive formula
\begin{equation}
\Phi^{(n)}(z) = \frac{1}{2\pi i} \oint_{u} \Phi^{(n-1)}(u)\ \Phi^{(1)}\left(\frac{z}{u}\right)
\frac{du}{u},
\end{equation}
where the integral over $u$ is taken over the complex unit circle.}


The dimension  of this space is bounded from above by (\ref{dim}). %\[\frac{1}{3}(2^{2r-3} + 3\cdot 2^{r-2} + 1).\]
In invariant theory, it is customary to encode the information about these dimensions into a
generating (complex) function $\Phi(z)$, called \emph{Molien function}. The Molien function of a
finite matrix group ${\cal G}\leq GL(N, \Bbb{C})$ is defined by the power series
\begin{equation}\label{molien1} \Phi(z) = \sum_{r=0}^{\infty} d_r z^r,\end{equation} where $d_r$ is the
dimension of the space of all homogeneous polynomials $f(x):=f(x_1, \dots, x_N)$ of degree $r$
which satisfy $f(Ax)=f(x)$ for every $A\in {\cal G}$. The Molien function of a finite matrix group
is a rational function in the complex variable $z$. Molien proved [] the following interesting
identity:
\begin{equation}\label{molien2}
\Phi(z)= \frac{1}{|{\cal G}|} \sum_{A\in {\cal G}} \frac{1}{\mbox{det}(I-zA)},
\end{equation}
which can be used to obtain a closed form of (\ref{molien1}) by an explicit calculation of the sum
over all elements in ${\cal G}$. As for the current problem, note that we are considering the
action $\rho\to U\rho U^{\dagger}$, where $\rho\in M_2(\Bbb{C})$ and $U\in {\cal C}_1$, which
corresponds to the linear action \[\vec \rho\to U\otimes \bar U \vec \rho,\] where $\vec
\rho=(\rho_{11}, \rho_{12}, \rho_{21}, \rho_{22})$ and $\bar U$ is the complex conjugate of $U$.
Therefore, a closed form for the Molien function can be obtained by evaluating the sum
\begin{equation}\label{molien3}
\Phi^{(1)}(z)= \frac{1}{192} \sum_{U\in {\cal C}_1} \frac{1}{\mbox{det}(I-zU\otimes\bar U)}.
\end{equation}
Using the software package MATHEMATICA, we find
\begin{equation}\label{molien4}
\Phi^{(1)}(z)= \frac{1}{192} \sum_{U\in {\cal C}_1} \frac{1}{\mbox{det}(I-zU\otimes\bar U)}.
\end{equation}

\textbf{Theorem 2} {\it The Molien function $\Phi^{(1)}(z)$ of the group $\{U\otimes\bar U\ |\ U\in
{\cal C}_1\}$ is
\begin{eqnarray}
\Phi^{(1)}(z) = \nonumber\\
\end{eqnarray} }

\section{Introduction}

\section{Stabilizer codes}

\section{Generalized weight polynomials}

\section{Self-dual codes and local graph complementation}

\section{Discussion}


link met vorig werk!

\section{conclusion}


Note, however, that for several codes it is not necessary to go as far as degree $k+1$ in order to
characterize their orbits. A first (trivial) example is the
$[n,n]$ code with generator matrix \[\left [ \begin{array}{c} \mbox{O}\\
I \end{array}\right],\] where O is the $n\times n$ zero matrix and $I$ is the $n\times n$ identity
matrix, for arbitrary $n$. Its easy to verify that the invariants of degree 2 (i.e. the weight
distribution of the code) completely determine this code up to Clifford equivalence. A second
example is the $[n,n]$ code with generator matrix \[\left [ \begin{array}{c} K\\
I \end{array}\right],\] where $K$ is the $n\times n$ matrix which has all ones except for the
diagonal entries, which are zero (i.e., $K$ is the adjacency matrix of the complete graph on $n$
vertices). This is the defining generator matrix for the generalized GHZ-state (which is a
self-dual stabilizer code or stabilizer state, see below). We show in appendix A that the Clifford
equivalence class of this code as well is completely determined by the invariants of degree 2.
These examples suggest that there possibly exist interesting classes of codes which are determined
up to Clifford equivalence by a set of invariants of small degree.

cliff_inv_graph_prl2.bbl
\begin{thebibliography}{10}

\bibitem{Gott}
D.~Gottesman.
\newblock {\em Stabilizer codes and quantum error correction}.
\newblock PhD thesis, Caltech, 1997.
\newblock quant-ph/9705052.

\bibitem{1wayQC}
R.~Raussendorf, D.E. Browne, and H.J. Briegel.
\newblock Measurement-based quantum computation with cluster states.
\newblock {\em Phys. Rev. A}, 68:022312, 2003.
\newblock quant-ph/0301052.

\bibitem{entgraphstate}
M.~Hein, J.~Eisert, and H.J. Briegel.
\newblock Multi-party entanglement in graph states.
\newblock {\em Phys. Rev. A}, 69:062311, 2004.
\newblock quant-ph/0307130.

\bibitem{graphbriegel}
W.~D\"ur, H.~Aschauer, and H.J. Briegel.
\newblock Multiparticle entanglement purification for graph states.
\newblock {\em Phys. Rev. Lett.}, 91:107903, 2003.
\newblock quant-ph/0303087.

\bibitem{localcliffgraph}
M.~Van~den Nest, J.~Dehaene, and B.~De~moor.
\newblock Graphical description of the action of local clifford transformations
  on graph states.
\newblock {\em Phys. Rev. A}, 69:022316, 2004.
\newblock quant-ph/0308151.

\bibitem{invar_stab}
M.~Van~den Nest, J.~Dehaene, and B.~De~Moor.
\newblock Local invariants of stabilizer codes.
\newblock {\em Phys. Rev. A}, 70:032323, 2004.
\newblock quant-ph/0404106.

\bibitem{alg_codes}
M.~Van~den Nest, J.~Dehaene, and B.~De~Moor.
\newblock Efficient algorithm to recognize local clifford equivalence of graph
  states.
\newblock {\em Phys. Rev. A}, 70:034302, 2004.
\newblock quant-ph/0405023.

\bibitem{val_bond}
F.~Verstraete and J.I. Cirac.
\newblock Valence bond solids for quantum computation.
\newblock {\em Phys. Rev. A}, 70:060302, 2004.
\newblock quant-ph/0311130.

\bibitem{LU_LC}
M.~Van~den Nest, J.~Dehaene, and B.~De~moor.
\newblock Local unitary versus local clifford equivalence of stabilizer states.
\newblock {\em Phys. Rev. A}, 71:062323, 2005.
\newblock quant-ph/0411115.

\bibitem{RainsMin2}
E.~Rains.
\newblock Quantum codes of minimum distance two.
\newblock {\em IEEE Trans. Inform. Theory}, 45(1):266--271, 1999.
\newblock quant-ph/9704043.

\bibitem{QCQI}
I.~Chuang and M.~Nielsen.
\newblock {\em Quantum computation and quantum information}.
\newblock Cambridge University press, Cambridge, 2000.

\bibitem{Shor_Lafl}
P.~Shor and R.~Laflamme.
\newblock Quantum analog of the macwilliams identities for classical coding
  theory.
\newblock {\em Phys. Rev. Lett.}, 78(8):1600--1602, 1997.
\newblock quant-ph/9610040.

\bibitem{RainsQWE}
E.M. Rains.
\newblock Quantum weight enumerators.
\newblock {\em IEEE Trans. Inform. Theory}, 44(4):1388--1394, 1998.
\newblock quant-ph/9612015.

\bibitem{Bouchet}
A.~Bouchet.
\newblock Recognizing locally equivalent graphs.
\newblock {\em Discrete Math.}, 114(1-3):75--86, 1993.

\end{thebibliography}
