CSS codes and the 9-qubit Shor code

In the 9-qubit Shor code, the stabilizer $S$ is generated by the following operators

$$\begin{align*} S_1=& Z_1Z_2 \\ S_2=&Z_2Z_3 \\ S_3=&Z_4Z_5 \\ S_4=&Z_5Z_6 \\ S_5=&Z_7Z_8 \\ S_6=&Z_8Z_9 \\ S_7=&X_1X_2X_3X_4X_5X_6 \\ S_8=&X_4X_5X_6X_7X_8X_9. \\ \end{align*}$$
 Thus, the the dimension of the code space is $2^{9-8}=2$, which implies that the code only encodes one logical qubit. In this case, $\hat{N}(S)/S\cong \hat{P}_1$, so $\hat{N}/S$ will be generated by some elements $\overline{X}, \overline{Z}\in\hat{N}(S)\backslash S$, satisfying the usual Pauli commutation relations:
  $$\overline{X}^2=\overline{Z}^2=\overline{I}, \  \text{and} \  \overline{X} \ \overline{Z}=-\overline{Z} \ \overline{X}$$
 In this regard, let
$$\begin{align*}  \overline{Z}=&X_1X_2X_3X_4X_5X_6X_7X_8X_9 \\   \overline{X}=& Z_1Z_2Z_3Z_4Z_5Z_6Z_7Z_8Z_9 \\ \end{align*}$$
 which satisfy the commutation relations described above. Moreover, $\overline{Z}\in\hat{N}(S)\backslash S$. To see this, note that
$$\begin{align*}  [\overline{Z},S_i]=0&, \ \text{for} \  i=7,8 \\   [\overline{X},S_i]=0&, \ \text{for} \  i=1,2,3,4,5,6 \\  \end{align*}$$
 because each of these ease either a product of only $X$ operators or only $Z$ operators. The less trivial relations
  $$\begin{align*}  [\overline{Z},S_i]=0&, \ \text{for} \ i=1,2,3,4,5,6  \\   [\overline{X},S_i]=0&, \ \text{for} \ i=7,8  \\  \end{align*}$$

also hold, because the intersection of the supports of $\overline{Z}$ and $S_i$ ( for $i=1,2,3,4,5,6$) is always an even number of qubits. Likewise, the intersection of the supports of $\overline{X}$ and $S_i$ ( for $i=7,8$) is also always an even number of qubits. Thus, $\overline{X},\overline{Z}\in \hat{N}(S)$.

 Now, to see that $\overline{X},\overline{Z}\notin S$ observe that the product$S_7S_8=X_1X_2X_3X_7X_8X_9\neq\overline{Z}$, which implies $\overline{Z}\notin S$. For $\overline{X}$, it is impossible to even generate an operator that contains all the factors $Z_1Z_2Z_3$ since the only stabilizers that even have nontrivial support on these first three qubits are $S_1$ and $S_2$, but yet  $S_1S_2=Z_1Z_3\neq Z_1Z_2Z_3$. Therefore, $\overline{X}\notin S$.


Consider the binary matrix
$$\delta=\begin{pmatrix} 1&1&1&0&0 \\ 0&0&1&1&1\\ 1&1&0&1&1 \\ 1&1&1&0&0 \\ 0&0&1&1&1\\ \end{pmatrix}.$$
 Associate to each row $j$ an $X$-type stbilizer
  $$M_j=\PROD{l=1}{5}X_l^{\delta_{jl}},$$
 and to each column a $Z$-stabilizer
  $$N_j=\PROD{l=1}{5}Z_l^{\delta_{lj}}.$$
 The product of the matrix $\delta$ with itself (modulo $2$) effectively computes products of  all the $M_j$ operators with all the $N_j$ operators. The $i,j$th coefficient in the matrix of $\delta^2$,  has a value of $0$ if $M_iN_j$ commute and has a value of $1$ if $M_iN_j$ anticommute. In fact, since $\delta^2$ gives the matrix with all coefficients $0$, each $M_i$ commutes with each $N_j$. Therefore, the set $Q$ generated by all such products of $M_j$ and $N_i$ forms an abelian subgroup of the Pauli group $\hat{P}_5$. Moreover, since each $M_j$ and $N_j$ square to $+I$, it is necessarily the case that $-I\notin Q$. Hence, $Q$ actually defines a stabilizer group. By choosing linearly independent operators $M_j$ and $N_i$, it is seen that the stabilizer $Q$ can be generated by $\{M_1,M_2,N_1, N_4\}$.


Let $C_1$ and $C_2$ be a classical linear codes with parity check matrices $H_1$ and $H_2$ given by

  $$H_1=\begin{pmatrix}  1&0&1&1&0 \\  0&1&1&0&1  \end{pmatrix}   \ \ \text{and} \  \   H_2=\begin{pmatrix}  1&1&1&0&0 \\  0&0&1&1&1  \end{pmatrix}.$$

Notice that $H_1$ consists of the two $Z$-type stabilizer generators $N_1$ and $N_4$, and $H_2$ consists of the two $X$-type stabilizer generators $M_1$ and $M_2$ defined in (2) that together generate the stabilizer group $Q$. In this way, $Q$ is the CSS code $CSS(H_1,H_2)$. Here, $Q=<S_1\cup S_2>$, where $S_1$ and $S_2$ are the stabilizer groups generated by the $Z$-type and $X$-type operators, respectively.  Namely,
  $$S_1=\begin{pmatrix}   0&0&0&0&0 \\  1&0&1&1&0 \\  0&1&1&0&1 \\   1&1&0&1&1  \end{pmatrix}   \ \ \text{and} \  \  S_2=\begin{pmatrix}   1&0&1&1&0 \\  1&1&1&0&0 \\  0&0&1&1&1\\   1&1&0&1&1 \\  \end{pmatrix}.$$

Let $G_1$ and $G_2$ be corresponding generator matrices of the codes $C_1$ and $C_2$, respectively. For each code, since there are $5$ physical bits and $3$ encoded bits ($H_1$ and $H_2$ are $2 \times 5$ matrices), both generator matrices have dimensions $3\times 5$. These generators must satisfy the constraints
$$G_iH_i^T=0 \  \ \text{and} \ \ H_iG_i^T=0.$$
for $i=1,2$. The constraints form a set of $k$ non-singular equations on $n$ bits. It can be checked that the following two particular matrices satisfy these constraints:
$$G_1=\begin{pmatrix}  1&0&0&1&0 \\  1&1&0&1&1 \\   0&1&1&1&0  \end{pmatrix}   \ \ \text{and} \  \ G_2=\begin{pmatrix}  1&0&1&0&1 \\  1&1&0&0&0 \\   0&1&1&1&0  \end{pmatrix}.$$

The rows of $G_1$ and $G_2$ form a basis of the code spaces $C_1$ and $C_2$, respectively. Hence, the span of each generates the entire code spaces. The elements of these code spaces are then
$$C_1=\begin{pmatrix}  0&0&0&0&0 \\  1&0&0&1&0 \\  1&1&0&1&1 \\   0&1&1&1&0 \\  0&1&0&0&1 \\   1&0&1&0&1 \\    1&1&1&0&0 \\     0&0&1&1&1  \end{pmatrix}   \ \ \text{and} \  \ C_2=\begin{pmatrix}  0&0&0&0&0 \\  1&0&1&0&1 \\  1&1&0&0&0 \\   0&1&1&1&0 \\    1&0&1&1&0 \\     0&1&1&0&1 \\      1&1&0&1&1 \\       0&0&0&1&1 \\  \end{pmatrix}.$$

By associating a $Z$-type (or $X$-type) operator $\overline{Z}$ (or $\overline{X}$) to each row of $C_2$ (or $C_1$), and demanding that $\overline{Z}\notin S_1$ (and $\overline{X}\notin S_2$) and also that $\overline{Z} \ \overline{X}=-\overline{X} \ \overline{Z}$, then the pair $(\overline{X},\overline{Z})$ can be made to correspond to a logical operation on a logical qubit. In this case, since there is only $1$ logical qubit a single pair satisfying these properties is all that is needed. In this regard, choose
$$\overline{X}=X_1X_4 \ \ \text{and} \ \ \overline{Z}=Z_1Z_3Z_5$$
corresponding to the second rows of $C_2$ and $C_1$. Then indeed, $\overline{X}\notin S_2$ and $\overline{Z}\notin S_1$, and $\overline{Z} \ \overline{X}=-\overline{X} \ \overline{Z}$. Therefore, the pair $(\overline{X},\overline{Z})$ function as logical operators on the encoded qubit, and hence generate $\mathcal{N}(S)/S\cong P_1$.


In the classical linear code context, the distances of codes $C_1$ and $C_2$ are both given by $d_1=d_2=2$, which can be seen by examining the elements of $C_1$ and $C_2$ and finding the minimum weight of any non-identity codeword. For $CSS(H_1,H_2)$, the distance of the code $Q$ must satisfy $d\geq min\{d_1,d_2\}=2$. In this context, the distance of $Q$ will be the minimum weight of an operator in $\mathcal{N}(S)\backslash S$, which by inspection is seen to be $d=2$.


In what follows, an algorithm will be described which begins with two parity check matrices $H_1$ and $H_2$ of a general CSS code, and computes a set of generators for $\hat{\mathcal{N}}(S)/S$ grouped into pairs $\{(\overline{X}_i,\overline{Z}_i)\}$.

First, using $H_1$ and $H_2$ (matrices with dimensions $(n-k)\times n$ construct generator matrices $G_1$ and $G_2$ (of dimensions $k\times n$) satisfying the constraints $G_iH_i^T=0$ and $H_iG^T=0$ for each $i=1,2$. Moreover, the rows of such $G_i$ should be linearly independent. Such a procedure can be done in general using the Gram-Schmidt process.

Next, consider the codes paces $C_i$ defined as the span of the rows of $G_i$, and also the stabilizer spaces $S_i$ defined as the span of the rows of $H_i$. Then to find generators of $\hat{\mathcal{N}}(S)/S$, it suffices to choose pairs $(\overline{X}_l,\overline{Z}_l)$ with $\overline{Z}_l\in C_1\backslash S_1$ and $\overline{X}_l\in C_2\backslash S_2$, such that $\overline{X}_l$ and $\overline{Z}_l$ anti commute, and all pairs $(\overline{X}_l,\overline{Z}_l)$ and$(\overline{X}_l',\overline{Z}_l')$ with $l\neq l'$ commute. For $k$ encoded qubits, there will be $k$ many many pairs, corresponding to the logical operations applied to each of the $k$ logical qubits.

Graph states

Let $G=(V,E)$ be a undirected graph with no self-loops. That is, for all $v,v'\in V$, $(v,v)\notin E$, and  if $(v,v')\in E$ then also $(v',v)\in E$. Associate a qubit to each vertex in $V$. When necessary, the vertices will be indexed as $v_i$ with $i\in\{1,\dots, N\}$ where $|V|=N$. Let $I_N=I^{\otimes N}$ be the identity operator on all $N$ qubits, where $I$ is the identity operator on a single qubit. For some single qubit unitary $U$, write $U_{v_i}=I\otimes\cdots\otimes I\otimes U\otimes\cdots\otimes I$ to denote the operator on the $N$-qubit space which applies the single qubit unitary $U$ to the qubit associated to vertex $v_i$. Now, define the operators
$$M_v=X_v\PROD{v':(v,v')\in E}{} Z_{v'}$$
for $v\in V$, where $X_v$ and $Z_v$ are the single qubit $X$ and $Z$ operators acting on the qubit associated to vertex $v$.


 For compatible operators $A$ and $B$, let $[A,B]=ABA^{-1}B^{-1}$. If $[A,B]=I$, then $A$ and $B$ \emph{commute}, and if $[A,B]=-I$ then $A$ and $B$ \emph{anticommute}. Now observe the following commutation relations:
$$\begin{align*} \text{for any} \ v_i,v_j\in V:& \ \ \ [I_N,X_{v_i}]=[I_N,Z_{v_i}]=[X_{v_i},X_{v_j}]=[Z_{v_i},Z_{v_j}]=I_N\\ \text{if} \  v_i\neq v_j:& \ \ \ [X_{v_i},Z_{v_j}]=I_N\\ \text{if} \ v_i=v_j:& \ \ \ [X_{v_i},Z_{v_j}] =-I_N. \end{align*}$$
These then imply the following commutation relations:
$$\begin{align*} \text{for any} \ v_i,v_j\in V:& \ \ \ \left[\PROD{v':(v_i,v')\in E}{} Z_{v'} \ , \ \PROD{v':(v_j,v')\in E}{} Z_{v'}\right]=I_N \\ \text{if} \ (v_i,v_j)\notin E:& \ \ \ \left[X_{v_i} \ , \ \PROD{v':(v_j,v')\in E}{} Z_{v'}\right]=I_N \\ \text{if} \ (v_i,v_j)\in E:& \ \ \ \left[X_{v_i} \ , \ \PROD{v':(v_j,v')\in E}{} Z_{v'}\right]=-I_N. \end{align*}$$

Trivially, for any graph $G$ and $v\in V$, the operator $M_v$ commutes with itself since $M_v^2=I_N$ as $M_v$ is only comprised of $X$ and $Z$ terms which satisfy $X^2=I$ and $Z^2=I$.  Therefore, consider graphs $G$ with more than one vertex so that $|V|\geq 2$. For any two $M_{v_i}, M_{v_j}\in \{M_v\}_{v\in V}$ such that $v_i\neq v_j$, there are two cases two consider: either $(v_i,v_j)\notin E$ or $(v_i,v_j)\in E$.

Suppose first that $(v_i,v_j)\notin E$. Then $Z_{v_j}$ does not appear in $M_{v_i}$, and likewise $Z_{v_i}$ does not appear in $M_{v_j}$. Then in the product $M_{v_i}M_{v_j}$, the pairs of operators that act on any particular qubit all commute. Therefore, $M_{v_i}M_{v_j}=M_{v_j}M_{v_i}$ so that $M_{v_i}$ and $M_{v_j}$ commute as well in this case.

Instead, suppose that $(v_i,v_j)\in E$. In this case, $Z_{v_j}$ does appear in $M_{v_i}$, and likewise $Z_{v_i}$ appears in $M_{v_j}$. Then in the product $M_{v_i}M_{v_j}$ there are two pairs of operators that anticommute--namely,  $X_{v_i}Z_{v_i}$  and $Z_{v_j}X_{v_j}$. Then since $X_{v_i}Z_{v_i}=-Z_{v_i}X_{v_i}$ and $Z_{v_j}X_{v_j}=-X_{v_j}Z_{v_j}$, the two resulting $-1$ factors will cancel. Hence, that $M_{v_i}M_{v_j}=M_{v_j}M_{v_i}$ implying that $M_{v_i}$ and $M_{v_j}$ commute. To see this more explicitly, consider the calculation shown below, which makes use of the nontrivial commutation relations given above:
$$\begin{align*} M_{v_i}M_{v_j}=&\left(X_{v_i}\PROD{v':(v_i,v')\in E}{} Z_{v'} \right)\left(X_{v_j}\PROD{v':(v_j,v')\in E}{} Z_{v'} \right)\\ &=(-1)X_{v_i}X_{v_j}\PROD{v':(v_i,v')\in E}{} Z_{v'}\PROD{v':(v_j,v')\in E}{} Z_{v'} \\ &=(-1)X_{v_j}X_{v_i}\PROD{v':(v_j,v')\in E}{} Z_{v'}\PROD{v':(v_i,v')\in E}{} Z_{v'} \\ &=(-1)(-1)X_{v_j}\PROD{v':(v_j,v')\in E}{} Z_{v'}X_{v_i}\PROD{v':(v_i,v')\in E}{} Z_{v'} \\ &=\left(X_{v_i}\PROD{v':(v_i,v')\in E}{} Z_{v'} \right)\left(X_{v_j}\PROD{v':(v_j,v')\in E}{} Z_{v'} \right)\\ &=M_{v_j}M_{v_i}. \end{align*}$$
It has now been shown that all operators in the set $\{M_v\}_{v\in V}$ commute with one another.

Since each operator $M_v$ contains the operator $X_v$, and any other $M_{v'}$ with $v\neq v'$ contains a different $X_{v'}$ operator, $M_v$ cannot be generated as a product of other $M_{v'}$ operators. Thus, the set $\{M_v\}_{v\in V}$ forms an independent set of commuting Pauli operators. Then the group $S_G:=<M_v>_{v\in V}$ generated by all $M_v$ forms a valid stabilizer group.

The stabilizer group $S_G=<M_v>_{v\in V}$ defines the code space
$$T(S_G):=\{\ket{\Psi}\in(\mathbb{C}^2)^{\otimes n} \mid M_v\ket{\Psi}=\ket{\Psi}, \ \text{for all} \ v\in V \}.$$
Furthermore, since are $|V|=N$ qubits and also $r=N$  independent generators, the number of encoded qubits expressed in $T(S_G)$ is given by $2^{N-r}=2^{0}=1$. Therefore, every graph $G$ can be associated to a unique (up to phase) state $\ket{\Psi_G}\in T(S_G)$ which encodes one logical qubit.



Suppose $G=C_n=(V,E)$ is the $n$-cycle graph with $n> 4$. Here, $V=\{v_1,v_2,\dots,v_n\}$ and $E=\{(v_a,v_b)\mid a\equiv b (mod \ n)\}$. Let $\ket{\Psi_{G}}\in T(S_G)$ be the associated graph state. Let $\mathcal{M}_{\bar{b}}\in S_G$,  Then the projection onto $T(S_G)$ satisfies
  $$\ket{\Psi_G}\bra{\Psi_G}=\frac{1}{2^n}\SUM{U_a}{}U_a,$$
 since $T(S_G)$ is one dimensional. Denote by $Tr_{(i-1,i,i+1)}(\ket{\Psi_G}\bra{\Psi_G})$, the reduced density operator that results by tracing out all qubit registers except for those associated to neighboring registers $i-1, i$, and $i+1$ (where addition is taken $mod \ n$). Then
  $$Tr_{(i-1,i,i+1)}(\ket{\Psi_G}\bra{\Psi_G})=\frac{1}{2^n}\SUM{U_a}{}Tr_{(i-1,i,i+1)}(U_a).$$
 Hence, consider $Tr_{(i-1,i,i+1)}(U_a)$ for an arbitrary $U_a\in S_G$. Each $U_a$ is a product of some $M_v$ operators. If  $U_a$ contains some $M_v$ which has nontrivial support on some vertex other than $v_{i-1},v_i$, or $v_{i+1}$, then $Tr_{(i-1,i,i+1)}(U_a)=0$, because the trace of any Pauli operator  is $0$.  Hence, the only nonzero contribution comes from $U_a=I$ and $U_a=M_{v_i}$ so that
$$\begin{align*}  Tr_{(i-1,i,i+1)}(\ket{\Psi_G}\bra{\Psi_G})=&\frac{1}{2^n}\SUM{U_a}{}Tr_{(i-1,i,i+1)}(U_a)\\  =&\frac{1}{2^n}\left(Tr_{(i-1,i,i+1)}(I)+Tr_{(i-1,i,i+1)}(M_{v_i})\right)\\  =&\frac{1}{2^{3}}\left(I+M_{v_i}\right) \\  =&\frac{1}{2^{3}}\left(I+X_{v_i}Z_{v_{i-1}}Z_{v_{i+1}}\right).  \end{align*}$$


 Let $G=(V_G,E_G)$ and $G'=(M_{G'},E_{G'})$ be graphs and suppose $G'$ is obtained from $G$ by adding a vertex $v'$ which has no edges. Then $V_{G'}=V_G\cup\{v'\}$, and $E_{G'}=E_G$. Let $\ket{\Psi_G}\in T(S_G)$ and $\ket{\Psi_G'}\in T(S_{G'})$ be the associated graph states of $S_G$ and $S_{G'}$, respectively. In terms of $\ket{\Psi_G}$, the state $\ket{\Psi_{G'}}$ can be expressed as
  $$\ket{\Psi_{G'}}=\ket{\Psi_G}\otimes\ket{\varphi},$$
 where $\ket{\varphi}$ is a yet to be determined single qubit state.

 In this case, the set of stabilizer generators for $G'$ is given by $\{M_v\}_{v\in V_G}\cup \{M_{v'}\}$, where $M_{v'}=X_{v'}$. All of the operators in $S_G$ act trivially on the state $\ket{\varphi}$ of $\ket{\Psi_{G'}}$, and the operator $M_{v'}$ acts trivially on all registers of the state $\ket{\Psi_{G'}}$ except for the qubit in the state $\ket{\varphi}$. However, since it must be the case that $M_v\ket{\Psi_{G'}}=\ket{\Psi_{G'}}$ for any $M_v\in S_{G'}$, then $\ket{\varphi}$ must be a $+1$ eigenstate of $M_{v'}=X_{v'}$. Therefore, $\ket{\varphi}=\ket{+}:=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$ as
  $$X\ket{+}=\frac{1}{\sqrt{2}}(X\ket{0}+X\ket{1})=\frac{1}{\sqrt{2}}(\ket{1}+\ket{0})=\ket{+},$$
  which shows that $\ket{+}$ is the unique $+1$ eigenstate of $X$. Hence, the associated graph state of $S_{G'}$ is given by
  $$\ket{\Psi_{G'}}=\ket{\Psi_G}\otimes\ket{+}.$$
 
  Now suppose $G'=(V_{G'},E_{G'})$ is obtained from $G=(V_{G},E_{G})$ by adding an edge $(v_1,v_2)$, where $(v_1,v_2)\notin E_{G}$, so that $E_{G'}=E_{G}\cup\{(v_1,v_2)\}$ and $V_{G'}=V_{G}$. Let $S_G=<M^G_v>_{v\in V_G}$ and $S_{G'}=<M^{G'}_v>_{v\in V_{G'}}$ be the stabilzer groups generated by the operators $M^G_v$ and $M^{G'}_v$, respectively. Then all  of the operators in $S_{G'}$ and $S_{G}$ are the same, except the operators $M^{G'}_{v_1},M^{G'}_{v_2}\in S_{G'}$ differ from those in $S_{G}$, by including additional $Z_{v_2}$ and $Z_{v_1}$ terms, respectively. That is,
$$M^{G'}_{v_i}= \left\{ \begin{array}{ll} M^{G}_{v_i} \ \ \text{if} \ \ v_i \neq v_1, v_2 \\ \\ M^{G}_{v_i}Z_2\ \ \text{if} \ \ v_i=v_1\\ \\ M^{G}_{v_i}Z_1\ \ \text{if} \ \ v_i=v_2.\\ \end{array} \right.$$


 Consider $\ket{\Psi_{G}}\in T(S_{G})$, and let $\ket{\Phi}=CZ_{z_1,z_2}\ket{\Psi_G}$, where $CZ_{z_1,z_2}$ is the two qubit phase gate applied to the qubits associated to vertices $v_1$ and $v_2$ given by
$$CZ=\begin{pmatrix}  1 & 0 & 0 & 0 \\  0 & 1 & 0 & 0 \\  0 & 0 &1 & 0  \\  0 & 0 & 0 & -1  \end{pmatrix}.$$
 Since $M^{G'}_{v_i}=M^{G}_{v_i}$ for $v_i\neq v_1, v_2$, and neither $X_{v_1}$ nor $X_{v_2}$ appear as factors in any of the operators  $M^{G'}_{v_i}$ in this case, then each  $M^{G'}_{v_i}$ commutes with $CZ_{z_1,z_2}$. Therefore,
$$M^{G'}_{v_i}\ket{\Phi}=M^{G'}_{v_i}CZ_{z_1,z_2}\ket{\Psi_G}=CZ_{z_1,z_2}M^{G'}_{v_i}\ket{\Psi_G}=CZ_{z_1,z_2}\ket{\Psi_G}=\ket{\Phi},$$
  in the case where $v_i\neq v_1, v_2$.
 
  For the other cases, first observe that $X_{v_1}Z_{v_2}CZ_{v_1,v_2}=CZ_{v_1,v_2}X_{v_1}$. Now suppose $v_i=v_1$, then
$$\begin{align*} M^{G'}_{v_1}CZ_{z_1,z_2}=&M^{G}_{v_1}Z_{v_2}CZ_{z_1,z_2} \\ =&M^{G}_{v_1}X_{v_1}X_{v_1}Z_{v_2}CZ_{z_1,z_2} \\ =&M^{G}_{v_1}X_{v_1}CZ_{z_1,z_2}X_{v_1}\\ =& CZ_{z_1,z_2}M^{G}_{v_1}X_{v_1}X_{v_1} \\ =&CZ_{z_1,z_2}M^{G}_{v_1}.  \end{align*}$$
 Hence,  $M^{G'}_{v_1}\ket{\Phi}=M^{G'}_{v_1}CZ_{z_1,z_2}\ket{\Psi_G}=CZ_{z_1,z_2}M^{G}_{v_1}\ket{\Phi_G}=CZ_{z_1,z_2}\ket{\Psi_G}=\ket{\Phi}$. Therefore, for all $v_i\in V_{G'}$, it follows that $M^{G'}_{v_1}\ket{\Phi}=\ket{\Phi}$, implying that $\ket{\Phi}=CZ_{z_1,z_2}\ket{\Psi_G}\in T(S_{G'})$ is the encoded graph state of $S_{G'}$.

 The consequences just shown can be applied to construct the graph state $\ket{\Psi_{C_4}}$ for the cycle graph $C_4$. In this approach, a Hadamard gate is applied  to each of the four qubits (that all begin in the $\ket{0}$ state) which puts each qubit into the $\ket{+}$  state. Then a controlled phase $CZ_{v_i,v_j}$ for each pair of adjacent vertices is applied. The resulting state produced by this circuit will then be $\ket{\Psi_{C_4}}$.

Permutation-invariant codes

Let $S_n$ be the group of permutations of the $n$-element set $[n]:=\{1 , 2, \dots, n\}$, and let $\pi\in S_n$. Define the unitary $U_\pi: (\mathbb{C}^2)^{\otimes n}\mapsto(\mathbb{C}^2)^{\otimes n}$ by
$$U_\pi(\ket{\varphi_1}\otimes\cdots\otimes\ket{\varphi_n})=\ket{\varphi_{\pi^{-1}(1)}}\otimes\cdots\otimes\ket{\varphi_{\pi^{-1}(n)}}$$
for all product states $\ket{\varphi_1}\otimes\cdots\otimes\ket{\varphi_n}$ (and extended linearly to all of $(\mathbb{C})^{\otimes{n}}$). Denote by $(i j)$ the transposition of $i,j\in[n]$ for $i\neq j$, and define the subspace
$$Q=\{\ket{\Psi}\in(\mathbb{C})^2)^{\otimes{n}} \mid U_{(i j)}\ket{\Psi}=\ket{\Psi} \  \text{for all} \ i\neq j \}.$$


An arbitrary state $\ket{\Psi}\in Q$ can be written generally as a linear combination
$$\ket{\Psi}=\SUM{}{}\gamma_k\ket{\xi_k},$$
 where $\ket{\xi_k}\in\mathcal{B}$ and $\mathcal{B}$ is a complete set of basis vectors of $Q$. Since every $\ket{\xi_k}\in Q$, must also satisfy the constraint $U_{(ij)}\ket{\xi_k}=\ket{\xi_k}$ for all $(ij)\in S_n$, each state $\ket{\xi_k}$ must be comprised of states possessing a property that remains invariant under the $U_{(ij)}$ operations. In this regard, let $\bar{b}=b_1b_2\dots b_n \in\{0,1\}^n$ with $b_i\in\{0,1\}$, and let $\ket{\bar{b}}\in(\mathbb{C}^2)^{\otimes n}$ be a $n$-qubit computational basis state. More explicitly, $\ket{\bar{b}}=\bigotimes_{i=1}^{n}\ket{b_i}$, describes the $n$-qubit state where each qubit is either in the state $\ket{0}$ or $\ket{1}$. Now define the map
  $$\omega: \{0,1\}^n\to \{0,1,\dots,n\} \ \ \text{given as} \ \  \omega(\bar{b})=\SUM{i=1}{n}b_i,$$
  which simply counts the number of $1$s appearing in the bit string $\bar{b}$, and call $\omega(\bar{b})$ the \emph{weight} of $\bar{b}$.
 
  For every $\bar{b}\in\{0,1\}^n$ and any $\pi\in S_n$, it will always be the case that $U_{\pi}\ket{\bar{b}}=\ket{\bar{b'}}$ for some $\bar{b'}\in\{0,1,\}^n$ such that $\omega(\bar{b})=\omega(\bar{b'})$, because $U_{\pi}$ will only permute the bits $b_i$ comprising the string $\bar{b}$ which preserves the  weight of the string. That is, if $\ket{\bar{b}}=\bigotimes_{i=1}^{n}\ket{b_i}$, then $U_\pi\ket{\bar{b}}=\ket{\bar{b'}}=\bigotimes_{i=1}^{n}\ket{b_{\pi^{-1}(i)}}$, where the bits of the resulting string $\bar{b'}$ are given by $b'_i=b_{\pi^{-1}(i)}$, and consequently $\omega(\bar{b})=\sum_{i=1}^{n}b_i=\sum_{i=1}^{n}b_{\pi^{-1}(i)}=\omega(\bar{b'})$.
 
  Therefore, let
  $$\ket{\xi_k}=\frac{1}{\sqrt{\binom{n}{k}}}\SUM{ \ \ \bar{b} \  : \  \omega(\bar{b})=k}{}\ket{\bar{b}}$$
  be an equally weighted superposition of the $\binom{n}{k}$ computational basis states $\ket{\bar{b}}$ with weight $\omega(\bar{b})=k$. Then it follows that $U_{(ij)}\ket{\xi_k}=\ket{\xi_k}$ for all $(ij)\in S_n$, since each $U_{(ij)}$ yields a bijection between the set of states $\ket{\bar{b}}$ having the same weight. Hence, the set of basis vectors of $Q$ is given by $\mathcal{B}=\{\ket{\xi_k} \mid  k=0,1,\dots, n\}$ consisting of $n+1$ basis vectors.
 
A projector $P$ onto the subspace $Q$ can be expressed in terms of the basis vectors in $\mathcal{B}$ as
$$P=\SUM{k=0}{n}\ket{\xi_k}\bra{\xi_k}.$$

In terms of the operators $U_\pi$, the projector can be equivalently expressed as an equally weighted superposition over all permutations as
$$P=\frac{1}{n!}\SUM{\pi\in S_n}{}U_\pi$$


Consider the set of errors
$$\mathcal{E}=\left\{\SUM{\pi\in S_n}{}a_\pi U_\pi \mid (a_\pi)_{\pi\in S_n} \subset \mathbb{C} \right\}.$$
 For the group symmetric $S_n$, recall that any permutation $\pi\in S_n$ can be expressed as a product of transpositions only. Actually, $S_n$ can  be generated by the $n-1$ transpositions of the form $(i,i+1)$ for $i\in\{1, 2, \dots, n-1\}$. This algebraic structure extends to the operators $U_\pi$, That is, for any $\pi\in S_n$,
  $$U_\pi=\PROD{(ab)\in S_n}{}U_{(ab)},$$
  where $(ab)=(i,i+1)$ for some $i\in\{1, 2, \dots, n-1\}$. Note that in this product, any particular $U_{(ab)}$ can appear multiple times. Therefore, for any $\pi\in S_n$ and any $\ket{\psi}\in Q$
  $$U_\pi\ket{\psi}=\PROD{(ab)\in S_n}{}U_{(ab)}\ket{\psi}=\ket{\psi},$$
  because $U_{(ab)}\ket{\psi}=\ket{\psi}$ for any $(ab)\in S_n$.
 
  In regards to to the correctability of the error set $\mathcal{E}$, consider any $\pi,\pi\in S_n$ and any basis vectors $\ket{\xi_k},\ket{\xi_{k'}}\in\mathcal{B}$. As a consequence of what was just shown $U_{\pi}\ket{\xi_k}=\ket{\xi_k}$ and $U_{\pi'}\ket{\xi_{k'}}=\ket{\xi_{k'}}$. Then,
  $$\bra{\xi_{k'}}U_{\pi'}^{\dagger}U_\pi\ket{\xi_k}=\ip{\xi_{k'}}{\xi_k}=\delta_{k'k}.$$
 Since the error correction conditions for a code state that
   $$\bra{\xi_{k'}}U_{\pi'}^{\dagger}U_\pi\ket{\xi_k}=c_{\pi'\pi}\ip{\xi_{k'}}{\xi_k},$$
  where the $c_{\pi'\pi}$ are constants that do not depend on the states $\ket{\xi_k}$ and $\ket{\xi_k'}$, then $c_{\pi'\pi}=1$ for all $\pi,\pi'\in S_n$.
  More generally, for any $\ket{\psi},\ket{\psi'}\in Q$ this implies
  $$\bra{\psi'}U_{\pi'}^{\dagger}U_\pi\ket{\psi}=\ip{\psi'}{\psi}$$
 
 Therefore, each $U_\pi$ for $\pi\in S_n$ is a correctable error. Then since any linear combination of correctable errors can also be corrected, any error of the form
  $$E=\SUM{\pi\in S_n}{}a_\pi U_\pi$$
  can be corrected. Thus, the set $\mathcal{E}$ is correctable.
 
 An operator basis $\{F_j\}_j$ of $\mathcal{E}$ which diagonalizes the matrix $C=(c_{ab})$ is given by $F_\pi =U_\pi$, where $\pi\in S_n$. Since the order of $S_n$ is $n!$ (meaning there are $n!$ different permutation operators), there are $n!$ many different operators $U_\pi$ in this basis. Then upon being diagonalized, the coefficients of the matrix $C$ are given by $c_{\pi'\pi}=1$ if $\pi'= \pi$ and $c_{\pi'\pi}=0$ if $\pi'\neq \pi$.
 
  For the subspace $Q$, the set of detectable errors is defined as
  $$\mathcal{E}_D:=\left\{E \mid \bra{\psi}E\ket{\phi}=c(E)\ip{\psi}{\phi}, \forall \ket{\psi},\ket{\phi}\in Q\right\}.$$
  Consider a single bit flip error, say, $E=X_1$ that applies the bit flip $X$ to the first qubit of the register. Moreover, consider the two basis states $\ket{\xi_0}$ and $\ket{\xi_1}$ of Q. Here, $\ket{\xi_0}=\bigotimes_{i=1}^{n}\ket{0}$ is the unique state with weight $0$, and $\ket{\xi_1}$ is the superposition of all states labelled by weight $1$ bit strings. Observe that $X_1\ket{\xi_0}=\ket{1}\bigotimes_{i=2}^{n}\ket{0}$, which is a state that appears in the superposition of states expressed in $\ket{\xi_1}$. Therefore,
  $$\bra{\xi_1}X_1\ket{\xi_0}=\frac{1}{\sqrt{\binom{n}{k}}}\neq 0,$$
  but yet $\ket{\xi_1}$ and $\ket{\xi_0}$ are orthogonal basis states so that $\ip{\xi_1}{\xi_0}=0$. Hence, the single bit flip error $E=X_1$ is an undetectable error by definition.  
 

Let $E=X^{\otimes n}$, and consider the two basis states $\ket{\xi_0},\ket{\xi_n}\in\mathcal{B}$ of $Q$. Then
$$E\ket{\xi_0}=X^{\otimes n}\TENSOR{i=1}{n}\ket{0}=\TENSOR{i=1}{n}\ket{1}=\ket{\xi_1},$$
Which implies that $\bra{\xi_n}E\ket{\xi_0}=\ip{\xi_n}{\xi_n}=1$. However, $\ip{\xi_n}{\xi_0}=0$ since they are orthogonal basis states, and thus
$E=X^{\otimes n}$ is an undetectable error.

More generally, let $U\in SU(2)$, with $U\neq I$, and consider the error $E=U^{\otimes n}$. According to the Shur-Weyl duality, $[E,U_\pi]=0$ for all $U\in SU(2)$ and $\pi\in S_n$. Consider an arbitrary state $\ket{\psi}\in Q$ so that $U_\pi\ket{\psi}=\ket{\psi}$ for all $\pi\in S_n$ as argued in above. Then,
$$U_\pi E\ket{\psi}=EU_\pi\ket{\psi}=E\ket{\psi},$$
Where the first equality follows from the Shur-Weyl duality. This implies that $E\ket{\psi}\in Q$.  Since, $\ket{\psi}$ was assumed to be arbitrary, this is equivalent to the statement $EQ=Q$.

Consider any basis state $\ket{\xi_j}$. Then since $EQ=Q$, it must be the case that $E\ket{\xi_j}\in Q$ so that $E\ket{\xi_j}$  itself can be expressed in terms of the basis $\mathcal{B}$ of $Q$. That is,
$$E\ket{\xi_j}=U^{\otimes n}\ket{\xi_j}=\SUM{k=1}{n=1}\alpha_k\ket{\xi_k}.$$
Then there must exist at least one $\alpha_{k'}\neq 0$, and perhaps more. Moreover, since $U\neq I$ by assumption, $k'\neq j$. Choose one such basis state $\ket{\xi_{k'}}$ with $\alpha_{k'}\neq 0$. With this choice,
$$\bra{\xi_{k'}}E\ket{\xi_j}>0.$$
However, since $\ip{\xi_k'}{\xi_j}=0$ this implies that
$$\bra{\xi_{k'}}E\ket{\xi_j}\neq c(E)\ip{\xi_k'}{\xi_j}.$$
Therefore, the error $E=U^{\otimes n}$ is undetectable.

Linear Optical Quantum Computation: The KLM Proposal

Abstract

A brief overview of quantum optics is given, and some early proposals for quantum computation using optics are discussed. The main focus is invested on the Knill, Laflamme, and Milburn proposal \cite{KLM} which achieves scalable universal quantum computation using only linear optics and the ability to prepare and detect single photon states.

(** All figures displayed in this post are borrowed from arXiv:quant-ph/0512104 **)


Introduction

Computation, although often thought of entirely in the abstract, is a physical process. Thus, a physical system able to undergo controlled transformations is a prerequisite for any successful computation. In quantum computation, the physical nature of the necessary system becomes even more relevant in order to harness sufficient quantum phenomenon. Despite many distinct paradigms for physically realizing quantum computation, the setting of quantum optics offers unique advantages. In quantum optics, photons are deployed as the main carriers of information, and various physical devices such as phase shifters and beam splitters can be used to enact transformations on the photon states to perform computation. The ability to operate at high temperatures, and long decoherence times are examples of some of the advantages gained when working with quantum optics. However, the same properties of light that offer such benefits also bring some disadvantages. In particular, it is generally difficult to make photons interact with one another. Such interactions seem necessary in order to implement multiple qubit entangling gates---a main requirement for achieving universal quantum computation.

In this post, a brief overview of quantum optics is given and various proposals for quantum computing in this optical setting are discussed. The main proposal described here is that of Knill, Laflamme and Milburn (KLM) \cite{KLM}, who offer a scheme for achieving scalable universal quantum computation using only linear optics (LOQC) that overcomes many detrimental features that existed in previous proposals.

Bosonic Modes

In quantum optics, photons are the main physical entities at play.  When referring to photons in what follows, we will mean noninteracting spin-less bosons. In this setting, the electromagnetic field is quantized in which the energy associated to the physical system  is given by the Hamiltonian
$$\hat{H}=\displaystyle\sum_{k}^{}\hbar\omega(\ani_k\cre_k +\frac{1}{2}),$$
where $\ani_k$ and $\cre_k$ are the annihilation and creation operators associated to mode $k$. A bosonic mode, $k$, can be considered as a quantum system whose state space is spanned by the number states $\ket{n}_k$, for $n=1,2,3,\dots$, where $n$ represents the number of photons in the mode $k$. The number states of a mode $k$ form a complete orthonormal set so that $\ip{n}{m}=\delta_{nm}$. The state $\ket{0}$ will denote the state in which every mode $k$ is in the state $\ket{0}_k$. In this way the observables of a particular mode $k$ are given by the annihilation and creation operators satisfying
$$\cre_k\ket{n}_k=\sqrt{n+1}\ket{n+1}_k$$
and
$$\begin{align*} \ani_k\ket{n}_k&=\sqrt{n}\ket{n-1}_k   \text{for}   k\geq 1, \\ \ani_k\ket{0}_k&=0. \end{align*}$$
Thus, any number state $\ket{n}_k$ can be expressed in terms $\ket{0}_k$ state
$$\ket{n}_k=\frac{(\cre_k)^n}{\sqrt{n!}}\ket{0}_k.$$
Moreover, the creation and annihilation operators satisfy the canonical commutation relations
$$[\ani_k,\cre_{k'}]=\delta_{kk'} \ \ \ \text{and} \ \ \ [\ani_k,\ani_{k'}]=[\cre_k,\cre_{k'}]=0.$$



Single Photon Creation and Detection

Necessary requirements for the paradigm of quantum optics are the abilities to both create single photons and to detect them reliably. In addition to the linear elements to be introduced later, controlled photon creation and detection are essential resources necessary for efficient linear optical quantum computation. Even though perfect reliable photon creation and detection are difficult to achieve in practice, this will be taken somewhat for granted in describing later protocols for LOQC where it is implicitly assumed that ideal photon creation and detection is readily available.

 In regards to single photon creation, methods can be essentially classified as either deterministic or probabilistic. A probabilistic source, for instance, may involve multiple photon detections where a second photon can be used to signal the creation of the first ``'single" photon. Such schemes are commonly used for quantum information processing. However,  deterministic means which are able to produce single photons on demand in a controlled way are beneficial. One way of achieving this is through spontaneous parametric down conversion (SPDC), in which photons interact with a nonlinear crystal to occasionally create a pair of correlated photons \cite{Kok}.

Although SPDC is commonly used for quantum optical purposes, other means involving single photon emission through the controlled stimulus of various physical systems is also possible \cite{Migdall}. It is also worth mentioning that single photon states can be created without the use of nonlinearities using weak squeezing where the Hamiltonian $\hat{s}_{jk}=\ani_j\ani_k+\cre_j\cre_k$ is applied to the vacuum state in order to produce specific number states in the modes. Experimental realizations of such a technique have been demonstrating in \cite{Hong}.

The matter of photon detection comes in two varieties: being able to distinguish merely between zero and some nonzero number of photons in a mode, or the more refined ability of actually being able to count the precise number of photons in a mode. This latter means of photon detection is required for various applications of LOQC. Such measurements involve some particle detector which destructively determines the presence of photons. One way to approximately count the number of photons in some mode $k$ is to use optical elements to effectively split the mode into $N$ other modes $k_1,k_2,\dots, k_N$, and then use $N$ particle detectors to count the number of photons in each of the modes $k_l$. Now suppose that mode $k$ has $n$ photons, then the probability that any of the modes $k_l$ has more than one photon is given by $1-\frac{N!}{(N-n)!N^n}\leq\frac{n(n+1)}{2N}$. Thus, provided that the number of photons $n$ in the mode is not too large, or if the number of split modes $N$ is sufficiently large, the probability of any of the modes $k_l$ having more than one photon is small. Therefore, with high probability the number of actual photons in the main mode $k$ would be given by the number of photon detectors (out of $N$ many) that detect a photon. Further details pertaining to photon detection and its associated errors can be found in \cite{Kok}.


Linear Optical Elements

The main dynamical elements that induce state transformations in linear optics are phase shifters and beam splitters. An important property of such passive linear optical elements is that they preserve the boson number of the states. That is, if $U$ represents the unitary operator associated with such a state transformation, then $U^\dagger\ket{0}=\ket{0}$. The effect of $U$ on the creation operators can then be described as follows:
$$\begin{align*} U\cre_k\ket{0}=U\cre_kU^\dagger\ket{0}=\displaystyle\sum_{j}u_{jk}\cre_{j}\ket{0}, \end{align*}$$
where $U=(u_{jk})_{jk}$ gives the matrix coefficients of $U$. By letting $\hat{b}^{\dagger}_k=U\cre_k$ represent the outmode mode, an optical element corresponding to the transformation $U$, is said to be \emph{linear} if each output mode is a linear combination on the input modes $\cre_j$:
$$\hat{b}^{\dagger}_{k}=\displaystyle\sum_{j}u_{jk}\cre_{j}\ $$

The phase shift optical element $P_\phi$, which acts on a single mode $k$, has the effect of introducing a phase factor $e^{in\phi}$ on the state $\ket{n}_k$.   This transformation can be described by the Hamiltonian $\hat{N}_k=\cre_k\ani_k$ so that the unitary representing the action of the phase shift is given by $U(P_\phi)=e^{i\phi\cre_k\ani_k}$. In an optical network, the phase shift element acting in a particular mode will be depicted schematically as shown in the figure below.

A phase shift element $P_\phi$.

The other main optical element predominantly used in linear optics is a beam splitter $B^{(jk)}_{\theta, \phi}$ that is defined to act on two different modes $j$ and $k$ of the system. The action of a beam splitter can be described by the Hamiltonian $\hat{B}_{jk}=e^{i\phi}\cre_j\ani_k+e^{-i\phi}\ani_j\cre_k$, with corresponding unitary matrix given by
$$U(B_{\theta, \phi})=\begin{pmatrix} \cos\theta &-e^{i\phi}\sin\theta \\ e^{-i\phi}\sin\theta & \cos\theta \end{pmatrix},$$
where mode indices have been suppressed. The schematic symbol for the beam splitter $B^{(jk)}_{\theta, \phi}$ is shown in the figure below.

A beam splitter element $B_{\theta,\phi}$.

Quantum Computation with Linear Optics

Given the paradigm of quantum linear optics discussed in the previous sections, the objective now is to show how quantum computation can be achieved in this setting. This requires a suitable way to encoding qubits using bosonic modes, and a means of implementing quantum gate operations  on the qubits using optical elements consisting of various phase shifters and beam splitters. Again, also implicit in these constructions will be a means of preparing and measuring qubits by means of photon creation and detection. In what follows, after discussing some schemes for quantum computation which fail to do so, a general scheme for quantum computation that does not rely on nonlinear optical elements but yet has efficient scalability properties will be discussed.

Early Proposals

Traditional quantum optics models (e.g. \cite{Chuang1}, \cite{Chuang2}) may use $n$ photons to represent $n$ qubits, and allow the use of nonlinear optical elements to achieve $2$ qubit quantum gates.  One example of a nonlinear element is a Kerr medium, which has the property that its refractive index contains nonlinear terms so that a beam traversing the Kerr medium undergoes a phase shift proportional to the beam's intensity. Moreover, photons in two paths incident to the Kerr medium can induce controlled-phase operations allowing for universal quantum computation when considered together with arbitrary single qubit operations. An early example concerning the implementation of a quantum optical Fredkin gate has been achieved through these means as demonstrated in \cite{Milburn}.

The issue with using nonlinear optical elements through a natural Kerr medium, is the high degree of nonlinearity that must be present in order to implement gates of interest making such methods extremely difficult to implement in practice.
  
   A proposal using only linear optics that can achieve universal computation was given by Adami and Cerf in \cite{Adami}. This proposal uses just a single photon that has access to $2^n$ distinct spatial paths or modes to encode $n$ qubits. Simple gate implementations in this scheme are achieved through particular arrangements of only linear optical elements consisting of phase shifters and beam splitters. The major drawback here is that $2^n-1$ beam splitters are needed to set up the $2^n$ paths necessary to encode $n$ qubits. Since this number is exponential in $n$, general quantum computations done this way will require an exponential amount or resources (beam splitters). Hence, this Adami-Cerf proposal does not possess the desired scaling properties for efficient quantum computation to be accomplished in general. Regardless, in \cite{Adami}, Adami and Cerf use their scheme to provide experimental realizations of the quantum teleportation protocol---a nontrivial quantum computation.


The KLM Proposal

Despite initial beliefs that scalable universal quantum computation may only be achieved when nonlinear optical elements are exploited, in \cite{KLM} Knill, Laflamme, and Milburn offered a scheme that yields efficient quantum computation using only linear optics together with single photon sources and detectors. The key insight made here is that a particular two qubit gate can be executed non-deterministically with some probability of success through the exclusive use of linear optical elements. Furthermore, this gate can be implemented through gate teleportation, which effectively reduces the problem of applying the two qubit gate to the problem of constructing a special state instead. The probability of success associated to such a procedure can be increased arbitrarily through the preparation of richer states and by using quantum error correction to eliminate certain errors. With these tools the KLM scheme offers a scalable means of quantum computation. An outline of the KLM proposal is provided in the following sections.

Qubit Encodings
Consider an optical system with two distinct modes $a$ and $b$ representing distinct spatial paths, and suppose a single photon is present in either of the two modes. The possibilities present for the state of the system can be used to encode a single qubit by letting the two computational basis states be given by
$$\begin{align*} \ket{0}_q&:=\ket{0}_a\ket{1}_b=\ket{01}_{ab} \\ \ket{1}_q&:=\ket{1}_a\ket{0}_b=\ket{10}_{ab}. \end{align*}$$
Here, the presence of the subscript $q$ for the qubit basis states does not refer to a mode, but is included to denote that the state $\ket{\cdot}_q$ represents a qubit. Such an encoding of qubits is often referred to in the literature as ``dual rail logic". Another possible way to encode an optical qubit is through the polarization properties of photons. If $\ket{H}$ and $\ket{V}$ represent the state of a single photon being horizontally and vertically polarized, respectively, then the computational basis states of the qubit can be alternatively identified as
$$\ket{0}_q:=\ket{H} \ \ \ \text{and} \ \ \ \ket{1}_q:=\ket{V}.$$
Although both of these qubit representations offer their own utilities in certain contexts, the dual rail logic encoding with be the used in what follows. However, it should be noted that one representation can be transformed to the other using linear optical elements as discussed in \cite{Myers}.

Single Qubit Gates
A natural consequence of linear optics using only phase shifters and beam splitters is that single qubit operations are easily implemented. Recall that an arbitrary single qubit unitary $U$ can be expressed as a product of rotations around the $Y$ and $Z$ axis of the Bloch sphere. More explicitly
$$U=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta),$$
where $R_z(\theta)=e^{i\frac{\theta}{2}\pz}$ and $R_y(\phi)=e^{i\frac{\phi}{2}\py}$ are the rotations about the corresponding axis. Here, $\pz$, $\py$ are the standard Pauli operators. The relevance of this decomposition will become apparent after describing the quantum gates corresponding to phase shifters and beam splitters.

By applying a phase shift to, say, the top mode of a dual rail encoded qubit a relative phase is introduced in the state. A schematic representation of such a gate is shown in the following figure.

A phase shift gate acting on the top mode of a dual rail qubit.

 To see this, consider an arbitrary single qubit state $\ket{\psi}_q=\alpha\ket{0}_q+\beta\ket{1}_q$. Then the action of $U(P_\phi)$ on this state is given by
$$\begin{align*} U(P_\phi)\ket{\psi}_q&=\alpha U(P_\phi)\ket{0}_q+\beta U(P_\phi)\ket{1}_q \\ &=\alpha U(P_\phi)\ket{0}_a\ket{1}_b+\beta U(P_\phi)\ket{1}_a\ket{0}_b \\ &=\alpha \ket{0}_a\ket{1}_b+\beta e^{i\phi}\ket{1}_a\ket{0}_b \\ &=\alpha\ket{0}_q+\beta e^{i\phi}\ket{1}_q \end{align*}$$
Further manipulations of this transformed state gives
$$\begin{align*} U(P_\phi)\ket{\psi}_q&=\alpha\ket{0}_q+\beta e^{i\phi}\ket{1}_q \\ &=e^{i\phi/2}(e^{-i\phi/2}\alpha\ket{0}_q+e^{i\phi/2}\beta\ket{1}_q) \\ &=e^{i\phi/2}e^{-i\phi Z_q/2}(\alpha\ket{0}_q+\beta\ket{1}_q) \\ &=e^{i\phi/2}R_z(\phi)(\alpha\ket{0}_q+\beta\ket{1}_q), \end{align*}$$
where now $Z_q$ denotes the effective Pauli-$Z$ operation on the encoded qubit. This shows that (up to a physically irrelevant global phase factor $e^{i\phi/2}$) the action of the phase shift $P_\phi$ amounts to a rotation about the $Z$ axis of the Block sphere.

Now consider the beam splitter $B_{\theta,0}$ acting on the two modes of a single dual rail qubit as depicted in the figure.

 A beam splitter acting on the two modes of a single dual rail qubit.

In this case, the matrix representation of $B_{\theta,0}$ is given by
$$U(B_{\theta, 0})=\begin{pmatrix} \cos\theta &\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix},$$
and its action on an arbitrary single qubit $\ket{\psi}_q=\alpha\ket{0}_q+\beta\ket{1}_q$ is given by
$$\begin{align*} U(B_{\theta,0})\ket{\psi}_q&=\alpha U(B_{\theta,0})\ket{0}_q+\beta U(B_{\theta,0})\ket{1}_q \\ &=\alpha U(B_{\theta,0})\ket{01}_{ab}+\beta U(B_{\theta,0})\ket{10}_ab \\ &=\alpha(\cos(\theta)\ket{01}_{ab}-\sin(\theta)\ket{10}_{ab})+\beta(\cos(\theta)\ket{10}_{ab}+\sin(\theta)\ket{01}_{ab}) \\ &=\cos(\theta)(\alpha\ket{01}_{ab}+\beta\ket{10}_{ab})-\sin(\theta)(\alpha\ket{10}_{ab}-\beta\ket{01}_{ab}) \\ &=e^{i\theta Y_q}(\alpha\ket{01}_{ab}+\beta\ket{10}_{ab} \\ &=R_y(-2\theta)\ket{\psi}_q, \end{align*}$$
where $Y_q$ represents the Pauli-$Y$ operation on the qubit. Hence, the beam splitter $B_{\theta,0}$ has the effect of performing a rotation of $-2\theta$ about the $Y$ acid of the Block sphere.

With these results in mind, together with the decomposition of an arbitrary single qubit unitary in terms of Bloch sphere rotations about the $Z$ and $Y$ axis described above, it is readily seen that any single qubit unitary can be executed by simply using a phase shift $P_\delta$ and a beam splitter $B_{-\gamma/2,0}$ followed by another phase shift $P_\beta$.

A Two Qubit Gate: $\mathbf{\con{Z}}$
In the previous section it was shown how arbitrary single qubit transformations can be accomplished using only linear optical elements consisting of phase shifts and beam splitters. It is known that in order to achieve universal quantum computation, two-qubit gates are also necessary in addition to the single qubit gates. Specifically, the two-qubit gate must be an entangling gate to ensure universality. A standard conventional choice for such a two-qubit entangling gate is the controlled-NOT gate $\con{X}$. However, for our purposes the controlled-SIGN gate $\con{Z}$ will be implemented instead. Abstractly, the action of the $\con{Z}$ gate is given by $\ket{u}\ket{v}\mapsto(-1)^{u\cdot v}\ket{u}\ket{v}$, where $u,v\in\{0,1\}$. In this way, $\con{Z}$ is related to $\con{X}$ through the relation $\con{Z}=(I\otimes H)(\con{X})(I\otimes H)$, where $H$ is the Hadamard transform.

In order to perform the $\con{Z}$ gate, observe that a basic transformation of the form
$$\alpha\ket{0}+\beta\ket{1}+\gamma\ket{2} \mapsto \alpha\ket{0}+\beta\ket{1}-\gamma\ket{2}$$
is needed. This operation will be called the nonliner sign shift gate, denoted by $NS_{-1}$, for reasons that are suggested by the name. Since $NS_{-1}$ is a nonlinear gate its action can not be given using only linear optical elements. Instead, the $NS_{-1}$ gate will be implemented nondeterministically (probabilistically) using just linear optics and ancilla modes. Once this is achieved for the $NS_{-1}$ gate,  the probabilistically implemented $NS_{-1}$ gates will be used to construct a probabilistic implementation of $\con{Z}$.

Consider three spatial bosonic modes where mode $1$ contains the main state of interest $\ket{\psi}_1$, and modes $2$ and $3$ serve as ancilla registers initialized in the states $\ket{1}_2$ and $\ket{ 0}_3$. Let the initial state of mode $1$ be in the state $\ket{\psi}_1=\alpha\ket{0}+\beta\ket{1}+\gamma\ket{2}$. Then it can be shown that the following optical network shown in the figure below produces the state $NS_{-1}\ket{\psi}_1$ in the first mode provided that the to ancillary modes are measured to be precisely $\ket{1}_2\ket{0}_3$.

 An optical circuit for the nonlinear sign shift gate $NS_{-1}$.

For the particular action of $NS_{-1}$ the angle parameters of the optical elements are given by
$$\begin{align*} &\theta_1=22.5^{\circ},   \phi_1=0^{\circ}\\ &\theta_2=65.5302^{\circ},   \phi_2=0^{\circ} \\ &\theta_3=-22.5^{\circ},   \phi_1=0^{\circ} \\ &\phi_4=180^{\circ}. \end{align*}$$
The corresponding unitary matrix $U(NS_{-1})$ acting on the three modes is given by
$$U(NS_{-1})=\begin{pmatrix} 1-\sqrt{2} & \frac{1}{\sqrt{\sqrt{2}}} & \sqrt{\frac{3}{\sqrt{2}}-2} \\ \frac{1}{\sqrt{\sqrt{2}}} &\frac{1}{2} & \frac{1}{2}-\frac{1}{\sqrt{2}} \\ \sqrt{\frac{3}{\sqrt{2}}-2} & \frac{1}{2}-\frac{1}{\sqrt{2}} & \sqrt{2}-\frac{1}{2} \end{pmatrix}.$$
 If the two ancillary modes after measurement are in a state different from $\ket{1}_2\ket{0}_3$, the state in the first mode is not the desired state $NS_{-1}\ket{\psi}$. Since there are $4$ possible output states for the two ancilla modes, and only one of these states (namely $\ket{1}_2\ket{0}_3$) yields the desired outcome in the first mode, the probability of success in this nondeterministic implementation of $NS_{-1}$ is $1/4$.

 Consider two dual rail qubits $\ket{Q_1}=\alpha\ket{0}_q+\beta\ket{1}_q$ and $\ket{Q_2}=\gamma\ket{0}_q+\delta\ket{1}_q$ in arbitrary states a nondeterministic $\con{Z}$ gate can be performed on these two qubits by making using of two $NS_{-1}$ gates as shown in the figure below. Since there are two $NS_{-1}$ gates, and each requires the use of two ancilla modes and has a individual success probability of $1/4$, there are four ancilla modes in total and the success probability of implementing the $\con{Z}$ gate is $1/16$.

 An optical network implementing the controlled-SIGN gate $\con{Z}$.

Gate Teleportation of $\mathbf{\con{Z}}$ 

 It has now been shown how to implement, albeit probabilistically, a two-qubit gate $\con{Z}$  which is universal for quantum computation when considered together with single qubit gates. Although this implementation was accomplished using linear optical elements alone, the inherent probabilistic nature of the gate does not allow for scalable quantum computation due to low success rates. The next key insight utilized in the KLM scheme helps overcome this obstacle by increasing the success probability through the means of gate teleportation. Such a teleportation procedure was originally discussed in \cite{Got}.

 In essence, by harnessing quantum teleportation the problem of needing to apply the probabilistic gate $\con{Z}$ is reduced to the problem of having to prepare a certain state "off-line". This has the advantage of first being able to ensure the proper state is created before carrying on with the gate implementation so that the states in the rest of the system do not get corrupted. In this way, if an error does occur during the state preparation phase it will be known. Then the state preparation can simply be repeated until the desired state is created successfully.

 To understand this more thoroughly, consider two qubits $\ket{\psi_1}_q$ and $\ket{\psi_2}$ on which a $\con{Z}$ is to be applied. This can be accomplished, although it may seem superfluous, by first teleporting the two qubits and then applying $\con{Z}$ as suggested in the figure below.

 Teleportation of two qubits follows by a $\con{Z}$ gate. The region contained in side the dashed/dotted box is the state preparation area.

Since $(\con{Z})^2=I$ consider adding the trivial action of two $\con{Z}$ gates prior to the correction procedure for the teleportation as shown in the following figure.

 Teleportation with the trivial addition of two $\con{Z}$ gates before the measurement phase.

 Focusing on the two middle registers of the network, and applying certain relations for when a Pauli operator is conjugated by a $\con{Z}$, it is seen that these sequences of gates containing $\con{Z}$ operations can equivalently expressed without any $\con{Z}$ gates as
  $$(\con{Z})(Z^{m'_1}X^{m_1}\otimes Z^{m'_2}X^{m_2})(\con{Z})=Z^{m'_1}X^{m_1}Z^{m_2}\otimes Z^{m_1}Z^{m'_2}X^{m_2} ,$$
  where $m_1, m'_1$ and  $m_2,m'_2$ are the two classical bits given by the measurements outcomes of the upper and lower teleportations, respectively. This is more clearly depicted in the the following figure.

 Teleportation with a $\con{Z}$ gates in the state preparation area and  only Pauli gates after measurement.

 Thus, it is seen here that there is only a single $\con{Z}$ gate that appears anywhere in the optical circuit. Moreover, this $\con{Z}$ gate has been delegated to the state preparation phase of the teleportation procedure, and the only gates that are to be applied after measurement are simply single qubit Pauli operators. Therefore, the only probabilistic aspect that comes into play when implementing the $\con{Z}$ gate can be thought of has happening ``off-line" so that any failure that may occur in the $\con{Z}$ implementation does not jeopardize the rest of the computation.

 To complete the implementation of $\con{Z}$ using only linear optical elements, it remains to describe an optical network that executes the teleportation task. As described in \cite{Myers}, a general teleportation protocol can be accomplished using the network displayed below.

An optical network describing the standard teleportation protocol.

Now, all of the elements introduced thus far can be combined to give a complete linear optical network for the implementation of $\con{Z}$ as shown:

 The complete optical network for the nondeterministic implementation of $\con{Z}$ using teleportation.

 Increasing the Success probability of $\mathbf{\con{Z}}$

 The successes probability associated to the probabilistic implementation of $\con{Z}$ described in the previous sections cannot be made arbitrarily close to $1$ in a scalable manner. In order to achieve better scaling rates, the state constructed during the state preparation phase of the teleportation protocol can be modified. This modification involves creating  more complex entangled states which involve more bosonic modes as a resource. By creating richer states to be used, the success probability of $\con{Z}$ can be made arbitrarily close to $1$ in a scalable manner. However, the catch here is that the appropriate states required can be difficult and resource intensive to create. The next improvement in the KLM proposal is to avoid having to prepare increasingly complex states, by using active error correction to correct errors that may occur during this stage. By analyzing the particular nature of the errors in this context, appropriate error correcting codes can be deployed that increase the success probability of $\con{Z}$. For the sake of brevity, further details pertaining to these aspects of the KLM proposal will be omitted here. The interested reader is invited to enlighten themself through references (\cite{KLM},\cite{Kok},\cite{Myers},)



Conclusion

 In this present work, a brief general overview of quantum optics was given and various proposals realizing quantum computation through quantum optics were discussed. The main scheme focused on here was the $KLM$ proposal which achieves scalable linear optical quantum computation, using only linear optical elements (such as phase shifters and beam splitters) together with the ability to prepare ancilla modes and make photon detections. Key features of this scheme that allow for scalability are the use of quantum teleportation and error correction to achieve arbitrarily large success probabilities in an efficient manner.

 Experimental demonstrations realizing various aspects of the KLM scheme have been carried out in the field. In \cite{Okamoto},  a controlled-NOT, or $\con{X}$ gate, was successfully implemented. In \cite{Pittman}, a demonstration of quantum error correction using linear optics was described. Some more exotic experiments include the observation of anyonic features in a toric code simulation using LOQC  in \cite{Pachos}, and another more recent demonstration of topological error correction in \cite{Yao}. The latter experiment makes use of the paradigm of \emph{one-way quantum computation} \cite{Walther} that involves the preparation of an initial \emph{cluster state} \cite{Nielsen}, which is then subject exclusively to various measurements conditions on the outcomes of previous measurements. This approach to quantum computation has its own merits, and when implemented with LOQC each paradigm further benefits the other. That is, cluster state/one-way quantum computation offers yet another means for improving LOQC.