format: text

text:
# Electrodynamics of the vortex lattice in untwinned YBaCuO by complex impedance measurements

## Abstract

We report complex impedance measurements in an untwinned YBaCuO crystal. Our broad frequency range covers both the quasi static response and the resistive response of the vortex lattice. It allow us to characterize the irreversibility line without the need of any frequency dependent pinning parameters. We confirm the validity of the two modes model of vortex dynamic, and extract both the surface critical current and the flux flow resistivity around the first order transition $`T_m`$. This latter is identified by the abrupt loss of pinning and by an unexpected step of $`\rho _{ff}(T)`$ at $`T_m`$.

The dynamic response of a vortex lattice is mainly determined by the critical current $`I_c`$ and by the flux flow resistivity $`\rho _{ff}`$. The classical method used to measure these values is to pass a transport current in the superconducting sample and to measure the voltage $`V`$ generated by the vortex lattice flow. A critical current can be extracted by extrapolating the linear part of this $`V(I)`$ curve down to $`V=0`$, and the flux flow resistance is given by the slope of this linear part. This simple and powerful method is unfortunately not applicable for high $`T_c`$ materials, due to the high critical current in the pinned vortex state, and to the corresponding heating due to Joule effect in the contact leads. Another way to proceed is to measure the high frequency skin depth of the complex penetration nonoupt3 . This response has been first observed by Gittleman and Rosenblum, who noticed that the linear high frequency response of a pinned vortex lattice mimics the ideal response of a free vortex lattice (the viscous force becomes greater than the ”pinning force” at high frequencies) Gittleman . On the contrary, the low frequency regime is linked to the critical current via the quasi static regime (the ”Campbell” regime) where the penetration $`\lambda _{ac}`$ is purely real (inductive response) as in the Meissner state campbell . Between these two regimes, the frequency spectrum around the depinning frequency $`\mathrm{\Omega }_p`$ is the quantity of interest for discriminating between different types of pinning state (bulk or surface)nono . Therefore, the frequency response of the vortex lattice allows investigation of the inductive and the resistive regimes. It is a powerful method to characterize both pinned and depinned vortex states. A small ac field is used as a probe, and one detects the vortex response in the form of a susceptibility, surface impedance or resistivity. $`HT_c`$ materials have been extensively studied by these different ac techniques, but it is quite difficult to draw an unique picture. Ac susceptibility focuses mainly on the so called loss peak ($`\chi _\mathrm{"}`$ peak) and on its frequency dependence. After strong controversy about its significance (onset of superconductivity worthington , melting transition gammel , depinning transition vanderberg …), other interpretations deal with the finite size effect of a resistivity driven by thermal depinning steel  supple . On the other hand, strong contradictions exist between the resistivity values and the expected geometrical frequencies steel , which raise questions about this theoretical treatment of vortex dynamics.

Among other cuprates, the case of untwinned YBaCuO is of particular interest. It is now obtained with a large enough size to avoid spurious size effects which may obscure experimental signatures contained in the full spectrum of the depinning transition. Moreover, thermodynamical evidence of a first order transition separating a pinned vortex state and a depinned vortex state have appeared recently marcenat . This transition is usually interpreted as the melting of a Bragg-Glass phase into a liquid phase without pinning thierry . By analogy with real crystals, thermally induced displacements of bulk pinned vortices added to a Lindemann criterion are the key elements of this transition. Nevertheless, the properties of these two phases are not so well known. In particular, it is usually assumed that vortex lattice pinning and dynamics are quite different in high $`T_c`$ materials compared to what is currently observed in low $`T_c^{}s`$. To evidence peculiarities of vortex dynamics in $`HT_c`$ materials, one has to perform experiments, the analysis of which successfully applies in conventional superconductors. As an example, high temperatures should lead to strong thermally activated behaviour, which is supposed to be reflected in pinning properties, leading to dominant thermally driven depinning. In such a case, the ac response should be quite different from what is observed in the samples where thermal activation was shown to be negligible for vortex depinning campbellevetts .

In this paper, we present a study of vortex lattice depinning in an untwinned YBaCuO crystal by mean of complex surface impedance measurements. Due to the important role of skin effects, we express this impedance in the form of a complex penetration depth. If the measurements of these complex penetration depths versus temperature looks quite complicated to interpret, due to frequency dependent features, we show that a study of the depinning spectrum leads to a simpler picture of a surface pinned vortex lattice with a bulk free flow resistivity, as it is observed in several conventional low $`T_c`$ superconductors nono . Nevertheless, the data exhibit two important differences. We observe the well known disappearance of the critical current at $`T_m<T_{B_{c2}}`$, but this disappearance is simultaneous with a less expected step in the temperature dependance of $`\rho _{ff}`$.

The sample is an untwinned crystal of $`YBa_2Cu_3O_{7\delta }`$ ($`(\mathrm{}_a=L=600,\mathrm{}_b=3000,\mathrm{}_c=1000)\mu `$m3), the preparation of which was detailed in ref rykov . The post annealing procedure and the high $`T_c`$ of $`93.5K`$ corresponds to the optimally doped state with $`\delta =0.07`$ in the Lindemer scale. Normal state resistivitity $`\rho _b`$ has been measured using standard four probe techniques and gives a value of about 40 $`\mu \mathrm{\Omega }.cm`$ at $`100K`$. Both this low value and the high $`T_c`$ attest to the good quality of the sample, as do the observed magnetization step at the first order transition rykov2 . The main part of the experimental set up consists of a waveform generator (DS345) and two lock-in amplifiers (SR850 and SR844), so as to cover a frequency range of about $`30Hz30MHz`$. The ac response is the flux taken by a small pick-up coil, directly glued to the sample, which reposes, itself, in the excitation coil. We have carefully checked that the applied alternative field $`b_{ac}=b_oexp(i\mathrm{\Omega }t)`$ has a low enough magnitude $`(1\mu T)`$ to stay in the linear regime. The complex penetration depth is then given by $`\lambda _{ac}=\varphi _{ac}/2\mathrm{}_bb_o=\lambda ^{}+i\lambda \mathrm{"}`$ (Fig. 1). The whole set up drives to an experimental resolution of few microns, and hence the London penetration can be easily neglected. Therefore, the calibration of the phase and of the zero of penetration have been done using the Meissner state as a reference ($`\lambda ^{^{}}=\lambda ^\mathrm{"}=0`$). For the highest frequency points, we have renormalized the signal using a small reference coil near the sample (when high frequencies and circuitry began to cause phase shifts). The complete penetration has been measured in the normal state at 100 K and at low frequency and the resistivity value has been confirmed by a skin effect fit which gave a value of $`\rho _b40.5\mu \mathrm{\Omega }.cm`$. As the theoretical models of interest are one dimensional in the simplest case, one has to choose a geometry which is as close as possible to a 1D penetration (Fig. 1). $`b_{ac}`$ is applied along the c-axis and the flux is measured through the ($`\stackrel{}{a},\stackrel{}{b}`$) surface. Most of the data were taken in the geometry $`\stackrel{}{B}//\stackrel{}{a}`$. In this case, the currents are mainly confined in the ($`\stackrel{}{b},\stackrel{}{c}`$) surfaces. This is specially true at high frequencies which restrict the penetration of the resistive wave in a thin layer. Vortices are shaken on the ($`\stackrel{}{b},\stackrel{}{c}`$) surface and the wave penetrates along the $`\stackrel{}{a}`$ direction. In the mixed state, there is also an anisotropy induced by the Josephson relation ($`\stackrel{}{E}=\stackrel{}{V_L}\stackrel{}{\omega }`$ so the electric field // $`\stackrel{}{j_b}`$ is perpendicular to the vortex field $`\stackrel{}{\omega }`$). The small part of the current along the $`\stackrel{}{a}`$ direction (along the vortices) can thus be neglected. To confirm the main conclusion of this study, a few measurements have been taken with $`\stackrel{}{B}//\stackrel{}{c}`$. Even if this geometry does not allow as many quantitative results, because of the problems of the closing currents along the $`\stackrel{}{a}`$ direction which are now perpendicular to vortices, the results were typically the same. The data presented here were taken at a magnetic field of 6 T.

Before discussing the experimental results, we have to recall the main features of the linear response of a vortex lattice. At high frequencies $`\mathrm{\Omega }\mathrm{\Omega }_p`$, all the models of ac response predict the response of a resistive medium: $`\lambda _{ac}=\lambda _{bulk}=\lambda _{ff}=\frac{(1+i)\delta _{ff}}{2}`$, where $`\delta _{ff}=\sqrt{\frac{2\rho _{ff}}{\mu _o\mathrm{\Omega }}}`$ is the usual flux-flow skin depth. A review of the ac response of bulk pinned vortices can be found in the ref vanderbeek . The main idea is that the bulk pinning response is governed by a modified skin depth equation with one mode. In the simplest case, this leads to $`K_{bulk}=(\lambda _c+\frac{\delta _{ff}}{2i})^1`$ campbell , ($`\lambda _c=\sqrt{\frac{B^2}{\mu _o}\alpha _{Lo}}`$ is the campbell length and $`\alpha _{Lo}`$ the Labusch parameter ). The thermal activation is taken into account when rewriting $`\alpha _{Lo}`$ as $`\alpha _L=\alpha _{Lo}\frac{i\mathrm{\Omega }}{1+i\mathrm{\Omega }\tau }`$ where $`\tau =\tau _oexp(\frac{U}{kT})`$ is the creep relaxation time vanderbeek  coffey  brandt . It is formally equivalent to introducing a low frequency skin effect governed by an activated resistivity $`\rho _{ff}exp(\frac{U}{kT})`$. Bulk pinning models with thermal activation predicts so two depinning frequency, $`\mathrm{\Omega }_p=\frac{\rho _{ff}}{\mu _o\lambda _c^2}`$ and $`\stackrel{~}{\mathrm{\Omega }_p}=\mathrm{\Omega }_pexp(\frac{U}{kT})`$. The low frequency response $`(\mathrm{\Omega }0)`$ must follow the law $`\lambda _{ac}\mathrm{\Omega }^{\frac{1}{2}}`$ (resistive response). The ac frequency spectrum should allow the extraction of the Boltzman like factor $`exp(\frac{U}{kT})`$. We emphasize that this kind of resistive response is at odds with the response in a Campbell-like regime $`\lambda _{ac}\lambda ^{^{}}cte`$ (inductive response) and is easily identifiable if one measures the phase of $`\lambda _{ac}`$.

It was also shown, both theoretically Sonin placais  and experimentally nono , that, taking into account vortex elasticity and appropriate boundary conditions for vortex lines, a non dissipative penetration mode $`k_{surf}=\frac{i}{\lambda _{surf}}`$ adds in the dispersion equation. This mode has a short spatial scale but, as shown in reference MS , allows for strong curvature of vortex lines. This mode is of particular importance for treating the case of surface pinning. Its weight is enhanced by the surface roughness present in any real sample and allows for the flow of a large non dissipative current (the critical current). Taking into account the finite size of the sample, the complex penetration depth was shown to take the form:

$$\frac{1}{\lambda _{\mathrm{ac}}}=\frac{1}{L_\mathrm{S}}+\frac{1\mathrm{i}}{\delta _{\mathrm{ff}}}\mathrm{cotanh}\frac{(1\mathrm{i})L}{2\delta _{\mathrm{ff}}}.$$
(1)
where $`\delta _{ff}`$ is the only frequency-dependent parameter. $`L_s\lambda ^{^{}}(0)\frac{a_o\omega }{\mu _oi_c}`$ is related to the superficial critical current $`i_c`$ $`(A/m)`$ and $`L`$ is the thickness of the sample (L=$`\mathrm{}_a`$ in our geometry). Note that $`L_s`$, as $`i_c`$, is independent of the frequency (as long as $`\mathrm{\Omega }\mathrm{\Omega }_{gap}`$). The bulk pinning contribution can be simply introduced following the same approach as the Campbell one. This results in a strong narrowing of the depinning spectrum, easily observable by experiment nono . Since the spectra measured in the present work always follow equation (1) with an accuracy within the noise of the data. We reach the conclusion that $`\lambda _c^10`$, i.e. bulk pinning is negligible compared to surface pinning in this sample.

Some typical penetration depths $`\lambda _{ac}(T)`$, measured for different frequencies and at a fixed field B=6T, are shown in figure 2. We note the maximum of the out of phase component $`\lambda ^\mathrm{"}`$ and the saturation of $`\lambda ^{^{}}`$ for frequency dependent temperature values. This can be associated with a thermal depinning of the vortex lattice. Anyway, because of the possible mixing of many effects, both intrinsic (pinning, flow, transition of the vortex lattice…) and extrinsic (finite size effects) and of the bad known temperature variation of thermodynamic parameters of the vortex lattice, a precise study of the ac dynamical response needs a study of the frequency dependence. Such a spectrum taken in the ”solid” phase $`(I_c0)`$ is presented in the figure 3. It reveals a two mode spectrum, with a pure surface pinning and free vortex flow in the bulk, as previously observed in conventional superconductors nono , and in a slightly overdoped YBaCuO nous . Other spectra taken at lower temperatures confirm this result (Fig.4).

Comparing with previous measurements nous , we have extended the frequency range so as to investigate the pure loss free response and the pure resistive response in the overdamped regime. In particular, the low frequency behaviour has been measured near $`T_m`$ ($`T/T_m0.993`$), in order to increase the probability of thermally activated vortex jumps. As evidenced in figure 5, $`\lambda ^{}`$ is nevertheless constant, within noise due to the smallest of low frequency signal, and there is no loss ($`\lambda ^{^{\prime \prime }}=0`$) down to a frequency of about $`10^5\mathrm{\Omega }_p`$. In others words, the critical current does not depend on the frequency even very close to $`T_m`$, and creep effects are thus negligible up to our lowest measurable frequency (few tens Hz) even close to $`T_m`$.

In the ”liquid” phase $`(T>T_m,I_c=0)`$, one measures the spectrum of a superconductor free from defects, as expected from the disappearance of any vortex pinning (fig 6). This is a classical electromagnetic skin effect driven by the flow resistivity $`\rho _f`$, growing up to $`T_{BC2}`$. As there is no more critical current, the surface mode is turned off ($`L_s^1=0`$ in the equation (1)) and only the bulk resistive mode is active. The low frequency penetration is that of a perfectly transparent slab: $`2L=\lambda _{ac}`$, which allows identification of the irreversibility temperature without ambiguity. Let us emphasize that $`2L=\lambda _{ac}(\frac{\mathrm{\Omega }}{2\pi }0)`$ only for $`TT_m=89.2K`$, and that $`T_m`$ is not frequency dependent. As the critical current and the irreversibility line do not depend on the frequency, the pinning parameters are not dispersing in the frequency range we have investigated. We conclude that we do not observe any role of thermal assisted depinning of vortices.

In figure 7, we present the two parameters extracted from the low frequency and the high frequency curves, the critical current and the flux flow resistivity. In the surface pinning model, $`i_c`$ is simply link with the main reversible magnetization $`M=_{vol}\epsilon 𝑑V`$, as diamagnetic currents and surface non dissipative currents are the same kind of equilibrium currents MS . The only adjustable parameter is the phenomenological angle $`\theta _{cr}\frac{i_c}{\epsilon }`$, which takes into account both the surface roughness and the vortex lattice elasticity. We have measured the main reversible magnetization of the sample by means of a squid magnetometer. Comparing with $`i_c`$ ($`T<T_m`$), this leads to a reasonable and quite standard value of $`\theta _{cr}5deg`$ (corresponding to a standard surface roughness) which goes to zero at $`T=T_m`$.

We will now focus on the cross over between the pinned and depinned state. As now well established, some very clean YBaCuO samples present a thermodynamic first order transition marcenat , at a field (temperature) where the critical current disappears. Such a feature is usually interpreted as the melting of a vortex solid into a liquid state. The vortex solid is Abrikosov-like, and more recent theories predict a quasi long range ordered lattice in the case of low enough pinning (the Bragg Glass) thierry . The properties of the ”liquid” state are badly known. As structural studies of the high temperature state of the VL are not possible due to the lack of resolution so close to $`T_c`$, most of the experimental answers are indirect. One can use transport measurements in order to test a pertinent property. Recent complex resistivity measurements in YBaCuO have interpreted the inductive to resistive transition as a collapse of the vortex shear constant $`C_{66}`$ mapple , as claimed if the first order transition is a genuine melting. We have shown here and discussed in comment , that this transition is simply described by the disappearance of the pinning strength, as it appends at $`B_{C2}`$ in low Tc materials. However, another feature appears in our data. The high frequency $`\lambda _{ac}(T)`$ curves present a step at the temperature of the first order transition. This is observed in the two directions (B//a-axis and B//c-axis). The remaining question is what could cause this feature. In principle, when measuring at high enough frequencies, the vortex lattice behaves as if it was ideal leading to $`\lambda _{ac}\lambda _{ff}=\frac{(1+i)\delta _{ff}}{2}`$. In fact, one has to correct this result by the diamagnetism of the mixed state $`\mu =\mu _o\frac{B}{B+\mu _o\epsilon }`$,i.e $`\lambda _{ac}\frac{\mu }{\mu _o}\lambda _f`$ and $`\delta _{ff}=\sqrt{\frac{2\rho _{ff}}{\mu \mathrm{\Omega }}}`$ placais . As the first order transition suddenly modifies this diamagnetism by $`\mathrm{\Delta }\epsilon `$, it could lead to a concomitant effect on $`\lambda _{ac}`$. Nevertheless, as $`B\mu _o\mathrm{\Delta }\epsilon (10^4T)`$, this effect is far too small to affect our measurement. Moreover, at the highest frequencies used, $`\delta _{ff}50\mu `$m$`<L/10`$, so the thick limit is well justified and spurious size effects are neglected. We have also checked that the values extracted both from a fit of the complete spectra or at a constant frequency f $``$ $`f_p`$ are equivalent. Our conclusion is that the step of $`\lambda _{ac}`$ reflects the one of $`\rho _{ff}`$. We emphasize that in conventional superconductors, there is no link between the flux flow resistivity and the critical current Rose , except at a critical field as $`B_{C2}`$ ($`I_c0`$, $`\rho _{ff}\rho _n`$). Such independence between the pinning characteristics and the bulk flow resistivity of a superconductor in the mixed state was evidenced in ref rosenblum . As an example, the flux flow resistivity, measured in dc or at high frequencies, was shown to be the same and clearly insensitive to the critical current peak effect in conventional superconductors kim . On the contrary, we see here that the first order transition affects both the critical current and the flux flow resistivity. As this latter is linked to the nature of the order parameter and to the quasiparticle excitations in the vortex state, it is tempting to conclude that the first order transition affects the electronic structure inside and (or) around the vortex core, or in contrast that a transition in this electronic structure drives the first order transition. The difficulty lies in understanding the key role of the different peculiarities of the vortex core in YBaCuO (short coherence length, d-wave symetry with nodes, strong antiferromagnetic fluctuations even for optimally doped samples veran ) compared to the simplest case of a conventional dirty s-wave superconductor. A question of the same type has been previously addressed by D’anna et al Danna , who observed a strong decrease of the Hall resistivity at a temperature just below the one of the first order transition. We note that a small distortion of the vortex lattice in a d-wave superconductor should lead to an important thermodynamic contribution ($`\mathrm{\Delta }`$S$``$kB) via the fermionic entropy Volovik , and that such kind of distortion does not necessary correspond to a melting.

In conclusion, complex impedance measurements have been performed in a clean YBaCuO crystal, with a particular attention to the vortex depinning transition. Two mode electrodynamic analysis of the data allow us to conclude that the vortex pinning is due to the surface roughness of the sample, and that the depinning (and the irreversibility line) is not driven by thermal activation. The flux flow resistivity exhibits a step at the first order transition, that remains to be interpreted, in the framework of a melting or using alternative descriptions.

This work was partially supported by NEDO, Japan for the R and D of Industrial Science and Technology Frontier Program.

AP, CG and CS are indebted to Bernard Plaçais et al (ENS, PARIS) whose work is at the origin of this type of experiment.


text:
# The Clifford group, stabilizer states, and linear and quadratic operations over GF(2).

## I Introduction

Stabilizer states and Clifford group operations play a central role in quantum error correction, quantum computing, and entanglement distillation. A stabilizer state is a state of an $`n`$-qubit system that is a simultaneous eigenvector of a commutative subgroup of the Pauli group. The latter consists of all tensor products of $`n`$ single-qubit Pauli operations. The Clifford group is the group of unitary operations that map the Pauli group to itself under conjugation. In quantum error correction these concepts play a central role in the theory of stabilizer codes Gottesman (1997). Although a quantum computer working with only stabilizer states and Clifford group operations is not powerful enough to disallow efficient simulation on a classical computer Chuang and Nielsen (2000); Gottesman , it is not unlikely that possible new quantum algorithms will exploit the rich structure of this group. In Dehaene et al. (2003), we also showed the relevance of a quotient group of the Clifford group in mixed state entanglement distillation.

In this paper, we link stabilizer states and Clifford operations with binary linear algebra and binary quadratic forms (over GF(2)). The connection between multiplication of Pauli group elements and binary addition is well known as is the connection between commutability of Pauli group operations and a binary symplectic inner product Gottesman (1997). In Dehaene et al. (2003) we extended this connection to a link between a quotient group of the Clifford group and binary symplectic matrices (there termed $`P`$ orthogonal). In this paper we give a binary characterization of the full Clifford group, by adding quadratic forms to the symplectic operations. In addition we show how the coefficients, with respect to a standard basis, of both stabilizer states and Clifford operations can also be described using binary quadratic forms. Our results also lead to efficient ways for decomposing Clifford group operations in a product of 2-qubit operations.

## II Clifford group operations and binary linear and quadratic operations

In this section, we show how the Clifford group is isomorphic to a group that can be entirely described in terms of binary linear algebra, by means of symplectic linear operations and quadratic forms.

We use the following notation for Pauli matrices.

$$\begin{array}{cccc}\sigma _{00}\hfill & \hfill =\tau _{00}& \hfill =\sigma _0& =\left[\begin{array}{cc}\hfill 1& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right],\hfill \\ \sigma _{01}\hfill & \hfill =\tau _{01}& \hfill =\sigma _x& =\left[\begin{array}{cc}\hfill 0& \hfill 1\\ \hfill 1& \hfill 0\end{array}\right],\hfill \\ \sigma _{10}\hfill & \hfill =\tau _{10}& \hfill =\sigma _z& =\left[\begin{array}{cc}\hfill 1& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right],\hfill \\ \sigma _{11}\hfill & & \hfill =\sigma _y& =\left[\begin{array}{cc}\hfill 0& \hfill i\\ \hfill i& \hfill 0\end{array}\right],\hfill \\ & \hfill \tau _{11}& \hfill =i\sigma _y& =\left[\begin{array}{cc}\hfill 0& \hfill 1\\ \hfill 1& \hfill 0\end{array}\right].\hfill \end{array}$$

We also use vector indices to indicate tensor products of Pauli matrices. If $`v,w_2^n`$ and $`a=\left[\begin{array}{c}v\\ w\end{array}\right]_2^{2n}`$, then we denote

$$\begin{array}{cc}\sigma _a\hfill & =\sigma _{v_1w_1}\mathrm{}\sigma _{v_nw_n},\hfill \\ \tau _a\hfill & =\tau _{v_1w_1}\mathrm{}\tau _{v_nw_n}\hfill \end{array}$$
(1)
If we define the Pauli group to contain all tensor products of Pauli matrices with an additional complex phase in $`\{1,i,1,i\}`$, an arbitrary Pauli group element can be represented as $`i^\delta (1)^ϵ\tau _u`$, where $`\delta ,ϵ_2`$ and $`u_2^{2n}`$. The separation of $`\delta `$ and $`ϵ`$, rather than having $`i^\gamma `$ with $`\gamma _4`$, is deliberate and will simplify formulas below. Throughout this paper exponents of $`i`$ will always be binary. As a result $`i^{\delta _1}i^{\delta _2}=i^{\delta _1+\delta _2}(1)^{\delta _1\delta _2}`$. Multiplication of two Pauli group elements can now be translated into binary terms in the following way:

###### Lemma 1

If $`a_1,a_2_2^{2n}`$, $`\delta _1,\delta _2,ϵ_1,ϵ_2_2`$ and $`\tau `$ is defined as in Eq. (1), then

$$\begin{array}{c}i^{\delta _1}(1)^{ϵ_1}\tau _{a_1}i^{\delta _2}(1)^{ϵ_2}\tau _{a_2}=i^{\delta _{12}}(1)^{ϵ_{12}}\tau _{a_{12}}\hfill \\ \text{with}\begin{array}{cc}\delta _{12}\hfill & =\delta _1+\delta _2\hfill \\ ϵ_{12}\hfill & =ϵ_1+ϵ_2+\delta _1\delta _2+a_2^TUa_1\hfill \\ a_{12}\hfill & =a_1+a_2,\hfill \\ U\hfill & =\left[\begin{array}{cc}\hfill 0_n& \hfill I_n\\ \hfill 0_n& \hfill 0_n\end{array}\right],\hfill \end{array}\hfill \end{array}$$

where multiplication and addition of binary variables is modulo 2.

These formulas can easily be verified for $`n=1`$ and then generalized for $`n>1`$. The term $`a_2^TUa_1`$ “counts” (modulo 2) the number of positions $`k`$ where $`w_{1}^{}{}_{k}{}^{}=1`$ and $`v_{2}^{}{}_{k}{}^{}=1`$ (with $`a_1=\left[\begin{array}{c}v_1\\ w_1\end{array}\right]`$ and $`a_2=\left[\begin{array}{c}v_2\\ w_2\end{array}\right]`$), as only these positions get a minus sign in the following derivation:

$$\begin{array}{cc}\hfill \tau _{v_{1}^{}{}_{k}{}^{}w_{1}^{}{}_{k}{}^{}}\tau _{v_{2}^{}{}_{k}{}^{}w_{2}^{}{}_{k}{}^{}}& =\sigma _z^{v_{1}^{}{}_{k}{}^{}}\sigma _x^{w_{1}^{}{}_{k}{}^{}}\sigma _z^{v_{2}^{}{}_{k}{}^{}}\sigma _x^{w_{2}^{}{}_{k}{}^{}}\hfill \\ & =(1)^{w_{1}^{}{}_{k}{}^{}v_{2}^{}{}_{k}{}^{}}\sigma _z^{v_{1}^{}{}_{k}{}^{}+v_{2}^{}{}_{k}{}^{}}\sigma _x^{w_{1}^{}{}_{k}{}^{}+w_{2}^{}{}_{k}{}^{}}\hfill \\ & =(1)^{w_{1}^{}{}_{k}{}^{}v_{2}^{}{}_{k}{}^{}}\tau _{v_{1}^{}{}_{k}{}^{}+v_{2}^{}{}_{k}{}^{},w_{1}^{}{}_{k}{}^{}+w_{2}^{}{}_{k}{}^{}}.\hfill \end{array}$$

A Clifford group operation $`Q`$, by definition, maps the Pauli group to itself under conjugation:

$$Q\tau _aQ^{}=i^\delta (1)^ϵ\tau _b$$

for some $`\delta `$,$`ϵ`$,$`b`$, function of $`a`$.

Because $`Q\tau _{a_1}\tau _{a_2}Q^{}=(Q\tau _{a_1}Q^{})(Q\tau _{a_2}Q^{})`$, it is sufficient to know the image of a generating set of the Pauli group to know the image of all Pauli group elements and define $`Q`$ (up to an overall phase). In binary terms it is sufficient to know the image of $`\tau _{b_k},k=1,\mathrm{},n`$ where $`b_k,k=1,\mathrm{},n`$ form a basis of $`_2^{2n}`$.

For this purpose it is possible to work with Hermitian Pauli group elements only as the image of a Hermitian matrix under $`XQXQ^{}`$ will again be Hermitian (and the images of Hermitian Pauli group elements are sufficient do derive the images of non Hermitian ones). In our binary language Hermitian Pauli group elements are described as

$$i^{a^TUa}(1)^ϵ\tau _a$$

as $`a^TUa`$ counts (modulo 2) the number of $`\tau _{11}`$ in the tensor product $`\tau _a`$. For $`\tau _{11}`$ is the only non-Hermitian (actually skew Hermitian) of the four $`\tau `$ matrices and multiplication with $`i`$ makes it Hermitian.

Now we take the standard basis of $`_2^{2n}`$ $`e_k,k=1,\mathrm{},n`$ where $`e_k`$ is the $`k`$-th column of $`I_{2n}`$, and consider the generating set of Hermitian operators $`\tau _{e_k}`$. These correspond to single-qubit operations $`\sigma _z`$ and $`\sigma _x`$. We denote their images under $`XQXQ^{}`$ by $`i^{d_k}(1)^{h_k}\tau _{c_k}`$ and assemble the vectors $`c_k`$ in a matrix $`C`$ (with columns $`c_k`$) and the scalars $`d_k`$ and $`h_k`$ in the vectors $`d`$ and $`h`$. As the images are Hermitian, $`d_k=c_k^TUc_k`$ or $`d=\text{diag}(C^TUC)`$ (with $`\text{diag}(X)`$ the vector with the diagonal elements of $`X`$).

Now, given $`C`$, $`d`$ and $`h`$, defining the Clifford operation $`Q`$, the image $`i^{\delta _2}(1)^{ϵ_2}\tau _{b_2}`$ of $`i^{\delta _1}(1)^{ϵ_1}\tau _{b_1}`$ under $`XQXQ^{}`$ can be found by mutliplying those operators $`i^{d_k}(1)^{h_k}\tau _{c_k}`$ for which $`b_{1}^{}{}_{k}{}^{}=1`$. By repeated application of Lemma 1, this yields

$$\begin{array}{cc}b_2\hfill & =Cb_1\hfill \\ \delta _2\hfill & =\delta _1+d^Tb_1\hfill \\ ϵ_2\hfill & =ϵ_1+h^Tb_1+b_1^T(\text{lows}(C^TUC+dd^T)b_1+\delta _1d^Tb_1\hfill \end{array}$$

where $`\text{lows}(X)`$ is the strictly lower triangular part of $`X`$. These formulas can be simplified by introducing the following notation

$$\begin{array}{cccc}\overline{C}\hfill & =\left[\begin{array}{cc}C\hfill & 0\hfill \\ d^T\hfill & 1\hfill \end{array}\right]\hfill & & \\ \overline{U}\hfill & =\left[\begin{array}{cc}\hfill U& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right]\hfill & & \\ \overline{h}\hfill & =\left[\begin{array}{c}\hfill h\\ \hfill 0\end{array}\right]\hfill & & \\ \overline{b}_1\hfill & =\left[\begin{array}{c}\hfill b_1\\ \hfill \delta _1\end{array}\right]\hfill & \overline{b}_2\hfill & =\left[\begin{array}{c}\hfill b_2\\ \hfill \delta _2\end{array}\right]\hfill \\ \tau _{\overline{b}_1}\hfill & =i^{\delta _1}\tau _{b_1}\hfill & \tau _{\overline{b}_2}\hfill & =i^{\delta _2}\tau _{b_2}\hfill \end{array}$$

We then get the following theorem

###### Theorem 1

Given $`\overline{C}`$ and $`\overline{h}`$, defining the Clifford operation $`Q`$ as above, the image under $`XQXQ^{}`$ of $`(1)^{ϵ_1}\tau _{\overline{b}_1}`$ is $`(1)^{ϵ_2}\tau _{\overline{b}_2}`$ with

$$\begin{array}{cc}\overline{b}_2\hfill & =\overline{C}\overline{b}_1\hfill \\ ϵ_2\hfill & =ϵ_1+\overline{h}^T\overline{b}_1+\overline{b}_1\text{lows}(\overline{C}^T\overline{U}\overline{C})\overline{b}_1\hfill \end{array}$$

With this theorem we can also compose two Clifford operations using the binary language. To this end we have to find the images under the second operation of the images under the first operation of the standard basis vectors. This can be done using Theorem 1:

###### Theorem 2

Given $`\overline{C}_1`$, $`\overline{h}_1`$, $`\overline{C}_2`$ and $`\overline{h}_2`$, defining two Clifford operations $`Q_1`$ and $`Q_2`$ as above, the product $`Q_{21}=Q_2Q_1`$ is represented by $`\overline{C}_{21}`$ and $`\overline{h}_{21}`$ given by

$$\begin{array}{cc}\overline{C}_{21}\hfill & =\overline{C}_2\overline{C}_1\hfill \\ \overline{h}_{21}\hfill & =\overline{h}_1+\overline{C}_1^T\overline{h}_2+\text{diag}(\overline{C}_1^T\text{lows}(\overline{C}_2^T\overline{U}\overline{C}_2)\overline{C}_1)\hfill \end{array}$$

The next question is which $`\overline{C}`$ and $`\overline{h}`$ or $`C`$, $`d`$ and $`h`$ can represent a Clifford operation. The answer is that $`C`$ has to be a symplectic matrix (and $`d`$ has to be equal to $`\text{diag}(C^TUC)`$ as above). If we define $`P`$ to be $`U+U^T`$, we call a matrix symplectic if $`C^TPC=P`$. One way to see that $`C`$ has to be symplectic is through the connection of the symplectic inner product $`b^TPa`$ with commutability of Pauli group elements:

$$\tau _a\tau _b=(1)^{b^TPa}\tau _b\tau _a$$

Since the map $`XQXQ^{}`$ preserves commutability, $`a`$ and $`b`$ have to represent commutable Pauli group elements ($`b^TPa=0`$) if and only if $`Ca`$ and $`Cb`$ represent commutable elements ($`b^TC^TPCa=0`$). This implies that $`C`$ has to be symplectic.

That symplecticity is also sufficient was first implied by Theorem 1 of Dehaene et al. (2003) (almost, as this result was set in the context of entanglement distillation where the signs $`ϵ`$ play no significant role). The idea is to give a constructive way of realizing the Clifford operation $`Q`$ given by $`\overline{C}`$ and $`\overline{h}`$. This can be done using only one and two-qubit operations, which makes the result also of practical use. In Sec. IV we give two such decompositions that are more transparent than the results of Dehaene et al. (2003).

First, to conclude this section, we complete the binary group picture by a formula for the inverse of a Clifford group element, given in binary terms.

###### Theorem 3

Given $`\overline{C}_1`$ and $`\overline{h}_1`$, defining a Clifford operation $`Q_1`$ as above, the inverse $`Q_2=Q_1^1`$ is represented by

$$\begin{array}{cc}\overline{C}_2\hfill & =\overline{C}_1^1=\left[\begin{array}{cc}C_1^1\hfill & 0\hfill \\ d^TC^1\hfill & 1\hfill \end{array}\right]=\left[\begin{array}{cc}PC_1^TP\hfill & 0\hfill \\ d_1^TPC_1^TP\hfill & 1\hfill \end{array}\right]\hfill \\ \overline{h}_2\hfill & =\overline{C}^T\overline{h}+\text{diag}(\overline{C}^T\text{lows}(\overline{C}^T\overline{U}\overline{C})\overline{C}^1)\hfill \end{array}$$

These formulas can be verified using Theorem 2. Finally note that since the Clifford operations form a group and the matrices $`\overline{C}`$ are simply multiplied when composing Clifford group operations, the matrices $`\overline{C}`$ with $`C`$ symplectic and $`d=\text{diag}(C^TUC)`$ must form a group of $`(2n+1)\times (2n+1)`$ matrices that is isomorphic to the symplectic group of $`2n\times 2n`$ matrices. This can be easily verified by showing that

$$\text{diag}(C_1^TC_2^TUC_2C_1)=C_1^T\text{diag}(C_2^TUC_2)+\text{diag}(C_1^TUC_1)$$

This follows from the fact that $`C^TUC+U`$ is symmetric when $`C^TPC=P`$ and $`x^TSx=x^T\text{diag}(S)`$ when $`S`$ is symmetric. In a similar way it can be proven that $`\text{diag}(C^TUC^1)=C^T\text{diag}(C^TUC)`$.

## III Special Clifford operations in the binary picture

In this section we consider a selected set of Clifford group operations and their representation in the binary picture of Sec. II.

First, we consider the Pauli group operations $`Q=\tau _a`$ as Clifford operations. Note that a global phase cannot be represented as it does not affect the action $`XQXQ^{}`$. To construct $`C`$ and $`h`$ we have to consider the images of the operators $`\tau _{e_k}`$ representing one-qubit operations $`\sigma _x`$ and $`\sigma _z`$. One can easily verify that $`\tau _a`$ is represented by

$$\begin{array}{cc}C\hfill & =I_{2n}\hfill \\ h\hfill & =Pa\hfill \end{array}$$
(2)
Second, note that Clifford operations acting on a subset $`\alpha \{1,\mathrm{},n\}`$ consist of a symplectic matrix on the rows and columns with indices in $`\alpha (\alpha +n)`$, embedded in an identity matrix (that is, with ones on positions $`C_{k,k}=1`$, $`k\alpha (\alpha +n)`$ and $`C_{k,l}=0`$ if $`kl`$ and $`k`$ or $`l`$ $`\alpha (\alpha +n)`$.) Also $`h_k=0`$ if $`k\alpha (\alpha +n)`$.

Third, qubit permutations, are represented by

$$\begin{array}{cc}C\hfill & =\left[\begin{array}{cc}\mathrm{\Pi }\hfill & 0\hfill \\ 0\hfill & \mathrm{\Pi }\hfill \end{array}\right]\hfill \\ h\hfill & =0\hfill \end{array}$$

where $`\mathrm{\Pi }`$ is a permutation matrix.

Fourth, the conditional not or CNOT operation on two qubits is represented by

$$\begin{array}{cc}C\hfill & =\left[\begin{array}{cccc}1\hfill & 1\hfill & 0\hfill & 0\hfill \\ 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill & 1\hfill \end{array}\right]\hfill \\ h\hfill & =0\hfill \end{array}$$

Fifth, by composing qubit permutations and CNOT operations on selected qubits any linear transformation of the index space $`|x|Rx`$ can be realized, where $`x_2^n`$ labels the standard basis states $`|x=|x_1\mathrm{}|x_n`$ and $`R_2^{n\times n}`$ is an invertible matrix (modulo 2). This operation is represented in the symplectic picture by

$$\begin{array}{cc}C\hfill & =\left[\begin{array}{cc}R^T\hfill & 0\hfill \\ 0\hfill & R\hfill \end{array}\right]\hfill \\ h\hfill & =0\hfill \end{array}$$
(3)
The qubit permutations and CNOT operation discussed above are special cases of such operations as qubit permutations can be represented as $`|x|\mathrm{\Pi }x`$ and the CNOT operation as $`|x|\left[\begin{array}{cc}1\hfill & 0\hfill \\ 1\hfill & 1\hfill \end{array}\right]x`$.

Decomposing a general linear transformation $`R`$ into CNOTS and qubit permutations can be done by Gauss elimination (a well known technique for the solution of systems of linear equations). In this process $`R`$ is operated on on the left by CNOTS and qubit permutations to be gradually transformed in an identity matrix. The process operates on $`R`$, column by column, first moving a nonzero element into the diagonal position by a qubit permutation, then zeroing the rest of the column by CNOTS. The inverses of the applied operations yield a decomposition of $`R`$.

Sixth, we consider Hadamard operations. The Hadamard operation on a single qubit $`Q=H=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right]`$ is represented by $`C=\left[\begin{array}{cc}0\hfill & 1\hfill \\ 1\hfill & 0\hfill \end{array}\right]`$ and $`h=0`$. A Hadamard operation on a selected set of qubits is represented by the embedding of such matrices in an identity matrix as explained above. As a special case we mention the Hadamard operation on all qubits, which is represented by $`C=P`$ and $`h=0`$.

Seventh, we consider operations $`e^{i(\pi /4)\tau _{\overline{a}}}=\frac{1}{\sqrt{2}}(I+i\tau _{\overline{a}})`$ where $`a_2^{2n}`$, $`\overline{a}=\left[\begin{array}{c}a\\ a^TUa\end{array}\right]`$, and $`\tau _{\overline{a}}=i^{a^TUa}\tau _a`$. These operations are represented by

$$\begin{array}{cc}C\hfill & =I+aa^TP\hfill \\ h\hfill & =C^TUa\hfill \end{array}$$
(4)
This is proved in the Appendix.

Finally, we mention that real Clifford operations have $`d=0`$.

## IV Decompositions of Clifford operations in one and two-qubit operations

In this section we write general Clifford group operations as products of one and two-qubit operations using the binary picture. This does not only complete the results of Sec. II, showing that every symplectic $`C`$ and arbitrary $`h`$ represent a Clifford operation. It is also of practical use for quantum computing applications as well as entanglement distillation applications since two-qubit operations can be realized relatively easily and the number of two-qubit operations needed is “only” quadratical in the number of qubits. We give two different schemes.

First, for both schemes, we observe that the main problem is realizing $`C`$, not $`h`$. For once a Clifford operation represented by $`C`$ and $`h^{}`$ is realized, we can realize $`h`$ by doing an extra operation $`Q=\tau _{CP(h+h^{})}`$ on the left or $`Q=\tau _{P(h+h^{})}`$ on the right. This can be proved by using Eq. (2) and Theorem 2.

The first scheme realizes $`C`$ by two-qubit operations, acting on qubit $`k`$ and $`l`$, of the type $`e^{i(\pi /4)\tau _{\overline{a}}}`$ with symplectic matrices $`(I+aa^TP)`$ where $`a`$ can be nonzero (i.e. one) only at positions $`k,l,n+k`$ and $`n+l`$. The scheme works by reducing a given symplectic matrix $`C`$ to the identity matrix by operating on the left with two-qubit operations. The product of the inverses of these two-qubit matrices is then equal to $`C`$. The reduction to the identity matrix is done by working on two columns $`m`$ and $`n+m`$ at a time, for $`m=1,\mathrm{},n`$. First columns $`1`$ and $`n+1`$ are reduced to columns $`1`$ and $`n+1`$ of the identity matrix. Because through all the operations $`C`$ remains symplectic, one can show that as a result also rows $`1`$ and $`n+1`$ are reduced to rows $`1`$ and $`n+1`$ of the identity matrix. Then one can repeat the same process on the submatrix of $`C`$ obtained by dropping rows and columns $`1`$ and $`n+1`$, until the whole matrix is reduced to the identity matrix.

Let $`\alpha =\{1,1+n\}`$ and $`\beta =\{l,l+n\}`$. The first step in reducing columns $`1`$ and $`n+1`$ of $`C`$ to the corresponding columns of the identity matrix is a qubit permutation, exchanging qubit $`1`$ with some qubit $`k`$ to make $`C_{\alpha ,\alpha }`$ invertible. This can be done for if all $`C_{\beta ,\alpha }`$ would be rank deficient, we would have $`c_1^TPc_{n+1}=0`$ which is in conflict with the symplecticity of $`C`$. (Note that a $`2\times 2`$-matrix is invertible if and only if it is symplectic). Next, we perform two-qubit operations $`e^{i(\pi /4)\tau _{\overline{a}}}`$ on qubits $`1`$ and $`l`$ with $`a_\alpha =c_{\alpha ,n+1}`$ and $`a_\beta =c_{\beta ,1}`$, for $`l=2,\mathrm{},n`$. Such an operation changes $`C`$ through multiplication with $`I+aa^TP`$. For the first column this means that $`c_1`$ is replaced by $`c_1+a`$, as $`a^TPc_1=c_{\alpha ,n+1}^TP_2c_{\alpha ,1}+c_{\beta ,1}^TP_2c_{\beta ,1}=1+0=1`$, where $`P_2=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]`$. This way $`c_{\beta ,1}`$ is reduced to $`0`$. $`C_{\alpha ,\alpha }`$ is changed at every step but remains invertible (and symplectic). Note that through these operations also the other columns of $`C`$ are changed. After the first column has been zeroed on all positions except $`\alpha `$, we tackle column $`n+1`$ with operations $`e^{i(\pi /4)\tau _{\overline{a}}}`$ on qubits $`1`$ and $`l`$ with $`a_\alpha =c_{\alpha ,1}`$ and $`a_\beta =c_{\beta ,n+1}`$, $`l=2,\mathrm{},n`$. These operations have no effect on $`c_1`$ because $`a^TPc_1=c_{\alpha ,1}^TP_2c_{\alpha ,1}+0=0`$, and reduce $`c_{\beta ,n+1}`$ to $`0`$ in the same way as was done for the first column. After these operations we are left with $`c_1`$ and $`c_{n+1}`$ all $`0`$ except for $`C_{\alpha ,\alpha }`$ which equals an invertible matrix. This matrix can be transformed into an identity matrix by a one-qubit symplectic operation on qubit $`1`$. One-qubit Clifford operations can be easily made by one-qubit operations of type $`e^{i(\pi /4)\tau _{\overline{a}}}`$.

An advantage of this scheme is that it is efficient if only some columns of $`C`$ (or rows, as one can also work on the right) are specified while the other columns do not matter. This is the case in the entanglement distillation protocols of Dehaene et al. (2003).

The second scheme also takes a number of steps that is quadratical in $`n`$. It is based on the following theorem, which will also be of importance in Sec. V, and for which we give a constructive proof.

###### Theorem 4

If $`C_2^{2n\times 2n}`$ is a symplectic matrix ($`C^TPC=P`$), it can be decomposed as

$`C`$ $`=`$ $`\left[\begin{array}{cc}T_1^T& 0\\ 0& T_1\end{array}\right]\times `$ (14)
$`\left[\begin{array}{cccc}I_{nr}\hfill & V_1\hfill & Z_3+V_1V_2^T\hfill & V_2+V_1Z_2\hfill \\ 0\hfill & Z_1\hfill & V_1^T+Z_1V_2^T\hfill & I_r+Z_1Z_2\hfill \\ 0\hfill & 0\hfill & I_{nr}\hfill & 0\hfill \\ 0\hfill & I_r\hfill & V_2^T\hfill & Z_2\hfill \end{array}\right]\left[\begin{array}{cc}T_2^T& 0\\ 0& T_2\end{array}\right]`$
$`=`$ $`\left[\begin{array}{cc}T_1^T& 0\\ 0& T_1\end{array}\right]\times `$ (33)
$`\left[\begin{array}{cccc}I_{nr}\hfill & 0\hfill & Z_3\hfill & V_1\hfill \\ 0\hfill & I_r\hfill & V_1^T\hfill & Z_1\hfill \\ 0\hfill & 0\hfill & I_{nr}\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & I_r\hfill \end{array}\right]\left[\begin{array}{cccc}I_{nr}\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & I_r\hfill \\ 0\hfill & 0\hfill & I_{nr}\hfill & 0\hfill \\ 0\hfill & I_r\hfill & 0\hfill & 0\hfill \end{array}\right]\times `$
$`\left[\begin{array}{cccc}I_{nr}\hfill & 0\hfill & 0\hfill & V_2\hfill \\ 0\hfill & I_r\hfill & V_2^T\hfill & Z_2\hfill \\ 0\hfill & 0\hfill & I_{nr}\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & I_r\hfill \end{array}\right]\left[\begin{array}{cc}T_2^T& 0\\ 0& T_2\end{array}\right]`$
where $`T_1`$ and $`T_2`$ are invertible $`n\times n`$ matrices, $`Z_1`$ and $`Z_2`$ are symmetric $`r\times r`$ matrices, $`Z_3`$ is a symmetric $`(nr)\times (nr)`$ matrix, $`V_1`$ and $`V_2`$ are $`(nr)\times r`$ matrices and the zero blocks have appropriate dimensions.

Proof: To prove this theorem We consider $`C`$ as a block matrix $`C=\left[\begin{array}{cc}E^{}& F^{}\\ G^{}& H^{}\end{array}\right]`$.

Then, we find invertible $`R_1`$ and $`R_2`$ in $`_2^{n\times n}`$ such that $`R_1^1G^{}R_2=\left[\begin{array}{cc}0& 0\\ 0& I_r\end{array}\right],`$ where $`r`$ is the rank of $`G^{}`$. This is a standard linear algebra technique and can be realized (for example) by (1) setting the first $`nr`$ columns of $`R_2`$ equal to a basis of the kernel of $`G^{}`$, (2) choosing the other columns of $`R_2`$ as to make it invertible, (3) setting the last $`r`$ columns of $`R_1`$ equal to the last $`r`$ columns of $`R_2`$ multiplied on the left by $`G^{}`$ (This yields a basis of the range of $`G^{}`$), and (4) choosing the other columns of $`R_1`$ as to make it invertible. By construction, this implies $`G^{}R_2=R_1\left[\begin{array}{cc}0& 0\\ 0& I_r\end{array}\right]`$.

Now we set

$$\begin{array}{c}\left[\begin{array}{cc}R_1^T& 0\\ 0& R_1^1\end{array}\right]C\left[\begin{array}{cc}R_2& 0\\ 0& R_2^T\end{array}\right]=\hfill \\ \left[\begin{array}{cccc}E_{11}\hfill & E_{12}\hfill & F_{11}\hfill & F_{12}\hfill \\ E_{21}\hfill & E_{22}\hfill & F_{21}\hfill & F_{22}\hfill \\ 0\hfill & 0\hfill & H_{11}\hfill & H_{12}\hfill \\ 0\hfill & I_r\hfill & H_{21}\hfill & H_{12}\hfill \end{array}\right]\hfill \end{array}$$
(34)
Because the three matrices in the left-hand side of Eq. (34) are symplectic, so is the right-hand side. This leads to the following relations between its submatrices:

$`E_{21}^T=0`$ (35)
$`E_{11}^TH_{11}+E_{21}^TH_{21}=I`$ (36)
$`E_{11}^TH_{12}+E_{21}^TH_{22}=0`$ (37)
$`E_{22}^T+E_{22}=0`$ (38)
$`E_{12}^TH_{11}+E_{22}^TH_{21}+F_{21}=0`$ (39)
$`E_{12}^TH_{12}+E_{22}^TH_{22}+F_{22}=I`$ (40)
$`F_{11}^TH_{11}+F_{21}^TH_{21}+H_{11}^TF_{11}+H_{21}^TF_{21}=0`$ (41)
$`F_{11}^TH_{12}+F_{21}^TH_{22}+H_{11}^TF_{12}+H_{21}^TF_{21}=0`$ (42)
$`F_{12}^TH_{12}+F_{22}^TH_{22}+H_{12}^TF_{12}+H_{22}^TF_{22}=0`$ (43)
With Eq. (35) and Eq. (36) we find $`H_{11}`$=$`E_{11}^T`$. Now, if we replace $`R_2`$ by $`R_2\left[\begin{array}{cc}E_{11}^1\hfill & 0\hfill \\ 0\hfill & I_r\hfill \end{array}\right]`$, both $`H_{11}`$ and $`E_{11}`$ are replaced by $`I_{nr}`$. We will assume that this choice of $`R_2`$ was taken from the start. Then, from Eq. (35) and Eq. (37) we find $`H_{12}=0`$. From Eq. (38) we learn that $`E_{22}`$ is symmetric. From Eq. (39) and Eq. (40) we find $`F_{21}=E_{12}^T+E_{22}^TH_{21}`$ and $`F_{22}=I+E_{22}H_{22}`$. Substituting these equations in Eqs. (41),(42) and (43), we find that $`F_{11}+H_{21}^TE_{12}^T`$ is symmetric, $`F_{12}=H_{21}^T+E_{12}H_{22}`$, and $`H_{22}`$ is symmetric. Setting $`T_1=R_1`$, $`T_2=R_2^T`$ (with $`R_2`$ chosen as to make $`E_{11}=H_{11}=I`$), $`V_1=E_{12}`$, $`V_2=H_{21}^T`$, $`Z_1=E_{22}`$, $`Z_2=H_{22}`$ and $`Z_3=F_{11}+V_1V_2^T`$, we obtain Eq. (14). Note that $`Z_3`$ is symmetric because $`F_{11}+V_2V_1^T`$ and $`V_2V_1^T+V_1V_2^T`$ are symmetric. Finally Eq. 33 can be easily verified. This completes the proof. $`\mathrm{}`$

To find a decomposition of $`C`$ in one and two-qubit operations we concentrate on the five matrices in the right-hand side of Eq. (33), all of which are symplectic. Clearly the first and last matrix are linear index space transformations as discussed in Sec. III. These can be decomposed into CNOTs and qubit permutations. The middle matrix corresponds to Hadamard operations on the last $`r`$ qubits. We will now show that the second and fourth matrix can be realized by one and two-qubit operations of the type $`e^{i(\pi /4)\tau _{\overline{a}}}`$. First note that both matrices are of the form $`\left[\begin{array}{cc}I\hfill & Z\hfill \\ 0\hfill & I\hfill \end{array}\right]`$ with $`Z`$ symmetric. These matrices form a commutative subgroup of the symplectic matrices with

$$\left[\begin{array}{cc}I& Z_a\\ 0& I\end{array}\right]\left[\begin{array}{cc}I& Z_b\\ 0& I\end{array}\right]=\left[\begin{array}{cc}I& Z_a+Z_b\\ 0& I\end{array}\right].$$

Now, we realize $`\left[\begin{array}{cc}I\hfill & Z\hfill \\ 0\hfill & I\hfill \end{array}\right]`$ with one and two-qubit operations by first realizing the ones on off-diagonal positions in $`Z`$ and then realizing the diagonal. Entries $`Z_{k,l}=Z_{l,k}=1`$ are realized by operations $`e^{i(\pi /4)\tau _{\overline{a}}}`$ with $`a_k=a_l=1`$ and $`a_m=0`$ if $`mk`$ and $`ml`$. These are two-qubit operations which realize the off-diagonal part of $`Z`$ and as a by-product produce some diagonal. Now this diagonal can be replaced by the diagonal of $`Z`$ by one-qubit operations $`e^{i(\pi /4)\tau _{\overline{a}}}`$ with $`a_k=1`$ and $`a_m=0`$ if $`mk`$, which affect only the diagonal entries $`Z_{k,k}`$. This completes the construction of $`C`$ by means of one and two-qubit operations.

## V Description of stabilizer states and Clifford operations using binary quadratic forms

In this section we use our binary language to get further results on stabilizer states and Clifford operations. First, we take the binary picture of stabilizer states and their stabilizers and show how Clifford operations act on stabilizer states in the binary picture. We also discuss the binary equivalent of replacing one set of generators of a stabilizer by another. Then we move to two seemingly unrelated results. One is the expansion of a stabilizer state in the standard basis, describing the coefficients with binary quadratic forms. The other is a similar description of the entries of the unitary matrix of a Clifford operation with respect to the same standard basis.

A stabilizer state $`|\psi `$ is the simultaneous eigenvector, with eigenvalues $`1`$, of $`n`$ commutable Hermitian Pauli group elements $`i^{f_k}(1)^{b_k}\tau _{s_k}`$, $`k=1,\mathrm{},n`$, where $`s_k_2^{2n},k=1,\mathrm{},n`$ are linearly independent, $`f_k,b_k_2`$ and $`f_k=s_k^TUs_k`$. The $`n`$ Hermitian Pauli group elements generate a commutable subgroup of the Pauli group, called the stabilizer $`𝒮`$ of the state. We will assemble the vectors $`s_k`$ as the columns of a matrix $`S_2^{2n\times n}`$ and the scalars $`f_k`$ and $`b_k`$ in vectors $`f`$ and $`b_2^n`$. This binary representation of stabilizer states is common in the literature of stabilizer codes Gottesman (1997). The fact that the Pauli group elements are commutable is reflected by $`S^TPS=0`$. One can think of $`S`$, $`f^T`$ and $`b^T`$ as the “left half” of $`C`$, $`d^T`$ and $`h^T`$ of Sec. II. In the style of that section we also define $`\overline{S}=\left[\begin{array}{c}S\hfill \\ f^T\hfill \end{array}\right]`$.

If $`|\psi `$ is operated on by a Clifford operation $`Q`$, $`Q|\psi `$ is a new stabilizer state whose stabilizer is given by $`Q𝒮Q^{}`$. As a result, the new set of generators, represented by $`\overline{S}^{}`$ and $`b^{}`$ can be found by acting with $`\overline{C}`$ and $`h`$, representing $`Q`$, as in Theorem 1 and Theorem 2. One finds

$$\begin{array}{cc}\overline{S}^{}\hfill & =\overline{C}\overline{S}\hfill \\ b^{}\hfill & =b+S^Th+\text{diag}(\overline{S}^T\text{lows}(\overline{C}^T\overline{U}\overline{C})\overline{S})\hfill \end{array}$$

The representation of $`𝒮`$ by $`\overline{S}`$ and $`b`$ is not unique as they only represent one set of generators of $`𝒮`$. In the binary language a change from one set of generators to another is represented by an invertible linear transformation $`R`$ acting on the right on $`S`$ and acting appropriately on $`b`$. By repeated application of Lemma 1 one finds that $`\overline{S}`$ and $`b`$ can be transformed as

$$\begin{array}{cc}\overline{S}^{}\hfill & =\overline{S}R\hfill \\ b^{}\hfill & =R^Tb+\text{diag}(R^T\text{lows}(\overline{S}^T\overline{U}\overline{S})R)\hfill \end{array}$$

Below we will refer to such a transformation as a stabilizer basis change.

Before we state the main results of this section, we show how binary linear algebra can also be used to describe the action of a Pauli matrix on a state, expanded in the standard basis.

$$\tau _a\underset{x_2^n}{}\psi _x|x=\underset{x_2^n}{}(1)^{v^Tx}\psi _{x+w}|x$$
(44)
where $`a=\left[\begin{array}{c}v\\ w\end{array}\right]`$. This is proved as follows. From $`\sigma _x|b=|b+1`$ with $`b_2`$, we have $`\tau _{\left[\begin{array}{c}0\\ w\end{array}\right]}_x\psi _x|x=_x\psi _x|x+w=_x\psi _{x+w}|x`$. From $`\sigma _z|b=(1)^b|b`$, we then find Eq. (44).

Now we exploit our binary language to get results about the expansion in the standard basis of a stabilizer state as summarized in the following theorem, for which we give a constructive proof.

###### Theorem 5

(i) If $`\overline{S}`$ and $`b`$ represent a stabilizer state $`|\psi `$ as described above, $`\overline{S}`$ and $`b`$ can be transformed by an invertible index space transformation $`|x|T^1x`$ with $`T_2^{n\times n}`$ and an invertible stabilizer basis change $`R_2^{n\times n}`$ into the form

$$\begin{array}{cc}\overline{S}^{}\hfill & =\left[\begin{array}{ccc}T^T& 0& 0\\ 0& T^1& 0\\ 0& 0& 1\end{array}\right]\overline{S}R=\left[\begin{array}{ccc}Z& 0& 0\\ 0& 0& 0\\ 0& 0& I_{r_c}\\ I_{r_a}& 0& 0\\ 0& I_{r_b}& 0\\ 0& 0& 0\\ f_a^T& 0& 0\end{array}\right]\hfill \\ b^{}\hfill & =\left[\begin{array}{c}b_{ab}\\ b_c\end{array}\right]\hfill \end{array}$$
(45)
where $`Z`$ is full rank and symmetric and $`f_a=\text{diag}(Z)`$.

(ii) The state $`|\psi `$ can be expanded in the standard basis as

$$\begin{array}{c}|\psi =(1/\sqrt{(2^{(r_a+r_b)})})\times \hfill \\ _{y_2^{(r_a+r_b)}}(i)^{f_a^Ty_a}(1)^{(y_a^T\text{lows}(Z+f_af_a^T)y_a+b_{ab}^Ty)}|T\left[\begin{array}{c}y\\ b_c\end{array}\right]\hfill \end{array}$$

where $`y=\left[\begin{array}{c}y_a\\ y_b\end{array}\right]`$ with $`y_a_2^{r_a}`$ and $`y_b_2^{r_b}`$.

In words this theorem reads as follows. If the coefficients of a stabilizer state $`|\psi `$, with respect to the standard basis $`\{|x|x_2^n\}`$, are considered as a function of the binary basis label $`x`$, this function is nonzero in an $`r_a+r_b`$ dimensional plane (a coset of a subspace of $`_2^n`$) and the nonzero elements are (up to a global scaling factor) equal to $`1`$,$`i`$,$`1`$ or $`i`$, where the signs are given by a binary quadratic function over the plane and $`i`$’s appear either in a subplane of codimension one or nowhere (if $`f_a=0`$).

Proof: First we write $`S`$ as a block matrix

$$S=\left[\begin{array}{c}V\\ W\end{array}\right]$$

with $`V,W_2^{n\times n}`$. Then we perform a first stabilizer basis change $`R_1`$, transforming $`W`$ to $`W^{(1)}=WR_1=[W_{ab}^{(1)}0]`$, where $`W_{ab}^{(1)}_2^{n\times (r_a+r_b)}`$ and $`r_a+r_b=\text{rank}(W)`$. This is achieved by setting the last columns of $`R_1`$ equal to a basis of the kernel of $`W`$ and choosing the other columns as to make it invertible. As a result the columns of $`W_{ab}^{(1)}`$ are a basis of the range of $`W`$. We also write the transformation of $`V`$ in block form as $`V^{(1)}=VR_1=[V_{ab}^{(1)}V_c^{(1)}]`$. Because $`S^{(1)}`$ is full rank, $`V_c^{(1)}`$ must also be full rank.

Now we perform a second stabilizer basis change $`R_2=\left[\begin{array}{cc}R_{ab,ab}\hfill & 0\hfill \\ R_{c,ab}\hfill & I_{r_c}\hfill \end{array}\right]`$, transforming $`V^{(1)}=[V_{ab}^{(1)}V_c^{(1)}]`$ to $`V^{(2)}=V^{(1)}R_2=[V_a^{(2)}0V_c^{(2)}]`$, where $`V_a^{(2)}_2^{n\times r_a}`$ and $`r_a+r_c=\text{rank}(V)`$. This is achieved by setting the columns $`r_a+1`$ till $`r_a+r_b`$ of $`R_2`$ equal to a basis of the kernel of $`V^{(1)}`$ and choosing the first $`r_a`$ columns as to make it invertible. (Note that the last $`r_c`$ columns of $`R_2`$ are equal to the corresponding columns of the identity matrix and no linear combination of them can be in the kernel of $`V^{(1)}`$ as $`V_c^{(1)}`$ is full rank). As a result the columns of $`[V_a^{(2)}V_c^{(2)}]`$ are a basis of the range of $`V`$. We also write the transformation of $`W^{(1)}`$ in block form as $`W^{(2)}=W^{(1)}R_2=[W_a^{(2)}W_b^{(2)}0]`$.

Next we perform an index space transformation $`|x|T^1x`$ with $`T=[W_a^{(2)}W_b^{(2)}W_c^{(2)}]`$ where the columns $`W_c^{(2)}`$ are chosen as to make $`T`$ invertible. As a result $`V^{(2)}`$ is transformed to $`V^{(3)}=T^TV^{(2)}=[V_a^{(3)}0V_c^{(3)}]`$, $`W^{(2)}`$ is transformed to $`W^{(3)}=T^1W^{(2)}=\left[\begin{array}{cc}I_{r_a+r_b}& 0\\ 0& 0\end{array}\right]`$. Because $`S^{(3)}=\left[\begin{array}{c}V^{(3)}\\ W^{(3)}\end{array}\right]`$ satisfies $`S_{}^{(3)}{}_{}{}^{T}PS^{(3)}=0`$, one also finds $`V^{(3)}=\left[\begin{array}{ccc}Z& 0& 0\\ 0& 0& 0\\ V_{ca}^{(3)}& 0& V_{cc}^{(3)}\end{array}\right]`$ where $`Z`$ is symmetric and $`V_{cc}^{(3)}`$ is full rank. A final stabilizer basis change $`R_3=\left[\begin{array}{ccc}I_{r_a}& 0& 0\\ 0& I_{r_b}& 0\\ V_{cc}^{(3)}{}_{}{}^{1}V_{ca}^{(3)}& 0& V_{cc}^{(3)}{}_{}{}^{1}\end{array}\right]`$ transforms $`V^{(3)}`$ to $`V^{}=V^{(3)}R_3=\left[\begin{array}{ccc}Z& 0& 0\\ 0& 0& 0\\ 0& 0& I_{r_c}\end{array}\right]`$ and leaves $`W^{(3)}=W^{}`$ unchanged. Through all the transformations we also have to keep track of $`f`$ and $`b`$. We find $`f^{}=\text{diag}(S^TUS^{})=\left[\begin{array}{c}\text{diag}(Z)\\ 0\end{array}\right]`$. Setting $`R=R_1R_2R_3`$ we find $`\left[\begin{array}{c}b_{ab}\\ b_c\end{array}\right]=R^Tb+\text{diag}(R^T\text{lows}(V^TW+dd^T)R)`$.

We still have to prove that $`Z`$ is full rank. First note that $`Z=W_{a}^{(2)}{}_{}{}^{T}V_a^{(2)}`$. From $`S_{}^{(2)}{}_{}{}^{T}PS^{(2)}=0`$ and the fact that $`[V_a^{(2)}V_c^{(2)}]`$ and $`[W_a^{(2)}W_b^{(2)}]`$ are full rank, it follows that the columns of $`W_b^{(2)}`$ span the orthogonal complement of $`[V_a^{(2)}V_c^{(2)}]`$ and the columns of $`V_c^{(2)}`$ span the orthogonal complement of $`[W_a^{(2)}W_b^{(2)}]`$. Assume now that there exists some $`x_2^{r_a}`$ with $`x0`$ and $`Zx=0`$, then $`V_a^{(2)}x`$ is orthogonal to the columns of $`W_a^{(2)}`$. And $`V_a^{(2)}x`$ is also orthogonal to the columns of $`W_b^{(2)}`$. Therefore $`V_a^{(2)}x`$ is a linear combination of the columns of $`V_c^{(2)}`$. This is in contradiction with the fact that $`[V_a^{(2)}V_c^{(2)}]`$ is full rank. Therefore, $`Z`$ is full rank. This completes the proof of part (i).

To prove part (ii), first observe that applying $`|x|T^1x`$ to $`|\psi `$ simply replaces $`|T\left[\begin{array}{c}y\\ b_c\end{array}\right]`$ by $`|\left[\begin{array}{c}y\\ b_c\end{array}\right]`$, and stabilizer basis transformations only change the description of a stabilizer state but not the state itself. Therefore, we have to prove that

$$\begin{array}{c}|\varphi =\hfill \\ _{y_2^{(r_a+r_b)}}(i)^{f_a^Ty_a}(1)^{(y_a^T\text{lows}(Z+f_af_a^T)y_a+b_{ab}^Ty)}|\left[\begin{array}{c}y\\ b_c\end{array}\right]\hfill \end{array}$$
(46)
is an eigenvector with eigenvalue one of the operators $`i^{f_k^{}}(1)^{b_k^{}}\tau _{s_k^{}}`$ described by $`\overline{S}^{}`$ and $`b^{}`$. For $`k=1,\mathrm{},r_a`$, we have

$$\begin{array}{cc}s_k^{}\hfill & =\left[\begin{array}{c}Ze_k\\ 0\\ e_k\\ 0\end{array}\right]\hfill \\ f_k^{}\hfill & =f_{a}^{}{}_{k}{}^{}=z_{k,k}\hfill \\ b_k^{}\hfill & =b_{ab}^{}{}_{k}{}^{}\hfill \end{array}$$

where $`e_k`$ is the $`k`$-th column of $`I_{r_a}`$. With Eq. (44) we find

$$\begin{array}{c}i^{f_k^{}}(1)^{b_k^{}}\tau _{s_k^{}}|\varphi \hfill \\ =_y[i^{f_{a}^{}{}_{k}{}^{}}(1)^{b_{ab}^{}{}_{k}{}^{}}(1)^{(Ze_k)^Ty_a}(i)^{f_a^T(y_a+e_k)}\times \hfill \\ (1)^{((y_a+e_k)^T\text{lows}(Z+f_af_a^T)(y_a+e_k)+b_a^T(y_a+e_k)+b_b^Ty_b)}\times \hfill \\ |\left[\begin{array}{c}y\\ b_c\end{array}\right]]\hfill \\ =_y[i^{f_{a}^{}{}_{k}{}^{}}(i)^{f_a^Ty_a}(i)^{f_{a}^{}{}_{k}{}^{}}(1)^{f_a^Ty_af_{a}^{}{}_{k}{}^{}}\times \hfill \\ (1)^{e_k^TZy_a+b_{ab}^{}{}_{k}{}^{}}(1)^{(y_a^T\text{lows}(Z+f_af_a^T)y_a)}\times \hfill \\ (1)^{(e_k^T(Z+f_af_a^T)y_a+b_a^Ty_a+b_{ab}^{}{}_{k}{}^{}+b_b^Ty_b)}|\left[\begin{array}{c}y\\ b_c\end{array}\right]]\hfill \\ =|\varphi \hfill \end{array}$$

For $`k=r_a+1,\mathrm{},r_b`$ we have

$$\begin{array}{cc}s_k^{}\hfill & =\left[\begin{array}{c}0\\ e_k\\ 0\end{array}\right]\hfill \\ f_k^{}\hfill & =0\hfill \\ b_k^{}\hfill & =b_{ab}^{}{}_{k}{}^{}\hfill \end{array}$$

where now $`e_k`$ is the $`k`$-th column of $`I_{(r_a+r_b)}`$. With Eq. (44) we find

$$\begin{array}{c}i^{f_k^{}}(1)^{b_k^{}}\tau _{s_k^{}}|\varphi \hfill \\ =_y[(1)^{b_{ab}^{}{}_{k}{}^{}}(i)^{f_a^Ty_a}\times \hfill \\ (1)^{(y_a\text{lows}(Z+f_af_a^T)y_a+b_{ab}^T(y+e_k))}|\left[\begin{array}{c}y\\ b_c\end{array}\right]]\hfill \\ =|\varphi \hfill \end{array}$$

For $`k=r_b+1,\mathrm{},n`$, we find with Eq. (44) that $`i^{f_k^{}}(1)^{b_k^{}}\tau _{s_k^{}}|x=(1)^{x_k+b_k^{}}|x`$. The state $`|\varphi `$ is clearly an eigenstate of this operator as $`x_k+b_k^{}=0`$ for all states $`|x=|\left[\begin{array}{c}y\\ b_c\end{array}\right]`$ and $`k=r_b+1,\mathrm{},n`$. This completes the proof. $`\mathrm{}`$

Finally, we show how also the entries of a Clifford matrix can be described with binary quadratic forms, by using Theorem 4. This leads to the following theorem for which we give a constructive proof.

###### Theorem 6

Given a Clifford operation $`Q`$, represented by $`\overline{C}`$ and $`h`$ (or $`C`$,$`d`$ and $`h`$) as in Sec. II, $`Q`$ can be written as

$$\begin{array}{cc}Q=\hfill & (1/\sqrt{2^r})_{x_b_2^{nr}}_{x_r_2^r}_{x_c_2^r}\hfill \\ & [(i)^{d_{br}^Tx_{br}}(i)^{d_{bc}^Tx_{bc}}(1)^{(h_{bc}^Tx_{bc}+x_r^Tx_c)}\times \hfill \\ & (1)^{x_{br}^T\text{lows}(Z_{br}+d_{br}d_{br}^T)x_{br}}\times \hfill \\ & (1)^{x_{bc}^T\text{lows}(Z_{bc}+d_{bc}d_{bc}^T)x_{bc}}|T_1x_{br}T_2^1x_{bc}+t|]\hfill \end{array}$$

where $`x_{br}=\left[\begin{array}{c}x_b\\ x_r\end{array}\right]`$ and $`x_{bc}=\left[\begin{array}{c}x_b\\ x_c\end{array}\right]`$, $`T_1,T_2_2^{n\times n}`$ are invertible matrices, $`Z_{br},Z_{bc}_2^{n\times n}`$ are symmetric, $`d_{br}=\text{diag}(Z_{br})`$, $`d_{bc}=\text{diag}(Z_{bc})`$ and $`h_{bc},t_2^n`$.

Proof: The proof is based on the decomposition of $`C`$ as a product of five matrices as in Theorem 4. Due to the isomorphism between the group of symplectic matrices $`C`$ and the extended matrices $`\overline{C}`$ as defined in Sec. II, this decomposition can be converted into a decomposition of $`\overline{C}`$ as follows.

$$\begin{array}{cc}\overline{C}\hfill & =\overline{C}^{(1)}\overline{C}^{(2)}\overline{C}^{(3)}\overline{C}^{(4)}\overline{C}^{(5)}\hfill \\ & =\left[\begin{array}{ccc}T_1^T& 0& 0\\ 0& T_1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}I_n\hfill & Z_{br}\hfill & 0\hfill \\ 0\hfill & I_n\hfill & 0\hfill \\ 0\hfill & d_{br}^T\hfill & 1\hfill \end{array}\right]\times \hfill \\ & \left[\begin{array}{ccccc}I_{nr}\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & I_r\hfill & 0\hfill \\ 0\hfill & 0\hfill & I_{nr}\hfill & 0\hfill & 0\hfill \\ 0\hfill & I_r\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right]\left[\begin{array}{ccc}I_n\hfill & Z_{bc}\hfill & 0\hfill \\ 0\hfill & I_n\hfill & 0\hfill \\ 0\hfill & d_{bc}^T\hfill & 1\hfill \end{array}\right]\left[\begin{array}{ccc}T_2^T& 0& 0\\ 0& T_2& 0\\ 0& 0& 1\end{array}\right],\hfill \end{array}$$

where $`Z_{br}=\left[\begin{array}{cc}Z_3& V_1\\ V_1^T& Z_1\end{array}\right]`$, $`Z_{bc}=\left[\begin{array}{cc}0& V_2\\ V_2^T& Z_2\end{array}\right]`$, $`d_{br}=\text{diag}(Z_{br})`$ and $`d_{bc}=\text{diag}(Z_{bc})`$.

If we define Clifford operations $`Q^{(k)}`$ by $`\overline{C}^{(k)}`$ and $`h^{(k)}=0`$, $`k=1,\mathrm{},5`$, the operation $`Q^{(1)}Q^{(2)}Q^{(3)}Q^{(4)}Q^{(5)}`$ is represented by $`\overline{C}`$ and some vector $`h^{}`$, that can be found by repeated application of Theorem 2. The vector $`h`$ of the given Clifford operation $`Q`$ can then be realized by an extra operation $`Q^{(6)}`$ to the right with $`\overline{C}^{(6)}=I`$ and $`h^{(6)}=h+h^{}`$. Now, $`Q^{(3)}`$ is a Hadamard operation on the last $`r`$ qubits. Because a Hadamard operation on one qubit can be written as $`H_1=(1/\sqrt{2})_{b_r,b_c_2}(1)^{b_rb_c}|b_rb_c|`$, the Hadamard operation on $`r`$ qubits can be written as $`H_r(1/\sqrt{2^r})_{x_r,x_c_2^r}(1)^{x_r^Tx_c}|x_rx_c|`$ and, including the $`nr`$ qubits that are not operated on, as

$$Q^{(3)}=(1/\sqrt{2^r})\underset{x_b_2^{nr}}{}\underset{x_r,x_c_2^r}{}(1)^{x_r^Tx_c}|x_{br}x_{bc}|.$$
(47)
Considered as a matrix this is a block diagonal matrix with $`2^{nr}`$ identical $`2^r\times 2^r`$ blocks with entries that are $`1`$ or $`1`$. The index $`x_b`$ addresses the blocks and the indices $`x_c`$ and $`x_r`$ adress the columns and rows inside the blocks. Now we will show that the matrix $`Q`$ can be derived from this matrix by multiplying on the left and the right with a diagonal matrix and a permutation matrix representing an affine index space transformation. First we concentrate on $`Q^{(2)}`$ and $`Q^{(4)}`$. $`\overline{C}^{(2)}`$ and $`\overline{C}^{(4)}`$ have the form

$$\overline{\stackrel{~}{C}}=\left[\begin{array}{ccc}I& \stackrel{~}{Z}& 0\\ 0& I& 0\\ 0& \stackrel{~}{d}& 1\end{array}\right].$$

We show that such a matrix (together with $`\stackrel{~}{h}=0`$) represents a diagonal Clifford operation

$$\stackrel{~}{Q}=\underset{x_2^n}{}(i)^{\stackrel{~}{d}^Tx}(1)^{x^T\text{lows}(\stackrel{~}{Z}+\stackrel{~}{d}\stackrel{~}{d}^T)x}|xx|.$$
(48)
This result can be derived using the decomposition in (diagonal) one and two-qubit operations given in Sec. IV, but can more easily be proved by showing that the Pauli group elements $`\tau _{e_k}`$, with $`e_k`$ the $`k`$-th column of $`I_{2n}`$, are mapped to operators represented by the columns of $`\overline{\stackrel{~}{C}}`$ under $`X\stackrel{~}{Q}X\stackrel{~}{Q}^{}`$. Clearly, for $`k=1,\mathrm{},n`$, $`\stackrel{~}{Q}\tau _{e_k}\stackrel{~}{Q}^{}=\tau _{e_k}\stackrel{~}{Q}\stackrel{~}{Q}^{}=\tau _{e_k}`$ (as $`\stackrel{~}{Q}`$ and $`\tau _{e_k}`$ are diagonal). For $`k=n+1,\mathrm{},2n`$ let $`e_k`$ again be the $`k`$-th column of $`I_{2n}`$ and $`e_k^{}`$ the $`k`$-th column of $`I_n`$. Then we have

$$\begin{array}{c}\stackrel{~}{Q}\tau _{e_k}\stackrel{~}{Q}^{}\tau _{e_k}\hfill \\ =_x[(i)^{\stackrel{~}{d}^Tx}(1)^{x^T\text{lows}(\stackrel{~}{Z}+\stackrel{~}{d}\stackrel{~}{d}^T)x}|xx|]\times \hfill \\ _x[(+i)^{\stackrel{~}{d}^T(x+e_k^{})}(1)^{(x+e_k^{})^T\text{lows}(\stackrel{~}{Z}+\stackrel{~}{d}\stackrel{~}{d}^T)(x+e_k^{})}|xx|]\hfill \\ =_x[(i)^{\stackrel{~}{d}^Tx}i^{\stackrel{~}{d}^Tx}i^{\stackrel{~}{d}^Te_k^{}}(1)^{\stackrel{~}{d}^Tx\stackrel{~}{d}^Te_k^{}}\times \hfill \\ (1)^{x^T(\stackrel{~}{Z}+\stackrel{~}{d}\stackrel{~}{d}^T)e_k^{}}]=i^{\stackrel{~}{d}_k}\tau _{\left[\begin{array}{c}Ze_k^{}\\ 0\end{array}\right]}.\hfill \end{array}$$

Bringing the second $`\tau _{e_k}`$ from the left-hand side to the right-hand side we finally prove Eq. (48).

Combining Eqs. (47) and (48), we find

$$\begin{array}{c}Q^{(2)}Q^{(3)}Q^{(4)}=\hfill \\ (1/\sqrt{2^r})_{x_b_2^{nr}}_{x_r,x_c_2^r}[(i)^{d_{br}^Tx_{br}}(i)^{d_{bc}^Tx_{bc}}\times \hfill \\ (1)^{x_r^Tx_c}(1)^{x_{br}^T\text{lows}(Z_{br}+d_{br}d_{br}^T)x_{br}}\times \hfill \\ (1)^{x_{bc}^T\text{lows}(Z_{bc}+d_{bc}d_{bc}^T)x_{bc}}|x_{br}x_{bc}|]\hfill \end{array}$$

To take into account the index space transformation $`C^{(1)}`$ we simply have to replace $`|x_{br}`$ by $`|T_1x_{br}`$. For $`C^{(5)}`$ and $`C^{(6)}`$ we first define $`t`$ and $`h_{bc}_2^n`$ by writing $`h^{(6)}`$ as $`h^{(6)}=\left[\begin{array}{c}t\\ T_2^Th_{bc}\end{array}\right]`$. Then, with Eqs. (2) and (44) we find $`x_{bc}|C^{(5)}C^{(6)}=(1)^{h_{bc}^Tx_{bc}}T_2^1x_{bc}+t|`$. This completes the proof. $`\mathrm{}`$

## VI Conclusion

We have shown the relevance of binary linear algebra (over GF(2)) for the theory of stabilizer states and Clifford group operations. We have described how the Clifford group is isomorphic to a group that can be entirely described in terms of binary linear algebra. This has led to two schemes for the decomposition of Clifford group operations in a product of one and two-qubit operations, and to the desription of standard basis expansions of both stabilizer states and Clifford group operations with binary quadratic forms.

*

## Appendix A Proof of equation (4)

Let $`e_k`$ be the $`k`$-th column of $`I_{2n}`$, $`k=1,\mathrm{},2n`$. Then we have to find the images of $`\tau _{e_k}`$ (Hermitian matrices) under $`XQXQ^{}`$ with $`Q=e^{i(\pi /4)\tau _{\overline{a}}}=\frac{1}{\sqrt{2}}(I+i\tau _{\overline{a}})`$ to yield the $`k`$-th column $`c_k=Ce_k`$ of $`C`$ and the $`k`$-th entry $`h_k=e_k^Th`$ of $`h`$. We find

$$\begin{array}{c}i^{c_k^TUc_k}(1)^{h_k}\tau _{c_k}\hfill \\ =\frac{1}{\sqrt{2}}(I+i\tau _{\overline{a}})\tau _{e_k}\frac{1}{\sqrt{2}}(Ii\tau _{\overline{a}})\hfill \\ =\frac{1}{2}(\tau _{e_k}+\tau _{\overline{a}}\tau _{e_k}\tau _{\overline{a}})+\frac{1}{2}i(\tau _{\overline{a}}\tau _{e_k}\tau _{e_k}\tau _{\overline{a}})\hfill \\ =\frac{1}{2}(1+(1)^{e_k^TPa})\tau _{e_k}+\frac{1}{2}i(1(1)^{e_k^TPa})\tau _{\overline{a}}\tau _{e_k},\hfill \end{array}$$

where in the last step we used $`\tau _{\overline{a}}^2=I`$ and $`\tau _a\tau _b=(1)^{b^TPa}\tau _b\tau _a`$ as follows from Lemma 1. When $`e_k^TPa=0`$ we find $`c_k=e_k`$ and $`h_k=0`$. When $`e_k^TPa=1`$ we find

$$\begin{array}{cc}i^{c_k^TUc_k}(1)^{h_k}\tau _{c_k}\hfill & =i\tau _{\overline{a}}\tau _{e_k}\hfill \\ & =ii^{a^TUa}(1)^{e_k^TUa}\tau _{a+e_k},\hfill \end{array}$$

From this formula it can be read that $`c_k=a+e_k`$. With $`ii^{a^TUa}=i^{a^TUa+1}(1)^{a^TUa}`$ (with the addition in the exponents modulo $`2`$) and $`(a+e_k)^TU(a+e_k)=a^TUa+e_k^TPa+e_k^TUe_k=a^TUa+1`$, we also find that $`h_k=a^TUa+e_k^TUa`$.

Combining the two cases $`e_k^TPa=0`$ and $`e_k^TPa=1`$ we find $`c_k=e_k+a(e_k^TPa)=(I+aa^TP)e_k`$, yielding $`C=(I+aa^TP)`$. For $`h`$ we find $`h_k=(e_k^TPa)(a^TUa+e_k^TUa)`$. With $`(e_k^TPa)(e_k^TUa)=e_k^TUa`$ this reduces to $`h_k=e_k^T(Paa^TUa+Ua)`$ and $`h=(I+aa^TP)^TUa`$. This completes the proof. $`\mathrm{}`$

###### Acknowledgements.

We thank Frank Verstraete for useful discussions. Our research is supported by grants from several funding agencies and sources: Research Council KULeuven: Concerted Research Action GOA-Mefisto 666 (Mathematical Engineering); Flemish Government: Fund for Scientific Research Flanders: several PhD/postdoc grants, projects G.0240.99 (multilinear algebra), G.0120.03 (QIT), research communities ICCoS, ANMMM; Belgian Federal Government: DWTC (IUAP IV-02 (1996-2001) and IUAP V-22 (2002-2006): Dynamical Systems and Control: Computation, Identification & Modelling