Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist
Подождите немного. Документ загружается.
20.7 Public-key cryptography 427
Following the standard, Bob must convert his message into 2-letter blocks and the
resulting blocks into decimal numbers, as follows:
Plaintext I l oveyou
PT-ASCII 1001001 1101100 1101111 1110110 1100101 1111001 1101111 1110101
Block 10 01 00 11 10 11 00 11 01 11 11 11 01 10 11 00 10 11 11 10 01 11 01 11 11 11 01 01
Decimal 9452 14 326 13 049 14 325
Alice has also chosen her public key, e. This public key must be co-prime with φ =
16 272. To be able to perform the encryption and decryption computations with a
pocket calculator (just for this example’s sake!), assume that Alice picked for her public
key e = 5, a number that represents the smallest eligible value (3 and 4 divide into
16 272). Going to the public directory or Alice’s website, Bob, like any other visitor,
may read, “Alice’s encryption instructions: please kindly use two-ASCII block encryption
modulo 16 571 as the standard; my public key is number 5.” No more instructions are
needed for Bob to proceed to encryption.
Bob then proceeds to encrypt his love declaration according to the formula c
i
=
m
e
i
mod N , where m
i
is the decimal block number i in Bob’s message sequence
m
1
m
2
m
3
m
4
. This gives
c
1
= m
5
1
mod 16 571 = 9452
5
mod 16 571 = 3704
c
2
= m
5
2
mod 16 571 = 14 326
5
mod 16 571 = 766
c
3
= m
5
3
mod 16 571 = 13 049
5
mod 16 571 = 475
c
4
= m
5
4
mod 16 571 = 14 325
5
mod 16 571 = 372.
(20.39)
In the above computations, it is absolutely essential that Bob make no truncation errors.
19
Having finished these computations, Bob emails his cipher message
c
1
c
2
c
3
c
4
= 3704 − 766 − 475 −372
to Alice; he may possibly include a few more words in order to identify himself (e.g.,
“Bob your classmate.”), but this is not the point of the endeavor.
Alice is then the only person who is able to decrypt Bob’s message. Her private key, d,is
defined by the formula ed = 1modφ,ord = e
−1
mod φ, namely d = 5
−1
mod 16 272.
Thus, Alice needs to find the inverse of 5 modulo 16 272. Since 16 272 is not the product
of two primes (16 272 = 16 × 9 × 113), she can’t use Euler’s theorem. Instead, she
19
For instance, with a pocket calculator the function 9452
5
yields 7.544293311 ×10
19
, but the last ten
digits are missing! To avoid truncations from the pocket calculator, the trick is to use the modulus-
arithmetic formula |m
5
|
N
=|m
2
|
N
×|m
2
|
N
×|m|
N
|
N
, in which the different terms and their suc-
cessive products (after reducing each one to their modulo N residue) fit in the calculator display
size.
428 Shor’s factorization algorithm
uses the extended Euclidian algorithm, which is described in Appendix T. It is not a
coincidence that, in this appendix, I use the above numbers to illustrate this algorithm
principle. The result is d = 6509. Such a big, 13-bit private key is the price for Alice
to pay for having chosen a public key as small as e = 5, but this does not affect the
generality of the demonstration. Alice then uses her private key to compute the following
blocks:
20
m
1
= c
6509
1
mod 16 571 = 3704
6509
mod 16 571 = 9452
m
2
= c
6509
2
mod 16 571 = 766
6509
mod 16 571 = 14 326
m
3
= c
6509
3
mod 16 571 = 475
6509
mod 16 571 = 13 049
m
4
= c
6509
4
mod 16 571 = 372
6509
mod 16 571 = 14 325.
(20.40)
Then Alice converts the decimal numbers m
1
m
2
m
3
m
4
into four 14-bit binary words,
splits each word into two 7-bit groups, and finally translates the resulting blocks into
ASCII, which yields and finally displays on Alice’s screen:
Decimal 9452 14 326 13 049 14 325
Binary 10 01 00 11 10 11 00 11 01 11 11 11 01 10 11 00 10 11 11 10 01 11 01 11 11 11 01 01
ASCII 1001001 1101100 1101111 1110110 1100101 1111001 1101111 1110101
Plaintext Il ov ey ou
Bob and Alice both having computers to perform RSA and a connection to the Inter-
net, the entire operation of encryption, transmission, and decryption of Bob’s message
(possibly completed with a few more statements!) took, in fact, milliseconds, as slowed
down by the IP routing protocol and other switching bottlenecks. This is the same
amount of time that after composing her reply, Alice will take to send Bob a PKC
message using Bob’s public key and Bob to retrieve into plaintext through his private
key.
20
One may wonder whether it is physically possible to compute numbers as monstrous as 100
6509
or 1000
6509
exactly with a personal computer or even worse, a pocket calculator. Indeed, if we make the conversion
through the formula a
x
= 10
x log a/ log 10
, we get for the first block 3704
6509
= 10
23 228.4794
≈ 3.01 ×
10
23 228
, namely a number with a whopping 23 229 digits! But surprisingly enough, such a computation can
be performed with a cheap pocket calculator! Here is how to proceed. Consider, for instance, the last cipher
block, 372
6509
. It takes a few minutes to calculate the following power series (modulo 16571): 372
2
= 5816,
372
4
= 4445, 372
8
= 5393, etc., up to 372
4096
= 8695. Thus, 372
6509
is the product 372
4096
× 372
1024
×
372
1024
× 372
256
× 372
64
× 372
32
× 372
8
× 372
4
× 372
1
. The result of each successive product must
be reduced to its residue so that no truncation occurs. The same procedure must be followed with the
other blocks 3704
6509
, 766
6509
and 475
6509
. This point being made, there is no reason not to develop a
simple computer program that can perform all these successive reduction tasks in a wink. With the present
example, we have chosen a block format (2
14
− 1 = 16 383) whose decimal size allows computing any
power of two, i.e., (2
14
− 1)
2
= 268 402 689, and its successive multiples, with a pocket calculator. But
with a personal computer, larger coding formats to encrypt four to eight ASCII or EBCDIC characters (i.e.,
2
32
− 1 = 4 294 967 295 or 2
64
− 1 ≈ 2 ×10
19
) are possible, provided the program is designed to handle
numbers up to (2
32
− 1)
2
or (2
64
− 1)
2
without truncation errors.
20.8 Exercises 429
As we have learnt, the key feature of the PKC algorithm is that the composite N = pq
is definitely too “big” to be readily factorized by any third party maliciously attempting
to intercept the communications between Alice and Bob. This is the reason why, so
long as no large-scale quantum computer able to factorize N is demonstrated, or no
state-grade computer is assigned to the task, Alice and Bob can exchange their thoughts,
safe from any third-party scrutiny.
20.8 Exercises
20.1 (M): Show that for any two integers x, N , satisfying x < N and any integer s,
the state
|
u
s
=
1
√
r
r−1
k=0
e
−
2iπks
r
|x
k
mod N
is an eigenstate of the operator defined by
U
x,N
|y=
|
xy mod N
with eigenvalue exp(2iπs/r ).
20.2 (M): Given the eigenstates
|
u
s
defined as
|
u
s
=
1
√
r
r−1
k=0
e
−
2iπks
r
|x
k
mod N ,
show that
1
√
r
r−1
s=0
|
u
s
=|1.
20.3 (M): Given the eigenstates
|
u
s
defined as
|
u
s
=
1
√
r
r−1
k=0
e
−
2iπks
r
|x
k
mod N ,
show that
1
√
r
r−1
s=0
e
2iπks
r
|u
s
=|x
k
mod N .
430 Shor’s factorization algorithm
20.4 (B): Show by induction that the two reals defined by
p
n
= a
n
p
n−1
+ p
n−2
q
n
= a
n
q
n−1
+q
n−2
for n ≥ 2, and
p
0
= a
0
, q
0
= 1, p
1
= 1 + a
0
a
1
, q
1
= a
1
for n = 0, 1, satisfy the relation
q
n
p
n−1
− p
n
q
n−1
= (−1)
n
.
21 Quantum information theory
This chapter sets the basis of quantum information theory (QIT). The central purpose
of QIT is to qualify the transmission of either classical or quantum information over
quantum channels. The starting point of the QIT description is von Neumann entropy,
S(ρ), which represents the quantum counterpart of Shannon’s classical entropy, H (X ).
Such a definition rests on that of the density operator (or density matrix) of a quantum
system, ρ, which plays a role similar to that of the random-events source X in Shannon’s
theory. As we shall see, there also exists an elegant and one-to-one correspondence
between the quantum and classical definitions of the entropy variants relative entropy,
joint entropy, conditional entropy, and mutual information. But such a similarity is
only apparent. Indeed, one becomes rapidly convinced from a systematic analysis of
the entropy’s additivity rules that fundamental differences separate the two worlds. The
classical notion of information correlation between two event sources for quantum states
shall be referred to as quantum entanglement. We then define a quantum communication
channel, which encodes and decodes classical information into or from quantum states.
The analysis shows that the mutual information H (X; Y ) between originator and recipient
in this communication channel cannot exceed a quantity χ, called the Holevo bound,
which itself satisfies χ ≤ H (X), where H (X ) is the entropy of the originator’s classical
information source. It is shown that the Holevo bound is maximal (χ = H (X)) when
the set of density operators used for coding the message have orthogonal supports or
eigenspaces.
21.1 Von Neumann entropy
The concept of source entropy, as introduced in Shannon’s classical information theory,
has been extensively described and developed in Chapters 4 to 6. To recall, a source
X of n random events labeled i (I = 1 ...n) and having associated probabilities p
i
(corresponding to the discrete probability distribution p), is characterized by an entropy
H(X ), defined by
H(X ) =−
n
i−1
p
i
log p
i
=
log
1
p
!
, (21.1)
432 Quantum information theory
with the continuity property x log x = 0 in the limit x → 0 and the logarithm conven-
tionally being in base two. Such entropy represents the average measurement of the
source’s information contents log(1/ p
i
) associated with each event. As we have seen in
Chapter 4, the entropy is maximum when all the source events are equiprobable, namely
when p
i
= 1/n, which yields H
max
≡ log n.
Consider now a quantum system. This system may exist in a quantum state |ψ,
which we shall assume here represents a statistical mixture of pure states |x
i
.
1
Such
pure states, which cannot be defined by any other mixtures of pure states, are orthogonal
to each other and have unit length, such that x
i
|x
j
=δ
ij
. The set of pure states {|x
i
} =
{|x
1
, |x
2
,...,|x
n
}, thus, defines an orthonormal basis for the n-dimensional space V
n
of all possible quantum states |ψ defining the system. Consistently, any state |ψof V
n
accepts a unique decomposition of the form
|ψ=x
1
|x
1
+x
2
|x
2
+···+x
n
|x
n
=
n
i=1
x
i
|x
i
, (21.2)
where x
i
(i = 1 ...n) are complex coordinates. We may choose to represent the quantum
system with a state |ψ of unit length, i.e., ψ|ψ =
i
|x
i
|
2
= 1, in which case the real
number p
i
=|x
i
|
2
, represents the probability of finding the state |ψ in the pure state
|x
i
. In the quantum world, the system in the quantum state |ψ, thus, plays the role of a
“random event” source and, naturally, the concepts of “information” and “entropy” may
be associated with such a system.
To establish such a connection, we need to use the concept of density operator (or
density matrix), which was introduced in Chapter 17. As we have learnt, the density
operator or matrix ρ is an alternative way to define a quantum system in a given state
|ψ.Formally,
ρ =
n
i=1
p
i
|x
i
x
i
|, (21.3)
where |x
i
x
i
| is the projector (or measurement) operator on the basis state |x
i
.Itis
clear that ρ|x
i
=p
i
|x
i
, which shows that |x
i
is an eigenstate of ρ with associated
eigenvalue p
i
. In the case where |ψ is a pure state, e.g., |ψ=|x
k
with p
i
= δ
ik
, and
only in such a case, the density operator is simply given by ρ =|ψψ|. As a general
definition, a pure state is a state that has 100% probability of being observed in a
quantum system, or which is exactly known. A given basis state (for instance |0 or |1
in a 2D space) may or may not be a pure state, according to whether this condition is
fulfilled or not (see more on this further on).
As we have also seen in Chapter 17, the matrix elements ρ
ij
of the density operator
satisfy ρ
ij
=x
i
|ρ|x
j
≡|x
i
|
2
δ
ij
= p
i
δ
ij
, showing that the matrix is diagonal in the
computational basis {|x
i
}, as expected from the fact that it is the basis of eigenstates.
1
The assumption according to which a system may be accurately or completely defined through a quantum
state |ψ, is equivalent to the assumption that the system is closed, meaning that it is neither coupled nor
entangled to any other unknown external system.
21.1 Von Neumann entropy 433
The matrix representation of ρ is, thus:
ρ =
p
1
0 ··· 0
0 p
2
···
.
.
.
.
.
.
.
.
.
.
.
.
0
0 ··· 0 p
n
. (21.4)
A key property is that the sum of diagonal elements, or the trace of the density matrix
satisfies tr(ρ) = 1, as for the definition of the probability distribution p ={p
i
}.As
shown in Chapter 17, the trace of any matrix or operator is independent of the choice
of the base representation {|x
i
}, or is invariant by unitary base transformation (see
Eq. (17.33)).
A useful property is that tr(ρ
2
) ≤ 1 applies for any density operator ρ, with equality
only for the case of pure states (ρ =|ψψ|), which is left as an exercise to establish.
We may note that such a property does not depend on the choice of basis. This is in spite
of the fact that a pure state may appear to be a mixed state in another basis! For instance,
given |0 assumed a pure state in basis {|0, |1}, the same state appears to be “mixed”
in the basis {|+, |−} according to the equality |0=(|+ + |−)/
√
2. But if |0 is a
pure state, the system has ρ =|00| for density operator. It is then an easy exercise to
show that ρ =|00| is actually transformed into ˜ρ = |++| in this new basis, which
illustrates that pure states remain pure states, independent of basis representation and
conserve their properties in any basis transformation. It is important, therefore, not to
confuse basis states (as a projection possibility for the system) and pure states (as the
only system state possibility).
Assume, next, an operator U corresponding to a physical observable (meaning that U
is Hermitian or has real, nonzero eigenvalues, see Chapter 17). Let us now take a close
look at the operator ρU , and its diagonal matrix elements in the basis {|x
i
}, namely
(ρU )
ii
=x
i
|ρU |x
i
.FromEq.((21.3)), we obtain
(ρU )
ii
=x
i
|ρU |x
i
=x
i
|
3
n
k=1
p
k
|x
k
x
k
|
4
U |x
i
=
n
k=1
p
k
x
i
|x
k
x
k
|U|x
i
=
n
k=1
p
k
δ
ik
x
k
|U|x
i
= p
i
x
i
|U|x
i
≡p
i
U
i
.
(21.5)
It is seen from this result that (ρU )
ii
represents the expectation value U
i
=
x
i
|U|x
i
of the observable U , should the system be measured in the state |x
i
(see
Eq. (17.57)), affected by the corresponding probability weight p
i
of such a measure-
ment event. The summation over all event possibilities, which is the trace of ρU , takes
434 Quantum information theory
the form
tr(ρU ) =
n
i=1
(ρU )
ii
=
n
i=1
p
i
x
i
|U|x
i
≡U
ψ
.
(21.6)
This result shows that given a physical system in state |ψwith associated density matrix
ρ, the expected value U
ψ
of the observable U is simply given by the trace tr(ρU).
Actually, this result enormously simplifies the perspective on quantum measurements
gained from Chapter 17. It will also be used to analyze the tricky issue of composite
quantum systems, as described later.
In Chapter 17, we have also established that for any operator U having a diagonal
matrix with nonnegative coefficients, it is possible to associate an operator U log U
with diagonal coefficients (U log U)
ii
= U
ii
log U
ii
. In the case U = ρ, we obtain the
matrix:
ρ log ρ =
p
1
log p
1
0 ··· 0
0 p
2
log p
2
···
.
.
.
.
.
.
.
.
.
.
.
.
0
0 ··· 0 p
n
log p
n
. (21.7)
From the above definition, the trace of ρ log ρ, with a minus sign, is given by:
S(ρ) =−tr(ρ log ρ)
=−
n
i=1
p
i
log p
i
.
(21.8)
A comparison between Eqs. (21.8) and (21.1) shows that S(ρ) =−tr(ρ log ρ) is strictly
analogous to Shannon’s classical entropy, H(X ), with X ={i }
i=1...n
being a random-
event source characterized by the probability distribution {p
i
}. The key difference
between S(ρ) and H (X) is that, in the former, the source is a quantum system, char-
acterized not by a probability distribution, like the latter, but by a density operator ρ.
We shall refer to S(ρ)asvon Neumann entropy. The von Neumann (VN) entropy, thus,
represents a quantum measure of the information contents in the quantum system or state
under consideration, referred to as a quantum source ρ. Since the VN entropy measure
is always equivalent to that of a classical source, H (X), it is nonnegative, or S(ρ) ≥ 0
always applies.
In Chapter 17, it was shown that the trace of any operator is independent of the
basis representation. Thus, the density operator transformation under change of basis,
i.e., ρ → ˜ρ = TρT
+
where T is a unitary operator, is of no effect on the VN entropy.
Formally:
S(˜ρ) = S(TρT
+
) = S(ρ). (21.9)
21.1 Von Neumann entropy 435
This result shows that quantum information, as defined by the VN entropy, represents an
incompressible feature in quantum systems, as is also the case for classical information
in random-event sources, as defined by Shannon entropy. What is the quantum infor-
mation contained in a qubit? The answer is straightforward. Assume a qubit of general
definition
|q=α|0+β|1, (21.10)
where |0, |1are two pure states in the 2D quantum space V
2
, and p =|α|
2
= 1 −|β|
2
.
From the definitions in Eqs. (21.3) and (21.4),wehave
ρ =|α|
2
|00|+|β|
2
|11|=p|00|+(1 − p)|11|, (21.11)
ρ =
|α|
2
0
0 |β|
2
=
p 0
01− p
, (21.12)
and
S(ρ) =−(|α|
2
log |α|
2
+|β|
2
log |β|
2
)
=−p log p − (1 − p)log(1− p) ≡ f ( p).
(21.13)
In the result in Eq. (21.13), we recognize the Shannon entropy of a two-event source
X ={0, 1}, corresponding to the two possible “states” of a classical bit (see Eqs. (4.13)
and (4.14)). The average qubit information is, thus, equivalent to that of two classical
bits, the amount depending on the weights p
0
, p
1
in the state mixture. As described in
Chapter 4, the function f (p) has a maximum of unity for p = 1/2, corresponding to
|α|=|β|=1/
√
2 (phases being arbitrary) or a uniform distribution p
0
= p
1
= 1/2,
and for the VN entropy, S
max
(ρ) ≡ log 2 = 1. In this case, the quantum information
amounts to exactly one classical bit. The minimum of f (p) is zero, which is reached
either when p
0
= 1, p
1
= 0 or when p
0
= 0, p
1
= 1, meaning that the qubit is in a pure
state, i.e., |q=|0 or |q=|1,givingS
max
(ρ) ≡ 0. In this case, there is no quantum
information in the system, as there is no information in a single, deterministic classical
bit.
It is clear that the VN entropy of an n-qubit (or quNit) in the quantum space V
n
always
has the maximum S
max
(ρ) ≡ log n when the system is in the most homogeneous state
superposition with a uniform probability distribution p
i
= 1/n, hence corresponding to
maximum quantum information. In the general case, we have 0 ≤ S(ρ) ≤ log n.
It is a generally possible that the state |ψ can be a mixture of nonorthogonal states.
In this case, the corresponding density matrix ρ is nondiagonal. How, then, can we
determine the VN entropy of the system? The answer is that we know it is possible to
express the density operator in the computational basis of eigenstates, where the matrix
is diagonal. Given the eigenvalues λ
i
(i = 1 ...n) corresponding to the eigenstates
{|λ
i
}
i=1...n
, the VN entropy, thus, takes the form
S(ρ) =−
n
i=1
λ
i
log λ
i
. (21.14)
436 Quantum information theory
As an illustration (see also the exercises), assume the following density operator:
ρ =
2
3
|00|+
1
3
|−−|
=
2
3
|00|+
1
3
|0−|1
√
2
0|−1|
√
2
.
(21.15)
In the computational basis {|0, |1}, it is easily established that the corresponding
matrix is
ρ =
0|ρ|00|ρ|1
1|ρ|01|ρ|1
≡
1
6
5 −1
−11
. (21.16)
As recalled in Chapter 17, the eigenvalues λ
i
are given by the solutions λ of the char-
acteristic equation, i.e., det(ρ − λI ) = 0. By definition, each eigenvalue corresponds to
an eigenvector |λ
i
,forwhichρ|λ
i
=λ
i
|λ
i
, with {|λ
i
} constituting an orthonormal
basis. In the example, the solutions of the characteristic equation are easily found to be
λ = (3 ±
√
5)/6, which, in the eigenstate-basis representation {|λ
i
}, yields the diagonal
density matrix:
2
˜ρ =
λ
1
|ρ|λ
1
0
0 λ
2
|ρ|λ
2
≡
1
6
3 +
√
50
03−
√
5
.
(21.17)
We can then determine the VN entropy of the associated quantum system, which is in
the state now represented as |ψ=
√
λ
1
|λ
1
+
√
λ
2
|λ
2
, as follows:
S(˜ρ) =−tr( ˜ρ log ˜ρ)
=−
3
3 +
√
5
6
log
3 +
√
5
6
+
3 −
√
5
6
log
3 −
√
5
6
4
≡ 0.55004.
(21.18)
This result concludes that this system contains quantum information amounting to about
0.55 classical bits, as measured when using the eigenstate basis {|λ
i
}.
The connection between classical and quantum information, as measured by Shannon
and von Neumann entropies, appears to be elegant and complete, almost to the extent
of hiding the fundamental differences between their respective worlds. As the follow-
ing sections will show, however, it would be largely erroneous to conclude from this
connection that QIT brings nothing new to information theory.
2
It is easily checked that the same density operator ˜ρ is obtained by starting from the computational basis
{|+, |−} instead of {|0, |1}.