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

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

24.4 Hadamard–Steane code 517

x Code word

0000 000 0111 001 1011 010 1100 011 1101 100 1010 101 0110 110 0001 111

Coset Equals

0000 000

0000 000 0111 001 1011 010 1100 011 1101 100 1010 101 0110 110 0001 111

0 + C2

0001 111

0001 111 0110 110 1010 101 1101 100 1100 011 1011 010 0111 001 0000 000 1 + C2 2 + C2

1 + C2 2 + C2

0010 011

0010 011 0101 010 1001 001 1110 000 1111 111 1000 110 0100 101 0011 100

2 + C2

0011 100

0011 100 0100 101 1000 110 1111 111 1110 000 1001 001 0101 010 0010 011

0100 101

0100 101 0011 100 1111 111 1000 110 1001 001 1110 000 0010 011 0101 010

0101 010

0101 010 0010 011 1110 000 1001 001 1000 110 1111 111 0011 100 0100 101

0110 110

0110 110 0001 111 1101 100 1010 101 1011 010 1100 011 0000 000 0111 001 6 + C2 0 + C2

0111 001

0111 001 0000 000 1100 011 1011 010 1010 101 1101 100 0001 111 0110 110

7 + C2 0 + C2

1000 110

1000 110 1111 111 0011 100 0100 101 0101 010 0010 011 1110 000 1001 001

1001 001

1001 001 1110 000 0010 011 0101 010 0100 101 0011 100 1111 111 1000 110

1010 101

1010 101 1101 100 0001 111 0110 110 0111 001 0000 000 1100 011 1011 010 10 + C2 0 + C2

1011 010

1011 010 1100 011 0000 000 0111 001 0110 110 0001 111 1101 100 1010 101 11 + C2 0 + C2

1100 011

1100 011 1011 010 0111 001 0000 000 0001 111 0110 110 1010 101 1101 100 12 + C2 0 + C2

1101 100

1101 100 1010 101 0110 110 0001 111 0000 000 0111 001 1011 010 1100 011 13 + C2 0 + C2

1110 000

1110 000 1001 001 0101 010 0010 011 0011 100 0100 101 1000 110 1111 1111

1111 111

1111 111 1000 110 0100 101 0011 100 0010 011 0101 010 1001 001 1110 000

Dual code C2

= (

)

Code C1 =

(

)

14 + C2 2 + C2

15 + C2 2 + C2

9 + C2 2 + C2

8 + C2 2 + C2

5 + C2 2 + C2

4 + C2 2 + C2

3 + C2 2 + C2

Figure 24.6 Cosets of C

= (7, 3) in C

= (7, 4). The codewords of C

are listed in the top row,

while the codewords of C

(called x = 0, 1, 2,...,15) are listed in the left column. The

elements of C

that are in C

are highlighted with a dark background. The two rightmost

columns show the coset names and identify their equivalences, the only two different cosets

being captured in 0 +C

and 2 +C

the code C

has the same correction capability as C

, namely t = (d

min

− 1)/2 = 1bit

(see Section 11.2). Then comparing the codes listed in Table 24.4 (C

= (7, 4)) and Table

24.5 (C

= C

⊥

= (7, 3)), we observe that the second is included in the ﬁrst, namely the

property C

⊂ C

, i.e., C

is a subgroup of C

. According to the previous section,

such a condition (along with the condition that C

must have the same error-correction

capability t as C

) makes the dual code C

fully eligible to construct a CSS(C

, C

)

quantum code of dimension 2

−k

= 2

4−3

= 2.

The construction of CSS(C

, C

) is made by applying the deﬁnition in Eq. (24.36),

which, given x ∈ C

, requires one to determine all the |C

|=8 binary codewords x + y

forming the cosets x +C

, and to sum up the

x + y



quantum states thus deﬁned.

Figure 24.6 provides the full list of cosets of C

in C

. The top row lists the codewords

of C

, while the left column lists the codewords of C

(called x = 0, 1, 2,...,15) and

whose elements that are in C

have been highlighted with a dark background. From

the table information, it is readily observed that all the common elements x ∈ C

, C

belong to the same coset 0 +C

, while all elements x



∈ C

, x



/∈ C

belong to the same

coset 2 +C

(which could as well be called 15 + C

, for instance). Therefore, taking

any codeword pair x, x



with such properties is sufﬁcient to generate and deﬁne the

two codewords of CSS(C

, C

), which we shall call |



0, |



1. For instance, we can use

x = 0000000 (x ∈ C

, C

) and x



= 1111111(x



∈ C

, x



/∈ C

). We, thus, obtain:



0≡

0000000 +C



√

0000000



0111001



1011010



1100011



1101100



1010101



0110110



0001111



(24.53)

518 Quantum error correction

Table 24.6 Deﬁning a rule for the codeword bits of C

(Table 24.5); see text for description.

1234 567

+ x

0000 000

0111 001

1011 010

1100 011

1101 100

1010 101

0110 110

0001 111



1≡

1111111 +C



√

1111111



1000110



0100101



0011100



0010011



0101010



1001001



1110000



(24.54)

To recall, to construct the Steane code {|



0, |



1}we have used a generator matrix

G =

in systematic form,asshowninEq.(24.52). As previously mentioned, there exist several

other possibilities for deﬁning the parity-check matrix

of the (7, 4) Hamming code.

It is left as an easy exercise to determine the Steane code {|



0, |



1}obtained with a matrix



T different from that used in this chapter. It does not matter that the resulting

codewords |



0, |



1 differ from those deﬁned in Eqs. (24.53)or(24.54), because in any

(n, k) block code the choice of generator and parity-check matrices is only a matter of

convention.

How can we realize a quantum circuit capable of encoding the above-deﬁned |



0, |



1

Steane codewords, which represent ﬁnely crafted superpositions of eight 7-qubits? Short

of a rule to predict the values of the individual qubits within each of these 7-qubit

superpositions, the task of designing such a circuit seems rather complex! But here

comes a bit of magic in the way we can deﬁne a rule for the two codewords. As a

starting point, we have seen that each 7-qubit |Y  in the deﬁnition |



0 refers to the block

codeword Y , which is an element of the coset 0 +C

. To ﬁnd the rule governing the

bit values of Y , we ﬁrst list the codewords in seven columns, as shown in Table 24.6.

Because the code is in systematic form, the ﬁrst four columns 1234 represent parity bits,

while the last three columns 567 represent the message bits. If we call x

, x

these

three bits, we observe from the table that the parity bits in columns 1234 are deﬁned by

the sums x

+ x

, x

+ x

, x

+ x

, and x

+ x

, respectively.

The Steane codeword |



0 is, thus, deﬁned by the three message bits x

, x

,as:



0=

√



y∈C

x + y



≡

√



+ x

|

+ x

|

+ x

|

+ x

|



(24.55)

24.4 Hadamard–Steane code 519

AsshowninEq.(24.54), the other Steane codeword |



1 is generated by the bitwise

addition of z = 1111111 to each of the elements in C

/0 + C

, which yields the alternate

deﬁnition:



1=

√



y∈C

|x + y + z

≡

√



=0,1

(|x

+ x

+ 1|x

+ x

+ 1|x

+ x

+ 1

⊗|x

+ x

+ 1|x

+ 1).

(24.56)

Letting the bit variable a = 0, 1 we ﬁnally obtain a common deﬁnition for the Steane

codewords:



a≡

√



=0,1

(|x

+ x

+ a|x

+ x

+ a|x

+ x

+ a

⊗|x

+ x

+ a|x

+ a). (24.57)

We may simplify the above deﬁnition even further by setting the bit variables y

+ a, y

= x

+ a and y

= x

+ a, which gives



a≡

√



=0,1

(|y

+ y

+ a|y

+ y

+ a|y

+ y

+ a

⊗|y

+ y

|y

). (24.58)

(where the modulo-2 addition property u + u = 0 is applied for any bit u = x

, y, a =

0, 1). As we shall see next, the general deﬁnition of |

a in Eq. (24.57) represents the

“magic formula” needed to build a complete Steane encoder circuit!

Indeed, consider the ﬁrst qubit in |

a, namely |y

+ y

+ a. The most elementary

subcircuit that can be implemented to generate |y

+ y

+ awith y

, y

= 0, 1isshown

in Figure 24.7. It is seen from the ﬁgure that the two Hadamard gates produce two

=|+states that can act as control qubits on the target qubit



through CNOT

gates (recalling that



CNOT|x=

y ⊕ x



≡

x + y



). We observe that



, which

represents the originator’s message qubit to be encoded, is not limited to the basis states

|0 or |1; most generally, it can be of the form



= α|0+β|1, where, as usual, α, β

are complex amplitudes satisfying

= 1.

Based on the above, it is not at all difﬁcult to conceive the full Steane-code encoding

circuit shown in Fig. 24.8, which represents only one possible implementation out of

many other variants, let alone the ﬂexibility associated with the many other choices

for generator matrix

G in the (7, 4) code. Note that the same circuit, as traversed

from right to left, can be used for decoding, i.e., retrieving the message qubit |a=

α|0+β|1from the 7-qubit |

a, as obtained from the recipient after implementing error

correction.

This concludes this chapter on quantum error correction. An eerie feeling may rise

from realising that the above-described CSS codes only represent another conceptual

subspace within a grander space of the so-called stabilizer codes. Such codes, which

are, by and large, not limited to error correction but rather are at the root of advanced

520 Quantum error correction

ayy

Figure 24.7 Elementary circuit to generate the quantum state |y

+ y

+ a given bit values

α, y

, y

= 0, 1, as based on H (Hadamard) and CNOT gates. The states obtained at

intermediate stages are shown and pointed to by dotted arrows.

)(

∑

++++++++≡

321321323121

321

yyyyy

ayyay

ayy ++

xxx

y ++

321

yyy ++

Figure 24.8 Possible circuit implementation for encoding the |

a=|

0, |

1 Steane code example,

as deﬁned in Eq. (24.58).

quantum computing, represent yet another ﬁeld by itself. Within the framework of these

chapters, hopefully the reader has grasped the essentials to exercise his or her curiosity

towards this direction. If the reader has gone this far in these chapters, there are no more

conceptual difﬁculties involved, except for the never-ending work of specialization in

the ﬁeld. The last chapter, concerning quantum cryptography should complete our basic

training towards the impossible or ill-deﬁned grander picture, whether or not we elect to

become a specialist!

24.5 Exercises 521

24.5 Exercises

24.1 (B): Establish the following three operator deﬁnitions

= Z ⊗ Z ⊗ I =

(

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

)

⊗ I −

(

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

)

⊗ I,

= I ⊗ Z ⊗ Z = I ⊗

(

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

)

− I ⊗

(

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

)

= Z ⊗ I ⊗ Z =|00|⊗I ⊗|00|+|11|⊗I ⊗|11|

−(|00|⊗I ⊗|11|+|11|⊗I ⊗|00|),

where Z is the Pauli matrix,

Z =



0 −1



24.2 (M): Given the 9-qubit quantum error-correction (Shor) code

0=

|000+|111

√

|000+|111

√

|000+|111

√

1=

|000−|111

√

|000−|111

√

|000−|111

√

show that a single qubit phase-ﬂip error in any of the three blocks A, B, C can

be detected through the successive measurements

123456

= X

456789

= X

where X is the Pauli matrix,

X =





24.3 (M): Assuming a 3-qubit entangled block with the second qubit being ﬂipped,

q=

|010+|101

√

show that the syndrome measurement Z

of the last two qubits yields the expec-

tation value





=+1.

24.4 (T): Establish that the set C of 16 elements shown in Table 24.7 (underscore “–”

being for reading clarity), together with bitwise addition ⊕, form a group

(

C, ⊕

)

Then determine the different subgroups of

(

C, ⊕

)

and possible cosets of C



in C.

522 Quantum error correction

Table 24.7 Elements for Exercise 24.4.

Number Element Number Element

0 0000 000 8 1000 110

1 0001

111 9 1001 001

2 0010

011 10 1010 101

3 0011

100 11 1011 010

4 0100

101 12 1100 011

5 0101

010 13 1101 100

6 0110

110 14 1110 000

7 0111

001 15 1111 111

24.5 (T): Given the 2 × 2 matrix,

U =





with coefﬁcients having the bit values u

= 0, 1 and a 2-qubit state |x, where x is

a two-bit codeword, determine a quantum circuit that achieves the transformation

|x|0→|x



uniquely based on CNOT gates. Show that a more compact circuit can be elabo-

rated with CCNOT gates.

24.6 (T): Given a linear block code C with codewords x = x

...x

, show that for

any y such that y ∈ C

⊥

(dual of C), we have

(a)



x∈C

(−1)

x·y

and otherwise (y /∈ C

⊥

)

(b)



x∈C

(−1)

x·y

= 0,

where x · y = x

+ x

+···+x

is the binary scalar product.

24.7 (M): Given the parity-check matrix of the C = (7, 4) Hamming code,

H =





0001111

0110011

1010101





determine the codewords of the corresponding C

⊥

= (7, 3) dual code, as gener-

ated by the matrix

G =

Then determine the two codewords |



0, |



1 of the CSS(C, C

⊥

) code.

25 Classical and quantum cryptography

This ﬁnal chapter concerns cryptography, the principle of securing information against

access or tampering by third parties. Classical cryptography refers to the manipulation

of classical bits for this purpose, while quantum cryptography can be viewed as doing

the same with qubits. I describe these two approaches in the same chapter, as in my view

the ﬁeld of cryptography should be understood as a whole and appreciated within such

a broader framework, as opposed to focusing on the speciﬁc applications offered by

the quantum approach. I, thus, begin by introducing the notions of message encryption,

message decryption, and code breaking, the action of retrieving the message information

contents without knowledge of the code’s secret algorithm or secret key. I then consider

the basic algorithms to achieve encryption and decryption with binary numbers, which

leads to the early IBM concept of the Lucifer cryptosystem, which is the ancestor of

the ﬁrst data encryption standard (DES). The principle of double-key encryption, which

alleviates the problem of key exchange, is ﬁrst considered as an elegant solution but

it is unsafe against code-breaking. Then the revolutionary principles of cryptography

without key exchange and public-key cryptography (PKC) are considered, the latter also

being known as RSA. The PKC–RSA cryptosystem is based on the extreme difﬁculty

of factorizing large numbers. This is the reason for the description made earlier in

Chapter 20 concerning Shor’s factorization algorithm. Here, the discussion is expanded

to qualify the difﬁculty of the factorization problem by classical computing means, with a

detailed analysis of the time and memory requirements, yielding predictions for solving

the various RSA challenges. I then brieﬂy describe DES with its double- and triple-

implementation variants (2DES, 3DES), and the innovative features of the advanced

encryption standard (AES). Then follows a discussion of the other applications of

modern cryptography, including signature and authentication, which are based on the

principle of one-way encryption or hashing. I then move to quantum cryptography, which

is now placed in the global context of communication security, rather than addressed as

a separate ﬁeld.

Quantum cryptography is widely believed to provide “provably secure” means to

exchange information, based on fundamental quantum-mechanics principles. This is the

introductory concept of secure communication channel. As we shall see in this chapter,

the concept boils down to that of quantum key distribution (QKD), solving the age-long

issue of key exchange, without interception risks, as an absolute, “quantum” competitor

to PKC–RSA. I then describe the three hero protocols, referred to as BB84, B92, and

EPR protocols for QKD. As it turns out, and contrary to widespread belief, none of

524 Classical and quantum cryptography

these protocols is provably safe unless extra security steps are implemented. Indeed,

classical-coding means, “esoterically” referred to as information reconciliation, privacy

ampliﬁcation,orsecret key distillation (SKD), are necessary to achieve “ultimate”

(albeit exponential) security conﬁdence in the protocol. The closing section discusses

the eventual vulnerability of quantum cryptosystems, when replaced in the realistic

network environment, with its various forms of attack. The conclusion is that assuming

all attacks are possible (as opposed to sheltering under “postulates” that these remain

out of the picture), quantum cryptography represents just another, albeit very elegant,

technique for key exchange. Despite its exponential degree of safety, QKD must be

situated within the grander domain of global network security, where there cannot be

“absolute” conﬁdence in any cryptosystem.

25.1 Message encryption, decryption, and code breaking

This section reviews the elementary basics of cryptography principles, deﬁnitions, and

jargon.

There exist several instances where some private, conﬁdential, sensitive, or even

classiﬁed information must be conveyed through a communication channel. Examples

abound, from online tax declaration and business reports on company’s intranets to

military and government communications. The driving concept for protecting such

contents is cryptography, which comes from the Greek kryptos (secret) and graphein

(writing). Thus, cryptography is the art of transforming a message into a self-contained

secret, while ensuring a practical technique for the destinee to retrieve the information

contents.

The action of encryption is to transform an original text, or plaintext,intoaciphertext.

Nowadays, “plaintexts” are raw computer data, namely blocks of bits, but the spirit is

exactly similar. The word cipher refers to the coding algorithm or method of encryption.

An equivalent, fancier, deﬁnition of cipher is cryptosystem. The reverse operation, i.e.,

resolving a ciphertext into the original plaintext, is called decryption. Decryption is

based on the principle of a secret key. Throughout cryptographic history, the secret key

could have been any method of encryption and decryption based on correspondence

tables, squares,orgrids, kept secret between the corresponding parties. Alternatively,

the secret key could have been a codeword (named keyword), usually simple to pass on

and memorize, but more or less difﬁcult to guess. Nowadays, full and public knowledge

of the algorithm used in cryptographic standards poses no threat whatsoever to security.

Rather, secrecy is based entirely on the secret key, its type, length, means of exchange,

and rapid renewal (the last two points to be addressed later).

A third party who may try to make sense of a ciphertext without the key must resolve

the enigma through more or less extensive labor. Such a task is referred to as cryptoanal-

ysis (or, for short, cryptoanalysis). The goal of cryptanalysis, also called code breaking,

is to “break” the cipher or ciphertext (familiarly called “code”), meaning recovering

the plaintext by practical, inexpensive, hopefully rapid, and effortless methods. Note

25.1 Message encryption, decryption, and code breaking 525

that code breaking should not be confused with the nobler, academic notion of code

cracking.

In any case, the task of trying either to “break” or “crack” a code is referred

to as an attack, giving a military ﬂavor. Codes may be attacked either by sophisti-

cated cryptanalysis algorithms or, more directly, by sheer “brute force” (hence the name

brute-force attack in crypto jargon). This latter approach refers to various techniques of

guessing keys at random, exploring what is referred to as the keyspace. For an N -bit

key size, the keyspace corresponds to 2

possibilities. In code breaking, rapidity of

execution is essential, because the plaintext is generally not only content-sensitive but

also time-sensitive. This is the reason why successive generations of cryptosystems and

key sizes have been designed to make it virtually impossible to a third party, even a

state with powerful cryptanalysis and computing means, to break them. With a key size

of N = 64 bits, the keyspace is 2

= 10

64 log 2/ log 10

= 1.8 × 10

. At a rate of trying

out one billion keys per second, a brute-force attack would, thus, require 1.8 ×10

seconds, or some 570 years to explore the full keyspace! Clearly, each extra bit of key

size doubles the number of key possibilities. Nowadays, some cryptosystems may use

key sizes as large as N = 512 bits or N = 1024 bits, corresponding to huge keyspaces

of 10

154

and 10

308

, respectively. However, one should not conclude that cryptosystems

become absolutely safe against attacks when the key size is sufﬁciently large. This sub-

ject being beyond the scope of this chapter, sufﬁce it to state here that one should not

underestimate the power of cryptanalysis, and also that the generation of truly random

keys is not technically simple. If a code breaker can guess the algorithm used to generate

the random keys, his or her task is simpliﬁed. But the most straightforward approach

is to intercept the key itself, at the time the communicating parties are doing what is

referred to as the key exchange.

Indeed, the weakness of cryptography lies in the fact that, in order to work, the secret

key must be communicated one way or another to the recipient. Such an exchange is

not without risk of interception, no matter how rapid and periodically changing. Clearly,

the worst situation is to be conﬁdent in the safety of a cryptosystem, while the channel

used to exchange the keys is in fact being wired! As a matter of fact, cryptography faces

a double security problem: transmitting the secret key without any measurable risk of

interception, and remaining virtually invulnerable to cryptanalysis.

The history of cryptography, or cryptology, represents a succession of increasingly

sophisticated cryptoalgorithms, which have invariably been broken at some point by

sheer cryptanalysis.

Most ancient and pre-computer-era algorithms have been based

Theconceptofcode cracking is somewhat different. It could be deﬁned as breaking a code for the ﬁrst

time. Put simply, code crackers are “champion” code breakers. The goal of code crackers is not so much

to retrieve secret messages (for which they usually cannot care less) as to prove to history that they have

been able to “crack” a previously reputed “invulnerable” or “unbreakable” cipher. Code cracking may be

viewed as a noble academic attempt to explore the limits of cryptosystem security, with a view to improve

the algorithms, or just as an engineering challenge to test security and standards.

For fascinating accounts of cryptology, from ancient to modern times, see, for instance: D. Kahn, The

Code Breakers (New York: Scribner, 1967); S. Singh, The Code Book (New York: Anchor Books, 1999);

S. Levy, Crypto, (New York: Penguin Books, 2001).

526 Classical and quantum cr yptography

on the principle of alphabetic substitution.

We may simplistically view any alphabetic-

substitution code as representing a one-to-one table correspondence between plaintext

and ciphertext letter symbols. There exist 26! possible permutations between the 26

letters, namely 26! = 1 × 2 × 3 × ... × 25 × 26 = 4.0 × 10

. Assuming that each

code possibility could be checked every second, breaking the code would take some

13 billion billion years, i.e., about one billion times the age of our Universe! And with

a rate of one billion checks per second, we still have the age of the Universe. Hence

brute-force attack is not a code-breaking solution. Older cryptanalysis would, rather,

attempt to guess which table, square, or grid algorithm and keys were used, based on

the fact that human beings at the time needed to keep the encryption and decryption

process simple and practical (as done by paper and pencil!), and the secret keys easy

to memorize. No matter how sophisticated, however, with mainframe computer power,

such alphabetic-substitution codes may now be broken in milliseconds or seconds. This

is because all possible algorithms and table, square, or grid combinations of past history

can be systematically explored, and also mainly because the keyword sizes remain

relatively small. Overall, cryptanalysis is facilitated by the detection of frequencies,

the repeated occurrences of certain ciphertext symbols and associations. The frequency

properties of the English language were described in Chapter 9. We have seen that the

two most likely letter associations are TH and HE, making THE the most likely three-

letter word in English. Thus, any frequent two-symbol or three-symbol occurrence in a

ciphertext is likely to correspond to these plaintext letter associations. I n cryptography

jargon, the word fragments, identiﬁed are called cribs. Based on a few cribs, the rest of

the guess can progress very fast, should the context of the message (most likely words,

e.g., in wartime) also be known to the code breaker. Frequency analysis and identiﬁcation

of cribs are basically the spirit of cryptanalysis as far as ancient (alphabetic-substitution)

cryptosystems are concerned.

Cryptography is over 2000 years old. The ingenuity and skills that were deployed

through the ages to conceive and then break ever-complex ciphers are both phenom-

enal and mind boggling. It is beyond the scope of this chapter to make even a brief

survey of cipher development. I shall just mention here the intriguing Enigma machine,

which was used by the German army during World War II.

It represented a major

turn in the history of cryptography, not solely because it was the ﬁrst “cryptographic

computer,” but because of its highly sophisticated encryption and decryption algorithm.

Probably one had never believed so much in cryptosystem invulnerability! The Enigma

cipher used only 26 typewriter characters with a three-rotor system, yielding as many

as 10 586 916 764 424 000 or 10 million billion (or 10 peta) polyalphabetic substitution

For a detailed and illustrated review of historical alphabetic-substitution algorithms, see, for instance, my

previous work: E. Desur vire, Wiley Survival Guide in Global Telecommunications, Broadband Access,

Optical Components and Networks, and Cryptography (New York: J. Wiley & Sons, 2004), Ch. 3,

pp. 345–477.

There exist many excellent websites dedicated to the Enigma machine, see for instance:

http://en.wikipedia.org/wiki/Enigma

machine,

www.codesandciphers.org.uk/enigma/index.htm,

www.mlb.co.jp/linux/science/genigma/enigma-referat/enigma-referat.html,