Introduction
Stabiliser codes were introduced by Calderbank, Rains, Shor and Sloane [8 ] and Gottesman [14 ] independently. They are a special type of quantum error-correcting codes. A stabiliser code is a subspace Q Q Q of a Hilbert space ( C q ) ⊗ n (\mathbb{C}^{q})^{\otimes n} ( C q ) ⊗ n that is the intersection of the eigenspaces of eigenvalue one of an abelian subgroup S S S of E ⊗ n \mathcal{E}^{\otimes n} E ⊗ n , where E \mathcal{E} E is a nice error basis. These codes are widely used in quantum error-correction, partly because it is often easier to work with the subgroup S S S , rather than with a basis for the subspace Q Q Q . In this article, we restrict ourselves to the case where q q q is prime. In this case, the stabiliser formalism allows us to interpret the abelian subgroup S S S as a classical additive code that is contained in its symplectic dual, see [2 , 3 , 8 , 20 ] .
One-dimensional binary stabiliser codes are called graphical states or graph states since they can be represented by a simple graph. Graph states have been well studied, see for example [1 , 12 , 16 , 21 ] . There have been many proposals to use graphs to represent stabiliser codes of general dimension, including [18 , 19 , 21 , 27 ] .
In this article, we prove that an [ [ n , k , d ] ] p [[n,k,d]]_p [[ n , k , d ] ] p stabiliser code over a prime field can be interpreted as a weighted graph on n + k n+k n + k vertices containing two independent sets of size k k k that induce a (non-weighted) matching. As far as we are aware, this equivalence has not been previously noted.
We go on to consider quantum sets of lines , sets of lines in projective space, associated to such a stabiliser code, from which it is possible to give a geometrical description of the minimum distance d d d . These ideas are inspired by the work of Glynn, Gulliver, Maks and Gupta [15 ] and build on the generalisations of Ball, Centelles and Huber [3 ] . See also the work of Bierbrauer, Faina, Giulietti, Marcugini and Pambianco [6 ] .
As an application, we present some tables on the number of stabiliser codes of dimension k = 1 k=1 k = 1 and local dimension q = 2 q=2 q = 2 (qubit) and q = 3 q=3 q = 3 (qutrit), expanding on the known classifications for k = 0 k=0 k = 0 and q = 2 q=2 q = 2 by Danielsen and Parker [11 ] and k = 0 k=0 k = 0 and q = 3 q=3 q = 3 by Danielsen [10 ] .
Preliminaries
Stabiliser formalism
Let F p \mathbb{F}_p F p denote the finite field of order p p p , where p p p is prime. Consider the standard symplectic inner product on the vector space F p 2 n \mathbb{F}_p^{2n} F p 2 n given by
⟨ u , v ⟩ = ∑ i = 1 n u i v n + i − v i u n + i . \langle\mathbf{u},\mathbf{v}\rangle=\sum_{i=1}^{n}u_i v_{n+i}-v_i u_{n+i}. ⟨ u , v ⟩ = i = 1 ∑ n u i v n + i − v i u n + i .
Given a subspace U ⊆ F p 2 n U\subseteq\mathbb{F}_p^{2n} U ⊆ F p 2 n , let U ⊥ = { v ∈ F p 2 n : ⟨ u , v ⟩ = 0 for all u ∈ U } U^\perp=\{\mathbf{v}\in\mathbb{F}_p^{2n}:\langle\mathbf{u},\mathbf{v}\rangle=0\text{ for all }\mathbf{u}\in U\} U ⊥ = { v ∈ F p 2 n : ⟨ u , v ⟩ = 0 for all u ∈ U } . A subspace U U U is called totally isotropic if U ⊆ U ⊥ U\subseteq U^\perp U ⊆ U ⊥ . The symplectic weight of a vector v ∈ F p 2 n \mathbf{v}\in\mathbb{F}_p^{2n} v ∈ F p 2 n is defined as
swt ( v ) = # { i ∈ { 1 , … , n } : ( v i , v n + i ) ≠ ( 0 , 0 ) } . \operatorname{swt}(\mathbf{v})=\#\{i\in\{1,\ldots,n\}:(v_i,v_{n+i})\ne(0,0)\}. swt ( v ) = # { i ∈ { 1 , … , n } : ( v i , v n + i ) = ( 0 , 0 )} .
Definition 1. An [ [ n , k ] ] p [[n,k]]_p [[ n , k ] ] p stabiliser code is a totally isotropic subspace S S S of F p 2 n \mathbb{F}_p^{2n} F p 2 n of dimension n − k n-k n − k . The minimum distance of S S S is
d ( S ) = { min { swt ( v ) : v ∈ S ⊥ ∖ S } if k > 0 , min { swt ( v ) : v ∈ S ∖ { 0 } } if k = 0. d(S)=
\begin{cases}
\min\{\operatorname{swt}(\mathbf{v}):\mathbf{v}\in S^\perp\setminus S\} & \text{if } k>0,\\
\min\{\operatorname{swt}(\mathbf{v}):\mathbf{v}\in S\setminus\{\mathbf{0}\}\} & \text{if } k=0.
\end{cases} d ( S ) = { min { swt ( v ) : v ∈ S ⊥ ∖ S } min { swt ( v ) : v ∈ S ∖ { 0 }} if k > 0 , if k = 0. If the minimum distance d d d is specified, we call S S S an [ [ n , k , d ] ] p [[n,k,d]]_p [[ n , k , d ] ] p code.
Definition 2. A stabiliser matrix of an [ [ n , k ] ] p [[n,k]]_p [[ n , k ] ] p stabiliser code S S S is an ( n − k ) × 2 n (n-k)\times2n ( n − k ) × 2 n matrix whose rows form a basis of S S S . A parity check matrix 4 of an [ [ n , k ] ] p [[n,k]]_p [[ n , k ] ] p stabiliser code S S S is an ( n + k ) × 2 n (n+k)\times2n ( n + k ) × 2 n matrix whose rows form a basis of S ⊥ S^\perp S ⊥ .
We denote a stabiliser matrix by G G G and a parity check matrix by H H H .
Equivalent stabiliser codes
Definition 3. Two stabiliser codes are (local Clifford ) equivalent if they can be obtained from one another by:
Permutations of the n n n pairs of positions.
For each pair, a symplectic transformation on that pair. That is, a change of basis of F p 2 \mathbb{F}_p^2 F p 2 that preserves the symplectic inner product.
The maps yielding equivalence are the elements of the local Clifford group Sp ( 2 , p ) n ⋊ Sym ( n ) \operatorname{Sp}(2,p)^n \rtimes\operatorname{Sym}(n) Sp ( 2 , p ) n ⋊ Sym ( n ) . For example, for a given i ∈ { 1 , … , n } i \in\{1,\ldots,n\} i ∈ { 1 , … , n } , we can replace ( v i , v n + i ) (v_i,v_{n+i}) ( v i , v n + i ) by ( v n + i , − v i ) (v_{n+i},-v_i) ( v n + i , − v i ) within every vector v \mathbf{v} v . Another possibility is to replace ( v i , v n + i ) (v_i,v_{n+i}) ( v i , v n + i ) by ( v i + v n + i , v n + i ) (v_i+v_{n+i},v_{n+i}) ( v i + v n + i , v n + i ) within every vector v \mathbf{v} v . These two operations are in fact enough to generate the whole group of symplectic transformations, since Sp ( 2 , p ) = SL ( 2 , p ) \operatorname{Sp}(2,p)=\operatorname{SL}(2,p) Sp ( 2 , p ) = SL ( 2 , p ) is generated as a multiplicative group by all products of the matrices
( 0 − 1 1 0 ) and ( 1 0 1 1 ) . \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}
\quad\text{and}\quad
\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}. ( 0 1 − 1 0 ) and ( 1 1 0 1 ) .
Equivalent codes have the same parameters.
Stabiliser codes as graphs
A particular type of one-dimensional (k = 0 k=0 k = 0 ) stabiliser codes are graph states . Given a graph on n n n vertices, we can construct from it a stabiliser matrix that has the identity matrix on the left and the adjacency matrix A A A of the graph on the right:
G = ( I n ∣ A ) . G=\left(I_n\mid A\right). G = ( I n ∣ A ) .
Bahramgiri and Beigi [5 ] proved that every [ [ n , 0 ] ] p [\![n,0]\!]_p [ [ n , 0 ] ] p stabiliser code, p p p prime, is equivalent to a graph state. This was proved already by Schlingemann [22 ] for the binary case. We generalise this result to multidimensional (k ≥ 1 k\geq1 k ≥ 1 ) stabiliser codes.
Multidimensional graph states
Theorem 4. Consider an [ [ n , k , d ] ] p [\![n,k,d]\!]_p [ [ n , k , d ] ] p stabiliser code and let r = n − k r=n-k r = n − k . Up to equivalence, its stabiliser matrix has the form
G = ( I r ∣ B ∣ A + B C T ∣ C ) G=\left(I_r\mid B\mid A+BC^T\mid C\right) G = ( I r ∣ B ∣ A + B C T ∣ C ) where A A A is a symmetric r × r r\times r r × r matrix with zeroes on the diagonal and B B B and C C C are r × k r\times k r × k matrices.
Proof. After row reduction and permutations of pairs of columns, we may assume that the code has stabiliser matrix
G = ( I r ′ B D C O O E O ) , G=\begin{pmatrix} I_{r'} & B & D & C \\ O & O & E & O \end{pmatrix}, G = ( I r ′ O B O D E C O ) ,
for some r ′ ≤ r r'\leq r r ′ ≤ r . Here, the part below C C C may be assumed zero, since otherwise we can swap the columns containing B B B and C C C and increase the rank r ′ r' r ′ of the left part. The rowspace of G G G is symplectic self-orthogonal if and only if G Λ G T = O G\Lambda G^T=O G Λ G T = O where
Λ = ( O I n − I n O ) . \Lambda=\begin{pmatrix} O & I_n \\ -I_n & O \end{pmatrix}. Λ = ( O − I n I n O ) .
Thus,
O = G Λ G T = ( I r ′ B D C O O E O ) ( D T E T C T O − I r ′ O − B T O ) = ( D T + B C T − D − C B T E T − E O ) . O=G\Lambda G^T=
\begin{pmatrix} I_{r'} & B & D & C \\ O & O & E & O \end{pmatrix}
\begin{pmatrix} D^T & E^T \\ C^T & O \\ -I_{r'} & O \\ -B^T & O \end{pmatrix}
=
\begin{pmatrix} D^T+BC^T-D-CB^T & E^T \\ -E & O \end{pmatrix}. O = G Λ G T = ( I r ′ O B O D E C O ) D T C T − I r ′ − B T E T O O O = ( D T + B C T − D − C B T − E E T O ) .
We deduce that E = O E=O E = O , and hence r ′ = r r'=r r ′ = r , and that A = A T A=A^T A = A T , where A = D − B C T A=D-BC^T A = D − B C T . Finally, we can replace any non-zero elements on the diagonal of the matrix A A A by zero, by adding the i i i th column to the ( n + i ) (n+i) ( n + i ) th column if needed (preserving the symplectic inner product of rows). ∎
More explicitly, we can always put the stabiliser matrix in the form
( 1 ⋯ 0 ∣ b 11 ⋯ b 1 k ∥ a 11 + ∑ i = 1 k b 1 i c 1 i ⋯ a 1 r + ∑ i = 1 k b 1 i c r i ∣ c 11 ⋯ c 1 k ⋮ ⋱ ⋮ ∣ ⋮ ⋮ ∥ ⋮ ⋱ ⋮ ∣ ⋮ ⋮ 0 ⋯ 1 ∣ b r 1 ⋯ b r k ∥ a r 1 + ∑ i = 1 k b r i c 1 i ⋯ a r r + ∑ i = 1 k b r i c r i ∣ c r 1 ⋯ c r k ) \begin{pmatrix}
1 & \cdots& 0 & \vert& b_{11} & \cdots& b_{1k} & \Vert& a_{11}+\sum_{i=1}^{k}b_{1i}c_{1i} & \cdots& a_{1r}+\sum_{i=1}^{k}b_{1i}c_{ri} & \vert& c_{11} & \cdots& c_{1k}\\
\vdots& \ddots& \vdots& \vert& \vdots& & \vdots& \Vert& \vdots& \ddots& \vdots& \vert& \vdots& & \vdots\\
0 & \cdots& 1 & \vert& b_{r1} & \cdots& b_{rk} & \Vert& a_{r1}+\sum_{i=1}^{k}b_{ri}c_{1i} & \cdots& a_{rr}+\sum_{i=1}^{k}b_{ri}c_{ri} & \vert& c_{r1} & \cdots& c_{rk}
\end{pmatrix} 1 ⋮ 0 ⋯ ⋱ ⋯ 0 ⋮ 1 ∣ ∣ ∣ b 11 ⋮ b r 1 ⋯ ⋯ b 1 k ⋮ b r k ∥ ∥ ∥ a 11 + ∑ i = 1 k b 1 i c 1 i ⋮ a r 1 + ∑ i = 1 k b r i c 1 i ⋯ ⋱ ⋯ a 1 r + ∑ i = 1 k b 1 i c r i ⋮ a r r + ∑ i = 1 k b r i c r i ∣ ∣ ∣ c 11 ⋮ c r 1 ⋯ ⋯ c 1 k ⋮ c r k
where a i i = 0 a_{ii}=0 a ii = 0 for all i ∈ { 1 , … , r } i\in\{1,\ldots,r\} i ∈ { 1 , … , r } . The matrix A A A gives rise to an (undirected, loopless) weighted graph Γ A \Gamma_A Γ A on n − k n-k n − k vertices with weights in F p \mathbb{F}_p F p . The matrices B B B and C C C can be seen as two empty graphs Γ B \Gamma_B Γ B and Γ C \Gamma_C Γ C on k k k vertices each, with a matching between them (this matching has no weights) and weighted edges between Γ A \Gamma_A Γ A and Γ B \Gamma_B Γ B (resp. Γ C \Gamma_C Γ C ), indicating the entries of B B B (resp. C C C ). Let Γ \Gamma Γ be the union (not disjoint) of Γ A \Gamma_A Γ A , Γ B \Gamma_B Γ B and Γ C \Gamma_C Γ C . An example is given in Figure 1 . Label its vertices as follows:
Figure 1. A multidimensional graph state is represented by a graph on n + k n+k n + k vertices containing two independent sets of size k k k with a matching in between. In this figure, n = 7 n=7 n = 7 , k = 3 k=3 k = 3 and p = 2 p=2 p = 2 (the graph is not weighted).
V A = { a 1 , … , a r } , V_A=\{a_1,\ldots,a_r\}, V A = { a 1 , … , a r } ,
V B = { b 1 , … , b k } , V_B=\{b_1,\ldots,b_k\}, V B = { b 1 , … , b k } ,
V C = { c 1 , … , c k } . V_C=\{c_1,\ldots,c_k\}. V C = { c 1 , … , c k } .
Beware of the difference in notation with weights of the edges between the vertices. For example, a 12 a_{12} a 12 is the weight of the edge between the vertices a 1 a_1 a 1 and a 2 a_2 a 2 .
Example 5. Consider the [ [ 5 , 1 , 3 ] ] 2 \left[\left[5,1,3\right]\right]_2 [ [ 5 , 1 , 3 ] ] 2 stabiliser code generated by
G = ( 1 0 0 1 1 ∣ 1 0 1 0 1 0 1 0 0 1 ∣ 1 0 0 1 1 0 0 1 1 0 ∣ 1 0 0 1 1 0 0 0 0 0 ∣ 0 0 1 1 1 ) . G=\begin{pmatrix}
1&0&0&1&1\vert1&0&1&0&1\\
0&1&0&0&1\vert1&0&0&1&1\\
0&0&1&1&0\vert1&0&0&1&1\\
0&0&0&0&0\vert0&0&1&1&1
\end{pmatrix}. G = 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1∣1 1∣1 0∣1 0∣0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 .
Swapping column 4 and column 9 and using row operations, yields an equivalent code with generator matrix
( 1 0 0 0 ∣ 1 ∣ 1 0 1 1 ∣ 1 0 1 0 0 ∣ 1 ∣ 1 1 1 0 ∣ 0 0 0 1 0 ∣ 0 ∣ 1 1 1 1 ∣ 0 0 0 0 1 ∣ 0 ∣ 0 1 1 0 ∣ 1 ) \begin{pmatrix}
1&0&0&0&\mid&1&\mid&1&0&1&1&\mid&1\\
0&1&0&0&\mid&1&\mid&1&1&1&0&\mid&0\\
0&0&1&0&\mid&0&\mid&1&1&1&1&\mid&0\\
0&0&0&1&\mid&0&\mid&0&1&1&0&\mid&1
\end{pmatrix} 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ∣ ∣ ∣ ∣ 1 1 0 0 ∣ ∣ ∣ ∣ 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 ∣ ∣ ∣ ∣ 1 0 0 1
which, by adding columns 2-3 to columns 7-8, is equivalent to
( 1 0 0 0 ∣ 1 ∥ 1 0 1 1 ∣ 1 0 1 0 0 ∣ 1 ∥ 1 1 1 0 ∣ 0 0 0 1 0 ∣ 0 ∥ 1 1 0 1 ∣ 0 0 0 0 1 ∣ 0 ∥ 0 1 1 0 ∣ 1 ) . \begin{pmatrix}
1&0&0&0&\mid&1&\Vert&1&0&1&1&\mid&1\\
0&1&0&0&\mid&1&\Vert&1&1&1&0&\mid&0\\
0&0&1&0&\mid&0&\Vert&1&1&0&1&\mid&0\\
0&0&0&1&\mid&0&\Vert&0&1&1&0&\mid&1
\end{pmatrix}. 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ∣ ∣ ∣ ∣ 1 1 0 0 ∥ ∥ ∥ ∥ 1 1 1 0 0 1 1 1 1 1 0 1 1 0 1 0 ∣ ∣ ∣ ∣ 1 0 0 1 .
We deduce that
A = ( 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 ) , B = ( 1 1 0 0 ) and C = ( 1 0 0 1 ) . A=\begin{pmatrix}
0&0&1&0\\
0&0&1&1\\
1&1&0&1\\
0&1&1&0
\end{pmatrix},\quad
B=\begin{pmatrix}1\\1\\0\\0\end{pmatrix}
\quad\text{and}\quad
C=\begin{pmatrix}1\\0\\0\\1\end{pmatrix}. A = 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 , B = 1 1 0 0 and C = 1 0 0 1 .
The corresponding graph is given in Figure 2 .
Figure 2. A graph describing a [ 5 , 1 , 3 ] 2 [5,1,3]_2 [ 5 , 1 , 3 ] 2 stabiliser code.
Vice versa, any graph on n + k n+k n + k vertices and two disjoint copies of the empty graph on k k k vertices, with a matching between them and with edges joined to the subset of n − k n-k n − k vertices, gives rise to an [ n , k ] [n,k] [ n , k ] stabiliser code. We call such codes multidimensional graph states . Theorem 4 says that every stabiliser code is equivalent to a multidimensional graph state.
Parity check matrix
Given the standard form
G = ( I n − k ∣ B ∥ A + B C T ∣ C ) G=\left(I_{n-k}\mid B\parallel A+BC^{T}\mid C\right) G = ( I n − k ∣ B ∥ A + B C T ∣ C )
from Theorem 4, we can determine a parity check matrix as follows.
Lemma 6. An [ n , k , d ] [n,k,d] [ n , k , d ] code with stabiliser matrix
G = ( I n − k ∣ B ∥ D ∣ C ) (1) G=\left(I_{n-k}\mid B\parallel D\mid C\right) \tag*{(1)} G = ( I n − k ∣ B ∥ D ∣ C ) (1)
has parity check matrix
H = ( I n − k O D T O O I k C T O O O − B T I k ) H=\begin{pmatrix}
I_{n-k} & O & D^{T} & O\\
O & I_k & C^{T} & O\\
O & O & -B^{T} & I_k
\end{pmatrix} H = I n − k O O O I k O D T C T − B T O O I k
Proof. H H H has full rank and n + k n+k n + k rows. We check that its rows are symplectic orthogonal with those of G G G . We have
G Λ H T = ( I n − k B D C ) ( D C − B O O I k − I n − k O O O − I k O ) = ( D − D C − C − B + B ) = O . G\Lambda H^{T}=
\begin{pmatrix} I_{n-k} & B & D & C \end{pmatrix}
\begin{pmatrix}
D & C & -B\\
O & O & I_k\\
-I_{n-k} & O & O\\
O & -I_k & O
\end{pmatrix}
=
\begin{pmatrix} D-D & C-C & -B+B \end{pmatrix}=O. G Λ H T = ( I n − k B D C ) D O − I n − k O C O O − I k − B I k O O = ( D − D C − C − B + B ) = O .
A parity check matrix is not unique. The following construction has the advantage that the parity check matrix contains G G G .
Lemma 7. An [ n , k , d ] [n,k,d] [ n , k , d ] code with stabiliser matrix
G = ( I n − k B D C ) G=\begin{pmatrix} I_{n-k} & B & D & C \end{pmatrix} G = ( I n − k B D C ) has parity check matrix
H = ( I n − k B D C O I k C T O O O − B T I k ) . H=\begin{pmatrix}
I_{n-k} & B & D & C\\
O & I_k & C^{T} & O\\
O & O & -B^{T} & I_k
\end{pmatrix}. H = I n − k O O B I k O D C T − B T C O I k . Proof. H H H has full rank and n + k n+k n + k rows. The first n − k n-k n − k rows form the matrix G G G itself, which is symplectic self-orthogonal. The remaining 2 k 2k 2 k rows are the same last 2 k 2k 2 k rows as in Lemma 6.
The Calderbank-Shor-Steane construction
The CSS construction of stabiliser codes is a construction of stabiliser codes introduced by Calderbank and Shor [7 ] and Steane [25 ] using two classical linear codes where the dual of one is contained in the other. The stabiliser matrix G G G for this construction has the form
G = ( G 1 O O G 2 ) G=\begin{pmatrix} G_1 & O\\ O & G_2 \end{pmatrix} G = ( G 1 O O G 2 )
where G 1 G_1 G 1 and G 2 G_2 G 2 have full rank and G 1 G 2 T = 0 G_1G_2^{T}=0 G 1 G 2 T = 0 .
We proved in Theorem 4 that an [ [ n , k ] ] [[n,k]] [[ n , k ]] stabiliser code is equivalent to a graph Γ \Gamma Γ on n + k n+k n + k vertices which has two copies of the empty graph on k k k vertices and an induced subgraph on n − k n-k n − k vertices. In the following theorem, we prove that the graph Γ \Gamma Γ for the CSS construction is bipartite.
Theorem 8. A stabiliser matrix is obtained from a CSS construction if and only if, up to equivalence, it is of the form
G = ( I n − k B A + B C T C ) G=\begin{pmatrix} I_{n-k} & B & A+BC^{T} & C \end{pmatrix} G = ( I n − k B A + B C T C ) where
A = ( O A ′ T A ′ O ) , B = ( B ′ O ) and C = ( O C ′ ) . A=\begin{pmatrix} O & A'^{T}\\ A' & O \end{pmatrix},\quad
B=\begin{pmatrix} B'\\ O \end{pmatrix}
\quad\text{and}\quad
C=\begin{pmatrix} O\\ C' \end{pmatrix}. A = ( O A ′ A ′ T O ) , B = ( B ′ O ) and C = ( O C ′ ) .
Proof. Let G = ( G 1 O O G 2 ) G=\left(\begin{array}{c|c}G_1&O\\ \hline O&G_2\end{array}\right) G = ( G 1 O O G 2 ) be a stabiliser matrix constructed using the CSS construction. We can use row operations and a re-ordering of the columns to put it in the form
G ∼ ( I r 1 G 12 G 13 O O O O O O G 21 I r 2 G 23 O O O E O O ) G\sim\left(\begin{array}{c|c|c|c|c|c}
I_{r_1}&G_{12}&G_{13}&O&O&O\\
\hline
O&O&O&G_{21}&I_{r_2}&G_{23}\\
\hline
O&O&O&E&O&O
\end{array}\right) G ∼ I r 1 O O G 12 O O G 13 O O O G 21 E O I r 2 O O G 23 O
where r 1 r_1 r 1 is the rank of G 1 G_1 G 1 and r 2 + rank ( E ) r_2+\operatorname{rank}(E) r 2 + rank ( E ) is the rank of G 2 G_2 G 2 . Since the symplectic inner product of the i i i -th row (i ∈ { 1 , … , r 1 } i\in\{1,\ldots,r_1\} i ∈ { 1 , … , r 1 } ) and the j j j -th row (j ∈ { r 1 + r 2 + 1 , … , n − k } j\in\{r_1+r_2+1,\ldots,n-k\} j ∈ { r 1 + r 2 + 1 , … , n − k } ) is zero, we deduce that E = O E=O E = O and r 1 + r 2 = n − k r_1+r_2=n-k r 1 + r 2 = n − k . Swapping (and adding a minus sign on one side) the i i i th and ( n + i ) (n+i) ( n + i ) th column for all i ∈ { r 1 + 1 , … , r 1 + r 2 } i\in\{r_1+1,\ldots,r_1+r_2\} i ∈ { r 1 + 1 , … , r 1 + r 2 } , we obtain
G ∼ ( I r 1 O G 13 O − G 12 O O I r 2 O G 21 O G 23 ) . G\sim\left(\begin{array}{c|c|c|c|c|c}
I_{r_1}&O&G_{13}&O&-G_{12}&O\\
\hline
O&I_{r_2}&O&G_{21}&O&G_{23}
\end{array}\right). G ∼ ( I r 1 O O I r 2 G 13 O O G 21 − G 12 O O G 23 ) .
Comparing this matrix with the matrix from Theorem 4, we get
A = ( O − G 12 − G 13 G 23 T G 21 O ) , B = ( G 13 O ) and C = ( O G 23 ) , A=\left(\begin{array}{c|c}
O&-G_{12}-G_{13}G_{23}^{T}\\
\hline
G_{21}&O
\end{array}\right),\quad
B=\left(\begin{array}{c}
G_{13}\\
\hline
O
\end{array}\right)
\quad\text{and}\quad
C=\left(\begin{array}{c}
O\\
\hline
G_{23}
\end{array}\right), A = ( O G 21 − G 12 − G 13 G 23 T O ) , B = ( G 13 O ) and C = ( O G 23 ) ,
and A A A is symmetric. By doing the inverse operations, a stabiliser matrix is of the given form can be obtained from the CSS construction with G 1 = ( I r 1 ∣ − A T − B ′ C ′ T ∣ B ′ ) G_1=\left(I_{r_1}\mid-A^{T}-B'C'^{T}\mid B'\right) G 1 = ( I r 1 ∣ − A T − B ′ C ′ T ∣ B ′ ) and G 2 = ( A ′ ∣ I r 2 ∣ C ′ ) G_2=\left(A'\mid I_{r_2}\mid C'\right) G 2 = ( A ′ ∣ I r 2 ∣ C ′ ) .
As in the discussion after the proof of Theorem 4, we can interpret A A A as describing an induced subgraph Γ A \Gamma_A Γ A of a graph Γ \Gamma Γ on n + k n+k n + k vertices. For the CSS construction, Theorem 8 implies that the graph Γ A \Gamma_A Γ A is bipartite with bipartitions of size r 1 r_1 r 1 and r 2 r_2 r 2 . The graph Γ \Gamma Γ is bipartite with bipartitions of size r 1 + k r_1+k r 1 + k and r 2 + k r_2+k r 2 + k , where each bipartition contains an independent set on k k k vertices.
Example 9. The Steane code is a [ [ 7 , 1 , 3 ] ] 2 [[7,1,3]]_2 [[ 7 , 1 , 3 ] ] 2 stabiliser code, obtained via a CSS construction where
G 1 = G 2 = ( 1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 ) G_1=G_2=\left(\begin{array}{ccccccc}
1&0&0&1&0&1&1\\
0&1&0&1&1&1&0\\
0&0&1&0&1&1&1
\end{array}\right) G 1 = G 2 = 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1
is the parity check matrix of the binary [ 7 , 4 , 3 ] [7,4,3] [ 7 , 4 , 3 ] Hamming code. Its stabiliser matrix is
G = ( 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 ) . G=\left(\begin{array}{ccccccc|ccccccc}
1&0&0&1&0&1&1&0&0&0&0&0&0&0\\
0&1&0&1&1&1&0&0&0&0&0&0&0&0\\
0&0&1&0&1&1&1&0&0&0&0&0&0&0\\
\hline
0&0&0&0&0&0&0&1&0&1&0&1&1&1\\
0&0&0&0&0&0&0&0&1&0&1&1&1&0\\
0&0&0&0&0&0&0&0&0&1&0&1&1&1
\end{array}\right). G = 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 1 .
By elementary row operations on the last three rows, we get
G ∼ ( 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 1 0 ) . G\sim\left(\begin{array}{ccccccc|ccccccc}
1&0&0&1&0&1&1&0&0&0&0&0&0&0\\
0&1&0&1&1&1&0&0&0&0&0&0&0&0\\
0&0&1&0&1&1&1&0&0&0&0&0&0&0\\
\hline
0&0&0&0&0&0&0&0&1&1&1&0&0&1\\
0&0&0&0&0&0&0&1&1&0&0&1&0&1\\
0&0&0&0&0&0&0&1&1&1&0&0&1&0
\end{array}\right). G ∼ 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 .
Switching columns 4, 5 and 6 with columns 11, 12 and 13 respectively, we get
G ∼ ( 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 ) . G \sim\left(\begin{array}{cccccc|cccccccc}
1&0&0&0&0&0&1&0&0&0&1&0&1&0\\
0&1&0&0&0&0&0&0&0&0&1&1&1&0\\
0&0&1&0&0&0&1&0&0&0&0&1&1&0\\
0&0&0&1&0&0&0&0&1&1&0&0&0&1\\
0&0&0&0&1&0&0&1&1&0&0&0&0&1\\
0&0&0&0&0&1&0&1&1&1&0&0&0&0
\end{array}\right). G ∼ 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 .
Using the notation of Theorem 4 , we have
A = ( 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 ) , B = ( 1 0 1 0 0 0 ) and C = ( 0 0 0 1 1 0 ) . A=\left(\begin{array}{cccccc}
0&0&0&0&1&1\\
0&0&0&1&1&1\\
0&0&0&1&0&1\\
0&1&1&0&0&0\\
1&1&0&0&0&0\\
1&1&1&0&0&0
\end{array}\right),\quad
B=\left(\begin{array}{c}1\\0\\1\\0\\0\\0\end{array}\right)
\quad\text{and}\quad
C=\left(\begin{array}{c}0\\0\\0\\1\\1\\0\end{array}\right). A = 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 , B = 1 0 1 0 0 0 and C = 0 0 0 1 1 0 .
Therefore, the Steane code is given by the bipartite graph in Figure 3 .
Figure 3. A graph describing the [ [ 7 , 1 , 3 ] ] 2 [[7,1,3]]_{2} [[ 7 , 1 , 3 ] ] 2 Steane code.
Local complementation
We define two graphs to be stabiliser-equivalent if they give rise to equivalent stabiliser codes. Recall that two stabiliser codes are equivalent if they can be obtained from one another by permutations of the n n n pairs of positions, and, for each pair, a symplectic transformation on that pair.
In the case k = 0 k=0 k = 0 and p = 2 p=2 p = 2 , equivalent graph states have attracted attention in [9 , 23 , 26 ] for example. For k = 0 k=0 k = 0 and general primes p p p , Bahramgiri and Beigi [5 ] , Theorem 5] describe this stabiliser-equivalence as a sequence of graph operations. Let A = ( a i j ) i , j ∈ { 1 , … , n } A=(a_{ij})_{i,j\in\{1,\ldots,n\}} A = ( a ij ) i , j ∈ { 1 , … , n } denote the adjacency matrix of a graph G G G whose edges have weights over F p = Z / p Z \mathbb{F}_{p}=\mathbb{Z}/p\mathbb{Z} F p = Z / p Z . For every vertex m ∈ { 1 , … , n } m\in\{1,\ldots,n\} m ∈ { 1 , … , n } and constant λ ∈ F p ∖ { 0 } \lambda\in\mathbb{F}_{p}\setminus\{0\} λ ∈ F p ∖ { 0 } , consider the following local complementation operations on the stabiliser matrix:
Weighted local complementation:
a i j ↦ a i j ′ = a i j + a m i a m j for all i , j ∈ { 1 , … , n } , i ≠ j . a_{ij}\mapsto a'_{ij}=a_{ij}+a_{mi}a_{mj}\quad\text{for all }i,j\in\{1,\ldots,n\},\ i\ne j. a ij ↦ a ij ′ = a ij + a mi a mj for all i , j ∈ { 1 , … , n } , i = j .
Rescaling the neighbourhood:
a i j ↦ a i j ′ = { λ a i j if m ∈ { i , j } , a i j else. for all i , j ∈ { 1 , … , n } . a_{ij} \mapsto a'_{ij} =
\begin{cases}
\lambda a_{ij} & \text{if } m \in\{i,j\},\\
a_{ij} & \text{else.}
\end{cases}
\qquad\text{for all } i,j \in\{1,\ldots,n\}. a ij ↦ a ij ′ = { λ a ij a ij if m ∈ { i , j } , else. for all i , j ∈ { 1 , … , n } .
They correspond to the following operations on the stabiliser code S S S :
replacing ( v m , v n + m ) (v_m,v_{n+m}) ( v m , v n + m ) by ( v m − v n + m , v n + m ) (v_m-v_{n+m},v_{n+m}) ( v m − v n + m , v n + m ) within every vector v ∈ S \mathbf{v} \in S v ∈ S ,
replacing ( v m , v n + m ) (v_m,v_{n+m}) ( v m , v n + m ) by ( λ − 1 v m , λ v n + m ) (\lambda^{-1}v_m,\lambda v_{n+m}) ( λ − 1 v m , λ v n + m ) within every vector v ∈ S \mathbf{v} \in S v ∈ S ,
and after each operation, putting the stabiliser matrix back in the standard form
G = ( I n ∣ A ) G=(I_n \mid A) G = ( I n ∣ A )
through row operations, and, in the case of weighted local complementation, making the diagonal of A A A zero again by replacing ( v i , v n + i ) (v_i,v_{n+i}) ( v i , v n + i ) with ( v i , v n + i − a m i 2 v i ) (v_i,v_{n+i}-a_{mi}^{2}v_i) ( v i , v n + i − a mi 2 v i ) within every vector v ∈ S \mathbf{v} \in S v ∈ S , for all i ≠ m i \ne m i = m . These two types of operations are enough to generate the entire local Clifford group:
Theorem 10 ([5 Theorem 5] ). Two (one-dimensional) graph states are equivalent if and only if there exists a sequence of local complementation operations to obtain one from the other.
Stabiliser-equivalence for multidimensional graph states
In this section, we work out what equivalence means for the multidimensional case. Recall from Theorem 4 that an [ [ n , k ] ] [[n,k]] [[ n , k ]] stabiliser code corresponds to a graph Γ \Gamma Γ on n + k n+k n + k vertices, containing two independent sets of size k k k with a matching between them. More precisely, Γ = ( V , E ) \Gamma=(V,E) Γ = ( V , E ) with V = V A ⊔ V B ⊔ V C V=V_A \sqcup V_B \sqcup V_C V = V A ⊔ V B ⊔ V C such that ∣ V A ∣ = n − k |V_A|=n-k ∣ V A ∣ = n − k and ∣ V B ∣ = ∣ V C ∣ = k |V_B|=|V_C|=k ∣ V B ∣ = ∣ V C ∣ = k . The induced graphs on V B V_B V B and V C V_C V C are empty and there is a non-weighted matching between V B V_B V B and V C V_C V C . This graph should be regarded as unlabelled on the vertices within each of the parts V A V_A V A , V B V_B V B and V C V_C V C , but this partition (colouring) is fixed. In particular, we cannot simply interchange the B B B and C C C parts.
Recall that we can always put the stabiliser matrix in the form
( 1 ⋯ 0 b 11 ⋯ b 1 k a 11 + ∑ i = 1 k b 1 i c 1 i ⋯ a 1 r + ∑ i = 1 k b 1 i c r i c 11 ⋯ c 1 k ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ 0 ⋯ 1 b r 1 ⋯ b r k a r 1 + ∑ i = 1 k b r i c 1 i ⋯ a r r + ∑ i = 1 k b r i c r i c r 1 ⋯ c r k ) \left(
\begin{array}{cccc|cccc|cccc}
1 & \cdots& 0 & b_{11} & \cdots& b_{1k} & a_{11}+\sum_{i=1}^{k}b_{1i}c_{1i} & \cdots& a_{1r}+\sum_{i=1}^{k}b_{1i}c_{ri} & c_{11} & \cdots& c_{1k}\\
\vdots& \ddots& \vdots& \vdots& & \vdots& \vdots& \ddots& \vdots& \vdots& & \vdots\\
0 & \cdots& 1 & b_{r1} & \cdots& b_{rk} & a_{r1}+\sum_{i=1}^{k}b_{ri}c_{1i} & \cdots& a_{rr}+\sum_{i=1}^{k}b_{ri}c_{ri} & c_{r1} & \cdots& c_{rk}
\end{array}
\right) 1 ⋮ 0 ⋯ ⋱ ⋯ 0 ⋮ 1 b 11 ⋮ b r 1 ⋯ ⋯ b 1 k ⋮ b r k a 11 + ∑ i = 1 k b 1 i c 1 i ⋮ a r 1 + ∑ i = 1 k b r i c 1 i ⋯ ⋱ ⋯ a 1 r + ∑ i = 1 k b 1 i c r i ⋮ a r r + ∑ i = 1 k b r i c r i c 11 ⋮ c r 1 ⋯ ⋯ c 1 k ⋮ c r k
and label the vertices of the graph as follows:
V A = { a 1 , … , a r } , V_A=\{a_1,\ldots,a_r\}, V A = { a 1 , … , a r } ,
V B = { b 1 , … , b k } , V_B=\{b_1,\ldots,b_k\}, V B = { b 1 , … , b k } ,
V C = { c 1 , … , c k } . V_C=\{c_1,\ldots,c_k\}. V C = { c 1 , … , c k } .
We consider three operations, and prove that a successive application of these three is enough to obtain every equivalent multidimensional graph state, similar to [5 Theorem 5] .
Note that isomorphic graphs (but with the same ( V A , V B , V C ) (V_A,V_B,V_C) ( V A , V B , V C ) partition) are equivalent. This corresponds to permutations of the pairs of positions. In what follows, isomorphic graphs are considered as the same.
Theorem 11. Two multidimensional graph states are equivalent if and only if they can be obtained from one another through a sequence of the following operations.
(Local complementation on a vertex of V B V_B V B or V C V_C V C ). Given b s ∈ V B b_s \in V_B b s ∈ V B , do
{ a i j ↦ a i j ′ = a i j + b i s b j s for all i , j ∈ { 1 , … , r } , i ≠ j , c i s ↦ c i s ′ = c i s − b i s for all i ∈ { 1 , … , r } . \begin{cases}
a_{ij} \mapsto a'_{ij}=a_{ij}+b_{is}b_{js} & \text{for all } i,j\in\{1,\ldots,r\},\ i\ne j,\\
c_{is} \mapsto c'_{is}=c_{is}-b_{is} & \text{for all } i\in\{1,\ldots,r\}.
\end{cases} { a ij ↦ a ij ′ = a ij + b i s b j s c i s ↦ c i s ′ = c i s − b i s for all i , j ∈ { 1 , … , r } , i = j , for all i ∈ { 1 , … , r } . Similarly for a vertex c s ∈ V C c_s\in V_C c s ∈ V C .
In particular, we can always make a given vertex of V A V_A V A non-adjacent to a given vertex of V C V_C V C (or V B V_B V B ).
(Local complementation on a vertex of V A V_A V A ). Given a m ∈ V A a_m\in V_A a m ∈ V A , if c m j = 0 c_{mj}=0 c mj = 0 for all j ∈ { 1 , … , k } j\in\{1,\ldots,k\} j ∈ { 1 , … , k } (which can always be accomplished by operation 1), do one of the following operations:
(a) Weighted complementation:
{ a i j ↦ a i j ′ = a i j + a m i a m j for all i , j ∈ { 1 , … , r } , i ≠ j , b i j ↦ b i j ′ = b i j + a m i b m j for all i ∈ { 1 , … , r } and j ∈ { 1 , … , k } . \begin{cases}
a_{ij} \mapsto a'_{ij}=a_{ij}+a_{mi}a_{mj} & \text{for all } i,j\in\{1,\ldots,r\},\ i\ne j,\\
b_{ij} \mapsto b'_{ij}=b_{ij}+a_{mi}b_{mj} & \text{for all } i\in\{1,\ldots,r\}\text{ and }j\in\{1,\ldots,k\}.
\end{cases} { a ij ↦ a ij ′ = a ij + a mi a mj b ij ↦ b ij ′ = b ij + a mi b mj for all i , j ∈ { 1 , … , r } , i = j , for all i ∈ { 1 , … , r } and j ∈ { 1 , … , k } . (b) Rescaling the neighbourhood with λ ∈ F p ∖ { 0 } \lambda\in\mathbb{F}_p\setminus\{0\} λ ∈ F p ∖ { 0 } :
{ a i j ↦ { λ a i j if m ∈ { i , j } , a i j else for all i , j ∈ { 1 , … , r } , i ≠ j , b i j ↦ { λ b i j if m = i , b i j else for all i ∈ { 1 , … , r } and j ∈ { 1 , … , k } . \begin{cases}
a_{ij}\mapsto
\begin{cases}
\lambda a_{ij} & \text{if }m\in\{i,j\},\\
a_{ij} & \text{else}
\end{cases}
& \text{for all }i,j\in\{1,\ldots,r\},\ i\ne j,\\
b_{ij}\mapsto
\begin{cases}
\lambda b_{ij} & \text{if }m=i,\\
b_{ij} & \text{else}
\end{cases}
& \text{for all }i\in\{1,\ldots,r\}\text{ and }j\in\{1,\ldots,k\}.
\end{cases} ⎩ ⎨ ⎧ a ij ↦ { λ a ij a ij if m ∈ { i , j } , else b ij ↦ { λ b ij b ij if m = i , else for all i , j ∈ { 1 , … , r } , i = j , for all i ∈ { 1 , … , r } and j ∈ { 1 , … , k } . (Swapping a vertex of V A V_A V A with a vertex of V C V_C V C ). Given a m ∈ V A a_m\in V_A a m ∈ V A and c s ∈ V C c_s\in V_C c s ∈ V C , if c m j = 0 c_{mj}=0 c mj = 0 for all j ∈ { 1 , … , k } j\in\{1,\ldots,k\} j ∈ { 1 , … , k } and b m s = 1 b_{ms}=1 b m s = 1 (which can always be accomplished by operation 1), swap a m a_m a m and c s c_s c s (only edges between V A V_A V A and V C V_C V C are affected by this swap), and change the weights of the edges between V A V_A V A and V B V_B V B as follows:
b i j ↦ b i j ′ = { b i j if m = i , − b i j if m ≠ i and s = j , b i j − b i s b m j else b_{ij}\mapsto b'_{ij}=
\begin{cases}
b_{ij} & \text{if }m=i,\\
-b_{ij} & \text{if }m\ne i\text{ and }s=j,\\
b_{ij}-b_{is}b_{mj} & \text{else}
\end{cases} b ij ↦ b ij ′ = ⎩ ⎨ ⎧ b ij − b ij b ij − b i s b mj if m = i , if m = i and s = j , else for all i ∈ { 1 , … , r } i\in\{1,\ldots,r\} i ∈ { 1 , … , r } and j ∈ { 1 , … , k } j\in\{1,\ldots,k\} j ∈ { 1 , … , k } .
Proof. We show that the first operation corresponds to adding the first column of B B B to the first column of C C C , that the second operation achieves local equivalence on Γ A \Gamma_A Γ A , and that the third one arises from a transposition of a pair on the first n − k n-k n − k positions and a pair on the last k k k positions.
Without loss of generality, we may assume that s = 1 s=1 s = 1 . Subtracting the first column of B B B from the first column of C C C gives
( 1 ⋯ 0 b 11 ⋯ b 1 k a 11 + ∑ i = 1 k b 1 i c 1 i ⋯ a 1 r + ∑ i = 1 k b 1 i c r i c 11 − b 11 c 12 ⋯ c 1 k ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ 0 ⋯ 1 b r 1 ⋯ b r k a r 1 + ∑ i = 1 k b r i c 1 i ⋯ a r r + ∑ i = 1 k b r i c r i c r 1 − b r 1 c r 2 ⋯ c r k ) . (2) \left(
\begin{array}{cccc|ccccc||cccc}
1 & \cdots& 0 & b_{11} & \cdots& b_{1k} & a_{11}+\sum_{i=1}^{k}b_{1i}c_{1i} & \cdots& a_{1r}+\sum_{i=1}^{k}b_{1i}c_{ri} & c_{11}-b_{11} & c_{12} & \cdots& c_{1k}\\
\vdots& \ddots& \vdots& \vdots& & \vdots& \vdots& \ddots& \vdots& \vdots& \vdots& & \vdots\\
0 & \cdots& 1 & b_{r1} & \cdots& b_{rk} & a_{r1}+\sum_{i=1}^{k}b_{ri}c_{1i} & \cdots& a_{rr}+\sum_{i=1}^{k}b_{ri}c_{ri} & c_{r1}-b_{r1} & c_{r2} & \cdots& c_{rk}
\end{array}
\right). \tag*{(2)} 1 ⋮ 0 ⋯ ⋱ ⋯ 0 ⋮ 1 b 11 ⋮ b r 1 ⋯ ⋯ b 1 k ⋮ b r k a 11 + ∑ i = 1 k b 1 i c 1 i ⋮ a r 1 + ∑ i = 1 k b r i c 1 i ⋯ ⋱ ⋯ a 1 r + ∑ i = 1 k b 1 i c r i ⋮ a r r + ∑ i = 1 k b r i c r i c 11 − b 11 ⋮ c r 1 − b r 1 c 12 ⋮ c r 2 ⋯ ⋯ c 1 k ⋮ c r k . (2)
Writing a i j ′ = a i j + b i 1 b j 1 a'_{ij}=a_{ij}+b_{i1}b_{j1} a ij ′ = a ij + b i 1 b j 1 and c i 1 ′ = c i 1 − b i 1 c'_{i1}=c_{i1}-b_{i1} c i 1 ′ = c i 1 − b i 1 , this is equal to
( 1 ⋯ 0 b 11 ⋯ b 1 k a 11 ′ + ∑ i = 1 k b 1 i c 1 i ′ ⋯ a 1 r ′ + ∑ i = 1 k b 1 i c r i ′ c 11 ′ ⋯ c 1 k ′ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ 0 ⋯ 1 b r 1 ⋯ b r k a r 1 ′ + ∑ i = 1 k b r i c 1 i ′ ⋯ a r r ′ + ∑ i = 1 k b r i c r i ′ c r 1 ′ ⋯ c r k ′ ) . \begin{pmatrix}
1 & \cdots& 0 & b_{11} & \cdots& b_{1k} & a'_{11}+\sum_{i=1}^{k}b_{1i}c'_{1i} & \cdots& a'_{1r}+\sum_{i=1}^{k}b_{1i}c'_{ri} & c'_{11} & \cdots& c'_{1k}\\
\vdots& \ddots& \vdots& \vdots& & \vdots& \vdots& \ddots& \vdots& \vdots& & \vdots\\
0 & \cdots& 1 & b_{r1} & \cdots& b_{rk} & a'_{r1}+\sum_{i=1}^{k}b_{ri}c'_{1i} & \cdots& a'_{rr}+\sum_{i=1}^{k}b_{ri}c'_{ri} & c'_{r1} & \cdots& c'_{rk}
\end{pmatrix}. 1 ⋮ 0 ⋯ ⋱ ⋯ 0 ⋮ 1 b 11 ⋮ b r 1 ⋯ ⋯ b 1 k ⋮ b r k a 11 ′ + ∑ i = 1 k b 1 i c 1 i ′ ⋮ a r 1 ′ + ∑ i = 1 k b r i c 1 i ′ ⋯ ⋱ ⋯ a 1 r ′ + ∑ i = 1 k b 1 i c r i ′ ⋮ a r r ′ + ∑ i = 1 k b r i c r i ′ c 11 ′ ⋮ c r 1 ′ ⋯ ⋯ c 1 k ′ ⋮ c r k ′ .
Without loss of generality, we may assume that m = 1 m=1 m = 1 . Since c 1 j = 0 c_{1j}=0 c 1 j = 0 for all j ∈ { 1 , … , k } j\in\{1,\ldots,k\} j ∈ { 1 , … , k } and a 11 = 0 a_{11}=0 a 11 = 0 , the stabiliser matrix is given by
( 1 0 ⋯ 0 b 11 ⋯ b 1 k 0 a 12 + ∑ i = 1 k b 1 i c 2 i ⋯ a 1 r + ∑ i = 1 k b 1 i c r i 0 ⋯ 0 0 1 ⋯ 0 b 21 ⋯ b 2 k a 21 a 22 + ∑ i = 1 k b 2 i c 2 i ⋯ a 2 r + ∑ i = 1 k b 2 i c r i c 21 ⋯ c 2 r ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ 0 0 ⋯ 1 b r 1 ⋯ b r k a r 1 a r 2 + ∑ i = 1 k b r i c 2 i ⋯ a r r + ∑ i = 1 k b r i c r i c r 1 ⋯ c r k ) . \begin{pmatrix}
1 & 0 & \cdots& 0 & b_{11} & \cdots& b_{1k} & 0 & a_{12}+\sum_{i=1}^{k}b_{1i}c_{2i} & \cdots& a_{1r}+\sum_{i=1}^{k}b_{1i}c_{ri} & 0 & \cdots& 0\\
0 & 1 & \cdots& 0 & b_{21} & \cdots& b_{2k} & a_{21} & a_{22}+\sum_{i=1}^{k}b_{2i}c_{2i} & \cdots& a_{2r}+\sum_{i=1}^{k}b_{2i}c_{ri} & c_{21} & \cdots& c_{2r}\\
\vdots& \vdots& \ddots& \vdots& \vdots& & \vdots& \vdots& \ddots& \vdots& \vdots& & \vdots\\
0 & 0 & \cdots& 1 & b_{r1} & \cdots& b_{rk} & a_{r1} & a_{r2}+\sum_{i=1}^{k}b_{ri}c_{2i} & \cdots& a_{rr}+\sum_{i=1}^{k}b_{ri}c_{ri} & c_{r1} & \cdots& c_{rk}
\end{pmatrix}. 1 0 ⋮ 0 0 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ 1 b 11 b 21 ⋮ b r 1 ⋯ ⋯ ⋯ b 1 k b 2 k ⋮ b r k 0 a 21 ⋮ a r 1 a 12 + ∑ i = 1 k b 1 i c 2 i a 22 + ∑ i = 1 k b 2 i c 2 i ⋱ a r 2 + ∑ i = 1 k b r i c 2 i ⋯ ⋯ ⋮ ⋯ a 1 r + ∑ i = 1 k b 1 i c r i a 2 r + ∑ i = 1 k b 2 i c r i ⋮ a r r + ∑ i = 1 k b r i c r i 0 c 21 c r 1 ⋯ ⋯ ⋮ ⋯ 0 c 2 r c r k .
(a) Subtracting column n + 1 n+1 n + 1 from column 1 gives the matrix
( 1 0 ⋯ 0 b 11 ⋯ b 1 k 0 a 12 + ∑ i = 1 k b 1 i c 2 i ⋯ a 1 r + ∑ i = 1 k b 1 i c r i 0 ⋯ 0 − a 12 1 ⋯ 0 b 21 ⋯ b 2 k a 21 a 22 + ∑ i = 1 k b 2 i c 2 i ⋯ a 2 r + ∑ i = 1 k b 2 i c r i c 21 ⋯ c 2 r ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ − a 1 r 0 ⋯ 1 b r 1 ⋯ b r k a r 1 a r 2 + ∑ i = 1 k b r i c 2 i ⋯ a r r + ∑ i = 1 k b r i c r i c r 1 ⋯ c r k ) , \begin{pmatrix}
1 & 0 & \cdots& 0 & b_{11} & \cdots& b_{1k} & 0 & a_{12}+\sum_{i=1}^{k}b_{1i}c_{2i} & \cdots& a_{1r}+\sum_{i=1}^{k}b_{1i}c_{ri} & 0 & \cdots& 0\\
-a_{12} & 1 & \cdots& 0 & b_{21} & \cdots& b_{2k} & a_{21} & a_{22}+\sum_{i=1}^{k}b_{2i}c_{2i} & \cdots& a_{2r}+\sum_{i=1}^{k}b_{2i}c_{ri} & c_{21} & \cdots& c_{2r}\\
\vdots& \vdots& \ddots& \vdots& \vdots& & \vdots& \vdots& \ddots& \vdots& \vdots& & \vdots\\
-a_{1r} & 0 & \cdots& 1 & b_{r1} & \cdots& b_{rk} & a_{r1} & a_{r2}+\sum_{i=1}^{k}b_{ri}c_{2i} & \cdots& a_{rr}+\sum_{i=1}^{k}b_{ri}c_{ri} & c_{r1} & \cdots& c_{rk}
\end{pmatrix}, 1 − a 12 ⋮ − a 1 r 0 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ 1 b 11 b 21 ⋮ b r 1 ⋯ ⋯ ⋯ b 1 k b 2 k ⋮ b r k 0 a 21 ⋮ a r 1 a 12 + ∑ i = 1 k b 1 i c 2 i a 22 + ∑ i = 1 k b 2 i c 2 i ⋱ a r 2 + ∑ i = 1 k b r i c 2 i ⋯ ⋯ ⋮ ⋯ a 1 r + ∑ i = 1 k b 1 i c r i a 2 r + ∑ i = 1 k b 2 i c r i ⋮ a r r + ∑ i = 1 k b r i c r i 0 c 21 c r 1 ⋯ ⋯ ⋮ ⋯ 0 c 2 r c r k ,
which, after row operations, becomes
( 1 0 ⋯ 0 b 11 ′ ⋯ b 1 k ′ a 11 ′ a 12 ′ + ∑ i = 1 k b 1 i ′ c 2 i ⋯ a 1 r ′ + ∑ i = 1 k b 1 i ′ c r i 0 ⋯ 0 0 1 ⋯ 0 b 21 ′ ⋯ b 2 k ′ a 21 ′ a 22 ′ + ∑ i = 1 k b 2 i ′ c 2 i ⋯ a 2 r ′ + ∑ i = 1 k b 2 i ′ c r i c 21 ⋯ c 2 r ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ 0 0 ⋯ 1 b r 1 ′ ⋯ b r k ′ a r 1 ′ a r 2 ′ + ∑ i = 1 k b r i ′ c 2 i ⋯ a r r ′ + ∑ i = 1 k b r i ′ c r i c r 1 ⋯ c r k ) , \begin{pmatrix}
1 & 0 & \cdots& 0 & b'_{11} & \cdots& b'_{1k} & a'_{11} & a'_{12}+\sum_{i=1}^{k}b'_{1i}c_{2i} & \cdots& a'_{1r}+\sum_{i=1}^{k}b'_{1i}c_{ri} & 0 & \cdots& 0\\
0 & 1 & \cdots& 0 & b'_{21} & \cdots& b'_{2k} & a'_{21} & a'_{22}+\sum_{i=1}^{k}b'_{2i}c_{2i} & \cdots& a'_{2r}+\sum_{i=1}^{k}b'_{2i}c_{ri} & c_{21} & \cdots& c_{2r}\\
\vdots& \vdots& \ddots& \vdots& \vdots& & \vdots& \vdots& \ddots& \vdots& \vdots& & \vdots\\
0 & 0 & \cdots& 1 & b'_{r1} & \cdots& b'_{rk} & a'_{r1} & a'_{r2}+\sum_{i=1}^{k}b'_{ri}c_{2i} & \cdots& a'_{rr}+\sum_{i=1}^{k}b'_{ri}c_{ri} & c_{r1} & \cdots& c_{rk}
\end{pmatrix}, 1 0 ⋮ 0 0 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ 1 b 11 ′ b 21 ′ ⋮ b r 1 ′ ⋯ ⋯ ⋯ b 1 k ′ b 2 k ′ ⋮ b r k ′ a 11 ′ a 21 ′ ⋮ a r 1 ′ a 12 ′ + ∑ i = 1 k b 1 i ′ c 2 i a 22 ′ + ∑ i = 1 k b 2 i ′ c 2 i ⋱ a r 2 ′ + ∑ i = 1 k b r i ′ c 2 i ⋯ ⋯ ⋮ ⋯ a 1 r ′ + ∑ i = 1 k b 1 i ′ c r i a 2 r ′ + ∑ i = 1 k b 2 i ′ c r i ⋮ a r r ′ + ∑ i = 1 k b r i ′ c r i 0 c 21 c r 1 ⋯ ⋯ ⋮ ⋯ 0 c 2 r c r k ,
where a i j ′ = a i j + a 1 i a 1 j a'_{ij}=a_{ij}+a_{1i}a_{1j} a ij ′ = a ij + a 1 i a 1 j and b i j ′ = b i j + a 1 i b 1 j b'_{ij}=b_{ij}+a_{1i}b_{1j} b ij ′ = b ij + a 1 i b 1 j . After making the diagonal entries of A ′ A' A ′ equal to zero, this is a graph state.
(b) Multiplying column 1 by λ − 1 \lambda^{-1} λ − 1 and multiplying column n + 1 n+1 n + 1 by λ \lambda λ , yields the matrix
( λ − 1 0 ⋯ 0 b 11 ⋯ b 1 k 0 a 12 + ∑ i = 1 k b 1 i c 2 i ⋯ a 1 r + ∑ i = 1 k b 1 i c r i 0 ⋯ 0 0 1 ⋯ 0 b 21 ⋯ b 2 k λ a 21 a 22 + ∑ i = 1 k b 2 i c 2 i ⋯ a 2 r + ∑ i = 1 k b 2 i c r i c 21 ⋯ c 2 r ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ 0 0 ⋯ 1 b r 1 ⋯ b r k λ a r 1 a r 2 + ∑ i = 1 k b r i c 2 i ⋯ a r r + ∑ i = 1 k b r i c r i c r 1 ⋯ c r k ) . \begin{pmatrix}
\lambda^{-1} & 0 & \cdots& 0 & b_{11} & \cdots& b_{1k} & 0 & a_{12}+\sum_{i=1}^{k}b_{1i}c_{2i} & \cdots& a_{1r}+\sum_{i=1}^{k}b_{1i}c_{ri} & 0 & \cdots& 0\\
0 & 1 & \cdots& 0 & b_{21} & \cdots& b_{2k} & \lambda a_{21} & a_{22}+\sum_{i=1}^{k}b_{2i}c_{2i} & \cdots& a_{2r}+\sum_{i=1}^{k}b_{2i}c_{ri} & c_{21} & \cdots& c_{2r}\\
\vdots& \vdots& \ddots& \vdots& \vdots& & \vdots& \vdots& \ddots& \vdots& \vdots& & \vdots\\
0 & 0 & \cdots& 1 & b_{r1} & \cdots& b_{rk} & \lambda a_{r1} & a_{r2}+\sum_{i=1}^{k}b_{ri}c_{2i} & \cdots& a_{rr}+\sum_{i=1}^{k}b_{ri}c_{ri} & c_{r1} & \cdots& c_{rk}
\end{pmatrix}. λ − 1 0 ⋮ 0 0 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ 1 b 11 b 21 ⋮ b r 1 ⋯ ⋯ ⋯ b 1 k b 2 k ⋮ b r k 0 λ a 21 ⋮ λ a r 1 a 12 + ∑ i = 1 k b 1 i c 2 i a 22 + ∑ i = 1 k b 2 i c 2 i ⋱ a r 2 + ∑ i = 1 k b r i c 2 i ⋯ ⋯ ⋮ ⋯ a 1 r + ∑ i = 1 k b 1 i c r i a 2 r + ∑ i = 1 k b 2 i c r i ⋮ a r r + ∑ i = 1 k b r i c r i 0 c 21 c r 1 ⋯ ⋯ ⋮ ⋯ 0 c 2 r c r k .
Multiplying the first row by λ \lambda λ , we get
( 1 0 ⋯ 0 λ b 11 ⋯ λ b 1 k 0 λ a 12 + ∑ i = 1 k λ b 1 i c 2 i ⋯ λ a 1 r + ∑ i = 1 k λ b 1 i c r i 0 ⋯ 0 0 1 ⋯ 0 b 21 ⋯ b 2 k λ a 21 a 22 + ∑ i = 1 k b 2 i c 2 i ⋯ a 2 r + ∑ i = 1 k b 2 i c r i c 21 ⋯ c 2 r ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ 0 0 ⋯ 1 b r 1 ⋯ b r k λ a r 1 a r 2 + ∑ i = 1 k b r i c 2 i ⋯ a r r + ∑ i = 1 k b r i c r i c r 1 ⋯ c r k ) . \begin{pmatrix}
1 & 0 & \cdots& 0 & \lambda b_{11} & \cdots& \lambda b_{1k} & 0 & \lambda a_{12}+\sum_{i=1}^{k}\lambda b_{1i}c_{2i} & \cdots& \lambda a_{1r}+\sum_{i=1}^{k}\lambda b_{1i}c_{ri} & 0 & \cdots& 0\\
0 & 1 & \cdots& 0 & b_{21} & \cdots& b_{2k} & \lambda a_{21} & a_{22}+\sum_{i=1}^{k}b_{2i}c_{2i} & \cdots& a_{2r}+\sum_{i=1}^{k}b_{2i}c_{ri} & c_{21} & \cdots& c_{2r}\\
\vdots& \vdots& \ddots& \vdots& \vdots& & \vdots& \vdots& \ddots& \vdots& \vdots& & \vdots\\
0 & 0 & \cdots& 1 & b_{r1} & \cdots& b_{rk} & \lambda a_{r1} & a_{r2}+\sum_{i=1}^{k}b_{ri}c_{2i} & \cdots& a_{rr}+\sum_{i=1}^{k}b_{ri}c_{ri} & c_{r1} & \cdots& c_{rk}
\end{pmatrix}. 1 0 ⋮ 0 0 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ 1 λ b 11 b 21 ⋮ b r 1 ⋯ ⋯ ⋯ λ b 1 k b 2 k ⋮ b r k 0 λ a 21 ⋮ λ a r 1 λ a 12 + ∑ i = 1 k λ b 1 i c 2 i a 22 + ∑ i = 1 k b 2 i c 2 i ⋱ a r 2 + ∑ i = 1 k b r i c 2 i ⋯ ⋯ ⋮ ⋯ λ a 1 r + ∑ i = 1 k λ b 1 i c r i a 2 r + ∑ i = 1 k b 2 i c r i ⋮ a r r + ∑ i = 1 k b r i c r i 0 c 21 c r 1 ⋯ ⋯ ⋮ ⋯ 0 c 2 r c r k .
This is a graph state when substituting every a 1 i = a i 1 a_{1i}=a_{i1} a 1 i = a i 1 for λ a 1 i \lambda a_{1i} λ a 1 i and every b 1 j b_{1j} b 1 j for λ b 1 j \lambda b_{1j} λ b 1 j .
Without loss of generality, we may assume that m = s = 1 m=s=1 m = s = 1 . Since c 1 j = 0 c_{1j}=0 c 1 j = 0 for all j ∈ { 1 , … , k } j\in\{1,\ldots,k\} j ∈ { 1 , … , k } and b 11 = 1 b_{11}=1 b 11 = 1 and a 11 = 0 a_{11}=0 a 11 = 0 , the stabiliser matrix is given by
( 1 0 ⋯ 0 1 b 12 ⋯ b 1 k 0 a 12 + ∑ i = 1 k b 1 i c 2 i ⋯ a 1 r + ∑ i = 1 k b 1 i c r i 0 ⋯ 0 0 1 ⋯ 0 b 21 b 22 ⋯ b 2 k a 21 a 22 + ∑ i = 1 k b 2 i c 2 i ⋯ a 2 r + ∑ i = 1 k b 2 i c r i c 21 ⋯ c 2 r ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 1 b r 1 b r 2 ⋯ b r k a r 1 a r 2 + ∑ i = 1 k b r i c 2 i ⋯ a r r + ∑ i = 1 k b r i c r i c r 1 ⋯ c r k ) . \left(\begin{array}{cccc|cccc|cccc|cccc}
1&0&\cdots&0&1&b_{12}&\cdots&b_{1k}&0&a_{12}+\sum_{i=1}^{k}b_{1i}c_{2i}&\cdots&a_{1r}+\sum_{i=1}^{k}b_{1i}c_{ri}&0&\cdots&0\\
0&1&\cdots&0&b_{21}&b_{22}&\cdots&b_{2k}&a_{21}&a_{22}+\sum_{i=1}^{k}b_{2i}c_{2i}&\cdots&a_{2r}+\sum_{i=1}^{k}b_{2i}c_{ri}&c_{21}&\cdots&c_{2r}\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots&\vdots&&\vdots\\
0&0&\cdots&1&b_{r1}&b_{r2}&\cdots&b_{rk}&a_{r1}&a_{r2}+\sum_{i=1}^{k}b_{ri}c_{2i}&\cdots&a_{rr}+\sum_{i=1}^{k}b_{ri}c_{ri}&c_{r1}&\cdots&c_{rk}
\end{array}\right). 1 0 ⋮ 0 0 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ 1 1 b 21 ⋮ b r 1 b 12 b 22 ⋮ b r 2 ⋯ ⋯ ⋯ b 1 k b 2 k ⋮ b r k 0 a 21 ⋮ a r 1 a 12 + ∑ i = 1 k b 1 i c 2 i a 22 + ∑ i = 1 k b 2 i c 2 i ⋮ a r 2 + ∑ i = 1 k b r i c 2 i ⋯ ⋯ ⋯ a 1 r + ∑ i = 1 k b 1 i c r i a 2 r + ∑ i = 1 k b 2 i c r i ⋮ a r r + ∑ i = 1 k b r i c r i 0 c 21 ⋮ c r 1 ⋯ ⋯ ⋯ 0 c 2 r ⋮ c r k .
Swapping column 1 and the first column of B B B and swapping column n + 1 n+1 n + 1 and the first column of C C C , gives
( 1 0 ⋯ 0 1 b 12 ⋯ b 1 k 0 a 12 + ∑ i = 1 k b 1 i c 2 i ⋯ a 1 r + ∑ i = 1 k b 1 i c r i 0 0 ⋯ 0 b 21 1 ⋯ 0 0 b 22 ⋯ b 2 k c 21 a 22 + ∑ i = 1 k b 2 i c 2 i ⋯ a 2 r + ∑ i = 1 k b 2 i c r i a 21 c 22 ⋯ c 2 r ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ b r 1 0 ⋯ 1 0 b r 2 ⋯ b r k c r 1 a r 2 + ∑ i = 1 k b r i c 2 i ⋯ a r r + ∑ i = 1 k b r i c r i a r 1 c r 2 ⋯ c r k ) . \left(\begin{array}{cccc|cccc|cccc|cccc}
1&0&\cdots&0&1&b_{12}&\cdots&b_{1k}&0&a_{12}+\sum_{i=1}^{k}b_{1i}c_{2i}&\cdots&a_{1r}+\sum_{i=1}^{k}b_{1i}c_{ri}&0&0&\cdots&0\\
b_{21}&1&\cdots&0&0&b_{22}&\cdots&b_{2k}&c_{21}&a_{22}+\sum_{i=1}^{k}b_{2i}c_{2i}&\cdots&a_{2r}+\sum_{i=1}^{k}b_{2i}c_{ri}&a_{21}&c_{22}&\cdots&c_{2r}\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\
b_{r1}&0&\cdots&1&0&b_{r2}&\cdots&b_{rk}&c_{r1}&a_{r2}+\sum_{i=1}^{k}b_{ri}c_{2i}&\cdots&a_{rr}+\sum_{i=1}^{k}b_{ri}c_{ri}&a_{r1}&c_{r2}&\cdots&c_{rk}
\end{array}\right). 1 b 21 ⋮ b r 1 0 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ 1 1 0 ⋮ 0 b 12 b 22 ⋮ b r 2 ⋯ ⋯ ⋯ b 1 k b 2 k ⋮ b r k 0 c 21 ⋮ c r 1 a 12 + ∑ i = 1 k b 1 i c 2 i a 22 + ∑ i = 1 k b 2 i c 2 i ⋮ a r 2 + ∑ i = 1 k b r i c 2 i ⋯ ⋯ ⋯ a 1 r + ∑ i = 1 k b 1 i c r i a 2 r + ∑ i = 1 k b 2 i c r i ⋮ a r r + ∑ i = 1 k b r i c r i 0 a 21 ⋮ a r 1 0 c 22 ⋮ c r 2 ⋯ ⋯ ⋯ 0 c 2 r ⋮ c r k .
Bringing it in row echelon form, we get
( 1 0 ⋯ 0 1 b 12 ′ ⋯ b 1 k ′ 0 c 12 + a 21 + ∑ i = 2 k b 1 i ′ c 2 i ⋯ c 1 r + a r 1 + ∑ i = 2 k b 1 i ′ c r i 0 0 ⋯ 0 0 1 ⋯ 0 b 21 ′ b 22 ′ ⋯ b 2 k ′ c 21 a 22 + b 21 ′ a 21 + ∑ i = 2 k b 2 i ′ c 2 i ⋯ a 2 r + b 21 ′ a r 1 + ∑ i = 2 k b 2 i ′ c r i a 21 c 22 ⋯ c 2 r ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 1 b r 1 ′ b r 2 ′ ⋯ b r k ′ c r 1 a r 2 + b r 1 ′ a 21 + ∑ i = 2 k b r i ′ c 2 i ⋯ a r r + b r 1 ′ a r 1 + ∑ i = 2 k b r i ′ c r i a r 1 c r 2 ⋯ c r k ) . \left(\begin{array}{cccc|cccc|cccc|cccc}
1&0&\cdots&0&1&b'_{12}&\cdots&b'_{1k}&0&c_{12}+a_{21}+\sum_{i=2}^{k}b'_{1i}c_{2i}&\cdots&c_{1r}+a_{r1}+\sum_{i=2}^{k}b'_{1i}c_{ri}&0&0&\cdots&0\\
0&1&\cdots&0&b'_{21}&b'_{22}&\cdots&b'_{2k}&c_{21}&a_{22}+b'_{21}a_{21}+\sum_{i=2}^{k}b'_{2i}c_{2i}&\cdots&a_{2r}+b'_{21}a_{r1}+\sum_{i=2}^{k}b'_{2i}c_{ri}&a_{21}&c_{22}&\cdots&c_{2r}\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots&\vdots&\vdots&&\vdots\\
0&0&\cdots&1&b'_{r1}&b'_{r2}&\cdots&b'_{rk}&c_{r1}&a_{r2}+b'_{r1}a_{21}+\sum_{i=2}^{k}b'_{ri}c_{2i}&\cdots&a_{rr}+b'_{r1}a_{r1}+\sum_{i=2}^{k}b'_{ri}c_{ri}&a_{r1}&c_{r2}&\cdots&c_{rk}
\end{array}\right). 1 0 ⋮ 0 0 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ 1 1 b 21 ′ ⋮ b r 1 ′ b 12 ′ b 22 ′ ⋮ b r 2 ′ ⋯ ⋯ ⋯ b 1 k ′ b 2 k ′ ⋮ b r k ′ 0 c 21 ⋮ c r 1 c 12 + a 21 + ∑ i = 2 k b 1 i ′ c 2 i a 22 + b 21 ′ a 21 + ∑ i = 2 k b 2 i ′ c 2 i ⋮ a r 2 + b r 1 ′ a 21 + ∑ i = 2 k b r i ′ c 2 i ⋯ ⋯ ⋯ c 1 r + a r 1 + ∑ i = 2 k b 1 i ′ c r i a 2 r + b 21 ′ a r 1 + ∑ i = 2 k b 2 i ′ c r i ⋮ a r r + b r 1 ′ a r 1 + ∑ i = 2 k b r i ′ c r i 0 a 21 ⋮ a r 1 0 c 22 ⋮ c r 2 ⋯ ⋯ ⋯ 0 c 2 r ⋮ c r k .
where b i j ′ b'_{ij} b ij ′ is defined as in the statement. This is equivalent to a graph state where a 1 a_1 a 1 and c 1 c_1 c 1 are swapped.
Now, consider two equivalent stabiliser codes. By definition, they can be obtained from one another by a permutation of the coordinate positions and a symplectic transformation on each of the coordinate pairs.
Symplectic transformations on the last k k k positions can be realized by the first operation since Sp ( 2 , p ) = SL ( 2 , p ) \operatorname{Sp}(2,p)=\operatorname{SL}(2,p) Sp ( 2 , p ) = SL ( 2 , p ) is generated multiplicatively by
( 1 1 0 1 ) and ( 1 0 1 1 ) . \begin{pmatrix}1&1\\0&1\end{pmatrix}
\quad\text{and}\quad
\begin{pmatrix}1&0\\1&1\end{pmatrix}. ( 1 0 1 1 ) and ( 1 1 0 1 ) .
Note that the order of the operations is important, since the first one is sometimes necessary before applying the other two.
Corollary 12. Two binary multidimensional graph states are equivalent if and only if they can be obtained from one another through a sequence of the following operations.
(Local complementation on a vertex of V B V_B V B or V C V_C V C ). Given b s ∈ V B b_s\in V_B b s ∈ V B , do
{ a i j ↦ a i j ′ = a i j + b i s b j s for all i , j ∈ { 1 , … , r } , i ≠ j , c i s ↦ c i s ′ = c i s + b i s for all i ∈ { 1 , … , r } . \left\{\begin{aligned}
a_{ij}&\mapsto a'_{ij}=a_{ij}+b_{is}b_{js} &&\text{for all }i,j\in\{1,\ldots,r\},\ i\ne j,\\
c_{is}&\mapsto c'_{is}=c_{is}+b_{is} &&\text{for all }i\in\{1,\ldots,r\}.
\end{aligned}\right. { a ij c i s ↦ a ij ′ = a ij + b i s b j s ↦ c i s ′ = c i s + b i s for all i , j ∈ { 1 , … , r } , i = j , for all i ∈ { 1 , … , r } .
Similarly for a vertex c s ∈ V C c_s\in V_C c s ∈ V C .
(Local complementation on a vertex of V A V_A V A ). Given a m ∈ V A a_m \in V_A a m ∈ V A , if c m j = 0 c_{mj}=0 c mj = 0 for all j ∈ { 1 , … , k } j \in\{1,\ldots,k\} j ∈ { 1 , … , k } (which can always be accomplished by operation 1), do a local complementation (but keeping the induced subgraph on V B V_B V B empty):
a i j ↦ a i j ′ = a i j + a m i a m j for all i , j ∈ { 1 , … , r } , i ≠ j , b i j ↦ b i j ′ = b i j + a m i b m j for all i ∈ { 1 , … , r } and j ∈ { 1 , … , k } . \begin{aligned}
a_{ij} &\mapsto a'_{ij}=a_{ij}+a_{mi}a_{mj} &&\text{for all }i,j\in\{1,\ldots,r\},\ i\ne j,\\
b_{ij} &\mapsto b'_{ij}=b_{ij}+a_{mi}b_{mj} &&\text{for all }i\in\{1,\ldots,r\}\text{ and }j\in\{1,\ldots,k\}.
\end{aligned} a ij b ij ↦ a ij ′ = a ij + a mi a mj ↦ b ij ′ = b ij + a mi b mj for all i , j ∈ { 1 , … , r } , i = j , for all i ∈ { 1 , … , r } and j ∈ { 1 , … , k } .
(Swapping a vertex of V A V_A V A with a vertex of V C V_C V C ). Given a m ∈ V A a_m\in V_A a m ∈ V A and c s ∈ V C c_s\in V_C c s ∈ V C , if c m j = 0 c_{mj}=0 c mj = 0 for all j ∈ { 1 , … , k } j\in\{1,\ldots,k\} j ∈ { 1 , … , k } and b m s = 1 b_{ms}=1 b m s = 1 (which can always be accomplished by operation 1), swap a m a_m a m and c s c_s c s (only edges between V A V_A V A and V C V_C V C are affected by this swap), and change the weights of the edges between V A V_A V A and V B V_B V B as follows:
b i j ↦ b i j ′ = { b i j if m = i or s = j , b i j + b i s b m j else b_{ij}\mapsto b'_{ij}=
\begin{cases}
b_{ij} & \text{if }m=i\text{ or }s=j,\\
b_{ij}+b_{is}b_{mj} & \text{else}
\end{cases} b ij ↦ b ij ′ = { b ij b ij + b i s b mj if m = i or s = j , else
for all i ∈ { 1 , … , r } i\in\{1,\ldots,r\} i ∈ { 1 , … , r } and j ∈ { 1 , … , k } j\in\{1,\ldots,k\} j ∈ { 1 , … , k } .
Remark 13. We cannot simply swap V B V_B V B and V C V_C V C to obtain an equivalent state. For example, if we change the roles of B B B and C C C in the ⟦ 4 , 1 , 2 ⟧ 2 \llbracket4,1,2\rrbracket_2 [ [ 4 , 1 , 2 ] ] 2 stabiliser code with stabiliser matrix
( 1 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 ) , \left(
\begin{array}{ccc|c|cccc|c}
1&0&0&0&0&0&0&1\\
0&1&0&1&1&1&1&1\\
0&0&1&1&1&1&1&1
\end{array}
\right), 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 ,
then we get the ⟦ 4 , 1 , 1 ⟧ 2 \llbracket4,1,1\rrbracket_2 [ [ 4 , 1 , 1 ] ] 2 stabiliser code with stabiliser matrix
( 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 ) . \left(
\begin{array}{ccc|c|cccc|c}
1&0&0&1&0&1&1&0\\
0&1&0&1&0&1&1&1\\
0&0&1&1&0&1&1&1
\end{array}
\right). 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 .
These codes have a different minimum distance, so they cannot be equivalent. Note that A = O A=O A = O , so Γ A \Gamma_A Γ A is edgeless.
Remark 14. It is not necessarily so that Γ A \Gamma_A Γ A is determined up to local complementation (independent of Γ B \Gamma_B Γ B and Γ C \Gamma_C Γ C ), as it is for the case k = 0 k=0 k = 0 . For example, the ⟦ 5 , 1 , 2 ⟧ 2 \llbracket5,1,2\rrbracket_2 [ [ 5 , 1 , 2 ] ] 2 stabiliser code with stabiliser matrix
( 1 0 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 ) \left(
\begin{array}{cccc|c|ccccc}
1&0&0&0&0&0&1&1&1&1\\
0&1&0&0&0&1&0&1&1&1\\
0&0&1&0&1&0&0&1&0&1\\
0&0&0&1&1&0&0&0&1&1
\end{array}
\right) 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1
corresponds to a graph where Γ A \Gamma_A Γ A is a triangle plus one pendant vertex (leaf). However, one can check (by computer; there are 24 graph states in its equivalence orbit) that it is not equivalent to a multidimensional graph state where the base graph is a path on four vertices.
Stabiliser codes as quantum sets of lines
Let PG ( r − 1 , p ) \operatorname{PG}(r-1,p) PG ( r − 1 , p ) denote the ( r − 1 ) (r-1) ( r − 1 ) -dimensional projective space over the finite field F p \mathbb{F}_p F p , obtained from an r r r -dimensional vector space over F p \mathbb{F}_p F p . Given a stabiliser matrix G G G of an ⟦ n , k ⟧ p \llbracket n,k\rrbracket_p [ [ n , k ] ] p code, we can look at its 2 n 2n 2 n columns as points in PG ( n − k − 1 , p ) \operatorname{PG}(n-k-1,p) PG ( n − k − 1 , p ) . These columns appear in pairs, so we can consider the (multi)set of lines2 ^2 2 { ℓ i : i ∈ { 1 , … , n } } \{\ell_i:i\in\{1,\ldots,n\}\} { ℓ i : i ∈ { 1 , … , n }} , where ℓ i \ell_i ℓ i is spanned by the i i i -th and ( i + n ) (i+n) ( i + n ) -th column of G G G . Such a set of lines is called quantum :
Definition 15. A (multi)set of lines ℓ 1 , … , ℓ n \ell_1,\ldots,\ell_n ℓ 1 , … , ℓ n in PG ( r − 1 , p ) \operatorname{PG}(r-1,p) PG ( r − 1 , p ) is quantum if there exists a stabiliser matrix G G G with elements in F p \mathbb{F}_p F p such that its i i i th and ( i + n ) (i+n) ( i + n ) th column span ℓ i \ell_i ℓ i for all i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i ∈ { 1 , … , n } .
Glynn, Gulliver, Maks and Gupta [15 ] gave a description of these quantum sets of lines for p = 2 p=2 p = 2 .
Theorem 16. ([15 Theorem 1.13] , see also [3 Theorem 3.7] ). A set of lines in PG ( r − 1 , 2 ) \operatorname{PG}(r-1,2) PG ( r − 1 , 2 ) is quantum if and only if every codimension two subspace is skew to an even number of its lines (see Figure 4 ).
Figure 4. A quantum set of lines in PG ( r − 1 , 2 ) \operatorname{PG}(r-1,2) PG ( r − 1 , 2 ) has the property that every codimension two subspace is skew to an even number of its lines.
Binary stabiliser codes are equivalent if and only if their quantum sets of lines are projectively equivalent. However, if p ≥ 3 p\geq3 p ≥ 3 , then projective equivalence is no longer the same as local Clifford equivalence. Indeed, multiplying a column with a nonzero scalar different from one, changes the symplectic inner product. Also Theorem 16 fails when p ≥ 3 p\geq3 p ≥ 3 . Still, we can use the geometry to determine the minimum distance of a code, even if p ≥ 3 p\geq3 p ≥ 3 . This is explained in the next section.
The minimum distance of a quantum set of lines
Recall that r r r points are independent if they span an ( r − 1 ) (r-1) ( r − 1 ) -dimensional subspace; they are dependent otherwise. The following theorem is a generalisation of [3 Theorem 3.8] , which itself was a refinement of [15 Proposition 1.14] .
Theorem 17. Let X X X be a quantum set of lines coming from an [ [ n , k , d ] ] p [[n,k,d]]_p [[ n , k , d ] ] p stabiliser code. If k = 0 k=0 k = 0 , then d d d is the minimum size of a set of dependent points on distinct lines of X X X . If k > 0 k>0 k > 0 , then d d d is the minimum size of a set of dependent points on distinct lines of X X X such that there is no hyperplane containing these points and all the lines of X X X that do not contain one of these points.
Proof. This is a straight-forward generalisation of the proof of [3 Theorem 3.8] , replacing F 2 \mathbb{F}_2 F 2 by F p \mathbb{F}_p F p . The main idea is that
S ⊥ = { v ∈ F p 2 n : ∑ i = 1 n u i v n + i − v i u n + i = 0 } S^\perp=\left\{\mathbf{v}\in\mathbb{F}_p^{2n}:\sum_{i=1}^{n}\mathbf{u}_i v_{n+i}-v_i\mathbf{u}_{n+i}=0\right\} S ⊥ = { v ∈ F p 2 n : i = 1 ∑ n u i v n + i − v i u n + i = 0 }
where u i \mathbf{u}_i u i is the i i i th column of G G G , together with the observation that u i v n + i − v i u n + i ∈ ℓ i \mathbf{u}_i v_{n+i}-v_i\mathbf{u}_{n+i}\in\ell_i u i v n + i − v i u n + i ∈ ℓ i .
Projecting quantum sets of lines
The projection of an object in geometry is a common operation. In this section, we show how a quantum set of lines X X X projects onto a quantum set of lines X ′ X' X ′ . In terms of the stabiliser matrix, a projection is equivalent to deleting rows. To see this, consider a basis in which the final s s s coordinates span the subspace π \pi π from which we are projecting. The projection is nothing more than deleting those coordinates. In the stabiliser matrix, this removes the final s s s rows and we get an ( n − k − s ) × 2 n (n-k-s)\times2n ( n − k − s ) × 2 n matrix G ′ G' G ′ . The following theorem demonstrates how we can bound the minimum distance of the projected code knowing only X X X and π \pi π .
Theorem 18. Let X X X be a quantum set of n n n lines in P G ( n − k − 1 , p ) \mathrm{PG}(n-k-1,p) PG ( n − k − 1 , p ) and let π \pi π be a subspace skew to the lines of X X X . The projection of X X X from π \pi π is a quantum set of lines. Its minimum distance is equal to the minimum size of a set of points p 1 , … , p d \mathbf{p}_1,\ldots,\mathbf{p}_d p 1 , … , p d on distinct lines such that they are either dependent or their span intersects π \pi π , that is, ∑ i = 1 d p i ∈ π \sum_{i=1}^{d}\mathbf{p}_i\in\pi ∑ i = 1 d p i ∈ π , without there being a hyperplane containing p 1 , … , p d \mathbf{p}_1,\ldots,\mathbf{p}_d p 1 , … , p d and all the lines of X X X that do not contain one of these points.
Proof. Projection is equivalent to deleting a row of a stabiliser matrix, so it preserves the quantum property. The claim about the minimum distance follows from Theorem 17 , together with the fact that the pre-image of dependent projected points corresponds to points that sum to a point of π \pi π or sum to zero.
We now demonstrate how the graphs associated to X X X and its projection X ′ X' X ′ are related. Suppose that the stabiliser matrix is in the standard form
G = ( I n − k ∣ B ∣ A + B C T ∣ C ) G=\left(I_{n-k}\mid B\mid A+BC^{T}\mid C\right) G = ( I n − k ∣ B ∣ A + B C T ∣ C )
from Theorem 4 , and let B = { e 1 , … , e r } B=\{\mathbf{e}_1,\ldots,\mathbf{e}_r\} B = { e 1 , … , e r } be the standard basis of F p r \mathbb{F}_p^r F p r . The elements of B B B are points on different lines. Let { f 1 , … , f s } \{\mathbf{f}_1,\ldots,\mathbf{f}_s\} { f 1 , … , f s } be a basis of π \pi π . We can extend it with elements of B B B to complete it to a basis of F p r \mathbb{F}_p^r F p r . Suppose, without loss of generality, that C = { e 1 , … , e r − s , f 1 , … , f s } C=\{\mathbf{e}_1,\ldots,\mathbf{e}_{r-s},\mathbf{f}_1,\ldots,\mathbf{f}_s\} C = { e 1 , … , e r − s , f 1 , … , f s } does the trick. The change of basis matrix from B B B to C C C is of the form
M = ( I r − s D 1 O D 2 ) . M=\left(\begin{array}{c|c}
I_{r-s} & D_1\\
O & D_2
\end{array}\right). M = ( I r − s O D 1 D 2 ) .
Let
G = ( I r − s O B 1 A 11 + B 1 C 1 T A 12 + B 1 C 2 T C 1 O I s B 2 A 21 + B 2 C 1 T A 22 + B 2 C 2 T C 2 ) G=\left(\begin{array}{c|c|c|c|c|c}
I_{r-s} & O & B_1 & A_{11}+B_1C_1^{T} & A_{12}+B_1C_2^{T} & C_1\\
O & I_s & B_2 & A_{21}+B_2C_1^{T} & A_{22}+B_2C_2^{T} & C_2
\end{array}\right) G = ( I r − s O O I s B 1 B 2 A 11 + B 1 C 1 T A 21 + B 2 C 1 T A 12 + B 1 C 2 T A 22 + B 2 C 2 T C 1 C 2 )
be the stabiliser matrix associated to X X X . It is equivalent to the matrix
M G = ( I r − s D 1 B 1 + D 1 B 2 A 11 + B 1 C 1 T + D 1 ( A 21 + B 2 C 1 T ) A 12 + B 1 C 2 T + D 1 ( A 22 + B 2 C 2 T ) C 1 + D 1 C 2 O D 2 D 2 B 2 D 2 ( A 21 + B 2 C 1 T ) D 2 ( A 22 + B 2 C 2 T ) D 2 C 2 ) MG=\left(\begin{array}{c|c|c|c|c|c}
I_{r-s} & D_1 & B_1+D_1B_2 & A_{11}+B_1C_1^{T}+D_1(A_{21}+B_2C_1^{T}) & A_{12}+B_1C_2^{T}+D_1(A_{22}+B_2C_2^{T}) & C_1+D_1C_2\\
O & D_2 & D_2B_2 & D_2(A_{21}+B_2C_1^{T}) & D_2(A_{22}+B_2C_2^{T}) & D_2C_2
\end{array}\right) M G = ( I r − s O D 1 D 2 B 1 + D 1 B 2 D 2 B 2 A 11 + B 1 C 1 T + D 1 ( A 21 + B 2 C 1 T ) D 2 ( A 21 + B 2 C 1 T ) A 12 + B 1 C 2 T + D 1 ( A 22 + B 2 C 2 T ) D 2 ( A 22 + B 2 C 2 T ) C 1 + D 1 C 2 D 2 C 2 )
where the last s s s positions correspond to π \pi π . Hence the matrix associated to X ′ X' X ′ is
G ′ = ( I r − s ∣ D 1 ∣ B 1 + D 1 B 2 ∣ A 11 + B 1 C 1 T + D 1 ( A 21 + B 2 C 1 T ) ∣ A 12 + B 1 C 2 T + D 1 ( A 22 + B 2 C 2 T ) ∣ C 1 + D 1 C 2 ) . G'=\left(I_{r-s}\mid D_1\mid B_1+D_1B_2\mid A_{11}+B_1C_1^{T}+D_1(A_{21}+B_2C_1^{T})\mid A_{12}+B_1C_2^{T}+D_1(A_{22}+B_2C_2^{T})\mid C_1+D_1C_2\right). G ′ = ( I r − s ∣ D 1 ∣ B 1 + D 1 B 2 ∣ A 11 + B 1 C 1 T + D 1 ( A 21 + B 2 C 1 T ) ∣ A 12 + B 1 C 2 T + D 1 ( A 22 + B 2 C 2 T ) ∣ C 1 + D 1 C 2 ) .
Comparing this with the standard form
G ′ = ( I n − k ∣ B ′ ∣ A ′ + B ′ C ′ T ∣ C ′ ) G'=\left(I_{n-k}\mid B'\mid A'+B'C'^{T}\mid C'\right) G ′ = ( I n − k ∣ B ′ ∣ A ′ + B ′ C ′ T ∣ C ′ )
from Theorem 4 , we have
A ′ = A 11 − B 1 C 2 T D 1 T − D 1 C 2 B 1 T − D 1 ( A 22 + B 2 C 2 T + C 2 B 2 T ) D 1 T , A'=A_{11}-B_1C_2^{T}D_1^{T}-D_1C_2B_1^{T}-D_1(A_{22}+B_2C_2^{T}+C_2B_2^{T})D_1^{T}, A ′ = A 11 − B 1 C 2 T D 1 T − D 1 C 2 B 1 T − D 1 ( A 22 + B 2 C 2 T + C 2 B 2 T ) D 1 T ,
B ′ = ( D 1 ∣ B 1 + D 1 B 2 ) and C ′ = ( A 12 + B 1 C 2 T + D 1 ( A 22 + B 2 C 2 T ) ∣ C 1 + D 1 C 2 ) . B'=\left(D_1\mid B_1+D_1B_2\right)\quad\text{and}\quad C'=\left(A_{12}+B_1C_2^{T}+D_1(A_{22}+B_2C_2^{T})\mid C_1+D_1C_2\right). B ′ = ( D 1 ∣ B 1 + D 1 B 2 ) and C ′ = ( A 12 + B 1 C 2 T + D 1 ( A 22 + B 2 C 2 T ) ∣ C 1 + D 1 C 2 ) .
In particular, if we start from a one-dimensional graph state, we have
A ′ = A 11 + D 1 A 22 D 1 T , B ′ = D 1 and C ′ = A 12 + D 1 A 22 . A'=A_{11}+D_1A_{22}D_1^{T},\qquad B'=D_1\quad\text{and}\quad C'=A_{12}+D_1A_{22}. A ′ = A 11 + D 1 A 22 D 1 T , B ′ = D 1 and C ′ = A 12 + D 1 A 22 .
Moreover, if the s s s vertices whose adjacency is given by A 22 A_{22} A 22 , is an independent set, then A 22 = O A_{22}=O A 22 = O and the graph Γ ′ \Gamma' Γ ′ is obtained from Γ \Gamma Γ by making that independent set equal to V C V_C V C and adding the s s s vertices V B V_B V B , the weight of the edges being determined by π \pi π .
Extending and shortening quantum sets of lines
The standard form
G = ( I n − k ∣ B ∣ A + B C T ∣ C ) G=\left(I_{n-k}\mid B\mid A+BC^{T}\mid C\right) G = ( I n − k ∣ B ∣ A + B C T ∣ C )
from Theorem 4 gives rise to a construction to extend or shorten quantum sets of lines by one line. We can add columns b \mathbf{b} b and c \mathbf{c} c to B B B and C C C respectively to obtain the stabiliser matrix
G ′ = ( I n − k ∣ B ∣ b ∣ A + B C T + b c T ∣ C ∣ c ) G'=\left(I_{n-k}\mid B\mid\mathbf{b}\mid A+BC^{T}+\mathbf{b}\mathbf{c}^{T}\mid C\mid\mathbf{c}\right) G ′ = ( I n − k ∣ B ∣ b ∣ A + B C T + b c T ∣ C ∣ c )
of an [ [ n + 1 , k + 1 , d ′ ] ] [[n+1,k+1,d']] [[ n + 1 , k + 1 , d ′ ]] code. Vice versa, we can remove any two corresponding columns in B B B and C C C to shorten the code.
Let C C C and C ′ C' C ′ be the codes generated by G G G and G ′ G' G ′ respectively.
Lemma 19. Let u , v ∈ F p n \mathbf{u},\mathbf{v}\in\mathbb{F}_p^n u , v ∈ F p n and c ∈ F p \mathbf{c}\in\mathbb{F}_p c ∈ F p . If ( u ∣ 0 ∣ v ∣ c ) ∈ C ′ (\mathbf{u}\mid0\mid\mathbf{v}\mid c)\in C' ( u ∣ 0 ∣ v ∣ c ) ∈ C ′ , then ( u ∣ ∣ v ) ∈ C (\mathbf{u}\mid\mid\mathbf{v})\in C ( u ∣∣ v ) ∈ C .
Proof. If ( u ∣ 0 ∣ v ∣ c ) ∈ C ′ (\mathbf{u}\mid0\mid\mathbf{v}\mid c)\in C' ( u ∣ 0 ∣ v ∣ c ) ∈ C ′ , then ( u ∣ 0 ∣ v ∣ c ) = x G ′ (\mathbf{u}\mid0\mid\mathbf{v}\mid c)=\mathbf{x}G' ( u ∣ 0 ∣ v ∣ c ) = x G ′ for some x ∈ F p r \mathbf{x}\in\mathbb{F}_p^r x ∈ F p r . Since the coordinate on position n + 1 n+1 n + 1 is zero, we have that x b = 0 \mathbf{x}\mathbf{b}=0 xb = 0 and hence x b c T = 0 \mathbf{x}\mathbf{b}\mathbf{c}^{T}=0 xb c T = 0 . Thus, ( u ∣ ∣ v ) = x G (\mathbf{u}\mid\mid\mathbf{v})=\mathbf{x}G ( u ∣∣ v ) = x G .
Lemma 20. If k ≥ 1 k\geq1 k ≥ 1 , then the above extension operation can increase the minimum distance by at most one, that is, d ( C ′ ) ≤ d ( C ) + 1 d(C')\leq d(C)+1 d ( C ′ ) ≤ d ( C ) + 1 .
Proof. First observe that the operation changes the parity check matrix of Lemma 6 into
H ′ = ( I n − k A + C B T + c b T I k C T 1 c T − B T I k − b T 1 ) . H'=
\left(
\begin{array}{ccccc}
I_{n-k} & & & A+CB^{T}+\mathbf{c}\mathbf{b}^{T} & \\
& I_k & & C^{T} & \\
& & 1 & \mathbf{c}^{T} & \\
& & & -B^{T} & I_k \\
& & & -\mathbf{b}^{T} & & 1
\end{array}
\right). H ′ = I n − k I k 1 A + C B T + c b T C T c T − B T − b T I k 1 .
(Empty blocks correspond to zeroes.) Choose a minimum weight vector ( u ∣ v ) (\mathbf{u}\mid\mathbf{v}) ( u ∣ v ) that is contained in the centraliser of the original code, but not contained in the code itself (for this we need k ≥ 1 k \ge1 k ≥ 1 ). It is a linear combination of rows of the parity check matrix. The corresponding vector in the new parity check matrix is either ( u ∣ 0 ∥ v ∣ 0 ) (\mathbf{u}\mid0\parallel\mathbf{v}\mid0) ( u ∣ 0 ∥ v ∣ 0 ) or ( u ∣ 0 ∥ v ∣ 0 ) + ( 0 ∣ 0 ∥ b T ∣ 0 ∣ 0 ) (\mathbf{u}\mid0\parallel\mathbf{v}\mid0)+(\mathbf{0}\mid\mathbf{0}\parallel\mathbf{b}^{T}\mid0\mid0) ( u ∣ 0 ∥ v ∣ 0 ) + ( 0 ∣ 0 ∥ b T ∣ 0 ∣ 0 ) .
In the first case, the (symplectic) weight does not change. By Lemma 19 , the vector in the new parity check matrix is not contained in the code.
In the second case, the vector
( u ∣ 0 ∥ v ∣ 0 ) + ( 0 ∣ 0 ∥ b T ∣ 0 ∣ 0 ) + ( 0 ∣ 0 ∥ − b T ∣ 0 ∣ 1 ) = ( u ∣ 0 ∥ v ∣ 1 ) (\mathbf{u}\mid0\parallel\mathbf{v}\mid0)+(\mathbf{0}\mid\mathbf{0}\parallel\mathbf{b}^{T}\mid0\mid0)+(\mathbf{0}\mid\mathbf{0}\parallel-\mathbf{b}^{T}\mid0\mid1)=(\mathbf{u}\mid0\parallel\mathbf{v}\mid1) ( u ∣ 0 ∥ v ∣ 0 ) + ( 0 ∣ 0 ∥ b T ∣ 0 ∣ 0 ) + ( 0 ∣ 0 ∥ − b T ∣ 0 ∣ 1 ) = ( u ∣ 0 ∥ v ∣ 1 )
belongs to the centraliser and has weight one more than ( u ∥ v ) (\mathbf{u}\parallel\mathbf{v}) ( u ∥ v ) . By Lemma 19 , it is not contained in the code.
The extension operation can be described geometrically if p = 2 p=2 p = 2 (this condition is needed for step 3 below). Given a quantum set of n n n lines in PG ( r − 1 , 2 ) \operatorname{PG}(r-1,2) PG ( r − 1 , 2 ) , where r = n − k r=n-k r = n − k , we can add a line and adjust the other lines such that they form a quantum set of lines again, as follows:
Choose a basis { e 1 , … , e r } \{\mathbf{e}_1,\ldots,\mathbf{e}_r\} { e 1 , … , e r } of r r r points on r r r different lines ℓ 1 , … , ℓ r \ell_1,\ldots,\ell_r ℓ 1 , … , ℓ r .
Choose two different points b \mathbf{b} b and c \mathbf{c} c such that ∀ i ∈ { 1 , … , r } \forall i\in\{1,\ldots,r\} ∀ i ∈ { 1 , … , r } : b ∈ ℓ i ∖ { e i } ⟹ c i = 0 \mathbf{b}\in\ell_i\setminus\{\mathbf{e}_i\}\Longrightarrow c_i=0 b ∈ ℓ i ∖ { e i } ⟹ c i = 0 . Let ℓ n + 1 = ⟨ b , c ⟩ \ell_{n+1}=\langle\mathbf{b},\mathbf{c}\rangle ℓ n + 1 = ⟨ b , c ⟩ be the line spanned by them.
For each i ∈ { 1 , … , r } i\in\{1,\ldots,r\} i ∈ { 1 , … , r } replace the line ℓ i = ⟨ e i , a i ⟩ \ell_i=\langle\mathbf{e}_i,\mathbf{a}_i\rangle ℓ i = ⟨ e i , a i ⟩ by the line ℓ i ′ = ⟨ e i , a i + c i b ⟩ \ell'_i=\langle\mathbf{e}_i,\mathbf{a}_i+c_i\mathbf{b}\rangle ℓ i ′ = ⟨ e i , a i + c i b ⟩ .
Now { ℓ 1 ′ , … , ℓ r ′ } ∪ { ℓ r + 1 , … , ℓ n } ∪ { ℓ n + 1 } \{\ell'_1,\ldots,\ell'_r\}\cup\{\ell_{r+1},\ldots,\ell_n\}\cup\{\ell_{n+1}\} { ℓ 1 ′ , … , ℓ r ′ } ∪ { ℓ r + 1 , … , ℓ n } ∪ { ℓ n + 1 } is a quantum set of n + 1 n+1 n + 1 lines in PG ( r − 1 , 2 ) \operatorname{PG}(r-1,2) PG ( r − 1 , 2 ) .
Figure 5 (PDF p. 17).
Conversely, we can also remove a line from a quantum set of n n n lines in PG ( r − 1 , 2 ) \operatorname{PG}(r-1,2) PG ( r − 1 , 2 ) , where r = n − k r=n-k r = n − k and k ≥ 1 k\ge1 k ≥ 1 , such that it is still a quantum set of lines, as follows:
Choose a basis { e 1 , … , e r } \{\mathbf{e}_1,\ldots,\mathbf{e}_r\} { e 1 , … , e r } of r r r points on r r r different lines ℓ 1 , … , ℓ r \ell_1,\ldots,\ell_r ℓ 1 , … , ℓ r .
Pick another line ℓ ∉ { ℓ 1 , … , ℓ r } \ell\notin\{\ell_1,\ldots,\ell_r\} ℓ ∈ / { ℓ 1 , … , ℓ r } from the quantum set of lines and two different points b \mathbf{b} b and c \mathbf{c} c on that line ℓ \ell ℓ such that ∀ i ∈ { 1 , … , r } \forall i\in\{1,\ldots,r\} ∀ i ∈ { 1 , … , r } : b ∈ ℓ i ∖ { e i } ⟹ c i = 0 \mathbf{b}\in\ell_i\setminus\{\mathbf{e}_i\}\Longrightarrow c_i=0 b ∈ ℓ i ∖ { e i } ⟹ c i = 0 .
For each i ∈ { 1 , … , r } i\in\{1,\ldots,r\} i ∈ { 1 , … , r } replace the line ℓ i = ⟨ e i , a i ⟩ \ell_i=\langle\mathbf{e}_i,\mathbf{a}_i\rangle ℓ i = ⟨ e i , a i ⟩ by the line ℓ i ′ = ⟨ e i , a i + c i b ⟩ \ell'_i=\langle\mathbf{e}_i,\mathbf{a}_i+c_i\mathbf{b}\rangle ℓ i ′ = ⟨ e i , a i + c i b ⟩ .
Now { ℓ 1 ′ , … , ℓ r ′ } ∪ { ℓ r + 1 , … , ℓ n } ∖ { ℓ } \{\ell'_1,\ldots,\ell'_r\}\cup\{\ell_{r+1},\ldots,\ell_n\}\setminus\{\ell\} { ℓ 1 ′ , … , ℓ r ′ } ∪ { ℓ r + 1 , … , ℓ n } ∖ { ℓ } is a quantum set of n − 1 n-1 n − 1 lines in PG ( r − 1 , 2 ) \operatorname{PG}(r-1,2) PG ( r − 1 , 2 ) .
Note that, in the above operation, b and c not interchangeable. The following example illustrates this.
Example 21. Consider the star graph K 1 , 4 K_{1,4} K 1 , 4 . It corresponds to the graph state with stabiliser matrix
( 1 0 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 ) \left(
\begin{array}{ccccc|ccccc}
1&0&0&0&0&0&1&1&1&1\\
0&1&0&0&0&1&0&0&0&0\\
0&0&1&0&0&1&0&0&0&0\\
0&0&0&1&0&1&0&0&0&0\\
0&0&0&0&1&1&0&0&0&0
\end{array}
\right) 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 and the corresponding set of lines is a point pencil through e 1 \mathbf{e}_1 e 1 , whose projection from e 1 \mathbf{e}_1 e 1 is a frame in the hyperplane X 1 = 0 X_1=0 X 1 = 0 . Suppose that we want to extend the set with another line through e 1 \mathbf{e}_1 e 1 , say the line ℓ = { e 1 , b , c } \ell=\{\mathbf{e}_1,\mathbf{b},\mathbf{c}\} ℓ = { e 1 , b , c } with b = ( 0 , 1 , 1 , 0 , 0 ) \mathbf{b}=(0,1,1,0,0) b = ( 0 , 1 , 1 , 0 , 0 ) and c = ( 1 , 1 , 1 , 0 , 0 ) \mathbf{c}=(1,1,1,0,0) c = ( 1 , 1 , 1 , 0 , 0 ) . If we follow the above operation, we get the stabiliser matrix
( 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 ) \left(
\begin{array}{ccccc|c|ccccc|c}
1&0&0&0&0&0&0&1&1&1&1&1\\
0&1&0&0&0&1&0&1&1&0&0&1\\
0&0&1&0&0&1&0&1&1&0&0&1\\
0&0&0&1&0&0&1&0&0&0&0&0\\
0&0&0&0&1&0&1&0&0&0&0&0
\end{array}
\right) 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 but if we would change the roles of b \mathbf{b} b and c \mathbf{c} c in the construction, we would get the matrix
( 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 ) . \left(
\begin{array}{ccccc|c|ccccc|c}
1&0&0&0&0&1&0&0&0&1&1&0\\
0&1&0&0&0&1&1&1&1&0&0&1\\
0&0&1&0&0&1&1&1&1&0&0&1\\
0&0&0&1&0&0&1&0&0&0&0&0\\
0&0&0&0&1&0&1&0&0&0&0&0
\end{array}
\right). 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 . These quantum sets of lines are not equivalent because the second one contains the line { e 2 , e 3 } \{\mathbf{e}_2,\mathbf{e}_3\} { e 2 , e 3 } with multiplicity 2 2 2 , while the first one contains every line only once.
Note that the choice of the basis { e 1 , … , e r } \{\mathbf{e}_1,\ldots,\mathbf{e}_r\} { e 1 , … , e r } matters. See also Remark 14.
Application: classifying stabiliser codes up to equivalence
Using Theorem 4 and Theorem 11 , we can classify all multidimensional graph states of a certain small size up to equivalence by computer.
We provide tables containing the number of graph states, up to equivalence, for k ∈ { 0 , 1 } k\in\{0,1\} k ∈ { 0 , 1 } and p ∈ { 2 , 3 } p\in\{2,3\} p ∈ { 2 , 3 } , generalising computational results for k = 0 k=0 k = 0 and p = 2 p=2 p = 2 by Danielsen and Parker [11 ] and for k = 0 k=0 k = 0 and p = 3 p=3 p = 3 by Danielsen [10 ] . These tables were obtained with SageMath [24 ] by a straight-forward implementation of the local complementation strategy from Theorem 11 . Our implementation can most probably be optimised with better code. But we do not focus on performance. Our goal is mostly to illustrate that, with the newly established graph formalism, it becomes easier to classify stabiliser codes with a given set of parameters for larger dimensions (k ≥ 1 k\ge1 k ≥ 1 ) as well.
Table 1. The number of [ [ n , 0 , d ] ] 2 [[n, 0, d]]_2 [[ n , 0 , d ] ] 2 stabiliser codes up to equivalence. Table taken from [11 Table 4] .
Table 2. The number of [ [ n , 1 , d ] ] 2 [[n, 1, d]]_2 [[ n , 1 , d ] ] 2 stabiliser codes up to equivalence.
Table 3. The number of [ [ n , 0 , d ] ] 3 [[n, 0, d]]_3 [[ n , 0 , d ] ] 3 stabiliser codes up to equivalence. The last row agrees with the values in [10 Table 2] .
Table 4. The number of [ [ n , 1 , d ] ] 3 [[n, 1, d]]_3 [[ n , 1 , d ] ] 3 stabiliser codes up to equivalence.
Final comments and further work
We proved that an [ [ n , k , d ] ] p [[n, k, d]]_p [[ n , k , d ] ] p stabiliser code is equivalent to a graph on n + k n+k n + k vertices, which has two independent sets on k k k vertices with a matching in between, and whose edges are weighted with elements of F p \mathbb{F}_p F p (Theorem 4 ). We translated local Clifford equivalence to a set of operations on such graphs (Theorem 11 ). It does not appear to be easy to deduce the minimum distance of a stabiliser code directly from the associated graph. However, it can be calculated using the geometry of quantum sets of lines (Theorem 17 ).
The graph formalism allowed us to define two operations on quantum sets of lines to obtain other sets of quantum sets of lines. As an application, we classified stabiliser codes for some given small parameters.
We propose the following directions for future work:
Can one extend the ideas of this article to prime powers that are not primes? For geometrical objects equivalent to stabiliser codes of fields of non-prime order, see [4 , 17 ] .
Extend the tables in § 5 . Something that might prove interesting, is an algorithm to calculate a canonical representative of a stabiliser code, similarly to the work of Feulner [13 ] for linear codes.
Can we lower bound the minimum distance of a stabiliser code using graph parameters of the corresponding graph state? What are families of graphs for which the associated stabiliser codes have a large minimum distance?
The projection and extension operations from § 4.2 and § 4.3 can be used to find codes with a large minimum distance in a recursive way. For example, we can follow the path
[ [ 1 , 0 , 1 ] ] 2 ⟶ [ [ 2 , 1 , 1 ] ] 2 ⟶ [ [ 2 , 0 , 2 ] ] 2 ⟶ ⋯ ⟶ [ [ n , 1 , d ] ] 2 ⟶ [ [ n , 0 , d ′ ] ] 2 [[1, 0, 1]]_{2} \longrightarrow[[2, 1, 1]]_{2} \longrightarrow[[2, 0, 2]]_{2} \longrightarrow\cdots\longrightarrow[[n, 1, d]]_{2} \longrightarrow[[n, 0, d']]_{2} [[ 1 , 0 , 1 ] ] 2 ⟶ [[ 2 , 1 , 1 ] ] 2 ⟶ [[ 2 , 0 , 2 ] ] 2 ⟶ ⋯ ⟶ [[ n , 1 , d ] ] 2 ⟶ [[ n , 0 , d ′ ] ] 2
while optimizing for the largest possible minimum distance.
To our knowledge, the existence of a [ [ 14 , 3 , 5 ] ] 2 [[14, 3, 5]]_{2} [[ 14 , 3 , 5 ] ] 2 stabiliser code is still open. We applied the extension operation on every [ [ 11 , 0 , 5 ] ] 2 [[11, 0, 5]]_{2} [[ 11 , 0 , 5 ] ] 2 stabiliser code to see if a [ [ 14 , 3 , 5 ] ] 2 [[14, 3, 5]]_{2} [[ 14 , 3 , 5 ] ] 2 could be obtained by walking the path
[ [ 11 , 0 , 5 ] ] 2 ⟶ [ [ 12 , 1 , 5 ] ] 2 ⟶ [ [ 13 , 2 , 4 ] ] 2 ⟶ [ [ 14 , 3 , 5 ] ] 2 . [[11, 0, 5]]_{2} \longrightarrow[[12, 1, 5]]_{2} \longrightarrow[[13, 2, 4]]_{2} \longrightarrow[[14, 3, 5]]_{2}. [[ 11 , 0 , 5 ] ] 2 ⟶ [[ 12 , 1 , 5 ] ] 2 ⟶ [[ 13 , 2 , 4 ] ] 2 ⟶ [[ 14 , 3 , 5 ] ] 2 .
After going through all possibilities, we conclude that it is impossible. This gives some evidence (but not a proof) that a [ [ 14 , 3 , 5 ] ] 2 [[14, 3, 5]]_{2} [[ 14 , 3 , 5 ] ] 2 stabiliser code does not exist.
The drawback with this strategy is that there are many ways to choose a line that extends a given quantum set of lines. For the given values, this was possible, but in general it seems like walking every possible path towards a [ [ 14 , 3 , 5 ] ] 2 [[14, 3, 5]]_{2} [[ 14 , 3 , 5 ] ] 2 stabiliser code is infeasible on a normal computer.
Acknowledgements We would like to thank Oriol Farràs and Cristina Fernández for their careful reading of the doctoral thesis of Ricard Vilar, on which the results in this paper are partially based.
AI declaration We did not use any AI-assisted technologies in the research, writing, or editing of the manuscript.
Simeon Ball
Department of Mathematics Universitat Politècnica de Catalunya C. Pau Gargallo 14, 08028 Barcelona, Spain E-mail: simeon.michael.ball@upc.edu
Gülizar Günay
Institute of Analysis and Number Theory Graz University of Technology Münzgrabenstrasse 36, 8010 Graz, Austria E-mail: gunaymert@math.tugraz.at
Robin Simoens
Department of Mathematics: Analysis, Logic and Discrete Mathematics Ghent University Krijgslaan 281, 9000 Gent, Belgium Department of Mathematics Universitat Politècnica de Catalunya C. Pau Gargallo 14, 08028 Barcelona, Spain E-mail: Robin.Simoens@UGent.be
Ricard Vilar
Department of Mathematics Universitat Politècnica de Catalunya C. Pau Gargallo 14, 08028 Barcelona, Spain E-mail: ricard.vilar@upc.edu