<< . .

. 5
( : 7)



. . >>

|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


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

<< . .

. 5
( : 7)



. . >>