. 2
( 2)

It is yet quite surprising that quantum information can be compressed as was proven by Schumacher 3.1.2.
Assume that quantum information transmitted can be in states |xi ∈ H —n with probability p (xi ) . This
i=1 p (xi ) |xi xi | . A compression-decompression scheme of rate R
is described by the density matrix ρ =
consists of two quantum operations Cn and Dn analogous to the maps de¬ned for the classical case. The
compression operation Cn is taking states from H —n to H —nR and the decompression Dn returns them back,
as Figure 3.1 demonstrates. One can de¬ne a sequence xi1 xi2 xi3 · · · xin as -typical by a relation resembling to
the classical (3.3)
1 1
’ S (ρ) ¤ .
p (xi1 ) p (xi2 ) · · · p (xin )
A state |xi1 |xi2 · · · |xin is said to be -typical if the sequence xi1 xi2 xi3 · · · xin is -typical. The -typical
subspace will be noted T (n, ) and the projector onto this subspace will be

|xi1 xi1 | — |xi2 xi2 | — · · · — |xin x in | .
P (n, ) =
xi1 xi2 xi3 ···xin ∈T (n, )

Now the quantum typical sequences theorem can be stated.

Typical subspace theorem:

> 0 then for any δ > 0, for su¬ciently large n, tr(P (n, ) ρ —n) ≥ 1 ’ δ.
1. Fix
> o and δ > 0, for su¬ciently large n, (1 ’ δ) 2n(S(X)’ ) ¤ |T (n, )| ¤ 2n(S(X)+ ) .
2. For any ¬xed
3. Let S (n) be a projector onto any subspace of H —n of dimension at most 2nR, where R < S (ρ) is ¬xed.
Then for any δ > 0 and for su¬ciently large n, tr(S (n) ρ —n) ¤ δ.

Following the same principles the quantum version of Shannon™s theorem as proved by Schumacher is,

Schumacher™s noiseless channel coding theorem:
Let ρ be information belonging in some a Hilbert space H then if R > S (ρ) there exists a reliable
compression scheme. Conversely if R < S (ρ) any compression scheme is not reliable.

Cn Dn
’ ’
ρ ρ ρ
n log d nS (ρ) n log d
qubits qubits qubits

Figure 3.1: Quantum data compression. The compression operation Cn compresses a quantum source ρ stored
in n log d qubits into nS (ρ) qubits. The source is accurately recovered via the decompression operation D n .

The compression scheme found by Schumacher is

Cn (σ) P (n, ) σP (n, ) + |0 i| σ |i 0| ,

where |i is an orthonormal basis for the orthocomplement of the typical subspace, and |0 is some standard
state. As one can see this quantum operation takes any state σ from H —n to H —nR , the subspace of -typical
sequences if σ can be compressed, and if not it gives as outcome the standard state |0 , which is meant to be
a failure. Finally Dn was found to be the identity map on H —nR, which obviously maps any compressed state
back to H —nR ¤ H —n .

3.2 Information over noisy channels
It is an everyday life fact that communication channels are imperfect and are always subject to noise which
distorts transmitted information. This of course prevents reliable communication without some special control
of information transmitted and received. One can use error correction in order to achieve such a control,
which is summarized in subsection 3.2.1. However there are some general theoretical results concerning such
transmissions, which help calculate the capacity of noisy channels. The cases of classical information over noisy
classical and quantum channels each presented in subsections 3.2.2 and 3.2.3. A a summary for the up today
results for quantum information over noisy quantum channels is given in subsection 3.2.4.

3.2.1 Error correction
Error correction is a practical procedure for transmission of information over noisy channels. The intuitive idea
behind it is common in every day life. As an example recall a typical telephone conversation. If the connection
is of low quality, people communicating often need to repeat their words, in order to protect their talk against
the noise. Moreover sometimes during a telephonic communication, one is asked to spell a word. Then by saying
words whose initials are the letters to be spelled, misunderstanding is minimized. If someone wants to spell the
word ”phone”, he can say ”Parents”, ”Hotel”, ”Oracle”, ”None” and ”Evangelist”. If instead of saying ”None”,
he said ”New” the person at the other side of the line could possibly hear ”Mew”. This example demonstrates
why words should be carefully selected. One can see that the last two words di¬er by only one letter, their
Hamming distance is small (refer to appendix B.1 for a de¬nition), hence they should select words with higher

The error correction procedure, as presented in the last paragraph, is the encoding and transmission of a
message longer than the one willing to communicate, containing enough information to reconstruct the initial
message up to a probability. If one wish to encode a k-bit word x, into an n-bit y (k ¤ n), then this encoding-
decoding scheme is named [n, k] , and represented by function C (x) = y. In the last case it is often written
x ∈ C. One can avoid misunderstandings similar to ”New” and ”Mew”, as found in the above paragraph, by
asking each codeword to be of Hamming distance greater than d. Then after receiving a codeword y, he tries to
¬nd to which Hamming sphere, Sph(x, d) , it belongs, and then identi¬es the received codeword with the center
of the sphere: x. Such a code is denoted by [n, k, d].
The basic notions of classical and quantum error correction are summarized in next paragraphs.

Classical error correction
From all the possible error correction codes, a subset is going to be presented here, the linear ones. A member
of this subset, namely a [n, k] linear code, is modeled by an n — l matrix G, often called the generator. The
k-bit message x, is treated as a column vector, and the encoded n-bit message is the Gx, where the numbers in
both G and x are numbers of Z2, that is zeros and ones, and all the operations are performed modulo 2.
The linear codes are used because for the case of [n, k] , nk bits are needed to represent it. In a general code
C, an n-bit string would correspond to one of 2k words, and to do this a table of n2k bits is needed. In contrast
by using linear codes much memory is saved the encoding program is more e¬cient.
In order to perform error correction one takes an (n ’ k) — n matrix H, named parity check, having the
property HG = 0. Then for every codeword y = Gx it is obvious that Hy = 0. Now if an noise was present
during transmission, one receives a state y y + e, where e is the error occurred. Hence Hy Hy + He = He.
Usually Hy is called the error syndrome. From the error syndrome one can identify the initial y if t ≥ d (y , y) =
d (y + e, y) = d (e, 0) , and then checking in which sphere y ∈ Sph(y, d) . To do this the distance of the code
must be de¬ned by d ≡ d (C) min d (x, y) , that is the spheres of radius d must be distinct. Then if
d ≥ 2t + 1, up to t bits can be corrected. All this are under the assumption that the probability that the channel
¬‚ips a bit is less than 1 .
It is easy to check that linear codes [n, k, d], must satisfy the Singleton bound
n ’ k ≥ d ’ 1. (3.4)

One can further prove, that for large n there exists an [n, k] error-correcting code, protecting against t bits for
some k, such that
k t
≥ 1 ’ Hbin . (3.5)
n n
This is known as Gilbert-Varshamov bound.
Some further de¬nitions are needed. Suppose an [n, k] code C is given, then its dual is denoted C ⊥ , and has
as generator matrix H T and parity check GT . Thus the words in C ⊥ are orthogonal to C. A code is said to be
weakly self-dual if C ⊆ C ⊥ , and strictly self dual if C = C ⊥ .

Quantum error correction
In what concerns quantum information theory, errors occurring are not of the same nature as in the classical
case. One has to deal, except from bit ¬‚ip errors, with phase ¬‚ip errors. The ¬rst codes found to be able to both
of them are named Calderbank-Shor-Steane after their inventors [28, 29]. Assume C 1 and C2 are [n, k1] and

[n, k2] classical linear codes such that C1 ‚ C2 and both C1 and C2 can correct t errors. Then an [n, k1 ’ k2]
quantum code CSS(C1, C2) is de¬ned, capable of correcting errors on t qubits, named the CSS code of C1
over C2 , via the following construction. Suppose x ∈ C1, then de¬ne |x + C2 y∈C |x + y , where
|C2 | 2

the addition is modulo 2. If now x is an element of C1 such that x ’ x ∈ C2, then it easy to verify that
|x + C2 = |x + C2 , and hence |x + C2 depends only upon the coset C1/C2 x. Furthermore, if x and x
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

a phase ¬‚ip error in denoted here by e2 . Then because of noise the original state |x + C2 |0 has changed
to √ 1 |x + y + e1 |0 , where an ancilla system |0 to store the syndrome for the C1 is
y∈C2 (’1)
|C2 |
introduced. Applying the parity matrix to the deformed state √ 1 |x + y + e1 |H1e1 , and
|C2 |
by measuring the ancilla system the error syndrome is obtained and one corrects the error by applying NOT gates
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 ,
to each qubit are applied, phase ¬‚ip error are detected. One then takes √ z y∈C2
|C2 |2n
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
|C2 |
|z + e2 , which resembles to a bit ¬‚ip error described by
state is further rewritten as z ∈C2 (’1)

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 .
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 )

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

¥§§¥ ¨#! 
$ "  % $"
)(& !&C)#(
)( 8 7654 " ¨21
" 3"
¢   £¢
FE3 ¨"#!A
$   7Q7F0E 3 "PI

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)’δ] ,
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) ,

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

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 ) .
The average probability of making an error while choosing from one of the 2 nR messages is
[1 ’ tr (σM EM )]
M pM M
pav = . (3.7)
2nR 2nR

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
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
S j pj S (σ j ) . Suppose σ j has a spectral decomposition k »k e k K
»M »M1 »M2 · · · »Mn eM1 M2
· · · eMn
K = (K1 , . . . , Kn) , and for convenience and EK e K2 are de¬ned.
1 2 n 1 n
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)

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
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

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.

¦ stolen
¦ information

Alice ”””””” Bob
← ’ ’’ ’ ’ ’
’’ ’’’

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.

Quantum Key Distribution

Quantum line

Public line

Security topics discussion
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
|ψ ≡ ψ a k bk ,

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 |+ = ,
|0 ’ |1

|ψ 11 |’ = ,
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

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

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
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
k k k
information between the result of any measurement Bob may do and Alice™s value, H (B : A) , is bounded above
by Holevo bound (2.6), thus H (B : A) ¤ χB , and similarly Eve™s mutual information is bounded above by
H (E : A) ¤ χE . Since any excess information Bob has relative to Eve, at least above a certain threshold can in
principle be exploited by Bob and Alice to distill a shared secret key using the techniques of the last subsection.
It makes sense to de¬ne privacy as

P sup [H (B : A) ’ H (E : A)] ,

where S are all the possible strategies Alice and Bob may employ to the channel. This is the maximum excess
classical information that Bob may obtain relative to Eve about Alice™s quantum signal. Using the HSW theorem
(3.10), Alice and Bob may employ a strategy such that H (B : A) = χB , while for any strategy Eve may employ,
H (E : A) ¤ χE . Thus P ≥ χB ’ χE . A lower bound may be obtained by assuming that Alice™s signal states
are pure (refer to discussion after equation (3.10) to see why), ρA = ψA ψA , and if Eve initially had an
k k

unentangled state 0E , which may also assumed pure. Suppose Eve™s interaction is ψEB = U ψA 0E ,
since it is a pure state, the reduced density matrices ρE and ρB will have the same non-zero eigenvalues, and thus
k k
the same entropies, S ρk = S ρk . Thus P ≥ χ ’ χ = S ρB ’ k pk S ρB ’ S ρE + k pk S ρE =
k k
S ρB ’ S ρE = I (ρ, E) , where the de¬nition (2.10) was used. Note that the lower bound for privacy is
protocol independent.
A quantum key distribution (QKD) protocol is de¬ned secure if, for any security parameters s > 0 and
l > 0 chosen by Alice and Bob, and for any eavesdropping strategy, either the scheme aborts, or succeeds with
probability at least 1 ’ O (2’s) , and guarantees that Eve™s mutual information with the ¬nal key is less than
2’l . The key string must also be essentially random.

4.1.4 A provable secure version of the BB84 protocol
It can be proven [1, p.593-599] that using CSS codes one can have a 100% secure quantum key distribution.
However CSS codes need perfect quantum computation, which is not yet achieved. Fortunately there is a chance
of using the classical properties of CSSu,v codes de¬ned in (3.6) to have an equally secure classical computation
version of BB84 protocol (refer to [1, p.599-602] for a proof). This version is made up of the following steps:

1. Alice creates (4 + δ) n random bits.
2. For each bit, she creates a qubit either in the {|0 , |1 } or in {|+ , |’ } basis, according to a random bit
string b, see for example (4.1).
3. Alice sends the resulting qubits to Bob.
4. Alice chooses a random vk ∈ C1.
5. Bob receives the qubits, publicly announces this fact, and measures each in the {|0 , |1 } or in {|+ , |’ }
basis randomly.
6. Alice announces b.
7. Alice and Bob discard those bits Bob measured in a basis other than b. With high probability, there are
at least 2n bits left; if not, abort the protocol. Alice decides randomly on a set of 2n bits to continue to
use, randomly selects n of these to check bits, and announces the selection.
8. Alice and Bob publicly compare their check bits. If more than t of these disagree, they abort the protocol.
Alice is left with the n bit string x, and Bob with x + .
9. Alice announces x ’ vk . Bob subtracts this from his result, correcting it with code C1 to obtain vk .
10. Alice and Bob compute the coset of vk + C2 in C1 to obtain the key k.

4.2 A commercial quantum cryptographic device
After a theoretical presentation of quantum key distribution it is time to present experimental results and then
discuss the possibility of having a commercial device realizing quantum cryptography. These two topics are
discussed correspondingly in subsections 4.2.1 and 4.2.2.

4.2.1 Experimental quantum key distribution
The ¬rst demonstration of quantum key distribution was performed at the IBM laboratory in 1989 [33] over
a distance of 30 cm. Since then there has been remarkable improvement, demonstrating quantum key distri-
bution over a distance of 10 km [34, 35], in IBM too, or over distances exceeding 40km, and also in installed
telecommunication ¬ber, under the Lake Geneva [36].
In most cases experimental quantum cryptography is done using single photons, and optical ¬bers are used
to guide them from Alice to Bob. Once the medium is chosen one should pick the right source and detectors.
Since they have to be compatible, the crucial choice is the wave length. There are two main possibilities. Either
one chooses a wavelength around 800 nm where e¬cient photon counters are commercially available, or one
chooses a wavelength compatible with today™s telecommunication optical ¬bers, that is near 1300 nm or 1550
nm. The ¬rst choice requires the use of special ¬bers, hence the installed telecommunications networks can™t
be used. The second choice requires the improvement or development of new detectors not based on silicon
semiconductors which are transparent above 1000 nm wavelength. It is still unclear which of the two alternatives
will turn out to be the best choice.
In what concerns the production of photons according to the BB84 states, de¬ned in equation (4.1), one can
choose di¬erent polarization states, which form non-orthogonal bases. Polarization can be for example linear,
identifying |0 ≡ |‘ and |1 ≡ |“ , or circular identifying |+ ≡ | and |’ ≡ | . However in practice single
photon states are di¬cult to realize thus approximately single photon states are produced by faint laser pulses.
Finally one should detect these approximate single photon states. This is achieved using a variety of tech-
niques. One can choose between photomultipliers, avalanche-photodiodes, multichannel plates and supracon-
ducting Josephson junctions.
A typical experimental setup for quantum key distribution, with the technology described above is sawn in
Figure 4.3.

Basis 1
LD 1 "1"
PBS "0"
LD 2 Channel /2
BS "1"
LD 3
BS "0"
LD 4
Basis 2

Figure 4.3: Typical system for quantum cryptography using polarization coding (LD: laser diode, BS: beamsplit-
ter, F: neutral density ¬lter, PBS: polarizing beam splitter, »/2: half waveplate, APD: avalanche photodiode).

For more experimental details on the single photon quantum key distribution one should refer to [4, p.11-29].

4.2.2 Commercial quantum cryptography
Once the experimental setup of quantum key distribution has been performed, as discussed in subsection 4.2.1
and as sawn in Figures 4.3 and 4.2, one needs to follow the steps presented in subsection 4.1.4, in order to
achieve perfectly secure quantum cryptography. Of course these steps are nothing but an algorithm, which can
be analyzed and easily implemented into a program which can run on current technology computers. Moreover
special controlling devices are needed in order to instruct the laser diodes, the beam splitters and get the result
of the measurements from the avalanche photodiodes. Such hardware is already available in the market. One
should not forget that a public connection is needed, like for example the internet. For this reason there exist

patents [37], which can convert quantum cryptography from a laboratory experiment into a commercial product.
Such a patent is discussed bellow.
One can reconstruct the steps of subsection 4.1.4 into the following computer program:

1. Alice™s computer creates (4 + δ) n random bits, using an unknown to anybody else algorithm. (One can
also use quantum techniques as discussed in the third paragraph of subsection 4.1.1)
2. For each bit, Alice™s computer triggers with a controller one of the four laser diodes, as shown in Figure
4.2, according to a random bit string b.

3. This way the light beams are sent to Bob™s site into an agreed beforehand rate.
4. Alice™s computer has already implemented the classical version of CSS codes, and then it picks up randomly
a v k ∈ C1 .
5. Bob™s computer instructs with a controller the beam splitter sawn in Figure 4.2 in which basis to measure
the light beam. The selection should be according to a random algorithm. There should be a device
returning the result of the measurement of the avalanche photodiodes to Bob™s computer. Bob™s computer
announces the fact through an internet line to Alice™s computer.
6. Alice™s computer announces b.
7. Both computers discard those bits Bob™s measured in a basis other than b. With high probability, there
are at least 2n bits left; if not, abort the protocol. Alice™s computer decides randomly on a set of 2n bits
to continue to use, randomly selects n of these to check bits, and announces to Bob™s computer through
8. Both computers compare through internet their check bits. If more than t of these disagree, they abort
the protocol. Alice™s computer is left with the n bit string x, and Bob™s with x + .
9. Alice™s computer announces x ’ vk . Bob™s computer subtracts this from his result, correcting it with code
C1 to obtain vk .
10. Both computer calculate the coset of vk + C2 in C1 to obtain the key k.

Concluding it should be noted that what is very important about the above implementation, is that it is
completely automatic and almost no human intervention is needed. Thus users can just write their messages,
command the computers to send them securely and in the other side receive them. Automatic process is what
makes such a device successfully commercial.


The most important tools and results of classical and quantum information theory, obtained in the present
Individual Study Option, are summarized in the Figure S.1.

Information Theory
Classical Quantum
Shannon entropy Von Neumann entropy
H (X) = ’ x px log px S (ρ) = ’tr(ρ log ρ)

Distinguishability and accessible information
Letters always distinguishable Holevo bound
N = |X| H (X : Y ) ¤ S (ρ) ’ px S (ρx )
ρ= px (ρx )

Information-theoretic relations
Fano inequality Quantum Fano inequality
H (F (ρ, E)) + (1 ’ F (ρ, E)) log d2 ’ 1
H (pe) + pe log (|X| ’ 1) ≥ H (X|Y )
≥ S (ρ, E)
Mutual information Coherent information
H (X : Y ) = H (Y ) ’ H (Y |X) I (ρ, E) = S (E (ρ)) ’ S (ρ, E)
Data processing inequality Quantum data processing inequality
X ’Y ’Z ρ ’ E1 (ρ) ’ (E2 —¦ E1) (ρ)
H (X) ≥ H (X : Y ) ≥ H (X : Z) S (ρ) ≥ I (ρ, E1) ≥ I (ρ, E2 —¦ E1)

Noiseless channel coding
Shannon™s theorem Schumacher™s theorem
nbits = H (X) nqubits = S ( x px ρx )

Capacity of noisy channels for classical information
Shannon™s noisy coding theorem Holevo-Schumacher-Westmoreland
C (1) (E) = max S (ρ ) ’ px S (ρx )
C (N ) = max H (Y : X)
{pj ,ρj }
p(x) x
ρx = E (ρx ) , ρ = px ρx

Figure S.1: Summary of classical and quantum information theory.

The most important results concerning quantum cryptography, are summarized in Figure (S.2).

Quantum Cryptography
BB84 protocol, sends the following states
ψ a k bk
see (4.1) for de¬nitions

Privacy of a quantum channel E
P ≥ I (ρ, E)

Figure S.2: Summary of quantum cryptography.

Appendix A

Omitted proofs

A.1 Special diagonal transformation of normal matrices
In this appendix it is going to be demonstrated that for a d — d normal matrix A, there exists a set of unitary
(A) (A) (A)†
matrices Ui , such that i=1 Ui AUi =tr(A) I. Since A is a normal matrix, by spectral decomposition
such that U (A) AU (A)† is diagonal, and for this diagonal matrix there exists
theorem there exists a matrix U

a unitary transformation Vi”j AVi”j which interchanges the i-th diagonal element with the j-th.
To see this suppose B is a d — d dimensional diagonal matrix, then the following matrix
 δ kl , k or l = i, j

1, k = j and l = i
(Vi”j )kl ,
 1, k = i and l = j

0, else
can be used to exchange the i-th diagonal element with the j-th of B. Following the next steps V i”j is initially
proven to be unitary
d d
† †
Vi”j Vi”j = (Vi”j )kl Vi”j = (Vi”j )kl (Vi”j )nl
l=1 l=1
« « 
δ kl , k or l = i, j δ nl , n or l = i, j
¬ 1, k = j and l = i · ¬ 1, n = j and l = i ·
¬ ·¬ ·
=  1, k = i and l = j   1, n = i and l = j 
0, else 0, else
« 
δ kn, k or n = i, j
¬ 1, k = j and n = j ·
¬ ·
=  1, k = i and n = i  = δ kn = I.
0, else
The ability of Vi”j to exchange the diagonal elements of matrix B = diag {. . . , bi, . . . , bj , . . . } is exhibited by
d d d
† † †
Vi”j BVi”j = (Vi”j )kl Blm Vi”j = (Vi”j )kl bl Vi”j
mn nl
l=1 m=1 l=1
«  « 
δ kl , k or l = i, j δ nl , n or l = i, j
¬ 1, k = j and l = i · ¬ 1, n = j and l = i ·
¬ ·¬ ·
=  1, k = i and l = j  bl  1, n = i and l = j 
0, else 0, else
« 
bnδ kn, k = i, j or n = i, j
¬ ·
bi, k = j and n = j
¬ · = diag {. . . , bj , . . . , bi, . . . } .
=  
bj , k = i and n = i
0, else

V1”2V2”3 · · · Vd’1”d Vd”1 , which is unitary matrix as a multiplication of unitary
De¬ning now V23···d1

matrices, then V23···d1U AU (A)† V23···d1 is a diagonal matrix where the in the ¬rst diagonal place is the second

diagonal element of A, in the second diagonal place the third diagonal element of A, and so on until the
¬nal diagonal place where the ¬rst diagonal element of A stands. The next display visualizes the similarity
transformation V23···d1
®  ® 
a11 a22
   
a22 a33
   
   
.. ..
  V23···d1  
. .
’ .

   
a(d’2)(d’2) a(d’1)(d’1)
   
° » ° »
a(d’1)(d’1) add
add a11

Enumerating all the cyclic permutations of (1, 2, . . . , d) with a number i then the following unitary matrices
Vi U (A) . It is straightforward to verify that,
are de¬ned Ui
® 
a11 + a22 + . . . + add
 
d a22 + a33 + . . . + a11
 
(A) (A)†
Ui AUi = 
° »
add + a11 + . . . + a(d’1)(d’1)
= tr (A) I.

A.2 Projective measurements are equivalent to an addition of uni-
tary operations
Let P be a projector and Q I’P the complementary projector, in this appendix it will be sawn that there exist
† †
unitary matrices U1 , U2 and a probability p such that for all ρ, P ρP + QρQ = pU1ρU1 + (1 ’ p) U2 ρU2 . Choose

p 2 , U1 Q’P and U2 Q+P I. It is obvious that U1 U1 = (Q ’ P ) (Q ’ P ) = QQ+QP ’P Q’+P P =

Q + 0 + P = I, and U2 U2 = II = I. Now it is easy to check that

1 1 1 1
† †
(Q ’ P ) ρ (Q ’ P ) + (Q + P ) ρ (Q + P )
U1 ρU1 + U2 ρU2 =
2 2 2 2
1 1
(QρQ ’ QρP ’ P ρQ + P ρP ) + (QρQ + QρP + P ρQ + P ρP )
2 2
= P ρP + QρQ.

q.e.d. (Abbas Edalat contributed to this proof)

Appendix B

Distance measures of information

B.1 Classical information distance: Hamming
The Hamming distance of two strings, is de¬ned to be the number of places their bits are di¬erent. Assuming
a and b are the two n-bit strings, and ai and bi are their i-th bits, one can write
|ai ’ bi | .
d (a, b)

Very naturally, a Hamming sphere of center c and radius δ, is de¬ned as the set of stings which have distance
from c less or equal to δ

{s : d (c, s) ¤ δ} .
Sph (c, δ)

B.2 Quantum information distance: Fidelity
Fidelity is a measure of distance of two quantum states, de¬ned by

1 1
ρ 2 σρ 2 = max | ψ|φ | ,
F (ρ, σ) tr
|ψ ,|φ

and used to determine how well a quantum channel preserves information. To do this the following function
can be de¬ned

min F (|ψ , E (|ψ ψ|)) .
Fmin (E)

where the quantum channel is simulated via the quantum operation E, and the minimization is considered as
the worst case of a quantum signal. Another interesting de¬nition is
¯ pj F ρ j , E ρ j
F ,

named the ensemble average ¬delity. Finally it is important to quantify, how much entanglement between R
and Q, sent through a quantum channel E (a trace preserving operation), is preserved. This can be done by
entanglement ¬delity
|tr (ρEi)|2 ,
F (ρ, E) F (RQ, R Q ) = RQ| [(IR — E) (|RQ RQ|)] |RQ = (B.1)

where the primes are for the states after the application of E, and Ei are the operation elements of E.


[1] M. A. Nielsen and I. L. Chuang. Quantum computation and quantum information. Cambridge University
Press, Cambridge (2000).
[2] J. Preskill. Physics 229: Advanced Methods of Physics - Quantum Computation and Information. California
Institute of Technology (1998). URL: http://www.theory.caltech.edu/people/preskill/ph229/
[3] A. Steane. Quantum computing. arXive e-print (URL: http://www.arXiv.org) quant-ph/9708022 (sub-
mitted to Rev. Mod. Phys.) (1997).
[4] N. Gisin, G. Ribordy, W. Tittel and H. Zbinden. Quantum cryptography. arXive e-print (URL:
http://www.arXiv.org) quant-ph/0101098 (2001). (submitted to Rev. Mod. Phys.).
[5] C. Cohen-Tannoudji, B. Diu and F. Lalo¨. Quantum Mechanics, Vol. I. John Wiley and Sons (1977).
[6] A. M. Turing. On computable numbers, with an application to Entsheidungsproblem. Proc. Lond. Math.
Soc. 2, 42: 230 (1936).
[7] C. E. Shannon. A mathematical theory of communication. Bell System Tech. J., 27: 379-423, 623-656
[8] C. E. Shannon and A. D. Weaver. The Mathematical Theory of Communication. University of Illinois Press,
Urbana (1949).
[9] R. Landauer. Information is physical. Physics Today, 44(5): 22-29 (1991).
[10] Y. Manin. Computable and Uncomputable (in Russian). Sovetskoye Radio, Moscow (1980).
[11] P. Benio¬. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of
computers as represented by Turing machines. J. Stat. Phys., 21(5): 563-591 (1980).
[12] R. P. Feynman. Simulating physics with computers. Int. J. Theor. Phys., 21: 467 (1982).
[13] D. Deutsch. Quantum theory, the Church-Turing Principle and the universal quantum computer. Proc. R.
Soc. Lond. A, 400: 97 (1985).
[14] R. S. Ingarden and K. Urbanik. Information as a fundamental notion of statistical physics, Bull. Acad.
Polon. Sci., S´r. math. astr. phys., 9: 313-316 (1961).
[15] R. S. Ingarden and K. Urbanik. Quantum informational thermodynamics, Bull. Acad. Polon. Sci., S´r.
math. astr. phys., 21: 281-304 (1962).
[16] R. S. Ingarden. A simpli¬ed axiomatic de¬nition of information, Bull. Acad. Polon. Sci., S´r. math. astr.
phys., 11: 209-211 (1963).
[17] R. S. Ingarden. Information theory and thermodynamics of light. Part I. Foundations of information theory,
Fortchr. Phys., 12: 567-594 (1964).
[18] R. S. Ingarden. Simpli¬ed axioms for information without probability, Prace Mat., 9: 273-282 (1965).
[19] K. Urbanik. On the concept of information, Bull. Acad. Polon. Sci., S´r. math. astr. phys., 20: 887-890

[20] P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings, 35 th
Annual Symposium on Fundamentals of Computer Science, IEEE Press, Los Alamitos, CA (1994).
[21] P. W. Shor. Polynomial time algorithms for prime factorization and discrete logarithms on a quantum
computer. SIAM J. Comput., 26(5): 1484-1509 (1997).
[22] L. Grover. In Proc. 28 th Annual ACM Symposium on the theory of Computation, pages 212-219, ACM
Press, New York (1996).
[23] L. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79(2): 325
(1997). arXive e-print (URL: http://www.arXiv.org) quant-ph/9706033.
[24] D. Dieks. Communication by EPR devices. Phys. Lett. A, 92(6): 271-272 (1982).
[25] W. K. Wooters and W. H. Zurek. A single quantum cannot be cloned. Nature, 299: 802-803 (1982).
[26] A. S. Holevo. Statistical problems in quantum physics. In Gisiro Maruyama and Jurii V. Prokhorov, editors,
Proceedings of the Second Japan-USSR Symposium on Probability Theory, pages 104-119, Springer-Verlag,
Berlin (1973).
[27] B. Schumacher. Quantum coding. Phys. Rev. A, 51: 2738-2747 (1996).
[28] A. R. Calderbank and P. W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54: 1098
(1996). arXive e-print (URL: http://www.arXiv.org) quant-ph/9512032.
[29] A. Steane. Multiple particle interference and quantum error-correction. Proc. R. Soc. London A, 452:
2551-2576 (1996).
[30] S. Singh. The Code Book. Fourth Estate Limited, London (1999).
[31] R. L. Rivest, A. Shamir and L. M. Adleman. A method of obtaining digital signatures and public-key
cryptosystems. Comm. ACM, 21(2): 120-126 (1978).
[32] C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In
Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, pages 175-
179, IEEE, New York (1984). Bangalore, India, December 1984.
[33] C. H. Bennet, F. Bessette, G. Brassard, L. Salvail and J. Smolin. Experimental Quantum Cryptography.
J. Cryptology, 5: 3-28 (1992).
[34] D. S. Bethune and W. P. Risk. An autocompensating quantum key distribution system using polarization
splitting of light. In IQEC™98 Digest of Postdeadline Papers, pages QPD12-2, Optical Society of America,
Washington, DC (1998).
[35] Donald S. Bethune and William P. Risk. An autocompensating ¬ber-optic quantum cryptography system
based on polarization splitting of light. J. Quantum Electronics, 36(3): 100 (2000).
[36] A. Muller, H. Zbinden and N. Gisin. Quantum cryptography over 23 km in installed under-lake telecom
¬bre. Europhys. Lett., 33: 334-339 (1996).
[37] Y. Bakopoulos, Y. Vrettaros and A. Drigas. An Automatic Process for the Reliable and Secure Creation
and Distribution of Quantum Keys. Pending patent submitted to Industrial Property Organization O.B.Y.
Application number: 20010100204, dated: 19-4-2001, Athens (2001).



. 2
( 2)