Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist
Подождите немного. Документ загружается.
25.10 The BB84 protocol for QKD 557
At his end, Bob uses a random-bit generator to produce a sequence B
= (b
1
, b
2
,...)
of N =
(
4 +
)
n bits length. This is the random sequence he uses to determine the
choice of measurement basis, X or Z, for each of the received qubit. For instance, Bob
can choose conventionally that if b
k
= 0, the measurement basis is Z , and if b
k
= 1
the measurement basis is X. In any case, there is a 50% chance of this measurement
choice being “right” or “wrong,” according to the description in the previous section.
The outcome of Bob’s measurement is, thus, a random sequence A
= (a
1
, a
2
,...)of
length N =
(
4 +
)
n.
Using a public channel, either Bob announces to Alice his sequence of state-
measurement bases (ZXZX ...), or Alice announces to Bob her sequence of state-
preparation bases (ZZXX ...). The other person then tells which bits are t o be discarded,
according to the fact that either measurement or preparation was made in the “wrong”
basis. The wrong bits being discarded, the two bit sequences A (from Alice) and A
(from
Bob) are, thus, reconciled. With a sufficiently large bit sequence length N =
(
4 +
)
n,
there is a high probability that there are at least 2n valid bits in A, A
. In the contrary
event, the protocol session must be aborted and restarted with new random sequences
A, B, B
.
We may conclude too quickly that the above protocol wholly suffices to guarantee
the strict equality of Alice’s and Bob’s bit strings, or A = A
. Indeed, there is yet a
possibility that the quantum channel used by Alice and Bob is corrupted by the effects
of random quantum noise and also Eve’s tampering actions (e.g., suppressing, injecting,
or modifying some of the qubits). In this last event, Eve is capable of obtaining par tial
information about the secret key and, therefore, a higher level of security is required from
Alice and Bob. This is where the techniques of secret key distillation (SKD) through
information reconciliation and privacy amplification come into the picture. It is beyond
the scope of this chapter to venture into the mathematical details of SKD algorithms.
Here, it will suffice to convey a rough idea of the underlying principle.
At this point, Alice and Bob have validated two 2n bit sequences, A, A
, but have no
reason to believe that these do perfectly match. Further, they suspect that some of the
bits might have been corrupted by quantum noise and eavesdropping. Their next step is
to effect “information r econciliation.” Alice selects a random subset X of n bits from
her sequence A, sends X to Bob over a public channel (assumedly error-free) and also
informs Bob which bits she has selected. Bob receives a sequence Y , which he is then
able to compare with the corresponding n-bit selection from his A
sequence. Bob then
deduces the error syndrome E (as defined by Y = X + E), deducts the number of errors
e and tells Alice the value over the public channel. If e is over a certain commonly agreed
threshold t , the QKD protocol is immediately aborted. In the favorable case (e ≤ t), Alice
and Bob use a secret classical code, C
1
, having an error-correction capability of t, and
unknown to Eve. This makes it possible for each to determine a common codeword
W = X
= Y
corresponding to the correction of X and Y under this code. Yet it can
be shown that Eve is able to possess partial information about W . Then the next step
is for Alice and Bob to perform “privacy amplification,” which consists of extracting
from W a smaller secret key S of size m < n, based on their remaining n bits. How they
achieve this and why, in this process, Eve’s information about the reduced key S is lost
558 Classical and quantum cr yptography
to an arbitrarily high level of confidence, is beyond the scope of this chapter to describe.
The lesson to retain from the obligation for Alice and Bob to perform SKD is that QKD
alone is not as “absolutely secure” a protocol as is commonly believed.
25.11 The B92 protocol
A simpler version of the BB84 protocol, referred to as B92 (after its inventor, C. H.
Bennet, and the year, 1992), uses only two reference qubits. Alice uses a random-bit
generator to produce a single sequence A = (a
1
, a
2
,...)ofN =
(
4 +
)
n bits length.
Then she produces an N -qubit block sequence
|
ψ
, which can be expressed in the form:
|
ψ
=|ψ
a
1
⊗|ψ
a
2
⊗···⊗|ψ
a
N
≡
N
⊗
k=1
|ψ
a
k
.
(25.26)
For each cbit a
k
the corresponding single qubit |ψ
a
k
is generated according to the
following convention:
⎧
⎨
⎩
|
ψ
0
=
|
0
|
ψ
1
=
|
+
=
|
0
+
|
1
√
2
.
(25.27)
On receiving the block
|
ψ
, Bob uses a random-bit generator to produce a sequence
A
= (a
1
, a
2
,...)ofN =
(
4 +
)
n bits length. Conventionally, Bob chooses that if
a
k
= 0, the qubit measurement basis is Z , and if a
k
= 1itisX . The outcome of
Bob’s eigenvalue measurement is a random-bit sequence B = (b
1
, b
2
,...) of length
N =
(
4 +
)
n. Here, I shall use the convention according to which the eigenvalue +1
corresponds to b
k
= 0 and −1 corresponds to b
k
= 1.
21
Bob’s different measurement
outcomes (eigenvalues and cbits b
k
as functions of cbits a
k
, a
k
) are summarized in
Table 25.9. We first observe from the table that if the “right” bases for Bob to measure
|
ψ
0
and
|
ψ
1
are Z and X , respectively, the outcome is deterministic, since in either cases
Bob certainly obtains b
k
= 0, corresponding to a
k
= a
k
. Therefore, contrary to the BB84
protocol, the infor mation about which are the “right” bases is surely not to be publicly
exchanged! Consider now the use of the “wrong” bases, which correspond to the cases
a
k
= 1 − a
k
. We observe from the table that Bob’s measurements randomly yield the
cbits b
k
= 0orb
k
= 1 with equal chances. Thus, it is a matter of Bob communicating
his cbit sequence B = (b
1
, b
2
,...b
N
) to Alice over a public channel, while keeping
A
= (a
1
, a
2
,...a
N
) secret. Only the bit pairs a
k
, a
k
yielding b
k
= 1 are retained by
Alice and Bob. Clearly, such public knowledge does not tell Eve anything about the
values of a
k
, a
k
= 1 − a
k
, which have equal chances of being 0 or 1. This operation
yields two common subsets of A, A
with at least 2n valid bits (Bob needs to complement
his own bits, according to a
k
= 1 − a
k
= a
k
, so that his subset matches Alice’s). The
21
The opposite convention, introduced earlier, is applicable to the B92 protocol if Alice chooses instead
|
ψ
0
=
|
1
.
25.12 The EPR protocol 559
Table 25.9 Outcomes of Bob’s measurements (eigenvalues and cbits) according to Alice’s qubits and
Bob’s measurement basis Z, X .
Alice
a
k
= 0 a
k
= 1
|
ψ
0
=
|
0
|
ψ
1
=
|
+
a
k
= 0 Z
|
0
=
|
0
Z
|
+
=
|
0
or
|
1
, 50% chances
Z Eigenvalue +1, b
k
= 0 b
k
= 0, 1
a
k
= 1 X
|
0
=
|
0
or
|
1
, 50% chances X
|
+
=
|
+
Xb
k
= 0, 1 Eigenvalue +1, b
k
= 0
Bob
rest of the B92 protocol follows the same path as that of BB84, i.e., using information
reconciliation and privacy amplification or SKD.
25.12 The EPR protocol
The EPR protocol, named after entangled EPR pairs or Bell states (see Chapter 16) was
invented by A. K. Eckert in 1991. The idea is that Alice and Bob share, over a quantum
channel, an ensemble of N =
(
4 +
)
n such EPR pairs, based, for instance, on one of
the four EPR–Bell states:
22
|
β
00
=
|
00
+
|
11
√
2
. (25.28)
Prior to any measurement, the quantum state of Alice’s and Bob’s system is, thus, defined
by the N -EPR tensor:
|
ψ
=
|
β
00
1
⊗
|
β
00
2
⊗···⊗
|
β
00
N
≡
N
⊗
k=1
|
β
00
k
=
1
√
2
N
(
|
00
+
|
11
)
⊗N
.
(25.29)
As with previous protocols, Alice and Bob use random-bit generators to produce bit
sequences A = (a
1
, a
2
,...) and A
= (a
1
, a
2
,...a
N
), of length N =
(
4 +
)
n bits.
The bit values a
k
, a
k
determine their choice of measurement basis, for instance Z for
a
k
= 0 (Alice’s side) or a
k
= 0 (Bob’s s ide), and X in the other case, as applicable to
the first (Alice) and second (Bob) qubits, respectively, of any of the EPR pairs from
the above N-EPR tensor. The cbit outcomes of Alice or Bob measurements generate
random bit sequences B = (b
1
, b
2
,...,b
N
) and B = (b
1
, b
2
,...,b
N
), respectively.
22
EPR–Bell states can be physically generated through pairs of entangled photons. See, for instance:
http://physicsworld.com/cws/article/print/11360/1/smallphotons,
http://physicsworld.com/cws/article/news/24358,
www.quantum.at/research/quantum-teleportation-communication-entanglement/
entangled-photons-over-144-km.html.
560 Classical and quantum cr yptography
How does an eigenvalue measurement with X or Z apply in the case of a single EPR
pair, such as
|
β
00
? The answer is simple, if one considers that the entangled state can
also be written in the form
23
|
β
00
=
|
++
+
|
−−
√
2
. (25.30)
If Alice uses X for her first qubit measurement of
|
β
00
, she obtains equally likely
eigenvalues ±1 with corresponding post-measurement or collapsed states
|
ψ
B
=
|
+
or
|
−
, and cbits b
k
= 0orb
k
= 1, respectively (using the same convention
as in B92); or
If Alice uses Z for her first qubit measurement of
|
β
00
, she obtains equally likely
eigenvalues ±1 with corresponding post-measurement or collapsed states
|
ψ
B
=
|
0
or
|
1
, and cbits b
k
= 0orb
k
= 1, respectively.
We note here that Alice’s measurements of the first qubits of the EPR pair
|
β
00
result in the instant collapse of the state into one of the qubits,
|
ψ
B
=
|
+
,
|
−
,
|
0
,or
|
1
, depending on the measurement type and its eigenvalue outcome. Such a
collapse is instant indeed, as a result of the intriguing property of entangled states
called nonlocality. This term is attached to any widely separated systems, which can-
not be treated as behaving independently, regardless their physical separation. It is
thought-provoking that the action of Alice (on her qubit) instantly affects the system
(hence, Bob’s qubit) without consideration of wave propagation subjected to the speed of
light, c.Asinquantum teleportation (Chapter 18), there is no violation of Einstein’s
theory of special relativity, according to which information cannot travel faster than
c. The nonlocality of entangled states, which permits their instant collapse, does
23
To recall, the states
|
±1
are given by the qubit superpositions
|
+
=
1
√
2
(
|
0
+
|
1
)
,
|
−
=
1
√
2
(
|
0
−
|
1
)
.
Thus,
|
0
=
√
2
2
(
|
+
+
|
−
)
=
1
√
2
(
|
+
+
|
−
)
,
|
1
=
√
2
2
(
|
+
−
|
−
)
=
1
√
2
(
|
+
−
|
−
)
and, hence,
|
β
00
=
1
√
2
(
|
00
+
|
11
)
=
1
√
2
(
|
0
|
0
+
|
1
|
1
)
=
1
√
2
|
+
+
|
−
√
2
⊗
|
+
+
|
−
√
2
+
|
+
−
|
−
√
2
⊗
|
+
−
|
−
√
2
=
1
√
2
|
++
+
|
+−
+
|
−+
+
|
−−
2
+
|
++
−
|
+−
−
|
−+
+
|
−−
2
≡
|
++
+
|
−−
√
2
.
25.12 The EPR protocol 561
not violate such a principle, because actually no information is exchanged in the
process.
24
Next comes the clever t hing about the EPR protocol. Indeed, if Bob then performs
a measurement on his remaining qubit (the post-measurement state)
|
ψ
B
, incidentally
at random with the same basis choices as Alice’s, there is absolute certainty that his
eigenvalues or cbits (b
k
) exactly match those of Alice’s (b
k
), just as with the BB84
protocol. Over a public channel, Alice and Bob only need to compare the bases they used
(namely the cbits a
k
, a
k
), and retain as valid only their secret cbits b
k
, b
k
corresponding
to the matching cases a
k
= a
k
.
The same conclusion applies should Bob perform his measurement before Alice,
or even at the same time! Indeed, the outcome of their measurements is independent
of their sequence order, as is an easy exercise to verify. In this perspective, the EPR
protocol is not a matter of mere key “exchange,” since, in fact, the key remains fully
undetermined until both measurements from Alice and Bob have been duly performed,
results compared, and valid cbits finally identified.
In view of making an inventory of common secret bits, by sharing measurement
bases over a public channel, the EPR protocol appears to be very similar to BB84.
The difference, however, is that Alice and Bob must share beforehand a wealth of
entangled states. This allows them to perform independent measurements, regardless of
time sequence and their roles as originator or recipient in the quantum channel. With
BB84, one or the other must agree on their roles (originator Alice or recipient Bob)
and about the protocol sequence, and only single qubits are “exchanged.” Although it
is more complex to implement, because of the need for entangled EPR–Bell states as
opposed to single qubits, EPR can be viewed as the conceptual “crown jewel” of QKD.
Like the other protocols, however, information reconciliation and privacy amplification
by SKD is required, to eliminate the effects of quantum noise and eavesdropping.
Another major issue, which concerns all QKD protocols, is distance. The different
quantum states that are exchanged (BB84, B92) or shared (EPR) by Alice and Bob must,
throughout the process, remain immune to various forms of physical perturbation, so as to
keep their coherence, a term to mean their initial qubit description. Those perturbations
introduce decoherence, whose nature is to ruin the protocol implementation and its
24
Here is a classical analogy (or Gedanken experiment) to illustrate the concept of nonlocality, which may
provoke animated discussions. Assume that Alice prepares two different envelopes, each including either a
picture of a cat or that of a dog, and seals them. Alice asks a third party to pick up one of the two envelopes.
This envelope is to be sent to Bob, an astronaut on a mission somewhere in the Solar System (meaning several
light-hours away). We may conceive of the system represented by the two envelopes altogether forming the
entangled superposition
|
β
=
|
cat
A
|
dog
B
+
|
dog
A
|
cat
B
/
√
2, where only the qubit
|
·
X
(X = A, B)
is accessible and measurable by Alice (A)orBob(B). The outcome of either measurement is equally likely to
be cat or dog. Alice may wait until Bob receives his envelope to open hers, or alternatively she may decide to
do it beforehand, hours ahead or just a few minutes before. Opening her envelope, Alice finds the dog! Then
she gets the instant knowledge that Bob will find, or has already found, the cat. And this despite the need for
the information to propagate for several hours through space. It may well be that Alice and Bob perform their
openings at the same universal time. They both instantly know who has the cat and who has the dog, without
exchanging information. This is an illustration of the principle of nonlocality of the combined system.
But it took Bob’s envelope to travel at (somewhere under) the speed of light to reach him, therefore, putting
a physical limit to the information flow from Alice to Bob, which is consistent with relativity.
562 Classical and quantum cr yptography
magic. This is where quantum error correction (Chapter 24) may come to the rescue, but
as an additional burden to an approach otherwise presumed to be fairly straightforward in
implementation. It is important to recall here that error-correction in the quantum domain
requires fully operational quantum-gate circuits with qubit dimensions of seven to nine in
the quantum channel (as applicable to BB84, B92). Other techniques have been proposed
to purify, distil,orswap EPR pairs, making it possible to expand the channel reach in the
presence of quantum noise. Such considerations illustrate that it is theoretically possible
to implement both local and nonlocal QKD algorithms at global scales, b ut at the expense
of increased complexity in quantum processing and gate circuits. In contrast, classical
cryptography can pretend to globality – the key requirement of truly seamless network
security – while lacking the “provable invulnerability” of the quantum cryptosystem.
25.13 Is quantum cryptography “invulnerable?”
In this concluding section, I shall analyze how a malicious Eve may be able to tamper
with Alice’s and Bob’s secure photon communication (or QKD) channel and, hence,
threaten the concept of absolute secrecy in key exchange and message communication.
Assume, first, that a malicious Eve puts a “wire tap” somewhere inside Alice and
Bob’s photon communication channel. To access the information originally destined for
Bob, Eve must perform photon measurements. But like Bob, she does not know, for each
of the incoming photons, which measurement basis, X or Z, could be the correct one.
Eve may perform the measurement anyway, but she now has to generate new photons in
replacement, so that Bob does not notice anything. But this is where Eve is tricked: she
does not know in which basis-state Alice generated the input photon (X or Z ), so she has
to make a guess with a 50% chance of being right. When Bob measures Eves’ photon
substitute, he also has a 50% chance of choosing the right measurement basis. At the
end of the process, when Bob communicates his measurements to Alice over the public
channel, it immediately appears that he has been only 25% successful! And this is the
signature of Eve’s wiretap. Eve may try to outsmart Alice and Bob by not measuring all of
Alice’s photons, but only a few at random, in the hope that her tampering is not detected,
and retrieve at least some part of the secret key. But even this approach cannot succeed.
This is because Alice will immediately detect that Bob does not get the right proportion
of correct bits. The widely known conclusion i s that it is not possible to eavesdrop a
photon communication channel without Alice and Bob becoming immediately aware of
it. To remain undetectable, however, Eve may choose instead to tamper with only a few
photons amongst a long sequence. She may even occasionally luck out in intercepting
and re-emitting some of the photons in the right bases. This approach is referred to as a
man-in-the-middle attack (MIMA), see more later. It may be justly argued that MIMA
would not give Eve sufficient information to figure out the whole key. However, the key
is weakened to some extent, and this fact justifies the need for SKD. Thus, contrary to
widespread acceptance (except in the exper t community), QKD alone is not absolutely
secure, while QKD +SKD provably is, as far as the key-exchange protocol is concerned.
See further for more discussion on how such a notion as “absolute security” may be
otherwise challenged.
25.13 Is quantum cryptography “invulnerable?” 563
If Eve is capable of eavesdropping Alice’s and Bob’s public communication channel,
can she derive any useful information about their secret key? At a first level of analysis,
the answer is definitely no. All the information that Eve has access to is ZXZX ...from
Bob’s side, and YesNoNoYes ... from Eve’s side. Such information does not reveal in
any way the outcome of Bob’s valid measurements (±1 eigenvalues, or 1 and 0 bits). The
fact that Eve knows which of Bob’s measurements were right does not tell her, in any way,
which are the measured and valid bits. At a second level of analysis, however, the tapped
information makes it possible for Eve to analyze the possible algorithms according to
which Alice and Bob choose their random basis and measurement sequences. Thus,
rather than trying to wiretap the key, Eve may figure out Alice’s and Bob’s random-
sequence generation algorithms and, thus, reconstruct or predict, with some potential
success, the key exchange. Should Eve access the technology used by Alice and Bob
for random-key generation, she does not need to eavesdrop their photon communication
channel anymore, having a powerful tool for key attacks on the classical DES and AES
ciphers. This is referred to as random-number generator attack (RNGA).
A second possibility for Eve is to impersonate Bob, which is the spirit of MIMA. Eve,
a central office (CO) or point-of-presence (POP) network employee, may, indeed, figure
out how to take over the public communication channel used by Alice and Bob to finalize
their key exchange. Basically, the operation results in a key exchange K between Alice
and Eve (and not Alice and Bob), all without Alice’s and Bob’s awareness. Eve may
then impersonate Alice by proceeding to a key exchange K
with Bob, again without
their awareness. Eve must also be able to intercept the encrypted messages, but this is an
easier task, considering her CO or POP access prerogatives. Assuming that Eve has been
successful in implementing such a complex arrangement altogether, she has become the
“man in the middle” (so to speak). Consider, indeed, Eve’s following course of action:
Intercept Alice’s encrypted message M, along with K as the secret key (that Alice
thought she was sharing with Bob), call it E
Alice
K
(M), and perform decryption, i.e.,
generate M = D
Eve
K
(E
Alice
K
(M));
Possibly change Alice’s message M into some other message M
and perform re-
encryption with Eve’s new key K
, i.e., generate E
Eve
K
(M
);
Perform key exchange with Bob, resulting in shared secret key K
;
Send Bob the encrypted message E
Eve
K
(M
).
The above appears as a perfect MIMA of the reputedly “invulnerable” channel. No
quantum-mechanical principles have been violated in the process, only the confidence
that Alice and Bob are the only, exclusive, communicating parties. To achieve such a
success in “breaking” the QKD channel and value chain, however, Eve must completely
control both photon and public communication channels, to prevent them to “compare
notes” and detect any anomaly. This would assume another level of verification protocol,
which can, in turn, be attacked by malicious Eve.
It is noteworthy to mention the giant-pulse attack (GPA). Alice’s and Bob’s transmitter
and receiver photon-measurement terminals are obviously protected from any optical
reflections in their shared link, a concept referred to as a return loss. Such a return
loss, which expresses the probability that a single photon will be reflected might range
564 Classical and quantum cr yptography
between 10
−2
and 10
−6
. A “giant” light pulse, with 10
2
− 10
6
photons, may provide
Eve some information about Alice’s and Bob’s choices of X and Z bases, as based on
the polarization state (, ↔, ∩, ∪) of the reflected pulse. Additionally, such a probing
is performed at a wavelength different from that used by Alice and Bob, so that Eve’s
probing action may remain essentially unnoticed. This type of “side-channel” attack
illustrates that QKD’s absolute security may be challenged by classical means, and
that great care must be taken in any physical inplementation of QKD to eliminate the
possibility of any side channels.
Another form of attack, which is far more straightforward, is for Eve to sever the
photon communication channel physically. This is referred to as the denial-of-service
attack (DoSA). The contingency plan for Alice and Bob would be to resort to classical
cryptosystems and network means, exposing themselves to ordinar y forms of classical
security attack. Finally, the weakest point in a quantum cryptosystem is not the link,
which, as we have seen, cannot be tampered with, without triggering alarms, but the
terminals themselves. Since these terminals must be connected to a network of some
kind, they are potentially exposed to attacks, for instance “spy” viruses, which can detect
the keys that are exchanged between Alice and Bob. Considering these possibilities, is
it possible to state that a quantum cryptosystem is absolutely secure? The answer is yes,
but only within a certain set of assumptions regarding the security of the other elements
in which the cryptosystem is embedded. The worst situation for Alice and Bob would be
to trust, in absolute confidence, a s ystem that could be wired without their awareness.
An element that remains central to the discussion about cryptosystem security is the
criticality of the application: what information must be protected, and how critical is the
communication success? In situations of conflict, where all the communications means
(civilian or military) may be disabled, denied, or destroyed, there must always remain
one way or another for communicating critical information. The cryptosystem must be
able to borrow multiple, if not redundant, paths, just as with the Internet protocol. It must
also be able to reach Alice or Bob anywhere they may happen to be, supposedly not in a
predefined place. Notwithstanding its inherent strength, QKD remains a point-to-point,
local cryptosystem whose extension at global scales and possibilities for path redundancy
seem impractical. Furthermore, a classical communication channel is always required
for Alice and Bob to compare measurements and agree on the secret key. The main
assumption of QKD is that such a channel is always available, and resilient against any
form of attack, and in realistic conflict situations this fact cannot be taken for granted!
Finally, it is important to stress that despite the availability of provably-secure QKD
protocols, the core cryptosystems eventually used in any classical message/ciphertext
channels (DES, AES, and future upgrades) remain 100% exposed to conventional attacks
(cryptanalysis, code-cracking . . .). Thus, channel security ultimately rests upon the
classical notion of “code invulnerability”, which represents a “reasonable conjecture”
within a cryptosystem’s lifetime.
This discussion leads to the closing conclusion that despite its awesome conceptual
elegance, quantum cryptography (or QKD) only represents a supplemental technique of
information protection, to be situated somewhere within the grander domain of global
network security, where there exists no such a thing as “absolute” confidence in any
cryptosystems.
Appendix A (Chapter 4) Boltzmann’s
entropy
Task 1
Show that the number of ways W of arranging N particles into m boxes with populations
N
i
is given by
W =
N !
N
1
!N
2
! ...N
m
!
. (A1)
Let us proceed as follows: we first apply the property according to which the number of
ways of selecting n objects out of m objects (m ≥ n)isC
n
m
=
m!
n!(m−n)!
, with ! representing
the factorial function:
1! = 1, 2! = 1 ×2, 3! = 1 ×2 ×3,...,n! = 1 ×2 ×···(n − 1) ×n,
with, by convention, 0! = 1. The number of ways of selecting N
1
particles out of m
particles is, thus,
C
N
1
m
=
m!
N
1
!(m − N
1
)!
. (A2)
The number of ways of selecting N
2
particles out of m − N
1
particles is then
C
N
2
m−N
1
=
(m − N
1
)!
N
2
!(m − N
1
− N
2
)!
, (A3)
and so on until the box of energy E
m−1
, which has a number of ways
C
N
m−1
m−N
1
−N
2
−...N
m−2
=
(m − N
1
− N
2
−···−N
m−2
)!
N
m−1
!(m − N
1
− N
2
−···−N
m−1
)!
=
(m − N
1
− N
2
−···−N
m−2
)!
N
m−1
!N
m
!
(A4)
of being filled up. Multiplying all these possibilities together, we get
W =
m!
N
1
!(m − N
1
)!
(m − N
1
)!
N
2
!(m − N
1
− N
2
)!
···
(m − N
1
− N
2
−···−N
m−2
)!
N
m−1
!N
m
!
(A5)
and crossing out terms appearing in both numerator and denominator, two by two, leads
to the result in Eq. (A1).
566 Appendix A
Task 2
Show that (1/N )logW takes the following limit when the number of particles N (N =
m
i=1
N
i
) becomes infinite:
lim
N →∞
log W
N
= H, (A6)
where
H =
m
i=0
p
i
log p
i
, (A7)
and p
i
= N
i
/N is the probability of finding N
i
particles in the microstate of energy E
i
.
To demonstrate the above result, notice first that from Eq. (A1), we have
log W
N
=
1
N
log
N !
N
1
!N
2
! ···N
m
!
=
1
N
log
N !
m
D
i=1
N
i
!
.
(A8)
Assuming x = N , N
i
, is large, we use Stirling’s approximation formula:
x! = x
x
e
−x
√
2π x
1 +
1
12x
+
a
x
2
+···
, (A9)
where the series in parenthesis can be approximated to unity. Thus,
log W
N
≈
1
N
log
N
N
e
−N
√
2π N
m
D
i=1
N
N
i
i
e
−N
i
2π N
i
=
1
N
log
N
N
e
−N
√
2π N
−
1
N
log
3
m
D
i=1
N
N
i
i
e
−N
i
2π N
i
4
=
log(N
N
)
N
+
log(e
−N
)
N
+
log
√
2π N
N
−
1
N
m
i=1
E
log
N
N
i
i
+ log(
e
−N
i
) + log
2π N
i
F