Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist
Подождите немного. Документ загружается.
Modular arithmetic and Euler’s theorem 657
otherwise). The following are basic examples:
(3 + 4) mod 6 = 7mod6= 1
(8 + 7) mod 15 = 15 mod 15 = 0
(7 − 4) mod 4 = 3mod4= 3
(2 × 3) mod 4 = 6mod4= 2
(7 × 9) mod 11 = 63 mod 11 = 8.
(T5)
In modular arithmetic, addition and multiplication are commutative, associative, and
distributive operations, meaning the following properties:
(a ± b)modm = (a mod m) ± (b mod m)modm, (T6)
(a × b)modm = (a mod m) × (b mod m)modm, (T7)
[a × (b + c)] mod m = (a × b)modm + (a × c)modm)modm. (T8)
Here are two other obvious or less trivial properties (k = integer):
(−a)modm = (m − a)modm = [(m − 1) ×a]modm, (T9)
(k × m)modm = 0, (T10)
(k × a)mod(k × m) = k × (a mod m). (T11)
While addition and multiplication are straightforward in modular arithmetic, division is
not. For instance, what is the residue r as defined through r = (11/5) mod 3? In modular
arithmetic, r should be the number that satisfies 5 ×r = 11 mod
3
= 2. The only solution
to this equation is r = 1, since 5 ×1mod3= 5mod3= 2. We, thus, see that |11/5|
3
=
1, which is not at all intuitive. One can also define the number (11/5) mod 3 as the
product (11 ×1/5) mod 3 or, equivalently, (11 mod 3) ×(1/5 mod 3) = 2 × (1/5mod
3) mod 3. According to the same procedure, we find that |1/5|
3
= 2, since 5 ×2 =
10 mod
3
= 1. We, thus, obtain 2 ×(1/5 mod 3) mod 3 = 2 ×2mod3= 4mod3=
1 = (11/5) mod 3, which is consistent with the previous definition of division. Since
inverses can be defined in modular arithmetic, there is no need to use the division
operation. However, a restriction applies to the relation between the number to be
inverted and the modulus: they should be co-prime, meaning that they should have one
as their greatest common divider (see further).
The conversion between x and its residue r (modulo m) is called modular reduction.
Such a reduction operation corresponds to a one-way function. This term refers to the fact
that the correspondence that is established is not reversible, since there is an infinity of
numbers with the same residue. Powers and exponentials of the type y = x
p
and y = a
x
(a, p = integers) are also one-way functions, since the result y is associated with an
infinity of possible values x. Here is an important property concerning the commutation
of exponents, which is the same as in ordinary arithmetic, and which we will have the
opportunity to exploit:
(a
p
mod m)
q
mod m = (a
q
mod m)
p
mod m = a
pq
mod m. (T12)
658 Appendix T
Having introduced modular arithmetic basics, I can describe two fundamental theorems
that have been derived by Fermat and Euler.
Two numbers are said to be relatively prime,orco-prime to each other, if they do not
divide each other, or if their greatest common divider (GCD) is unity. For instance, (3,4),
(2,9), and (5,12) are co-prime. Clearly, two prime numbers are co-prime. Primes and
co-primes play a central role in modular arithmetic, as the Fermat and Euler theorems
and applications illustrate.
Fermat’s theorem states that if m is prime and (a, m) are co-prime, then
a
m−1
mod m = 1, (T13)
which can be put into the equivalent form: a
m
mod m = a.Thus,wehavea mod 2 = 1
or a
2
mod 3 = 1 for any a that is prime with number two or number three, and so on
with any prime modulus, for instance 11
23−1
mod 23 = 1. We see that as a first benefit,
Fermat’s theorem makes it possible to considerably simplify calculations in modular
arithmetic.
Euler’s theorem (named after the Swiss mathematician) states that if p and q are two
primes and N = pq is their product, then we have for any integer a which is prime
with n:
a
(p−1)(q−1)
mod N = 1. (T14)
The factor ( p − 1)(q − 1) with pq = N is also called φ(N ). A consequence of Euler’s
theorem is that the inverse 1/a is readily defined as
1
a
= a
−1
= a
φ(n)−1
mod N . (T15)
For instance, what is the inverse of 5 modulo 21? We have 21 = 3 ×7, so φ(21) = (3 −
1) × (7 −1) = 12 and 1/5 = 5
12−1
mod 21 =48 828 125 mod 21 =17. Thus, |1/5|
21
=
17, which is readily verified as (17 ×5) mod 21 = 85 mod 21 = 1. We see that the
calculation of an inverse through Euler’s theorem is quite straightforward, compared
with the method previously described. But the requirement is that the modulus N is
defined by the product of two primes, which represents a special or fortuitous case.
It is important to note that if (a, N )arenot co-prime to each other, the inverse a
−1
does not exist. If the two are co-primes but Euler’s theorem cannot apply, the inverse a
−1
can be found using the extended Euclidian algorithm. Here, I shall explain this algorithm
through two representative examples: for instance, find the inverse of 7 in modulus 39,
and the inverse of 5 in modulus 16 272, i.e., the values of 7
−1
mod 39 and 5
−1
mod
16 272. Taking the first example, the algorithm proceeds as shown in Table T1, with the
steps as numbered in the first column.
In steps 1 and 2, we fill out the table as shown. We first divide 39 by 7, to find that
the integer part of the result is [39/7] = 5. In step 3, we multiply line 2 by 5, and in
step 4 we subtract the result of line 3 from that of line 1. This completes the first round.
Consider next the ratio 7/4, whose integer part is [7/4] = 1. In step 5, we multiply the
results of line 4 by 1, and in step 6, we subtract the result of line 5 from that of line 2.
This completes the second round. Consider next the ratio 4/3, whose integer part is
Modular arithmetic and Euler’s theorem 659
Table T1 Extended Euclidian algorithm to find 7
−1
mod 39.
139 39
27 1
35× 7 = 35 5 × 1 = 5
439− 35 = 439− 5 = 34
51× 4 = 41× 34 = 34
67–4= 3 1–34=−33
71× 3 = 31× (−33) =−33
84–3= 134− (−33) = 67 = 28
Table T2 Extended Euclidian algorithm to find 5
−1
mod 16 272.
1 16 272 16 272
25 1
3 3 254 × 5 = 16 270 3 254 × 1 = 3 254
4 16 272 – 16 270 = 2 16 272 − 3254 = 13 018
52× 2 = 42× 13 018 = 26 036
65− 4 = 11− 26 036 =−26 035
[4/3] = 1. In step 7, we multiply the results of line 6 by 1, and in step 8, we subtract
the result of line 7 from that of line 4. If we have obtained 1 in the first column (line
8), we have finished. When positive, the number to the right is the inverse we have been
looking for. Here, we find that the inverse of 7 is 28. Proof: 7 × 28 = 196 = 1 (modulo
39).
Consider next the example in Table T2, which concerns the search of 5
−1
mod
16 272.
In steps 1 and 2, we fill out the table as shown. We first divide 8064 by 7, to find
that the integer part of the result is [16 272/5] = 3254. In step 3, we multiply line 2 by
1612, and in step 4 we subtract the result of line 3 from that of line 1. This completes
the first round. Consider next the ratio 5/2, whose integer part is [5/2] = 2. In step 5,
we multiply the results of line 4 by 2, and in step 6, we subtract the result of line 5 from
that of line 2. This completes the search, since we have obtained 1 in the first column
(line 6). However, the number in the right column, b =−26 035 is negative. In this case,
the inverse is the complement km + b, namely 5
−1
= 2 × 16 272 – 26 035 = 6509.
The proof is that 5 × 6509 = 32 545 = (2 × 16 272) + 1 = 1 (modulo 16 272). This
numerical value will be used in the main text concerning my numerical illustration of
the PKC algorithm.
Appendix U (Chapter 21) Klein’s
inequality
This appendix provides a basic demonstration of Klein’s inequality, according to which
the relative entropy S(ρσ ) between two quantum systems characterized by the density
operators ρ and σ is nonnegative.
Assume the following eigenstate-basis decompositions for the density operators:
ρ =
i
p
i
|ii |
σ =
k
p
k
|kk|.
(U1)
Substituting the first of the above definitions into the relative entropy, we obtain
S(ρσ ) = tr(ρ log ρ) −tr(ρ log σ )
=
i
i|ρ log ρ|i −
i
i|ρ log σ |i
=
i
p
i
log p
i
−
i
i|ρ log σ |i.
(U2)
The last term in the right-hand side can then be developed using the eigenstate property
i|ρ =i |p
i
, which gives i|ρ log σ |i=p
i
i|log σ |i. Furthermore, since σ is diagonal
we have, from the second definition in Eq. (U1), log σ =
k
log q
k
|kk|and, therefore,
i|log σ |i=i|
3
k
log q
k
|kk|
4
|i
=
k
i|kk|ilog q
k
=
k
|i|k|
2
log q
k
.
(U3)
Substituting these results into Eq. (U2), we obtain
S(ρσ ) =
i
p
i
log p
i
−
i
p
i
k
|i|k|
2
log q
k
=
i
p
i
3
log p
i
−
k
|i|k|
2
log q
k
4
.
(U4)
Klein’s inequality 661
Then we use the property according to which log y≤logy for any function y or,
in the discrete case,
x
k
log y
k
≤ log
x
k
y
k
, where {x
k
} is a probability distribution.
Such a property stems from the concavity of the logarithm function (see Exercise 5.10).
Letting x
k
(i) =|i|k|
2
, we note that x
k
(i) ≥ 0 and
k
x
k
(i) = 1, which makes x
k
(i)a
probability distribution. Thus, we have
k
|i|k|
2
log q
k
≤ log
3
k
|i|k|
2
q
k
4
≡ log r
i
.
(U5)
Combining, then, Eqs. (U4) and (U5) we finally obtain
S(ρσ ) ≥
i
p
i
(log p
i
− log r
i
)
=
i
p
i
log
p
i
r
i
≥ 0.
(U6)
In the term
p
i
log( p
i
/r
i
), we recognize the classical definition of relative entropy
or the Kullback–Leibler distance D( pr) between two discrete probability distributions
{p
i
}, {r
i
}. As we have seen in Chapter 5, D(pr) is nonnegative, which justifies the last
inequality introduced in the right-hand side in Eq. (U6). The above, thus, proves Klein’s
inequality or the nonnegativity of S(ρσ ).
Appendix V (Chapter 21) Schmidt
decomposition of joint pure states
This appendix describes the so-called Schmidt decomposition. Such a decomposition
applies to the case of a composite system made of two subsystems A, B, which is in a
pure joint state |ψ, namely, |ψ=|ψ
A
⊗|ψ
B
≡|ψ
A
|ψ
B
≡|ψ
A
ψ
B
. According to
Schmidt decomposition, the joint state can be expressed in the form
|ψ=
i
x
i
|i
A
|i
B
, (V1)
where x
i
(i = 1 ...n) are nonnegative numbers, called Schmidt coefficients, satisfying
the property
i
x
2
i
= 1, and where {|i
A
}, {|i
B
} are some orthonormal basis for the
subsystems A, B.
The proof that the decomposition in Eq. (V1) exists and is unique proceeds as follows.
Let {|j} and {|k} be two orthonormal bases for the subsystems A and B, respectively.
The joint state can most generally be defined through the expansion
|ψ=
jk
ω
jk
|j|k, (V2)
where ω
jk
are the complex coefficients of some matrix . According to the principle of
singular value decomposition,
1
it is possible to express in the form = UDV, where
U, V are unitary matrices, and D is a diagonal matrix having nonnegative elements.
The diagonal elements x
i
= d
ii
of D are called the singular values of . The matrix
elements of , thus, decompose as follows
ω
jk
=
i
u
ji
d
ii
v
ik
=
i
x
i
u
ji
v
ik
, (V3)
which we substitute into Eq. (V2) to obtain:
|ψ=
ijk
x
i
u
ji
v
ik
|j|k
=
i
x
i
j
u
ji
|j
k
v
ik
|k
.
(V4)
1
See, for instance: http://mathworld.wolfram.com/SingularValueDecomposition.html; http://en.wikipedia.
org/wiki/Singular_value_decomposition.
Schmidt decomposition of joint pure states 663
We then introduce the definitions
|i
A
=
j
u
ji
|j
|i
B
=
k
v
ik
|k.
(V5)
The states |i
A
, |i
B
form orthonormal sets, because of the unitarity of the matrices U, V .
Considering |i
A
, for instance, we have
l
A
|i
A
=
3
k
u
∗
kl
k|
4
j
u
ji
|j
=
jk
u
∗
kl
u
ji
k|j
=
jk
u
∗
kl
u
ji
δ
kj
=
j
u
∗
jl
u
ji
= (U
+
U )
li
= I
li
= δ
li
,
(V6)
which proves the orthonormality of the set {|i
A
}, and likewise for {|i
B
}. Substituting
Eq. (V5) into Eq. (V4) yields Eq. (V1), i.e., the Schmidt decomposition of |ψ. Because
|ψ is a pure state, we also have ψ|ψ=
i
x
2
i
= 1, which completes the proof.
Here are two examples of Schmidt decomposition according to Eq. (V1):
|ψ=
1
√
2
(|10+|01)
≡ 0 ×|0
A
|0
B
+
1
√
2
|0
A
|1
B
+
1
√
2
|1
A
|0
B
+0 ×|1
A
|1
B
(V7)
and
|ψ=
1
√
2
(|00−|11)
≡
1
√
2
|0
A
|
˜
0
B
+0 ×|0
A
|
˜
1
B
+0 ×|1
A
|
˜
0
B
+
1
√
2
|1
A
|
˜
1
B
,
(V8)
with the other choice of orthonormal basis {|
˜
0
B
, |
˜
1
B
} = {|0
B
, −|1
B
} for the subsys-
tem B.
Appendix W (Chapter 21) State
purification
This appendix describes the operation of state purification. The operation consists of
associating a pure joint state |ψ
AR
with a system A that is in a mixed state |ψ
A
.The
benefit of the operation is the possibility of deriving the density operator ρ
A
directly from
the partial trace of the pure-state density operator ρ
AR
=|ψ
AR
ψ
AR
|.Thetermstate
purification, thus, means expanding the system A in mixed state |ψ
A
into a composite
system AR, whose joint state |ψ
AR
is a pure state. The state |ψ
AR
is referred to as the
purification of |ψ
A
, or the purification of ρ
A
.
The principle of state purification is relatively simple to explain. First, assume for the
mixed state |ψ
A
the following decomposition over the orthonormal basis {|i
A
}:
|ψ
A
=
i
√
p
i
|i
A
. (W1)
Second, assume a reference system R of same dimension of A and same basis {|i
R
},
meaning i
R
|j
A
=δ
ij
. Then define the joint state |ψ
AR
:
|ψ
AR
=
i
√
p
i
|i
A
|i
R
. (W2)
The above-defined joint state |ψ
AR
is a pure state, because it cannot be defined by any
other possible state |φ
AR
of AR. We can show this by using the most general definition
for |φ
AR
:
|φ
AR
=
i
j=i
α
ij
|i
A
|j
R
. (W3)
Then we have
ψ
AR
|φ
AR
=
3
k
√
p
k
k
A
|k
R
|
4
i
j=i
α
ij
|i
A
|j
R
=
k
i
j=i
α
ij
k
A
|i
A
k
R
|j
R
=
k
i
j=i
α
ij
δ
ki
δ
kj
=
i
j=i
α
ij
δ
ij
≡ 0,
(W4)
which establishes that |ψ
AR
, |φ
AR
are, indeed, orthogonal.
State purification 665
Since |ψ
AR
is a pure state, the density operator of the composite system AR is
ρ
AR
=|ψ
AR
ψ
AR
|
≡
ij
√
p
i
p
j
|i
A
j
A
|⊗|i
R
j
R
|.
(W5)
As the next step, we execute the partial tracing over R according to the generic definition
in Eq. (21.25), which here reads (B = R):
tr
R
U = tr
R
(|i
A
j
A
|⊗|k
R
l
R
|)
≡|i
A
j
A
|×tr(|k
R
l
R
|),
(W6)
hence,
tr
R
(ρ
AR
) = tr
R
ij
√
p
i
p
j
|i
A
j
A
|⊗|i
R
j
R
|
=
ij
√
p
i
p
j
tr(|i
A
j
A
|⊗|i
R
j
R
|)
=
ij
√
p
i
p
j
|i
A
j
A
|×tr(|i
R
j
R
|)
=
ij
√
p
i
p
j
|i
A
j
A
|×δ
ij
=
i
p
i
|i
A
i
A
|
≡ ρ
A
.
(W7)
This result shows that the partial trace over R of the composite system AR yields the
density operator ρ
A
, which corresponds to the definition of state purification.
Appendix X (Chapter 21) Holevo bound
In this appendix, I formally establish that the mutual information H(X ; Y ) in a quantum
communication channel is bounded by a maximum, χ, referred to as Holevo bound, and
defined by
H(X ; Y ) ≤ S(ρ) −
x
p
x
S(ρ
x
)
= χ
(X1)
where ρ =
x
p
x
ρ
x
=ρ. In the above definition, ρ
x
represents the density matrix of
any quantum state used for the transmission, as selected from an “alphabet” X according
to some probability distribution {p
x
}. The retrieval of information is made by POVM
measurements, which define a source of random outcomes Y of size n.
The formal proof of the Holevo bound requires one to assume three quantum systems,
P, Q, R. The first system, P, corresponds to the quantum source used by the originator
to “prepare” the states ρ
x
, namely with density operator:
ρ
P
=
x
p
x
|xx|, (X2)
with {|x}being the orthonormal basis where ρ is diagonal. The composite system PQ,
as described by the tensor product
ρ
PQ
=
x
p
x
|xx|⊗ρ
x
, (X3)
represents the joint state of the system after the preparation of the states ρ
x
, based on
the definition of partial tracing, i.e.,
tr
P
(ρ
PQ
) = tr
P
3
x
p
x
|xx|⊗ρ
x
4
=
x
tr
P
(p
x
|xx|⊗ρ
x
)
=
x
tr( p
x
|xx|) ×ρ
x
=
x
p
x
ρ
x
≡ ρ,
(X4)