Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist
Подождите немного. Документ загружается.
Holevo bound 667
tr
Q
(ρ
PQ
) = tr
Q
3
x
p
x
|xx|⊗ρ
x
4
=
x
tr
Q
(
p
x
|xx|⊗ρ
x
)
=
x
p
x
|xx|tr
(
ρ
x
)
=
x
p
x
|xx|
≡ ρ
P
.
(X5)
The third system, R, is a fictitious auxiliary system representing, together with Q,the
measuring apparatus of the recipient. We assume that before measurement, R is in the
pure state |0, corresponding to ρ
R
=|00|. Thus, the initial state of the whole system
(or quantum communication channel) is described by the density operator
ρ
PQR
=
x
p
x
|xx|⊗ρ
x
⊗|00|. (X6)
Next, we need to define the effect of the recipient’s POVM measurement. As seen in
Chapter 17, the POVM measurement is defined as a set of Hermitian operators, {E
y
},
which satisfy the completeness relation (Eq. (17.62)), and which correspond to a set of
measurement operators, {M
y
=
E
y
}, satisfying the property M
y
M
+
y
= E
y
. Applying
any single measurement labeled y to a system in state ρ is a quantum operation that
leaves the system in the post-measurement state ρ
= M
y
ρ M
+
y
. Here, we shall use a
somewhat different quantum operation. It consists of effecting the POVM measurement
in system Q and storing the result in system R. The corresponding quantum operation
leaves the composite system QR in the post-measurement state
ρ
QR
=
y
M
y
ρ
x
M
+
y
⊗|yy|. (X7)
This definition is justified by the partial tracing over system Q to yield, for system R:
ρ
R
= tr
Q
(ρ
QR
)
= tr
Q
3
y
M
y
ρ
x
M
+
y
⊗|yy|
4
=
y
tr
Q
M
y
ρ
x
M
+
y
⊗|yy|
=
y
tr
M
y
ρ
x
M
+
y
×|yy|
=
y
tr
M
+
y
M
y
ρ
x
×|yy|
=
y
tr
E
y
ρ
x
×|yy|
≡
y
E
y
x
|yy|,
(X8)
668 Appendix X
where E
y
x
= tr(E
y
ρ
x
) represents the expectation value of the measurement E
y
, given
the input state ρ
x
. Note that tr(ρ
R
) = 1. To get the actual final state of R we need to
effect the normalization
˜ρ
R
=
tr
Q
(ρ
QR
)
tr[tr
Q
(ρ
QR
)]
≡
y
E
y
x
|yy|
y
E
y
x
,
(X9)
or, in the matrix form in base {|y}:
˜ρ
R
=
1
y
E
y
x
E
1
x
0000
0 E
2
x
0 ··· 0
00
.
.
.
.
.
.
0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
00··· 0 E
n
x
. (X10)
The coefficients in this density-matrix definition, thus, provide the conditional probabil-
ity of obtaining E
y
x
as the outcome of the measurement, given the input state ρ
x
.This
justifies the definition in Eq. (X7) of the proposed quantum operation (not normalized,
for simplicity).
In summary, our measurement operation leaves the composite system PQR in the
state
ρ
PQR
=
xy
p
x
|xx|⊗M
y
ρ
x
M
+
y
⊗|yy|. (X11)
We may now trace out the system over Q to obtain ρ
PR
and, hence, to be able to derive
later on the mutual information S(ρ
P
; ρ
R
) existing after the measurement. This tracing
gives
ρ
PR
= tr
Q
3
xy
p
x
|xx|⊗M
y
ρ
x
M
+
y
⊗|yy|
4
=
xy
p
x
|xx|×tr(M
y
ρ
x
M
+
y
) ⊗|yy|
=
xy
p
x
|xx|×tr(E
y
ρ
x
) ⊗|yy|.
(X12)
In the above, we may substitute tr(E
y
ρ
x
) = p(y|x)asaconditional probability, because
{E
y
} form a POVM operator set satisfying the completeness relation. Using Bayes’s
theorem (see Chapter 1), we havep(x, y) = p(y|x)p
x
for the joint probability, which,
Holevo bound 669
from Eq. (X12), yields:
ρ
PR
=
xy
p
x
p(y|x)|xx|
P
⊗|yy|
R
=
xy
p(x, y)|xx|
P
⊗|yy|
R
.
(X13)
Because of the above tensor-operator form, we might as well express the post-
measurement joint state in the tensor-state form:
|ψ
PR
=
xy
p(x, y)|xy. (X14)
It is clear, then, that the joint VN entropy S
(ρ
P
,ρ
R
) and mutual information S
(ρ
P
; ρ
R
)
of the post-measurement system are simply given by
S
(ρ
P
,ρ
R
) ≡ H (X, Y )
S
(ρ
P
; ρ
R
) ≡ H (X; Y ),
(X15)
just as in a classical communication channel with an originator source X and a recipient
source Y , correlated together with joint probability p(x, y).
The next and final step is to relate the post-measurement mutual information
S
(ρ
P
; ρ
R
) to that characterizing the system before the measurement, which we call
S(ρ
P
; ρ
Q
). To this effect, we shall first assume the following inequality (the proof being
provided at the end of this appendix):
S
(ρ
P
; ρ
R
) ≤ S(ρ
P
; ρ
Q
). (X16)
This property states that in quantum channels, mutual information may not necessarily
be conserved, neither be increased by measurement. We obtain S(ρ
P
; ρ
Q
)as:
S(ρ
P
; ρ
Q
) = S(ρ
P
) + S(ρ
Q
) − S(ρ
P
,ρ
Q
), (X17)
with (from Eqs. (X2) and (X3)):
S(ρ
P
) = S
3
x
p
x
|xx|
4
≡ H (X)
S(ρ
Q
) = S
&
tr
P
3
x
p
x
|xx|⊗ρ
x
4'
= S
&
x
p
x
|xx|×tr
(
ρ
x
)
'
(X18)
1
= S
3
x
p
x
|xx|
4
≡ S(ρ)
S(ρ
P
,ρ
Q
) = S
3
x
p
x
|xx|⊗ρ
x
4
≡ H (X) +
x
p
x
S(ρ
x
).
1
To obtain this result, define R
x
=|x x|⊗ρ
x
. We have, then,
S
3
x
p
x
|x x|⊗ρ
x
4
= S
3
x
p
x
R
x
4
.
670 Appendix X
From Eqs. (X17) and (X18), we obtain
S(ρ
P
; ρ
Q
) = S(ρ) −
x
p
x
S(ρ
x
). (X19)
Combining the results in Eqs. (X15), (X16), and (X19), we finally obtain
H(X ; Y ) ≤ S(ρ) −
x
p
x
S(ρ
x
) = χ, (X20)
which establishes the proof of the Holevo bound stated in Eq. (X1).
To reach such a conclusion, the inequality in Eq. (X16), namely, S
(ρ
P
; ρ
R
) ≤
S(ρ
P
; ρ
Q
), was made as a key assumption. The following discussion, destined for the
demanding, provides the key elements proving such an assumption. This proof is, how-
ever, not complete, because it eventually rests on an additional property, referred to as
strong subadditivity. Proving strong subadditivity requires no less than two theorems, of
which the proofs are quite mathematically involved! Therefore, and for the purpose of
these chapters, such a property shall be taken here as a given postulate.
Proof of the inequality in Eq. (X16), with discussion
In the following, I simplify the notation by setting S(ρ
A
) ≡ S(A), S(ρ
A
; ρ
B
) ≡ S(A; B),
and the like for A, B = P, Q, R. By definition, S( A; B, C) refers to the mutual infor-
mation between system A and composite system BC. Then I shall observe and discuss
the three following properties:
(i) S(P; Q) = S(P; Q, R), since prior to measurement, R is uncorrelated to PQ and,
thus, does not contribute to PQ mutual information;
(ii) S(P; Q, R) ≥ S
(P; Q, R), since the measurement between P and R has no reason
to increase the mutual information between P and QR;
(iii) S
(P; Q, R) ≥ S
(P; R), since discarding the reference system Q between P and
R has no reason to increase the mutual information between P and R.
The first property (i) is obvious. The second property (ii) can be established as fol-
lows. Let S( A; B) and S
(A; B) be the mutual information before and after the mea-
surement between any systems A and B (here, A plays the role of system P and
B plays the role of the composite system QR). We introduce another system C in
By application of the property in Eq. (21.47), we have
S
3
x
p
x
R
x
4
≡
x
p
x
S(R
x
) + H (X ).
And because R
x
is a tensor operator, we have
S(R
x
) = S(|xx|⊗ρ
x
) = S(|xx|) + S(ρ
x
) = 0 + S(ρ
x
) ≡ S(ρ
x
),
which, finally, yields
S
3
x
p
x
|x x|⊗ρ
x
4
= H (X) +
x
p
x
S(ρ
x
).
Holevo bound 671
a pure state (e.g., |0 or |1). We then have S(A; B) = S(A; B, C), because of prop-
erty (i). A measurement on B with the information being transferred to C must not
change mutual information between A and BC, therefore, S(A; B, C) = S
(A; B, C).
But on discarding C,wemusthaveS
(A; B) ≤ S
(A; B, C), according to property (iii),
which states that discarding a system cannot increase mutual information. We must
now focus on this property (iii), rewriting the inequality as S(A; B) ≤ S(A; B, C)for
any systems A, B, C. According to the definition of mutual information, we have
S(A; B) = S(A) + S(B) − S(A, B) and S(A; B, C) = S(A) + S(B, C) − S(A, B, C),
which yields by substitution S(A, B, C) + S(B) ≤ S(A, B) + S(B, C). This last prop-
erty is referred to as strong subadditivity inequality. Its demonstration requires no less
than two additional theorems (including the so-called Lieb’s theorem), both being rather
mathematically involved! Therefore, here we shall take the “strong subadditivity” prop-
erty as a given postulate, which closes the loop. Combining properties (i)–(iii) we finally
obtain S(P; Q) ≥ S
(P; R), which is the inequality in Eq. (X16).
Appendix Y (Chapter 25) Polynomial
byte representation and modular
multiplication
The novelty introduced by the AES cryptosystem is the use of modular multiplication by
byte blocks, which is described in this appendix. For multiplied bytes to remain within
a one-byte size, this multiplication must be defined modulo a certain “prime” number.
This requires one to introduce another representation for binary numbers, which is the
polynomial (byte) representation.
A polynomial is an element that can be defined according to the expression
m(x) = c
n
x
n
+ c
n−1
x
n−1
+···+c
1
x + c
0
, where c
n
, c
n−1
...c
1
, c
0
are called the poly-
nomial coefficients and n is the polynomial’s degree. Since a byte is the eight-bit
word c
7
c
6
c
5
c
4
c
3
c
2
c
1
c
0
(c
k
= 0 or 1), its equivalent polynomial representation is
m(x) = c
7
x
7
+ c
6
x
6
···+c
1
x + c
0
. Let’s look now at the XOR operation between
two polynomials. Consider the two numbers {1010 0010}={A3} and {0101 1111}=
{5F}. In binary, hexadecimal, and polynomial representations, we get
{1010 0010}⊗{0101 1111}={1111 1101}, (Y1)
{A3}⊗{5F}={FD}, (Y2)
{x
7
+ x
5
+ x}⊕{x
6
+ x
4
+ x
3
+ x
2
+ x + 1}
={x
7
+ x
6
+ x
5
+ x
4
+ x
3
+ x
2
+ 1}. (Y3)
The operation of polynomial multiplication, modulo a polynomial m(x), which we label
with the symbol •, is no more difficult to grasp. The idea is that the reduction modulo
m(x) should give a polynomial whose degree (here) is strictly less than eight, so that
the result of the multiplication can always be represented by a one-byte word. The
modulus m(x) = x
8
+ x
4
+ x
3
+ x + 1, which is used in the AES cryptosystem, meets
such a requirement. This specific polynomial is also irreducible, meaning that it has no
dividers other than 1 and itself. It is the conceptual equivalent of a prime number in the
polynomial field. The polynomial dividers of m(x) are any numbers u(x),v(x) that verify
u(x) × v(x) = m(x), where × is the usual algebraic multiplication. Let us look now at
how multiplications ×and • work through a simple example. Take u(x) = x
3
+ x
2
+ 1
and v(x) = x
2
+ x. Following usual algebra, we first get the product
u(x) × v(x) = (x
3
+ x
2
+ 1)(x
2
+ x)
= (x
5
+ x
4
+ x
2
) ⊕ (x
4
+ x
3
+ x)
= x
5
+ x
3
+ x
2
+ x.
(Y4)
Polynomial byte representation and modular multiplication 673
To obtain this result, we use ⊕ to perform the addition between the polynomial coef-
ficients of the same order, since this is the operation used in the corresponding binary
representation. The second task is to reduce the above result modulo a given polynomial,
say, m(x) = x
4
+ 1. By definition, we have for any polynomial p(x),
p(x) = q(x) × m(x) +r (x), (Y5)
where q(x)isthequotient and r (x)istheremainder, also noted p(x)modm(x). Note
that the degree of the remainder must be lower than that of m(x), otherwise it could
divide it. Taking the previous example, we must find the polynomials q(x) and r(x) that
satisfy
x
5
+ x
3
+ x
2
+ x = p(x) × (x
4
+ 1) +q(x). (Y6)
From the above relation, we must conclude that p(x) = ax + b and q(x) = cx
3
+ dx
2
+
ex + f , where a, b, c, d, e, f are the unknowns. Substituting these two definitions into
the right-hand side yields a = c = d = 1, b = e = f = 0, which gives p(x) = x and
q(x) = x
3
+ x
2
. Thus,
x
3
+ x
2
= x
5
+ x
3
+ x
2
+ x mod x
4
+ 1, (Y7)
which illustrates how modulus reduction is performed.
With the modulus-reduction tool in hand, we can now consider an example that uses
the irreducible polynomial m(x) = x
8
+ x
4
+ x
3
+ x + 1. Take, for instance, the two
numbers {4A} and {18}. What is p(x) ={4A}•{19}? The conversion into polynomial
representation gives
p(x) ={01001010}•{00011001}
= (x
6
+ x
3
+ x) ×(x
4
+ x
3
+ 1) mod m(x)
= x
10
+ x
9
+ x
7
+ x
5
+ x
4
+ x
3
+ x mod m(x)
= x
7
+ x
6
+ x
5
mod m(x)
={11100000}
={E0},
(Y8)
which is the result of the operation. Since we have defined a multiplication law for
polynomials (modulo m(x)), we must also introduce the corresponding concept of inverse
polynomials. The inverse polynomial of a nonzero polynomial, p(x), is noted p
−1
(x)
and is defined by the equivalent identities
p(x) • p
−1
(x) = 1
p
−1
(x) = p(x)modm(x).
(Y9)
We also know that the inverse exists because m(x) is irreducible, i.e., p(x) and m(x)do
not have a common divider. As with modular arithmetic, the search for the inverse can
be performed by the extended Euclidian algorithm (EEA).
Let me explain the EEA through two representative examples: for instance, find
(1) the inverse of 7 in modulus 39, i.e., the value of 7
−1
mod 39 and (2) the inverse
of 5 in modulus 16 272, i.e., the value of 5
−1
mod 16 272. Considering example (1),
674 Appendix Y
Table Y1 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 = 31− 34 =−33
71× 3 = 31× (−33) =−33
84− 3 = 134− (−33) = 67 = 28
Table Y2 Extended Euclidian algorithm to find 5
−1
mod 16 272.
1 16 272 16 272
25 1
3 3254 ×5 = 16 270 3254 ×1 = 3254
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
the algorithm proceeds as shown in Table Y1, 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 7/3, whose integer part is
[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 that we have
been looking for. Here, we find that the inverse of 7 is 28. Proof: 7 × 28 = 196 ≡ 1
(modulo 39).
Consider the second example, which concerns the search of 5
−1
mod 16 272. We
obtain Table Y2.
In steps 1 and 2, we fill out the table as shown. We first divide 16 272 by 5, to find
that the integer part of the result is [16 272/5] = 3254. In step 3, we multiply line 2 by
3254, 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 (k > 1), namely 5
−1
= 16 272 – 26 035 = 6509.
Proof: 5 × 6509 = 32 545 = (2 × 16 272) + 1 ≡ 1 (modulo 16 272).
Polynomial byte representation and modular multiplication 675
I shall now implement the EEA with polynomials modulo m(x). For instance,
we want the inverse of p(x) = x
5
+ x
3
+ 1 modulo m(x) = x
8
+ x
4
+ x
3
+ x + 1.
Table Y3 shows the different calculation steps:
Table Y3 The steps in calculating p
−1
(x).
1 x
8
+ x
4
+ x
3
+ x + 1 x
8
+ x
4
+ x
3
+ x + 1
2 x
5
+ x
3
+ 11
3(x
3
+ x)(x
5
+ x
3
+ 1) = x
8
+ x
4
+ x
3
+ x (x
3
+ x) ×1 = x
3
+ x
4(x
8
+ x
4
+ x
3
+ x + 1) ⊕(x
8
+ x
4
+ x
3
+ x)(x
8
+ x
4
+ x
3
+ x + 1) ⊕(x
3
+ x)
= 1 = x
8
+ x
4
+ 1
Since we obtained 1 in the last line of left column, the result in the right column,
x
8
+ x
4
+ 1, is the inverse p
−1
(x). We can readily check that
p(x) • p
−1
(x) = (x
5
+ x
3
+ 1) × (x
8
+ x
4
+ 1) mod m(x)
= x
13
+ x
11
+ x
9
+ x
8
+ x
7
+ x
5
+ x
4
+ x
3
+ x mod m(x)
≡ 1modm(x).
Index
A-law, 592
Action table (Turing machine), 97, 107
Adaptive coding, see Coding
Adder (plain), 299
Addition (quantum operation), 326
Additive noise, see Noise
Adleman L., 424, 536
ADSL, 225
Advanced encryption standard, see AES
AES (advanced encryption standard), 523, 541–3,
555, 563, 597, 672
Ait Sab O., 229
Algebra/arithmetic (modular), see Modular
Algorithm
continued fraction expansion, 399, 408–10,
648–52
Deutsch, 378–80
Deutsch–Jozsa, xv, xix, 378, 381, 394, 512
Diffie–Hellmann–Merkle algorithm, 534, 535,
541
Dixon, 411
extended Euclidian, 413, 428, 658, 673
Fermat, 411
general number field sieve, 400, 411, 538
Grover quantum database search, xv, xix, 378,
389–98
Hughes, 535
Lenstra, 411
order-finding (-), 399, 400, 405–8, 414
Pollard, 411
Shank, 411
Shor factorization (-), xv, xix, 327, 329, 378, 389,
399, 415–17, 523, 527, 536, 653–5
triple data encryption (TDEA), 542
V (code), see Code
William, 411
Algorithmic
and logical unit, see ALU
complexity, see Kolmogorov
entropy, see Entropy
independence, 121
information theory, see Information
Alphabet (symbol), 57, 127
Alphabetic
poly (-) substitution, 526
substitution, 526
ALU (algorithmic and logical unit), 283, 288, 289
American
Automobile Association (AA), 159
Civil War, 132
wheel, 170
Ammeter, 360
Ampersand
Amplified coherent light, see Coherent
Analog-to-digital voice conversion, see Speech
Ancilla
bit, see Bit
qubit, see Qubit
space, 352
state, 354
AND (logical/Boolean), 70, 76, 291, 293, 299, 529
ANSI (Americal National Standards Institute), 541,
542
Arabic numerals, see Numerals
Araki–Lieb inequality, 442
Architecture
multi-processor, 289
parallel processor (-), 289
von Neumann, see Vo n N e u m a n n
Arithmetic coding, see Coding
Arobase, 167
Arrangement without repetition, 10–11
Artificial intelligence, see Intelligence
ASCII (American standard code for information
exchange), 112, 113, 130, 131, 133, 152,
156, 157, 159, 169, 192, 197, 426–8, 527,
528, 530
Aspect, A., xii
At sign or @, 167
Attack, see Cryptosystem
brute-force, see Cryptosystem
cryptosystem, see Cryptosystem
denial of service (DoS), 564
giant pulse, 563
impersonation, 563
key, see Key
man-in-the-middle (-), 562, 563
random-number generator, 563