A Short Introduction toStabilizer CodesAndreas KlappeneckerDepartment of Computer ScienceTexas A&M UniversityRepetition CodesClassical Codes0 7→ 0001 7→ 111Quantum Codes|0i 7→ | 000i|1i 7→ | 111iWhat kind of errors can be corrected?Repetition CodesThe classical code is able to correct a single bit flip.The quantum code is able to correct single bit flips,X ⊗ I ⊗ I, I ⊗ X ⊗ I, I ⊗ I ⊗ X,and more!Syndrome Calculation|ψi|0i|0i|0i|0iError X ⊗ I ⊗ I syndrome 10Error I ⊗ X ⊗ I syndrome 01Error I ⊗ I ⊗ X syndrome 11Linearity of Syndrome CalculationError X ⊗ I ⊗ I syndrome 10Error I ⊗ X ⊗ I syndrome 01E =1√2X ⊗ I ⊗ I +1√2I ⊗ X ⊗ I1√2|10i ⊗³X ⊗ I ⊗ I¯¯¯ψE´+1√2|01i ⊗³I ⊗ X ⊗ I¯¯¯ψE´Discretization of ErrorsConsider errors E = En⊗ ··· ⊗ E1Ei∈ {I, X, Y, Z}X =0 11 0, Z =1 00 −1, Y = XZ =0 −11 0.The weight of E is the number of Ei6= I.If a code Q corrects errors E of weight t or less, thenQ can correct arbitrary errors affecting ≤ t qubits.The Goal of the GameA quantum error control code Q is a K-dimensionalsubspace of C2n.The goal is to find a quantum error control code whichis able to correct (or detect) errors of weight t or less,where t is as large as possible.The Stabilizer of a CodeLet E+n= {En⊗ ··· ⊗ E1|Ei= I, X, Y, Z}.Let Q ≤ C2nbe a quantum error control code.The stabilizer of Q is defined to be the setS = {M ∈ E+n|Mv = v for all v ∈ Q}.S is a group, necessarily abelian if Q 6= {0}.The Stabilizer of the Repetition CodeQ ≤ C23is the 2-dimensional code spanned by|0i = |000 i|1i = |111 iThe stabilizer of Q is given byS = {I ⊗ I ⊗ I, Z ⊗ Z ⊗ I, I ⊗ Z ⊗ Z, Z ⊗ I ⊗ Z}Stabilizer CodesLet Q be a quantum error correcting code.Let S be the stabilizer of Q.The code Q is called a stabilizer code if and only ifthe condition Mv = v for all M ∈ S implies that v ∈ Q.Q is the joint +1-eigenspace of the operators in S.Is it a Stabilizer Code?The repetition code is a stabilizer code. Why?The code spanned by|0i =1√2(|01i + |10i)|1i = |11 iis not a stabilizer code. Why?Projections and DimensionsLet Q ≤ C2nbe a stabilizer code with stabilizer S.PQ=1|S|XM∈SMis an orthogonal projection onto Q.Indeed, check that P2Q= PQand PQ= P†Qhold.dim Q = trPQ= 2n/|S|Stabilizer TriviaThe repetition code is a stabilizer code.Stabilizer S contains four elements,S = {I ⊗ I ⊗ I, Z ⊗ Z ⊗ I, I ⊗ Z ⊗ Z, Z ⊗ I ⊗ Z}Therefore, the projection operation PQassociated withS givesdim Q = 23/|S| = 2Stabilizer versus Non-Stabilizer CodesIf Q is not a stabilizer code, and S is the stabilizer ofQ, then1|S|XM∈ SMwill project onto a space properly containing Q.The Gretchen QuestionHow can we constuct good stabilizer codes?What Next?We discuss some constructions of stabilizer codes.• We will have a closer look at errors.• Symplectic geometry associated with stabilizer codes.• Algebraic and combinatorial constructions.Detectable ErrorsAn error E is detectable by a quantum code Q iffPQEPQ= cEPQ, cE∈ C.Distinguishable states v, w ∈ Q, hv|wi = 0, remaindistinguishable hv|E|wi = 0.Detection of the error does not reveal anything aboutthe encoded state hv|E|vi = hv0|E|v0i.Correctable ErrorsA set E ⊆ E+nof errors is correctable by a quantumcode Q iff all errors in{E†F |E, F ∈ E}are detectable.No confusion principle: v⊥w implies Ev⊥F w. Syn-drome measurement does not reveal the encoded state.Errors in Stabilizer CodesXZ =0 11 01 00 −1= −ZXError operators in E+n(tensor products of I, X, Y, Z)either• commute EF = F E• or anticommute EF = −F E.Errors in Stabilizer CodesLet S be the stabilizer of a quantum code Q.If an error E anticommutes with some M ∈ S, then Eis detectable by Q.Indeed,PQEPQ= PQEMPQ= −PQMEPQ= −PQEPQ.hence PQEPQ= 0.Errors: the Good, the Bad, and the UglyLet S be the stabilizer of a stabilizer code Q.An error E is good if it does not affect the encodedinformation, e.g. E ∈ S.An error E is bad if it is detectable, e.g. anticommuteswith some M ∈ S.An error E is ugly if it cannot be detected.Examples of the Good, the Bad, and the UglyLet Q be the repetition code.Good Z ⊗ Z ⊗ I Z ⊗ Z ⊗ I |111i = |111iBad X ⊗ I ⊗ IUgly X ⊗ X ⊗ X X ⊗ X ⊗ X |111i = |000 iError Correction CapabilitiesLet Q be a stabilizer code with stabilizer S.Let C(S) the commutator of S in E+n.All errors outside C(S) − h±Si can be detected.If C(S) −h±Si does not contain errors of weight ≤ 2t,then Q can correct errors of weight ≤ t. Why?Error Correction CapabilitiesSuppose that E contains all errors of weight ≤ t.Then E†F has weight ≤ 2t. Show: E†F is detectableIf E†F 6∈ C(S), then E†F anticommutes with someM ∈ S, hence is detectable.If E†F ∈ h± Si, then E†F is good, hence detectable.Short SummaryAny M1, M2in the stabilizer S commute.Detectable errors anticommute with some M in S orare elements in S (up to a sign).Task: Find a short description of these properties.NotationDenote by Xa, a = (an, . . . , a1) ∈ F2, the operatorXa= Xan⊗ . . . ⊗ Xa1.For instance, X110= X1⊗ X1⊗ X0= X ⊗ X ⊗ I.Operators in E+nare of the form ±XaZb.Symplectic GeometryConsiderM1= XaZbM2= XcZdWhen do M1and M2commute?M1M2= XaZbXcZd= (−1)b·cXa+bZb+dM2M1= XcZdXaZb= (−1)a·dXa+bZb+dM1, M2commute iff a · d + b · c = 0 mod 2.Short Description of a StabilizerSuppose that S is the stabilizer of a 2k-dimensionalstabilizer code. Then | S| = 2n−k.S can be generated by n − k operators XaZb.Let H = (Hx|Hz) be an (n − k) × 2n matrix over F2.The rows of H contain the vectors (a|b).Short Description of a StabilizerLetS = {I ⊗ I ⊗ I, Z ⊗ Z ⊗ I, I ⊗ Z ⊗ Z, Z ⊗ I ⊗ Z}S is generated by Z ⊗ Z ⊗ I and Z ⊗ I ⊗ Z.H =000 110000 101(a|b) = (000|110) and (c|d) = (000|101)a · d + b · c = 000 · 101 + 110 · 000 = 0The New LanguageThe commutator C(S) contains all the ugly errors.Modulo a sign, each operator in C(S) is of the formM = XaZbwith a · d + b · c = 0 for all XcZd∈ S. Hence(a|b) ⊥(c|d)w.r.t. the symplectic inner product.The New LanguageIf |S| = 2n−k, then |C(S)| = 2 · 2n+k.[2n+kbecause of the symplectic duality, twice becauseof the signs ±]Adding 2k rows to H gives a new matrix G describingthe commutator C(S). Recall that ugly errors arecontained in C(S) − h±Si.The Repetition Code RevisitedG =000 110000 101111 000000
View Full Document