Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist

Подождите немного. Документ загружается.

24.2 Shor code 507

Table 24.3 Corrective actions in Shor code from bit-

ﬂip syndrome diagnostic based on measurements of

(

, Z

)

in entangled 3-qubit block U, and the prin-

ciple of majority logic.

Z



Z



Corrective action

1 1 None

1 −1 Flip 3rd qubit

−1 1 Flip 1st qubit

−1 −1 Flip 2nd qubit

syndrome measurements! Next, we can apply Z

on block U to obtain, in turn:



[

I ⊗

(

|0000|+|1111|

)

− I ⊗

(

|0101|+|1010|

)

]

|010+|101

√







I ⊗|0000|

|010+|101

√

+ I ⊗|1111|

|010+|101

√

− I ⊗|0101|

|010+|101

√

− I ⊗|1010|

|010+|101

√







= 0 + 0 −

|101

√

−

|010

√

≡−

|101+|010

√

≡ Z



(24.29)

Hence, the measurement





=Z



≡−1. (24.30)

The above two measurements, each yielding −1, are sufﬁcient to diagnose that the

second qubit in block U is corrupted. If we are not convinced, we may perform a third

measurement with Z

, which, according to expectation, will yield +1 (this being left

as an exercise). Such a result indicates that the ﬁrst and third qubits are the same, which

conﬁrms the previous diagnostic. Table 24.3 summarizes the different diagnostic and

corrective action possibilities in the general case. Clearly, the complete diagnostic and

error-correction procedure requires one to perform the two comparative measurements

, Z

on each of the three blocks A, B, C, representing altogether six measurements

and 4

= 64 possible bit-ﬂip error diagnostics. It is also clear that a bit ﬂip error occurring

on any block U of |

0 replicates on the same block U of |

1 (observing from Eq. (24.23)

that these two blocks only differ by their relative phase factor).

The above description concerned the detection and correction of either phase-ﬂip or

bit-ﬂip errors occurring in the encoded 9-qubits |

0 and |

1. It is clear that since the

syndrome measurements leave the qubit invariant, both error types can be corrected in

508 Quantum error correction

any order. What about error correction on encoded 9-qubits of the form

= α

+ β

, (24.31)

corresponding to an originator message |q=α|0+β|1? To answer this question, we

may ﬁrst deﬁne the channel output qubit as



= α



+ β



. (24.32)

As we have seen earlier, the phase-ﬂip syndrome diagnosis consists of making two

successive measurements of the type (ijklmn = 123456, 123789, 456789):

ijklmn



ijklmn



¯α



ijklmn



+ β











ijklmn



+ ¯αβ



ijklmn



+α



ijklmn



ijklmn









≡



ijklmn



ijklmn



≡±1. (24.33)

In the above result, we ﬁrst used the property that the measurement X

ijklmn

leaves

the state invariant, therefore, the nondiagonal elements in the right-hand side in Eq.

(24.33) are zero. Since the same phase-ﬂip error must be found in the two qubits |





and |



, the two nonzero matrix elements must be equal, and considering the property

= 1, we ﬁnally have X

ijklmn

=±1, corresponding to no (+1) or one (−1)

phase-ﬂip error between the blocks A, B. Thus, syndrome diagnostic and error correction

can be implemented on the encoded qubit |



=α|



+β|



 in exactly the same way

as described earlier for the qubits |



 and |



. Clearly, the same conclusion applies to

the case of bit-ﬂip errors with two successive measurements Z

(ij = 12, 23, 13) on

the individual blocks U = A, B, C, yielding measurement outcomes Z



=±1. The

key conclusion is that the Shor code can be implemented to correct both phase-ﬂip and

bit-ﬂip errors on any qubit of the general form |q=α|0+β|1.

The powerful error-correction capability of the Shor code does not end here. Indeed,

we may conceive of this code as being able to correct a true continuum of error events,

while simply using the discrete set of the above-described syndrome operators!

To show, this recall from Chapter 23 that a noisy quantum channel can be described

by a trace-preserving quantum operation ε of the form

ε(ρ

) =



, (24.34)

which is referred to as its operator-sum representation. In this deﬁnition,

=|ψ

ψ

|is the originator message density matrix, which most generally is an nth

24.3 Calderbank–Shor–Steine (CSS) codes 509

tensor product of symbol states ρ

=|q

q

| selected from a qubit symbol alphabet

{|q

}. The operators U

, called channel-operator elements, are responsible for vari-

ous sources of noise impairment. For single qubits (ρ

), the operator elements take

the form: U

√

X for the bit-ﬂip channel, U

√

Z for the phase-ﬂip channel,

√

Y for the bit-phase-ﬂip channel, and U

√

I =

√

1 − p

− p

I for

the noiseless channel, with {p

}representing the corresponding probability distribution.

We may deﬁne U

as the operator of noise-type k acting on the qubit i in the Shor

codeword |

q. Thus, we have:







q

(

+ p

)

q

(24.35)

with {p

}being the corresponding probability distribution. We observe that through the

weighted action of the operator I, X, Y, Z , the above-deﬁned quantum channel deﬁnes

a continuous qubit transformation onto the Bloch sphere. As we have seen, the Shor

code makes it possible to perform syndrome diagnosis and corrections onto any discrete,

single-error type, as caused by the operator elements U

. Therefore, any qubit passed

through this channel, and corrupted by an “error continuum,” can be effectively restored

in its full original integrity. This remarkable property has no counterpart in the classical

world of error-correction codes.

24.3 Calderbank–Shor–Steine (CSS) codes

In this section, I describe a new class of quantum error-correction codes referred to as

the Calderbank–Shor–Steine (CSS) codes, which have the capability of correcting up

to t bit-ﬂip and phase-ﬂip qubit errors. The construction of CSS codes is based on the

use of two classical linear block codes, as described in Chapter 11. To recall, a linear

block code C is deﬁned as a set (n, k)of

= 2

codewords x of bit length n.Itis

characterized by:

(i) A generator matrix G, of dimension n × k, which, for any n-vector z to be encoded,

yields the corresponding codeword x = Gz;

(ii) A parity-check matrix H , of dimension n × (n − k), which satisﬁes Hx = 0 for all

codewords x ∈ C.

Let (n, k

) and (n, k

), with k

> k

deﬁne two linear block codes C

, C

of sizes

| < |C

|. To construct a CSS code, we require the following two conditions:

(a) C

⊂ C

: all codewords of C

belong to C

;

(b) C

and C

⊥

have a bit-error correction capability of t.

In Chapter 11,weusedtheleft vector-matrix multiplication y

U,wherey

is a line vector, instead of the

right vector-matrix multiplication Uy,wherey is a column vector, which is only a matter of convention.

Also we previously called x the vectors to be encoded and y the resulting codewords, while in this chapter

we shall use x and y to designate codewords from two different linear block codes.

510 Quantum error correction

In condition (b), C

⊥

is called the dual of C

. Given a block code with G, H as generator

and parity-check matrices, respectively, the dual of C, noted C

⊥

, is a unique block code

having H

, G

for generator and parity-check matrices, respectively (the matrix U

the transposed matrix of U).

Given two linear block codes C

, C

satisfying the above conditions, we can construct

a CSS code as follows. Let x, y be two n-bit codewords, such that x ∈ C

and y ∈ C

.It

is possible to deﬁne a quantum state |x + y, where + indicates here bit-wise addition

modulo 2 (or in Boolean logic, the exclusive OR, noted ⊕). For instance, if x = 00101

and y = 10111, we have |x + y=|10010. With such a deﬁnition at hand, given x ∈ C

we are able to construct all possible quantum states |x + y with y ∈ C

as well as the

normalized sum:

x + C



≡

√



y∈C

x + y



. (24.36)

Given the number 2

=|C

|of codewords x in C

, how many orthogonal quantum states

|x + C

 can be, thus, generated? The answer to this question is |C

|/|C

|=2

−k

which stems from group theory (GT) and the ﬁne notion of cosets.

Here, I shall not

venture into GT, but leave it as an interesting exercise to establish that the C = (7, 4)

Hamming code, (described in Chapter 11) forms a group (C, ⊕) under the bit-wise

addition ⊕ and to make the inventory of its various cosets.

A key property is that any element x ∈ C

must belong to one and only one coset of

. The same coset x +C

= x



corresponds to two different elements x, x



∈ C

satisfying the property x − x



∈ C

and, hence |x + C

=|x



+ C

.

It is clear that

if two different elements x, x



∈ C

do not belong to the same coset (x + C

= x



I provide here a simpliﬁed description of cosets, which also explains the notation x +C

. First, it is impor-

tant to be familiar with, or to quickly revisit the basics of groups and subgroups, for instance through the

links: http://en.wikipedia.org/wiki/Group_%28mathematics%29, http://en.wikipedia.org/wiki/Subgroup.

Then assume two commutative groups C

and C

with additive operation +, such that C

⊂ C

is a

subgroup of C

. The cosets of C

in C

, noted x

, are deﬁned for all elements x

∈ C

as follows

≡



+ y



∈C

Taking an illustrative example, assume C

= (0, 1, 2, 3), with + representing the addition modulo 4, and

which has the only “nontrivial” subgroup C

= (0, 2). The cosets of C

in C

are

0 +C

≡ (0, 2) = C

1 +C

≡ (1, 3)

2 +C

≡ (2, 0) = (0, 2) = C

3 +C

≡ (3, 1) = (1, 3) = 1 +C

It is seen that there are two distinct cosets of C

in C

, including C

itself, which are (0, 2) and (1, 3).

In the general case with groups and subgroups of ﬁnite sizes |C

|, |C

|, Lagrange’s theorem states

that the number of cosets is given by the ratio |C

|/|C

|. See also http://en.wikipedia.org/wiki/Coset,

http://en.wikipedia.org/wiki/Lagrange%27s_theorem_%28group_theory%29, and Exercise (24.4), which

studies the (7, 4) Hamming code as a group under the bit-wise addition operation.

Indeed, taking into account that 0 ∈ C

is a subgroup with the identity element under ⊕) and assuming

x − x



∈ C

,wehave

x + C

={x + 0, x + (x − x



),...}={x, x



,...}



={x



+ 0, x



+ (x − x



),...}={x



, x,...},

24.3 Calderbank–Shor–Steine (CSS) codes 511

) there is no y, y



∈ C

such that x + y = x



+ y



and, therefore, |x + C

 must be

orthogonal to |x



. Based on GT, the number of distinct cosets is |C

|/|C

|, hence

the quantum space spanned by the states |x + C

, as generated from the codewords

x ∈ C

, has a dimension |C

|/|C

|=2

−k

. This quantum space corresponds to a new

class of quantum code, noted CSS(C

, C

), which is to be pronounced, “CSS code of

over C

.”

Next, I shall describe how the CSS(C

, C

) code can correct up to t bit-ﬂip (X) and

phase-ﬂip (Z ) errors. Just as in the classical ECC case, the signature of errors, whether

of the X -orZ-type, is an n-vector with 1 s indicating the position where any error

occurred. Deﬁne e

and e

as the corresponding vectors. If x is an n-bit codeword

and |x the corresponding quantum state, the applications of the combined error pattern

, e

shall transform the state |x into the errored state |x

∗

 according to:

∗

=(−1)

x·e

|x + e

, (24.37)

where x · e

is the dot product of x and e

. For instance, |x=|10011, e

(0, 1, 0, 1, 0) (X errors on the second and fourth qubits) and e

= (1, 0, 0, 1, 1) (Z

errors on the ﬁrst and last two qubits) yield x · e

= 1.1 + 0.0 +0.0 +1.1 +1.1 ≡ 3

and |x + e

=|1 +0|0 +1|0 +0|1 +1|1 +0≡|11001, and the errored state

∗

=(−1)

|11001≡−|11001. When the error pattern e

, e

is applied to the CSS

codeword |x + C

 deﬁned in Eq. (24.36), the resulting errored state is

|(x + C

)

∗

≡

√



y∈C

(

−1

)

(

x+y

)

·e

x + y + e



. (24.38)

The next step consists of the introduction of the parity-check matrix

H to detect the t

errors of the X type (not to be confused here with the Hadamard gate H ). This is achieved

by appending an n-qubit ancilla |0 to the recipient’s codeword |x

∗

=|x + e

, and

passing the result through a quantum circuit that achieves the transformation |x

∗

|0→

∗

|

∗

. Recall from Chapter 11 that if x is a codeword, then

Hx = 0, and hence

∗

=|

H(x + e

)≡|

. Measuring each of the qubits in the ancilla |



yields the syndrome vector

and, hence, the full error diagnosis e

, which is

common to each of the series terms in Eq. (24.38). The ancilla can then be discarded

and each of the errored qubits can be corrected (or back ﬂipped) by applying X gates in

the corresponding circuit wires, to obtain the X -corrected state

(

x + C

)

∗

≡

√



y∈C

(

−1

)

(

x+y

)

·e

x + y



. (24.39)

A quantum circuit performing the operation |z|0→|z|Uz for any n × n matrix

U (here with U ≡

H and



≡|(x + C

)

∗

) can be realized by exclusively using

CCNOT (controlled-CNOT) gates, as illustrated in Fig. 24.5. The design concept of

such a circuit can be grasped by analyzing the basic functionality



→



with U

where we used the (equivalent) bit-wise addition properties x + x = 0andx



=−x



. The same result is

obtained with the assumption x + x



∈ C

. It shows that the cosets x + C

and x



have two elements

in common, which necessarily implies that x + C

= x



and, hence, |x + C

=|x



.

512 Quantum error correction

zuzu

111

...

…

……

zuzu

221

...

…

Figure 24.5 Quantum circuit to achieve the transformation



|0→

|



, given an n-qubit

|z and an n × n matrix U with binary coefﬁcients.

being a 2 ×2 matrix with binary coefﬁcients, which is left as an interesting exercise.

The ﬁgure actually shows that the binary coefﬁcients u

= 0, 1ofU can be directly

used as corresponding ancilla qubits |u

=|0, |1, with the input state of the circuit

being



|1|u

...u

|u

...u

...|u

...u

. After discarding the useless (or

“garbage”) computation qubits, the circuit output is indeed |z



. To summarize, we

have shown that the CSS(C

, C

) code can correct all t errors of the X type, as allowed by

the C

linear block code, and the syndromes |

 and

, can be generated through

a basic quantum circuit of CCNOT gates (Fig. 24.5), followed by the corresponding

qubit measurements and bit-ﬂip corrections.

The correction of phase-ﬂip, or Z -type errors, is achieved by ﬁrst passing each qubit

of the X-corrected state |(x + C

)

∗



through a Hadamard gate, i.e., to obtain the state

⊗n

|(x + C

)

∗



.InChapter 19, when describing the Deutsch–Joszsa algorithm,we

have established (as supported through Exercise 19.1) that the action of H

⊗n

on any

n-qubit |x yields the transformation

⊗n

|x=

√



(−1)

z·x



, (24.40)

where z is any possible n-bit combination. Applying this property to the state

|(x + C

)

∗



in Eq. (24.39), namely, for each of the terms

x + y



in the sum, we

24.3 Calderbank–Shor–Steine (CSS) codes 513

obtain:

⊗n

|(x + C

)

∗



≡

√



y∈C

(

−1

)

(

x+y

)

·(z+e

)



. (24.41)

By introducing z



= z + e

, we may rewrite the above in the form

⊗n

|(x + C

)

∗



≡

√







y∈C

(

−1

)

(

x+y

)

·z



+ e

. (24.42)

To reduce the right-hand side in Eq. (24.42) to a single summation, we ﬁrst isolate the

term involving the dot-product y · z



as follows

⊗n

|(x + C

)

∗



≡

√











y∈C

(

−1

)

y·z







(

−1

)

x·z



+ e

. (24.43)

It can be shown through a (not so trivial but tractable) exercise that the sum in brackets

[

]

is equal to |C

|for all z



∈ C

⊥

being the dual of the C

code), and zero otherwise



/∈ C

⊥

). Hence, the simpliﬁcation of the deﬁnition in Eq. (24.43):

⊗n

|(x + C

)

∗



≡





∈C

⊥

(

−1

)

x·z



+ e

. (24.44)

Except for the normalization factor and the phase terms, the above expression is similar

to that in Eq. (24.38) concerning the bit-ﬂip errored state, but here with e

as the error

pattern and C

⊥

as the code (as opposed to e

and C

, respectively). A similar error-

correction procedure can, thus, be implemented. First, we append an n-qubit ancilla |0

to this state, transforming each term in the sum in Eq. (24.44)into|z



+ e

|0, then

pass the result through a quantum circuit to achieve the transformation



+ e

|0→|z



+ e

|

⊥



+ e

)=|z



+ e

|

⊥



⊥

)

≡|z



+ e

|

⊥

),

(24.45)

where

⊥

is the parity-check matrix of the code C

⊥

,forwhich

⊥



= 0. Measuring

each qubit in the ancilla |

⊥

 yields the syndrome vector

⊥

and, hence, the full

error diagnosis e

, which is common to each of the series terms in Eq. (24.44). The

ancilla can then be discarded and each of the errored qubits can be corrected (or back

ﬂipped) by applying Y gates in the corresponding circuit wires, to obtain the Y -corrected

state

⊗n

|(x + C

)

∗



≡





∈C

⊥

(

−1

)

x·z



. (24.46)

The ﬁnal step consists of passing each qubit in the above state through a Hadamard gate,

i.e., to obtain the state H

⊗n

|(x + C

)

∗



. Here, there is no point in going through

the detailed calculation of such an operation, because as a useful property, H and H

⊗n

are self-inverse operators (HH = I, H

⊗n

= I

⊗n

). If we let e

= 0inEq.(24.44),

514 Quantum error correction

we obtain

⊗n

|(x + C

)

∗



≡





∈C

⊥

(

−1

)

x·z





≡ H

⊗n

|x + C

,

(24.47)

which is precisely the same state as H

⊗n

|(x + C

)

∗



, and also the H

⊗n

transform of

the error-free state |x +C

! Thus, a second application of H

⊗n

on the states deﬁned in

either Eq. (24.46)orEq.(24.47) yields

⊗n

|(x + C

)

∗



= H

⊗n

|(x + C

)

∗



=|x + C



≡

√



y∈C

x + y



(24.48)

which yields our initial CSS-encoded state |x + C

. Thus, the second round of correc-

tion concerning Z -errors has successfully restored the CSS codeword in its full integrity.

The next section concerning the Steane code provides an applied illustration of the

CSS(C

, C

) codes.

24.4 Hadamard–Steane code

The Hadamard–Steane code, also sometimes called the Steane code, belongs to the

CSS(C

, C

) family. It has the same bit-ﬂip and phase-ﬂip error correction capability

as the earlier-described Shor code, namely, up to one error in either or both cases, but

it uses 7-qubit codewords as opposed to nine qubits in the second case. It is based on

the Hamming code C

= C = (7, 4), which was described in Chapter 11, and its dual

= C

⊥

. To recall, a possible parity-check matrix

H for the (7, 4) Hamming code,

which we used in that chapter,

is deﬁned as:

H =





1101100

1011010

0111001





. (24.49)

Some other possible parity-check matrices

H for the (7, 4) Hamming code commonly used in the literature

or the Internet are

H =





1001011

0101101

0010111





H =





1101001

0101110

1110000





H =





0001111

0110011

1010101





24.4 Hadamard–Steane code 515

Table 24.4 Block codewords Y of the

Hamming code C

= (7, 4),aspro-

duced from the generator matrix

G =

according to Y = X

G. The parity bits are

showninbold.

Message word X Block code Y

0000 0000 000

0001 0001 111

0010 0010 011

0011 0011 100

0100 0100 101

0101 0101 010

0110 0110 110

0111 0111 001

1000 1000 110

1001 1001 001

1010 1010 101

1011 1011 010

1100 1100 011

1101 1101 100

1110 1110 000

1111 1111 111

In the convention of left matrix-vector multiplication, the corresponding generator matrix

G is:

G =







1000110

0100101

0010011

0001111







. (24.50)

Note that the above deﬁnitions correspond to a code expressed in a systematic form,as

shown by the fact that the right 3 × 3 sub-matrix of

H and the left 4 × 4 sub-matrix of

G are identity matrices. The |C

|=2

= 2

= 16 block codewords Y = X

G of C

(7, 4), which were already listed in Chapter 11, are reproduced here for convenience in

Table 24.4.

Consider next the dual code C

= C

⊥

. By deﬁnition, its parity-check matrix is

H =

, with corresponding generator matrix

G =

. From the deﬁnitions in Eqs. (24.49)

In Chapter 11 we used the convention of left vector-matrix multiplication. Thus, the codewords are generated

according to the product Y = X

G,seeEq.(11.2)inChapter 11. Under this convention, for an (n, k) code

with m = n − k, the systematic form of the generator and parity-check matrices are

G = [I

k×m

]and

H = [(P

)

m×k

], respectively. Thus, for the (7, 4) Hamming code (m = 3),

G is a 4 × 7 matrix and

is a 3 ×7 matrix.

516 Quantum error correction

Table 24.5 Block codewords Y of the dual

code C

= C

⊥

= (7, 3) of the Hamming

code C

= (7, 4), as produced from the gen-

erator matrix

G =

, where

H is the parity-

check matrix of C

, according to Y =

GX.

The parity bits are shown in bold.

Message word X Block code Y

000 0000 000

001 0111 001

010 1011 010

011 1100 011

100 1101 100

101 1010 101

110 0110 110

111 0001 111

and (24.50), we obtain:

H =







1000

0100

0010

0001

1101

1011

0111







, (24.51)

G =







110

101

011

111

100

010

001







. (24.52)

As deﬁned in Eq. (24.52), the 7 ×3 generator matrix

G of the dual code C

generates

seven-bit codewords from three-bit message words, this time using the right vector-

matrix multiplication, i.e., Y =

GX. Since

G has the systematic form

G = [P

4×3

and since

G = 0 =

G, the dual code is a valid (n, k) = (7, 3)

code (note that it is not a Hamming code since n = 2

n−k

− 1). The |C

|=2

= 2

= 8

block codewords Y =

GX are listed in Table 24.5.

Analyzing Table 24.5, we ﬁrst note that, as expected, the code C

is in systematic form,

with the four parity bits appearing at the left of the codewords Y and the three message

bits (X) appearing at the right. Next, it is easily checked that the bit-wise sum ⊕ of any

two codewords in C

belongs to C

; since C

contains the identity element 0000000,

, ⊕)isagroup. Then, we observe that the minimum Hamming distance (the minimum

difference in bit positions between any two codewords) is d

min

= 3. This indicates that