belong to di¬erent coset of C2, then for no y, y ∈ C2 does x + y = x + y , and therefore x + C2|x + C2 = 0.

The quantum code CSS(C1, C2) is de¬ned to be the vector space spanned by the states |x + C2 for all x ∈ C1.

|C | |C |

The number of cosets of C2 in C1 is |C1 | , so dim (CSS (C1 , C2)) = |C1 | = 2k1’k2 , and therefore CSS(C1, C2) is

2 2

an [n, k1 ’ k2] quantum code.

⊥

The quantum error correction can be exploited by the classical error correcting properties of C 1 and C2 .

In the quantum case there is like in the classical a possibility of a ¬‚ip bit error, given in e 1 , but additionally

23

a phase ¬‚ip error in denoted here by e2 . Then because of noise the original state |x + C2 |0 has changed

(x+y)·e2

to √ 1 |x + y + e1 |0 , where an ancilla system |0 to store the syndrome for the C1 is

y∈C2 (’1)

|C2 |

(x+y)·e2

introduced. Applying the parity matrix to the deformed state √ 1 |x + y + e1 |H1e1 , and

(’1)

y∈C2

|C2 |

by measuring the ancilla system the error syndrome is obtained and one corrects the error by applying NOT gates

(x+y)·e2

to the ¬‚ipped bits as indicated by e1 , giving √ 1 |x + y . If to this state Hadamard gates

y∈C2 (’1)

|C2 |

(’1)(x+y)·(e2 +z) |z ,

1

to each qubit are applied, phase ¬‚ip error are detected. One then takes √ z y∈C2

|C2 |2n

(x+y)·z

1

z + e2 , one can write the last state as √ |z + e2 . Assuming

and de¬ning z (’1)

z y∈C2

|C2 |2n

y·z y·z

⊥

/⊥

z ∈ C2 then it easy to verify that = |C2| , while if z ∈ C2 then

(’1) (’1) = 0. Hence the

y∈C2 y∈C2

x·z

|C2 |

|z + e2 , which resembles to a bit ¬‚ip error described by

state is further rewritten as z ∈C2 (’1)

⊥

2n

vector e2 . Following the same procedure for the bit ¬‚ips the state is ¬nally as desired quantum error-corrected.

A quantum analogue of Gilbert-Varshamov bound is proven for the CSS codes, guaranteeing the existence

of good quantum codes. In the limit n becomes large, an [n, k] quantum code protecting up to t errors exist for

some k such that n ≥ 1 ’ 2Hbin 2t .

k

n

Concluding this summary on error correction, it is useful for quantum cryptography to de¬ne codes by

1 u·v

|x + C2 (’1) |x + y , (3.6)

|C2| y∈C2

parametrized by u and v, and named CSSu,v (C1, C2) , which are equivalent to CSS(C1, C2) .

3.2.2 Classical information over noisy classical channels

The theoretical study of transmission of information over noisy channels is motivated by Shannon™s correspond-

ing theorem, which demonstrates the existence of codes capable of realizing it, without giving clues how they

could be constructed. To model transmission of information over noisy channel a ¬nite input alphabet X and

a ¬nite output alphabet Y are considered; if a letter x ∈ X is transmitted by one side, over the noisy channel,

then a letter y ∈ Y is received by the other, with probability p (y|x) , where of course y p (y|x) = 1 for all x.

The channel will be assumed memoryless in the sense of Markov™s process, where the action on the currently

transmitted letter is independent of the previous one.

Now the process of transmitting information according to Shannon™s noisy channel coding theorem uses the

result of the noiseless one. According to this theorem it is always possible to pick up a reliable compression

decompression scheme of rate R. Then a message M can be viewed as one of the possible 2 nR typical strings and

encoded using the map Cn : 1, . . . , 2nR ’ X n which assigns M to each n-sequence of the input alphabet.

This sequence is sent over the noisy channel and decoded using the map Dn : Y n ’ 1, . . . , 2nR . This

procedure is shown in Figure 3.2. It is very natural for a given encoding-decoding pair to de¬ne the probability

of error as the maximum probability over all messages M that the decoded output of the channel is not equal

to M,

max p (Dn (Y ) = M |X = Cn (M )) .

p (Cn, Dn )

M

Then it is said that a rate R is achievable if there exists such a sequence of encoding-decoding pairs (C n, Dn)

and require in addition p (Cn, Dn) approaching zero as n approaches in¬nite. The capacity C (N ) of a noisy

channel N is de¬ned as the supremum over all the achievable rates for the channel and is going to be calculated

in the following paragraph.

For the calculation, random coding will be used, that is 2nH(X) strings will be chosen from the possible

input strings, which with high probability will belong in the set of typical ones. If these strings are sent over the

channel a message belonging in the set Y n will be received. But for each received letter Y there is an ignorance

on knowing X given by H (Y |X) . Hence for each letter, 2H(Y |X) bits could have been sent, which means that

totally there are 2nH(Y |X) possible sent messages. In order to achieve a reliable decoding the string received

must be close to the 2nH(X) initially chosen strings. Then decoding can be modeled by drawing a Hamming

sphere of radius δ around the received message, containing 2n[H(Y |X)+δ] possible input strings. In case exactly

one input string belongs in this sphere then the encoding-decoding scheme will work reliably. It is unlike that

24

¨#!A@9B

©©¨¦¤

¥§§¥ ¨#!

$ " % $"

0!'

)(& !&C)#(

)( 8 7654 " ¨21

" 3"

D

¢ £¢

¡

HG64G0A0

FE3 ¨"#!A

$ 7Q7F0E 3 "PI

H4

Figure 3.2: The noisy channel coding problem for classical messages. It is required that every one of the 2 nR

possible messages should be sent uncorrupted through the channel with high probability.

no word will be contained in the Hamming sphere, but it should be checked whether other input strings are

contained in it. Each decoding sphere contains a fraction

2n[H(Y |X)+δ]

= 2’n[H(Y :X)’δ] ,

nH(X)

2

of the typical input strings. If there are 2nR strings, where R can be related to Gilbert-Varshamov bound in

equation 3.5, the probability that one falls in the decoding sphere by accident is

2nR 2’n[H(Y :X)’δ] = 2’n[H(Y :X)’R’δ] .

Since δ can be chosen arbitrarily small, R can be chosen to be as close to H (Y : X) as desired. Now getting

the maximum over the prior probabilities of the strings Shannon™s result is found.

Shannon™s noisy channel coding theorem:

For a noisy channel N the capacity is given by

C (N ) = max H (Y : X) ,

p(x)

where the maximum is taken over all input distributions p (x) (a priori distributions) for X, for

one use of the channel, and Y is the corresponding induced random variable at the output of the

channel.

It should be noted that the capacity found in the above mentioned theorem is the maximum one can get for

the noisy channel N .

3.2.3 Classical information over noisy quantum channels

The case of sending classical information over noisy quantum channels is quite similar to the classical channel.

Each message is selected out of the 2nR, chosen by random coding as was done for the classical case. Suppose

now a message M, is about to be sent and the i-th letter letter, denoted by Mi ∈ {1, 2, . . . , k} , is encoded in

the quantum states {ρ1 , ρ2, . . . , ρk } of potential inputs of a noisy channel represented by a quantum operation

E. Then the message M sent is written as a tensor product ρ M1 — ρM2 — · · · — ρMn . Because of noise, the

channel has some impact to the transmitted states, such that the output states are σ Mi = E ρMi , thus the

total impact on the message M will be denoted σ M = E —n (ρM ) . The receiver must decode the σ M message

with a similar way to the one for the noisy classical channel. Now because the channel is quantum, a set of

POVM measurements is going to describe the outcome of information on the part of the receiver. To be more

speci¬c for every M message a POVM operator EM is going to be corresponded. The probability of successfully

decoding the message, will be tr(σ M EM ) , and therefore the probability of an error being made for the message

M is pe 1’tr(σM EM ) .

M

The average probability of making an error while choosing from one of the 2 nR messages is

e

[1 ’ tr (σM EM )]

M pM M

pav = . (3.7)

2nR 2nR

25

Now the POVM operators EM can be constructed as follows. Let > 0, and assume pj is a probability

distribution over the indices {1, 2, . . . , k} of the letters, named the a priori distribution, then for the space of

output alphabet a matrix density can be de¬ned, σ ¯ j pj σ j , and let P be a projector onto the -typical

—n

subspace of σ . By the theorem of quantum typical sequences, it follows that for any δ > 0 and for su¬ciently

¯

large n, tr(¯ —n (I ’ P )) ¤ δ. For a given message M the notion of -typical subspace for σ M can be de¬ned,

σ

based on the idea that typically σ M is a tensor of about np1 copies of ρ1 , np2 copies of ρ2 and so on. De¬ne

¯ j j

ej , so σM = »M EK EK , where

M M

S j pj S (σ j ) . Suppose σ j has a spectral decomposition k »k e k K

k

K

»M »M1 »M2 · · · »Mn eM1 M2

· · · eMn

M

K = (K1 , . . . , Kn) , and for convenience and EK e K2 are de¬ned.

1 2 n 1 n

K K K K K K

M

De¬ning ¬nally the projector PM onto the space spanned by all EK such that

1 1 ¯

log M ’ S ¤ . (3.8)

n »K

Moreover the law of large numbers imply that for any δ > 0 and for su¬ciently large n, E [tr (σ M PM )] ≥ 1 ’ δ,

where the expectation is taken with respect to the distribution over the strings ρ M , hence E [tr (σM (I ’ PM ))] ¤

δ. Also note that by the de¬nition (3.8) the dimension of the subspace onto which PM projects can be at most

¯ ¯

2n(S+ ) , and thus E [tr (PM )] ¤ 2n(S+ ) . Now the POVM operators are de¬ned

’1 ’1

2 2

EM P PM P P PM P P PM P . (3.9)

M M

To explain intuitively this construction, up to small corrections EM is equal to the projector PM and the

measurements {EM } correspond essentially to checking whether the output of the channel falls into the subspace

on which PM projects. This can be though as analogous to the Hamming sphere around the output. Using (3.7)

¯

and (2.9) one can ¬nd out that E [pav ] ¤ 4δ + 2nR ’ 1 2’n[S(¯)’S’2 ] . Provided R < S (¯ ) ’ S it follows that

¯

σ

σ

E [pav ] approaches zero as n approaches in¬nity. These where the main steps to prove the following theorem.

Holevo-Schumacher-Westmoreland (HSW) theorem:

Let E be a trace-preserving quantum operation. De¬ne

®««

max °S E pj ρ j ’ pj S E ρ j » ,

χ (E) (3.10)

{pj ,ρj } j j

where the maximum is over all ensembles pj , ρj of possible input states ρj to the channel. Then

χ (E) is the product state capacity for then channel E, that is, χ (E) = C (1) (E) .

In the aforementioned theorem the symbol C (1) (E) is used to denote the capacity of the channel, but just

in the case of a product case. Whether this kind of capacity might be exceeded if the input states are prepared

in entangled states is not known and it is one of the many interesting open questions of quantum information

theory. It should be emphasized that like in the case of a classical channel, the capacity found here is the

maximum one can get for the noisy channel E.

Finally for the maximization in equation (3.10) is potentially over an unbounded set, therefore for practical

reasons one takes the maximum over and ensemble of pure states (refer to [2, p.212-214] for more details).

3.2.4 Quantum information over noisy quantum channels

Unfortunately up to day there is no complete understanding of quantum channel capacity. As far as it concerns

the present state of knowledge, the most important results were already presented in subsections 2.1.2 and 2.2.2,

concerning each the accessible quantum information and quantum data processing. One should also mention

that there exist a quantum analogue to equation 3.4, the quantum Singleton bound, which is n ’ k ≥ 2 (d ’ 1)

for an [n, k, d] quantum error correcting code.

However an additional comment should be mentioned. The coherent information de¬ned in (2.10), because

of its rˆle in quantum data processing (equation (2.11) compared with (2.9)), it is believed to be the quantum

o

analogue of mutual information H (X : Y ) , and hence perhaps related to quantum channel capacity. This

intuitive argument is yet unproven. For some progress to that hypothesis, see [1, p.606] and the references

therein.

26

Chapter 4

Practical quantum cryptography

One of the most interesting applications of quantum information theory and the only one realized until now,

is quantum cryptography. For an overview of the history and the methods of classical cryptography, and for a

simple introduction in quantum cryptography refer to [30].

It is widely known that there exist many secure cryptographic systems, like for example the RSA [31].

Then why quantum cryptography is needed? The reason is that as long quantum laws hold, it is theoretically

unbreakable. In addition to this all known classical cryptographic systems, like the RSA, seem to be broken by

quantum computers [1, 30], using quantum factoring and quantum discrete logarithms [20, 21], or by methods

found in quantum search algorithms [22, 23].

In this chapter the basic notions of quantum cryptography and a proof of its security are analyzed in section

4.1. Then the possibility of constructing a commercial device capable of performing quantum cryptography is

discussed in section 4.2.

4.1 Theoretical principles of quantum cryptography

Cryptography usually concerns two parties A and B, willing to securely communicate, and possibly an eaves-

dropper E. These points are sometimes given human names for simplicity, calling A : Alice, B : Bob and E :

Eve. The situation is visualized in Figure 4.1.

Eve

¦ stolen

¦

¦ information

Alice ”””””” Bob

← ’ ’’ ’ ’ ’

’’ ’’’

communicated

messages

Figure 4.1: Alice and Bob communicating with the fear of Eve stealing information.

Quantum mechanics can be used to secure communication between Alice and Bob. To achieve this a

quantum line will be used to send a randomly produced cryptographic key (see Figure 4.3). This can be done

using protocols described in subsection 4.1.1. Moreover Alice and Bob need a classical line to discuss their

result, as described by the same protocol, and send the encrypted message.

The encryption and the decryption of the message is done using a string K, the key, which should be of equal

length to the message, M. Then by applying the modulo 2 addition • for each bit of the strings, the encrypted

message is E = M • K. Finally the message is decrypted by further addition of the key, (M • K) • K =

M • (K • K) = M • 0 = M.

27

Quantum Key Distribution

Quantum line

Public line

Security topics discussion

and

Encrypted messages

Figure 4.2: The setup of BB84 quantum key distribution protocol. The quantum line is used for the distribution

of the key, while the classical line for discussing security topics and the transmission of encrypted messages.

4.1.1 The BB84 quantum key distribution protocol

Looking back in Figure 1.2, presented in page 7, one can see from the basic features of quantum mechanics that

it is not easy for Eve to steal information, since it cannot be copied by no-cloning theorem. Moreover, it is

impossible for her to distinguish non-orthogonal states, and any information gain related to such a distinction

involves a disturbance. Then Alice and Bob by sacri¬cing some piece of information, and checking through

the coincidence of their key can verify whether Eve was listening to them. Motivated by the above arguments

Bennet and Brassard presented in 1984 the ¬rst quantum cryptographic protocol [32] described next.

Suppose Alice has an n-bit message. Then in order to generate an equal length cryptographic key she begins

with some a and b (4 + δ) n-bit strings randomly produced. She must then encode this to a (4 + δ) n-qubit

string

(4+δ)n

|ψ ≡ ψ a k bk ,

k=1

where ak the k-th bit of a (and similarly for b), and each qubit just mentioned can be

|ψ 00 |0 , (4.1)

|ψ 10 |1 ,

|0 + |1

√

|ψ 01 |+ = ,

2

|0 ’ |1

√

|ψ 11 |’ = ,

2

where |+ is produced by application of the Hadamard gate on |0 , and |’ by applying the same gate on

|1 . The above procedure, encodes a, in the basis {|0 , |1 } if bk = 0, or in {|+ , |’ } if bk = 1. The states of

each basis are not orthogonal to the ones of the other basis, and hence they cannot be distinguished, without

distortion. δ is used as a tolerance due to noise of the channel.

The pure state |ψ ψ| is sent over the quantum channel, and Bob receives E (|ψ ψ|) . He announces the

receipt in the public channel. At this stage Alice, Bob and Eve have each their own states, described by their

own density matrices. Moreover Alice has not revealed b during the transmission, and Eve has di¬culty in

identifying a by measurement, since she does not know in which basis she should do it, and hence any trial to

28

measure disturbs E (|ψ ψ|) . However E (|ψ ψ|) = |ψ ψ| in general, because the channel can be noisy. The

above description implies that a and b should be completely random, because any ability of Eve to infer anything

about these strings, would jeopardize the security of the protocol. Note that quantum mechanics o¬ers a way

of perfect random number generation, just by applying on |0 state, the Hadamard gate, one obtains |0 √2 , +|1

1

and after a measurement either |0 or |1 are returned with probability p = 2 .

In order to ¬nd their key Bob proceeds in measuring E (|ψ ψ|) in the basis determined by a string b he

generated randomly too. This way he measures the qubits and ¬nds some string a . After the end of his

measurements he asks Alice, on the public channel, to inform him about b. They then discard all bits a m and

am having bm = bm , since they measured them in di¬erent bases and hence are uncorrelated. It should be

stressed that the public announcement of b does not help Eve to infer anything about a or a .

At this point they both have new keys aA and aB of statistically approximate length 2n, and Alice selects

randomly n-bits and informs Bob publicly about their values. If they ¬nd that a number of qubits above a

threshold t, disagree then they stop the procedure and retry. In case of many failures there is de¬nitely an

invader and they should locate him. In case of success, there are some approximately n bit strings a A and aB ,

not communicated in public. Then if for example Alice wants to send a message M, she encodes it, taking

E = M • aA, and send E through the public channel. Then Bob decodes it by M = E • aB . The current keys,

strings aA and aB , should be discarded and not reused.

How can Alice™s key aA be the same as Bob™s aB in the case of a noisy channel which results E (|ψ ψ|) =

|ψ ψ|? This is the main topic of the next subsection.

4.1.2 Information reconciliation and privacy ampli¬cation

As anyone can assume, the communication over the noisy quantum channel is imperfect, E (|ψ ψ|) = |ψ ψ|,

and hence even if there was no interference by Eve in general aA = aB . Alice and Bob should perform an error

correction to get the same key a— , by discussing over the public channel and revealing some string g related to

aA and aB . This is named information reconciliation. In order to have a secure key they should have privacy

ampli¬cation by removing some bits of a— to get a , minimizing Eve™s knowledge, since a— are related to string

A

g publicly communicated. It is known that both procedures can be used with high security.

As already seen information reconciliation is nothing more than error-correction; it turns out that privacy

ampli¬cation it related to error-correction too, and both tasks are implemented using classical codes. To be

more speci¬c decoding from a randomly chosen CSS code, already presented in subsection 3.2.1, can be thought

of as performing information reconciliation and privacy ampli¬cation. This can be seen by considering their

classical properties. Consider two classical linear codes C1 and C2 which satisfy the conditions for a t bit error-

correcting [n, m] CSS code. To perform the subsequent task the channel should sometimes randomly tested and

seen to have errors less than t, including eavesdropping.

Alice should pick randomly the codes C1 and C2. Assume that aA = aB + e, where e is some error. Since

it is known that less than t errors occurred, if Alice and Bob both correct their states to the nearest codeword

in C1, their results will be a— . This step is information reconciliation. To reduce Eve™s knowledge Alice and

Bob identify which of the 2m cosets of C2 in C1 their state a— belongs to. This is done by computing the

coset a— + C2 in C1. The result is their m bit key sting a . By virtue of Eve™s knowledge about C2, and the

error-correcting properties of C2, this procedure can reduce Eve™s mutual information with a to an acceptable

level, performing privacy ampli¬cation.

4.1.3 Privacy and security

In order to quantify bounds in quantum cryptography, two important notions are de¬ned in this subsection:

privacy and security.

Assume Alice sends the quantum states ρA , k = 0, 1, 2, . . . , and Bob receives ρ B = E ρA . The mutual