Francoise J.-P., Naber G.L., Tsun T.S. (editors) Encyclopedia of Mathematical Physics
Подождите немного. Документ загружается.
completely positive maps. In particular, this implies
that D
(n)
must be of the form
D
ðnÞ
ðÞ¼
X
i
D
i
D
i
½11
for linear operators D
i
:
e
H
n
7!H
n
such that
P
i
D
i
D
i
= I (see Nielson and Chuang 2000).
Obviously, in order to achieve the maximum
possible compression of Hilbert space dimensions
per signal state, the goal must be to make the
dimension d
c
(n) as small as possible, subject to the
condition that the information carried in the signal
states can be retrieved with high accuracy upon
decompression.
The ‘‘rate of compression’’ is defined as
R
n
:¼
logðdim
e
H
n
Þ
logðdim H
n
Þ
¼
log d
c
ðnÞ
log N
n
It is natural to consider the original Hilbert space
H
n
to be the n-qubit space. In this case N
n
= 2
n
and
hence log N
n
= n. As in the case of classical data
compression, we are interested in finding the
optimal limiting rate of data compression, which in
this case is given by
R
1
:¼ lim
n!1
log d
c
ðnÞ
n
½12
Unlike classical signals, quantum signal states are
not completely distinguishable. This is because they
are, in general, not mutually orthogonal. As a result,
perfectly reconstructing a quantum signal state from
its compressed version is often an impossible task
and therefore too stringent a requirement for the
reliability of a compression–decompression scheme.
Instead, a reasonable requirement is that a state can
be reconstructed from the compressed version which
is nearly indistinguishable from the original signal
state. A measure of indistinguishability useful for
this purpose is the average fidelity defined as
follows:
F
n
:¼
X
k
p
ðnÞ
k
h
ðnÞ
k
jD
ðnÞ
ð
e
ðnÞ
k
Þj
ðnÞ
k
i½13
This fidelity satisfies 0 F
n
1 and F
n
= 1if
and only if D
(n)
(
e
(n)
k
) = j
(n)
k
ih
(n)
k
j for all k.A
compression–decompression scheme is said to be
reliable if F
n
!1asn !1.
The key idea behind data compression is the fact
that some signal states have a higher probability of
occurrence than others (these states playing a role
analogous to the typical sequences of classical
information theory). These signal states span a
subspace of the original Hilbert space of the source
and is referred to as the typical subspace.
Schumacher’s Theorem for Memoryless
Quantum Sources
The notion of a typical subspace was first
introduced in the context of quantum information
theory by Schumacher (1995) in his seminal paper.
He considered the simplest class of quantum
information sources, namely quantum memoryless
or i.i.d sources. For such a source the density matrix
(n)
, defined through [10], acts on a tensor product
Hilbert space H
n
= H
n
and is itself given by a
tensor product
ðnÞ
¼
n
½14
Here H is a fixed Hilbert space (representing an
elementary quantum subsystem) and is a density
matrix acting on H; for example, H can be a single
qubit Hilbert space, in which case dim H= 2, H
n
is
the Hilbert space of n qubits and is the density
matrix of a single qubit. If the spectral decomposi-
tion of is given by
¼
X
dim H
i¼1
q
i
j
i
ih
i
j½15
then the eigenvalues and eigenvectors of
(n)
are
given by
ðnÞ
k
¼ q
k
1
q
k
2
...q
k
n
½16
and
j
ðnÞ
k
i¼j
k
1
ij
k
2
ij
k
n
i½17
Thus, we can write the spectral decomposition of
the density matrix
(n)
of an i.i.d. source as
ðnÞ
¼
X
k
ðnÞ
k
j
ðnÞ
k
ih
ðnÞ
k
j½18
where the sum is over all possible sequences
k = (k
1
...k
n
), with each k
i
taking (dim H) values.
Hence, we see that the eigenvalues
(n)
are labeled
by a classical sequence of indices
k = k
1
...k
n
.
The von Neumann entropy of such a source is
given by
Sð
ðnÞ
ÞSð
n
Þ¼nSðÞ¼nHðXÞ½19
where X is the classical random variable with
probability distribution {q
i
}.
Let T
(n)
be the classical typical subset of indices
(k
1
...k
n
) for which
1
n
log q
k
1
...q
k
n
SðÞ
½20
as in the theorem of typical sequences. Defining
T
(n)
as the space spanned by the eigenvectors j
(n)
k
i
612 Source Coding in Quantum Information Theory
with k 2 T
(n)
then immediately yields the quantum
analog of the theorem of typical sequences – Theorem
4 given below. We refer to T
(n)
as the typical subspace
(or more precisely, the –typical subspace).
Theorem 4 (Typical subspace theorem). Fix >0.
Then for any >0 9 n
0
() > 0 such that 8n n
0
()
and
(n)
=
n
, the following are true:
(i) Tr(P
(n)
(n)
) > 1 and
(ii) (1 )2
n(S())
dim (T
(n)
) 2
n(S()þ)
, where
P
(n)
is the orthogonal projection onto the
subspace T
(n)
.
Note that tr (P
(n)
(n)
) gives the probability of the
typical subspace. As tr(P
(n)
(n)
) approaches unity for
n sufficiently large, T
(n)
carries almost all the weight
of
(n)
. Let T
(n)?
denote the orthocomplement of the
typical subspace, that is, for any pair of vectors
j i2T
(n)
and ji2T
(n)?
, hj i= 0. It follows from
the above theorem that the probability of a signal
state belonging to T
(n)?
can be made arbitrarily
small for n sufficiently large.
Let P
(n)
denote the orthogonal projection onto the
typical subspace T
(n)
. The encoding (compression)
of the signal states j
(n)
k
i of [10], is done in the
following manner. C
(n)
: j
(n)
k
ih
(n)
k
j7!
e
(n)
k
, where
~
ðnÞ
k
:¼
2
k
j
~
ðnÞ
k
ih
~
ðnÞ
k
jþ
2
k
j
0
ih
0
j½21
Here
j
~
ðnÞ
k
i:¼
P
ðnÞ
j
ðnÞ
k
i
kP
ðnÞ
j
ðnÞ
k
ik
k
:¼kP
ðnÞ
j
ðnÞ
k
ik;
k
¼kðI P
ðnÞ
Þj
ðnÞ
k
ik
½22
and j
0
i is any fixed state in T
(n)
.
Obviously
~
(n)
k
2B(T
(n)
), and hence the typical
subspace T
(n)
plays the role of the compressed space.
The decompression D
(n)
(
e
(n)
k
) is defined as the
extension of
e
(n)
k
on T
(n)
to H
n
:
D
ðnÞ
e
ðnÞ
k
¼
e
ðnÞ
k
0
The fidelity of this compression–decompression
scheme satisfies
F
n
¼
X
k
p
ðnÞ
k
ðnÞ
k
j
~
ðnÞ
k
j
ðnÞ
k
¼
X
k
p
ðnÞ
k
2
k
jh
ðnÞ
k
j
~
ðnÞ
k
ij
2
þ
2
k
jh
ðnÞ
k
j
0
ij
2
hi
X
k
p
ðnÞ
k
2
k
jh
ðnÞ
k
j
~
ðnÞ
k
ij
2
¼
X
k
p
ðnÞ
k
4
k
X
k
p
ðnÞ
k
ð2
2
k
1Þ¼2A
n
1 ½23
where A
n
= tr(P
(n)
n
).
Using the typical subspace theorem, Schumacher
(1995) proved the following analog of Shannon’s
noiseless channel coding theorem for memoryless
quantum information sources:
Theorem 5 (Schumacher’s quantum coding theo-
rem). Let {
n
, H
n
} be an i.i.d. quantum source:
n
=
n
and H
n
= H
n
. If R > S(), then there exists
a reliable compression scheme of rate R. If R < S(),
then any compression scheme of rate R is not reliable.
Proof
(i) R > S(). Choose >0 such that R > S() þ .
For a given >0, choose the typical subspace as
above and choose n large enough so that (i) and (ii)
in the typical subspace theorem hold. In particular,
A
n
= tr(P
(n)
n
)> 1 . Thus, the fidelity tends to 1
as n !1.
(ii) Suppose R < S(). Let the compression map
be C
(n)
. We may assume that
e
H
n
is a subspace of H
n
with dim
e
H
n
= 2
nR
. We denote the projection onto
e
H
n
as
e
P
n
and let
~
(n)
k
= C
(n)
(j
(n)
k
ih
(n)
k
j). Since
~
(n)
k
is concentrated on
e
H
n
, we have
~
(n)
k
e
P
n
and hence D
(n)
(
~
(n)
k
) D
(n)
(
e
P
n
), for any decompres-
sion map D
(n)
. Inserting into the definition of the
fidelity, we then have
F
X
k
p
ðnÞ
k
h
ðnÞ
k
jD
ðnÞ
ð
e
P
n
Þj
ðnÞ
k
i¼tr
ðnÞ
D
ðnÞ
ð
e
P
n
Þ
X
k2T
ðnÞ
ðnÞ
k
h
ðnÞ
k
jD
ðnÞ
ð
e
P
n
Þj
ðnÞ
k
iþ
X
k =2T
ðnÞ
ðnÞ
k
½24
By the typical subspace theorem, the latter sum
tends to 0 as n !1, and in the sum over
k 2 T
(n)
we have
(n)
k
2
n(S())
. The first sum can therefore
be bounded as follows:
X
k2T
ðnÞ
ðnÞ
k
h
ðnÞ
k
jD
ðnÞ
ð
e
P
n
Þj
ðnÞ
k
i
2
nðSðÞÞ
X
k
h
ðnÞ
k
jD
ðnÞ
ð
e
P
n
Þj
ðnÞ
k
i
¼ 2
nðSðÞÞ
tr D
ðnÞ
ð
e
P
n
Þ
¼ 2
nðSðÞÞ
tr
X
i
D
i
e
P
n
D
i
!
¼ 2
nðSðÞÞ
2
nR
½25
by the cyclic property of the trace and the fact that
P
i
D
i
D
i
= I and dim
e
H
n
= 2
nR
. h
Even for a quantum source with memory, reliable
data compression is achieved by looking for a
typical subspace T
(n)
of the Hilbert space H
n
for a
given >0. In the following subsections, we discuss
two different classes of such sources for which one
Source Coding in Quantum Information Theory 613
can find typical subspaces T
(n)
such that the fidelity
F
n
tends to 1 as n !1.
Ergodic Quantum Sources
A quantum generalization of classical ergodic
sources is defined as follows. First consider the
analog of an infinite sequence of random variables
which is a state on the infinite tensor product of a
finite-dimensional -algebra M. The latter is given
by the norm closure of the increasing sequence of
finite tensor products
M
1
¼
[
n
n
k¼n
M½26
A translation-invariant state
1
on M
1
is said to be
ergodic if it cannot be decomposed as a (nontrivial)
convex combination of other translation-invariant
states. The analog of the Kolmogorov–Sinai entropy
[5] for an ergodic state
1
is called the mean
entropy and is given by
S
M
ð
1
Þ¼lim
n!1
1
n
Sð
n
Þ¼inf
n2N
1
n
Sð
n
Þ½27
where
n
is the restriction of
1
to M
n
:= M
n
.
Following Hiai and Petz (1991), we define the
following quantity for any state on an arbitrary
finite-dimensional -algebra M and a given >0:
ðÞ¼infflog trðqÞ: q 2M; q
¼ q;
q
2
¼ q;ðqÞ1 g½28
We also define a state
1
on M
1
to be completely
ergodic if it is ergodic under transformations on M
1
,
induced by l-fold shifts on Z, for arbitrary l 2 N.The
following theorem is due to Hiai and Petz (1991),
who proved it in a slightly more general setting:
Theorem 6 (Hiai and Petz). Suppose that
1
is a
completely ergodic state on M
1
and d := dim M < 1,
and set
n
=
1
(
M
n
. Then, for any >0, the following
hold:
(i)
lim sup
n!1
1
n
ð
n
ÞS
M
ð
1
Þ½29
(ii)
lim inf
n!1
1
n
ð
n
ÞS
M
ð
1
Þ log d ½30
Proof of (i) Choose r > S
M
(
1
) and let < r
S
M
(
1
) and h = r . By the definition of S
M
(
1
),
there exists l 2 N such that S(
l
) < lh.Let{je
i
i}
ld
i = 1
be an orthonormal set of eigenvectors of
l
, with
corresponding eigenvalues
i
, that is, let
l
¼
X
ld
i¼1
i
p
i
½31
where p
i
= je
i
ihe
i
j is the projection onto je
i
i, be the
spectral decomposition for
l
. Denote the spectrum
X = {
i
}
ld
i = 1
. For n 2 N, introduce the probability
measures
n
on X
n
by
n
ðAÞ¼
nl
ðq
A
Þ½32
where, for any A X
n
,theprojectionq
A
is defined by
q
A
¼
X
ð
i
1
;...;
i
n
Þ2A
p
i
1
... p
i
n
½33
Similarly, we define
1
on X
Z
. The sequence of
random variables (X
n
)
n2Z
with distribution
1
is
then ergodic since
1
is completely ergodic (and
hence l-ergodic).
By the Shannon–McMillan–Breiman theorem
(Theorem 2),
1
n
log
n
ðfðx
1
; ...; x
n
ÞgÞ ! h
KS
½34
almost surely w.r.t.
1
,whereh
KS
is the Kolmogorov–
Sinai entropy. The latter is given by h
KS
= lim
n !1
(1=n)H
n
= inf
n2N
ð1/nÞH
n
,where
H
n
¼
X
ðx
1
;...;x
n
Þ2X
n
n
ðfðx
1
; ...; x
n
ÞgÞ
log
n
ðfðx
1
; ...; x
n
ÞgÞ ½35
Notice in particular that
h
KS
H
1
¼ Sð
l
Þ< lh ½36
If let T
(n)
be the (typical) subset of X
n
such that
1
n
log
n
ðfðx
1
; ...; x
n
ÞgÞ2ðh
KS
; h
KS
þ Þ½37
for (x
1
, ..., x
n
)2 T
(n)
then we have
1
(T
(n)
) 1
for n large enough. Moreover, since
n
({(x
1
, ..., x
n
)})
e
n(h
KS
þ)
for all (x
1
, ..., x
n
)2 T
(n)
, and the total
measure is 1,
jT
ðnÞ
je
nðh
KS
þÞ
e
nðlhþÞ
½38
It follows that tr(q
T
(n)
) e
n(lhþ)
whereas
nl
(q
T
(n)
) =
n
(T
(n)
) 1 and we conclude that
1
nl
ð
nl
Þ
nðlhþ Þ
nl
< r ½39
from which [29] follows upon taking n !1, since
r > S
M
(
1
) was arbitrary. (Notice that
(
n
)is
decreasing in n since M
n
M
nþ1
.)
&
Proof of (ii) Given , >0 and n 2 N, choose a
projection q
n
with
n
(q
n
) 1 and log tr(q
n
) <
(
n
) þ . Since S
M
(
1
) = inf (1=n)S(
n
) we have
614 Source Coding in Quantum Information Theory
S
M
(
1
) (1=n)S(
n
). We now use the following
lemma:
Lemma 7 If is a state on a finite-dimensional
-algebra M, and q 2Mis a projection, then
SðÞHðpÞþðqÞlog trðqÞ
þð1 ðqÞÞlog trð1 qÞ½40
where H(p) = p log p (1 p) log (1 p)(the bin-
ary entropy) with p = (q).
Proof First notice that if [
, q] = 0 then the result
[40] follows from the simple inequality:
X
m
i¼1
~
i
log
~
i
log m if
X
m
i¼1
~
i
¼ 1 ½41
Indeed, diagonalizing
, the eigenvalues
i
divide into
two subsets with corresponding eigenvectors belong-
ing to the range of q, respectively, its complement.
Considering the first set, we have, if m = dim (Ran(q)),
and taking
~
i
=
i
=(
P
m
i = 1
i
)in[41],
X
m
i¼1
i
log
i
X
m
i¼1
i
!
log
1
m
X
m
i¼1
i
!
¼trðq
Þ log trðq
Þlog trðqÞ
Adding the analogous inequality for the part of the
spectrum corresponding to 1 q, we obtain [40].
In the general case, that is, if [
, q] 6¼ 0, define
the unitary u = 2q 1 and the state
0
ðxÞ¼
1
2
½ðxÞþðuxuÞ ½42
Then [
0
, q] = 0 and by concavity of S() and the
result for the previous case
HðXÞþðqÞ log trðqÞ
þð1 ðqÞÞ log trð1 qÞSð
0
ÞSðÞ½43
since
0
(q) = (q).
&
Continuing with the proof of (ii), we conclude that
Sð
n
ÞHðpÞþ
n
ðq
n
Þlog trðq
n
Þ
þð1 ðq
n
ÞÞlog trð1 q
n
Þ
1 þ
ð
n
Þþ þ n log d
Dividing by n and taking the limit we obtain (30).
&
It follows from this theorem that we can define a
typical subspace in the same way as in Schumacher’s
theorem. Indeed, given >0 and >0, we have
that for n large enough, there exists a subspace T
(n)
equal to the range of a projection q
n
such that
n
(q
n
) > 1 and e
n(S
M
(
1
) log d)
< dim (T
(n)
) =
tr(q
n
)< e
n(S
M
(
1
)þ)
. The proof of the quantum
analog of the Shannon–McMillan theorem is then
similar to that of Schumacher’s theorem (Petz and
Mosonyi 2001, Bjelakovic
´
et al. 2004):
Theorem 8 Let
1
be a completely ergodic
stationary state on the infinite tensor product
algebra M
1
. If R > S
M
(
1
), then for any decom-
position of the form
ðnÞ
¼
X
p
ðnÞ
k
j
ðnÞ
k
ih
ðnÞ
k
j½44
there exists a reliable quantum code of rate R.
Conversely, if R < S
M
(
1
) then any quantum
compression–decompression scheme of rate R is
not reliable.
Remarks Theorem 6 also holds for higher-
dimensional information streams, with essentially
the same proof. (The existence of the mean entropy
is more complicated in that case.) The condition of
complete ergodicity in this theorem is unnecessary.
Indeed, Bjelakovic
´
et al. (2004) showed that the
result remains valid (also in more than one dimen-
sions) if the state
1
of the source is simply ergodic.
They achieved this by decomposing a general
ergodic state into a finite number of l-ergodic states,
and then applying the above strategy to each. It
should also be mentioned that a weaker version of
Theorem 6 was proved by King and Lesniewski
(1998). They considered the entropy of an asso-
ciated classical source, but did not show that this
classical entropy can be optimized to approximate
the von Neumann entropy. This had in fact already
been proved by Hiai and Petz (1991). The relevance
of the latter work for quantum information theory
was finally pointed out by Mosonyi and Petz (2001).
Source Coding for Quantum
Spin Systems
In this section we consider a class of quantum
sources modeled by Gibbs states of a finite strongly
interacting quantum spin system in Z
d
with
d 2. Due to the interaction between spins, the
density matrix of the source is not given by a tensor
product of the density matrices of the individual
spins and hence the quantum information source is
non-i.i.d. We consider the density matrix to be
written in the standard Gibbsian form:
!;
¼
e
H
!
!;
½45
where >0 is the inverse temperature. Here !
denotes the boundary condition, that is, the config-
uration of the spins in
c
= Z
d
n, and H
!
is the
Hamiltonian acting on the spin system in under
this boundary condition. (see Datta and Suhov (2002)
Source Coding in Quantum Information Theory 615
for precise definitions of these quantities). The
denominator on the right-hand side of [45] is the
partition function.
Note that any faithful density matrix can be
written in the form [45] for some self-adjoint
operator H
!
with discrete spectrum, such that
e
H
!
is trace class. However, we consider H
!
to
be a small quantum perturbation of a classical
Hamiltonian and require it to satisfy certain
hypotheses (see Datta and Suhov (2002)). In
particular, we assume that H
= H
0
þ V
, where
(1) H
0
is a classical, finite-range, translation-
invariant Hamiltonian with a finite number of
periodic ground states, and the excitations of these
ground states have an energy proportional to the
size of their boundaries (Peierls condition); (2) V
is a translation-invariant, exponentially decaying,
quantum perturbation, being the perturbation
parameter. These hypotheses ensure that the quan-
tum Pirogov–Sinai theory of phase transitions in
lattice systems (see, e.g., Datta et al. (1996)) applies.
The power of quantum Pirogov–Sinai theory is
such that, in proving reliable data compression for
such sources, we do not need to invoke the concept
of ergodicity.
Using the concavity of the von Neumann entropy
S(
!,
), one can prove that the von Neumann
entropy rate (or mean entropy) of the source
h :¼ lim
%Z
d
Sð
!;
Þ
jj
exists. For a general van Hove sequence, this follows
from the strong subadditivity of the von Neumann
entropy (see, e.g., Ohya and Petz (1993)).
Let
!,
have a spectral decomposition
!;
¼
X
j
j
j
j
ih
j
j
where the eigenvalues
j
,1 j 2
jj
, and the
corresponding eigenstates j
j
i, depend on ! and .
Let P
!,
denote the probability distribution {
j
} and
consider a random variable K
!,
which takes a value
j
with probability
j
:
K
!;
ð
j
Þ¼
j
; P
!;
ðK
!;
¼
j
Þ¼
j
The data compression limit is related to asympto-
tical properties of the random variables K
!,
as
% Z
d
. As in the case of i.i.d. sources, we prove
the reliability of data compression by first proving
the existence of a typical subspace. The latter
follows from Theorem 9 below. The proof of this
crucial theorem relies on results of quantum
Pirogov–Sinai theory (Datta et al. 1996).
Theorem 9 Under the above assumptions, for
large and small enough, for all >0
lim
%Z
d
P
!;
1
jj
log K
!;
h
¼ lim
%Z
d
X
j
j
fjjj
1
log
j
hjg
¼1 ½46
where
{...}
denotes an indicator function.
Theorem 9 is essentially a law of large numbers
for random variables (log K
!,
). The statement of
the theorem can be alternatively expressed as
follows. For any >0,
lim
%Z
d
P
!;
2
jjðhþÞ
K
!;
2
jjðhÞ
¼ 1 ½47
Thus, we can define a typical subspace T
!,
by
T
!;
:¼ span fj
j
i: 2
jjðhþÞ
j
2
jjðhÞ
g½48
It clearly satisfies the analogs of (i) and (ii) of the
typical subspace theorem, which implies as before
that a compression scheme of rate R is reliable if and
only if R > h.
Universal and Variable Length Data Compression
Thus far we discussed source-dependent data com-
pression for various classes of quantum sources. In
each case data compression relied on the identifica-
tion of the typical subspace of the source, which in
turn required a knowledge of its density matrix. In
classical information theory, there exists a general-
ization of the theorem of typical sequences due to
Csisza´r and Ko¨rner (1981) where the typical set is
universal, in that it is typical for every possible
probability distribution with a given entropy. This
result was used by Jozsa et al. (1998) to construct a
universal compression scheme for quantum i.i.d
sources with a given von Neumann entropy S using
a counting argument for symmetric subspaces. This
was generalized to ergodic sources by Kaltchenko
and Yang (2003) along the lines of Theorem 6.
Hayashi and Matsumoto (2002) supplemented the
work of Jozsa et al. (1998) with an estimation of the
eigenvalues of the source (using the measurement
smearing technique) to show that a reliable compres-
sion scheme exists for any quantum i.i.d source,
independent of the value of its von Neumann entropy
S, the limiting rate of compression being given by S.If
one admits variable length coding, the Lempel–Ziv
algorithm gives a completely universal compression
scheme, independent of the value of the entropy, in
the classical case (Cover and Thomas 1991). This
algorithm was generalized to the quantum case for
i.i.d sources by Jozsa and Presnell (2003),andto
616 Source Coding in Quantum Information Theory
sources modeled by Gibbs states of free bosons or
fermions on a lattice by Johnson and Suhov (2002).
Another important question is the efficiency of the
various coding schemes. The above-mentioned
schemes for quantum i.i.d. sources are not efficient,
in the sense that they have no polynomial time
implementation. Recently, it was shown by Bennett
et al. (2004) that an efficient, universal compression
scheme for i.i.d sources can be constructed by
employing quantum state tomography.
Acknowledgment
The authors would like to thank Y M Suhov for
helpful discussions.
See also: Capacity for Quantum Information; Channels in
Quantum Information Theory; Positive Maps on C
-Algebras.
Further Reading
Bennett CH, Harrow AW, and Lloyd S (2004) Universal quantum
data compression via gentle tomography, quant-ph/0403078.
Bjelakovic
´
I, Kru¨ ger T, Siegmund-Schultze R, and Szkoła A
(2004) The Shannon–McMillan theorem for ergodic quantum
lattice systems. Inventiones Mathematicae 155: 203–222.
Breiman L (1957) The individual ergodic theorem of information
theory. Annals of Mathematical Statistics 28: 809–811.
Breiman L (1960) The individual ergodic theorem of information
theory – correction note. Annals of Mathematical Statistics 31:
809–810.
Cover TM and Thomas JA (1991) Elements of Information
Theory. New York: Wiley.
Csisza´r I and Ko¨ rner J (1981) Information Theory. Coding
Theorems for Discrete Memoryless Systems. Budapest:
Akade´miai Kiado´.
Datta N, Ferna´ndez R, and Fro¨ hlich J (1996) Low-temperature
phase diagrams of quantum lattice systems. I. Stability for
quantum perturbations of classical systems with finitely-many
ground states. Journal of Statistical Physics 84: 455–534.
Datta N and Suhov Y (2002) Data compression limit for an
information source of interacting qubits. Quantum Informa-
tion Processing 1(4): 257–281.
Hayashi M and Matsumoto K (2002) Quantum universal
variable-length source coding. Physical Review A 66: 022311.
Hiai F and Petz D (1991) The proper formula for the relative
entropy and its asymptotics in quantum probability. Commu-
nications in Mathematical Physics 143: 257–281.
Johnson O and Suhov YM (2002) The von Neumann entropy and
information rate for integrable quantum Gibbs ensembles.
Quantum Computers and Computing 3/1: 3–24.
Jozsa R, Horodecki M, Horodecki P, and Horodecki R (1998)
Universal quantum information compression. Physical Review
Letters 81: 1714–1717.
Jozsa R and Presnell S (2003) Universal quantum information
compression and degrees of prior knowledge. Proceedings of
Royal Society of London Series A 459: 3061–3077.
Kaltchenko A and Yang E-H (2003) Universal compression of
ergodic quantum sources. Quantum Information & Computa-
tion 3: 359–375.
King C and Lesniewski A (1998) Quantum sources and a quantum
coding theorem. Journal of Mathematical Physics 39: 88–101.
McMillan B (1953) The basic theorems of information theory.
Annals of Mathematical Statistics 24: 196–219.
Nielson MA and Chuang IL (2000) Quantum Computation and
Quantum Information. Cambridge: Cambridge University Press.
Ohya M and Petz D (1993) Quantum Entropy and Its Use.
Heidelberg: Springer.
Petz D and Mosonyi M (2001) Stationary quantum source coding.
Journal of Mathematical Physics 42: 4857–4864.
Schumacher B (1995) Quantum coding. Physical Review A 51:
2738–2747.
Shannon CE (1918) A mathematical theory of communication.
Bell System Technical Journal 27: 379–423, 623–656.
Spacetime Topology, Causal Structure and Singularities
R Penrose, University of Oxford, Oxford, UK
ª 2006 Elsevier Ltd. All rights reserved.
The Value of Topological Reasoning
in General Relativity
Solving the equations of Einstein’s general relativity
(see General Relativity: Overview) can be an exceed-
ingly complicated business; it is commonly found
necessary to resort to numerical solutions involving
very complex computer codes (see Computational
Methods in General Relativity: The Theory). The
essential content of the basic equations of the theory
itself is, however, something that can be phrased in
simple geometrical terms, using only basic concepts
of differential geometry (see General Relativity:
Overview). By virtue of this, it is sometimes the
case, in general relativity, that geometrical arguments
of various kinds – including purely topological ones
(i.e., arguments depending only upon the properties
of continuity or smoothness) – can be used to great
effect to obtain results that are not readily accessible
by standard procedures of differential equation
theory or by direct numerical calculation.
One particularly significant family of situations
where this kind of argument has a key role to play is
in the important issue of the singularities that arise
in many solutions of the Einstein equations, in
which spacetime curvatures may be expected to
diverge to infinity. These are exemplified, particu-
larly, by two important classes of solutions of the
Spacetime Topology, Causal Structure and Singularities 617
Einstein field equations in which singularities arise.
In the first instance, we have cosmological models,
which tend to exhibit the presence of an initial
singularity referred to as the ‘‘Big Bang,’’ as was first
noted in the standard Friedmann models (which are
solutions of the Einstein equations with simple
matter sources; see Cosmology: Mathematical
Aspects). Secondly, we find a final singularity (for
local observers) at the endpoint of gravitational
collapse to a black hole (where in the relevant
region, outside the collapsing matter, Einstein’s
vacuum equations are normally taken to hold). In
either case, there are canonical exact models, in
which considerable symmetry is assumed, and where
the models indeed become singular at places where
the spacetime curvature diverges to infinity. For
many years (prior to 1965), there had been much
debate as to whether these singularities were an
inevitable feature of the general physical situation
under consideration, or whether the presence of
singularities might be an artifact of the assumed
high symmetry. The use of topological-type argu-
ments has established that, in general terms, the
occurrence of a singularity is not merely an artifact
of symmetry, and cannot generally be removed by
the introduction of small (finite) perturbations.
Let us first consider the standard picture, put
forward in 1939 by Oppenheimer and Snyder (OS),
of the gravitational collapse of an over-massive star
to a black hole; see Figure 1 (and see Stationary
Black Holes). This assumes exact spherical symme-
try. The region external to the matter is described by
the well-known Schwarzschild solution of the
Einstein vacuum equations, appropriately extended
to inside the ‘‘Schwarzschild radius’’ r = 2mG=c
2
(G being Newton’s gravitational constant and c , the
speed of light, and where m is the total mass of
the collapsing material; from now, for convenience,
we choose units so that G = c = 1). In Figure 1,
this internal extension is conveniently expressed
using Eddington–Finkelstein coordinates (r, v, , )
(see Eddington (1924) and Finkelstein (1958)),
where v = t þ r þ 2m log (r 2m), the metric form
being
ds
2
¼ð1 2m=rÞdv
2
2dv dr
r
2
ðd
2
þ sin
2
d
2
Þ
(The signature convention þ is being adopted
here; see General Relativity: Overview.) We find
that, in this model, there is a singularity (at r = 0) at
the future endpoint of each world line of collapsing
matter. Moreover, no future-timelike line starting
inside the horizon can avoid reaching the singularity
when we try to extend it, as a timelike curve,
indefinitely into the future, where the ‘‘horizon’’ is
the three-dimensional region obtained by rotating,
over the (, ) 2-sphere, the null (lightlike) line
which is r = 2m outside the matter region and which
is the extension of this line, as a null line, into the
past until it meets the axis. It is easy to see that any
observer’s world line within this horizon is indeed
trapped in this sense.
The question naturally arises: how representative
is this model? Here, the singularity occurs at the
center (r = 0), the place where all the matter is
directed, and where it all reaches without rebound-
ing. So it may be regarded as unsurprising that the
density becomes infinite there. Now, let us suppose
that the collapsing material is not exactly spherically
symmetrical. Even if it is only slightly (though
finitely) perturbed away from this symmetrical
situation, having slight (but finite) transverse
motions, the collapsing matter is now not all
directed exactly towards the center, as it is in the
OS model. One might imagine that the singularity
Horizon
Observe
r
Horizon
Singularity
Collapsing
matter
Figure 1 Spacetime diagram of collapse to a black hole.
(One spatial dimension is suppressed.) Matter collapses inwards,
through the 3-surface that becomes the (absolute) event horizon.
No matter or information can escape the hole once it has been
formed. The null cones are tangent to the horizon and allow
matter or signals to pass inwards but not outwards. An external
observer cannot see inside the hole, but only the matter – vastly
dimmed and redshifted – just before it enters the hole.
(Reproduced with permission from Penrose R. (2004) The Road
to Reality : a Complete Guide to the Laws of the Universe.
London: Jonathan Cape.)
618 Spacetime Topology, Causal Structure and Singularities
could now be avoided, the different portions of
matter just ‘‘missing’’ each other and then being
finally flung out again, after some complicated
motions, where the density and spacetime curvatures
might well become large but presumably still finite.
To follow such an irregular collapse in full detail
would present a very difficult task, and one would
have to carry it out by numerical means. As yet,
despite enormous advances in computational tech-
nique, a fully effective simulation of such a
‘‘generic’’ collapse is still not in hand. In any case,
it is hard to make a convincing case as to whether or
not a singularity arises, because as soon as metric or
curvature quantities begin to diverge, the computa-
tion becomes fundamentally unreliable and simply
‘‘gives up.’’ So we cannot really tell whether the
failure is due to some genuine divergence or whether
it is an artifact. It is thus fortunate that other
mathematical techniques are available. Indeed, by
use of a differential–topological–causal argument,
we find that such perturbations do not help, at least
so long as they are small enough not to alter the
general character of the collapse, which we find has
an ‘‘unstoppable’’ character, so long as a certain
criterion is satisfied its early stages.
Trapped Surfaces
But how are we to characterize the collapse as
‘‘unstoppable,’’ where no symmetries are to be
assumed, and the simple picture illustrated in
Figure 1 cannot be appealed to? A convenient
characterization is the presence of what is called a
‘‘trapped surface.’’ This notion generalizes a key
feature of the 0 < r < 2m region inside the horizon
of the vacuum (Eddington–Finkelstein) picture of
Figure 1. To understand what this feature is,
consider fixing a point s in the vacuum region of
the (v, r)-plane of Figure 1. We must, of course, bear
in mind that, because this plane is to be ‘‘rotated’’
about the central vertical axis (r = 0) by letting and
vary as coordinates on a 2-sphere S
2
, the point s
actually describes a closed 2-surface S (coordina-
tized by and ) with topology S
2
(so S is
intrinsically an ordinary 2-sphere). We shall be
concerned with the region I
þ
(S), which is the
(chronological) ‘‘future’’ of S, that is, the locus of
points q for which a timelike curve exists having a
future endpoint at q and a past endpoint on S.We
shall also be interested, particularly, in the boundary
@I
þ
(S)ofI
þ
(S). This boundary is described, in
Figure 1, by the pair of null curves v = const. and
2r þ 4m log (r 2m) = const., proceeding into the
future from s (and rotated in and ). The region
I
þ
(S) itself is represented by that part of Figure 1
which lies between these null curves.
We observe that, in this symmetrical case (s being
chosen in the vacuum region), a characterization of s
as being ‘‘trapped,’’ in the sense that it lies in a
region that is within the horizon, is that the future
tangents to these null curves both point ‘‘inwards,’’
in the sense of decreasing r. Since r is the metric
radius of the S
2
of rotation, so that the element of
surface area of this sphere is proportional to r
2
,it
follows that the surface area of the boundary @I
þ
(S)
reduces, on both branches, as we move away from S
into the future. The three-dimensional region @I
þ
(S)
consists of two null surfaces joined along S,in
the sense that their Lorentzian normals are null
4-vectors. For each fixed value of and , this
normal is a tangent to one or other of the two null
curves of Figure 1, starting at s. For a trapped s,
these normals point in the direction of decreasing r,
and it follows that the divergence of these normals is
negative (so >0 in what follows below).
In the general case, it is this property of negativity
of the divergence, at S, of both sets of Lorentzian
normals (i.e., of null tangents to @I
þ
(S)), that
characterizes S as a trapped surface, where in the
general case we must also prescribe S to be compact
and spacelike. But now there are to be no assump-
tions of symmetry whatever. Such a characterization
is stable against small, but finite, perturbations of
the location of S, within the spacetime manifold M,
and also against small, but finite, perturbations of M
itself.
We can think of a trapped surface in more direct
physical/geometrical terms. Imagine a flash of light
emitted all over some spacelike compact spherical
surface such as S, but now in ordinary flat space-
time, where for simplicity we suppose that S is
situated in some spacelike (flat) 3-hypersurface H,of
constant time t = 0. There will be one component to
the flash proceeding outwards and another proceed-
ing inwards. Provided that S is convex, the outgoing
flash will represent an initial increase of the surface
area at every point of S and the ingoing flash, an
initial decrease. In four-dimensional spacetime
terms, we express this as positivity of the divergence
of the outward null normal and the negativity of the
divergence of the inward one. The characteristic
feature of a trapped surface is that whereas the
ingoing flash will still have an initially reducing
surface area, the ‘‘outgoing’’ flash now has the
curious property that its surface area is also initially
decreasing, this holding at every point of S.
Locally, this is not particularly strange. For a
surface wiggling in and out, we are quite likely to
find portions of ingoing flash with increasing area,
Spacetime Topology, Causal Structure and Singularities 619
and portions of outgoing flash with decreasing area.
An extreme case in Minkowski spacetime has S as the
intersection of two past light cones. All the null
normals to S point along the generators of these past
cones, and therefore all converge into the future. Such
asurfaceS (indeed spacelike) looks ‘‘trapped’’ every-
where locally, but fails to count as trapped, not being
compact. Since there is nothing causally extreme about
Minkowski space, it is appropriate not to count such
surfaces as ‘‘trapped.’’ What is the peculiar about a
trapped surface is that both ingoing and outgoing
flashes are initially decreasing in area, over the entire
compact S.(N.B.Hawking and Ellis (1973) adopt a
slightly different terminology; the term ‘‘trapped,’’
used here, refers to their ‘‘closed trapped.’’)
The Null Raychaudhuri Equation
What do we deduce from the existence of a trapped
surface? A glance at Figure 1 gives us some
indication of the trouble. As we trace @I
þ
(S) into
the future, we find that its cross-sectional area
continues to decrease, until becoming zero at the
central singularity. This last feature need not reflect
closely what happens in more general cases, with no
spherical symmetry. But the reduction in surface
area is a general property. This is the first point to
appreciate in a theorem (Penrose 1965, 1968,
Hawking and Ellis 1973) which indicates the
profoundly disturbing physical implications of the
existence of a trapped surface in physically realistic
gravitational collapse, according to Einstein’s gen-
eral relativity. The surface-area reduction arises
from a result known as ‘‘Raychaudhuri’s equation,’’
in the case of null rays – where we refer to this as
the ‘‘Sachs’’ equations. We come to this next.
Although many different notations are used to
express the needed quantities, we can here conve-
niently employ the spin-coefficient formalism, as
described elsewhere in this Encyclopedia (see Spi-
nors and Spin Coefficients).
Suppose that we have a congruence (smooth three-
parameter family) of rays (null geodesics) in four-
dimensional spacetime. Let ‘
a
be a real future-null
vector, tangent to a null geodesic of the congruence,
and let m
b
be complex-null, also defined along ,
where its real and imginary parts are unit vectors
spanning a 2-surface element orthogonal to ‘
a
at each
point of ,sowehave
‘
a
‘
a
¼ 0;‘
a
m
a
¼ 0;
m
a
m
a
¼ 0;
m
a
m
a
¼1;
‘
a
¼
‘
a
where it is assumed that each of ‘
a
, m
a
is parallel-
propagated along :
‘
a
r
a
‘
b
¼ 0;‘
a
r
a
m
b
¼ 0
(r
a
denoting covariant derivative). The spin-coefficient
quantities
¼ m
a
m
b
r
a
‘
b
and ¼ m
a
m
b
r
a
‘
b
are of importance. Here, the real part of measures the
convergence of the congruence and the imaginary part
defines its rotation; measures its shear, where the
argument of defines the direction (perpendicular
to ) of the axis of shear, and whose strength is defined
by jj (see Penrose and Rindler (1986) for a graphic
description of these quantities). Defining propagation
derivative along by
D ¼ ‘
a
r
a
we can write the Sachs equations as
D ¼
2
þ þ
D ¼ 2 þ
where =(1=2)R
ab
‘
a
‘
b
and =C
abcd
‘
a
m
b
‘
c
m
d
,
conventions for the Ricci tensor R
ab
and the Weyl
tensor C
abcd
being those of General Relativity:
Overview (and of Penrose and Rindler (1984)). We
note that it is the real Ricci component which
governs the propagation of the divergence and the
complex Weyl component which governs the
propagation of shear, though there are some non-
linear terms. The quantity is normally taken non-
negative, since it measures the energy flux across
(with, in fact =4GT
ab
‘
a
‘
b
,whereT
ab
is the
energy tensor). The condition that 0 at all points
of spacetime and for all null directions ‘
a
,iscalled
the ‘‘weak energy condition.’’ (Again there is a minor
discrepancy with Hawking and Ellis (1973) who
adopt a somewhat stronger ‘‘weak energy condition,’’
which is the above but where ‘
a
is also allowed to be
future-timelike. Unfortunately, with this terminology,
their ‘‘weak energy condition’’ is not strictly weaker
than their ‘‘strong energy condition.’’)
It will now be assumed that is real:
¼
which is always the case for propagation along the
generators of a null hypersurface. The weak energy
condition then has an important implication for us.
We find that if A is an element of 2-surface area
within the plane spanned by the real and imaginary
parts of m
a
, then (this area element being propa-
gated by D along the lines )
DA
1=2
¼A
1=2
620 Spacetime Topology, Causal Structure and Singularities
As a consequence, assuming 0,
D
2
A
1=2
¼ð þ ÞA
1=2
0
This tells us that once the divergence () becomes
negative, then the area element must reduce to zero
sometime in the future along , assuming that is
future-null-complete in the sense that it extends to
indefinitely large values of an affine parameter u
defined along it, where an affine parameter asso-
ciated with the parallel-propagated ‘
a
satisfies
‘
a
r
a
u ¼ 1
Such a place where the cross-sectional area pinches
down to zero is a singularity of the congruence or null
hypersurface, referred to as a ‘‘caustic.’’ (There are
also terminological confusions arising from different
authors defining the term ‘‘caustic’’ in slightly
different ways. The terminology used here is slightly
discrepant from that of Arnol’d (1992) (Chapter 3).)
From this property, it follows that if we have a
trapped surface S, then every generator of @I
þ
(S), if
extended indefinitely into the future, must eventually
encounter a caustic. This, so far, tells us nothing about
actual singularities in the spacetime M; even Minkowski
space contains many null hypersurfaces with multitudes
of caustic points. However, caustics do tell us some-
thing significant about sets like @I
þ
(S), which are the
boundaries of future sets, and we come to this shortly.
Causality Properties
First, consider the basic causal relations. If a an b
are two points of M, then if there is a nontrivial
future-timelike curve in M from a to b we say that a
‘‘chronologically’’ precedes b and write
a b
(so it would be possible for some observer’s world line
to encounter first a and then b). If there is a future-null
curve in M from a to b (trivial or otherwise), we say that
a ‘‘causally’’ precedes b and write
a b
(so it would be possible for a signal to get from a to
b). We have the following elementary properties (see
Penrose (1972)):
a a
if a b then a b
if a b and b c then a c
if a b and b c then a c
if a b and b c then a c
if a b and b
c then a c
We generalize the definition of I
þ
(S), above, to an
arbitrary subset Q in M, obtaining the chronological
future I
þ
(Q)andpast I
(Q)ofQ in M by
I
þ
ðQÞ¼fqjp q for some p 2 Qg
I
ðQÞ¼fqjq p for some p 2 Qg
The notation {qj some property of q} denotes the set
of q’s with the stated property and the causal future
J
þ
(Q) and past J
(Q)ofQ in M by
J
þ
ðQÞ¼fqjp q for some p 2 Qg
J
ðQÞ¼fqjq p for some p 2 Qg
The I
(Q) are always open sets, but the J
(Q) are not
always closed (though they are for any closed set Q in
Minkowski space). Thus, the sets I
(Q) have a more
uniform character than the J
(Q), and it is simpler to
concentrate, here, on the I
(Q)sets.
The boundary @I
þ
(Q)ofI
þ
(Q) has an elegant
characterization:
@I
þ
ðQÞ¼fqjI
þ
ðqÞ@I
þ
ðQÞ; but q =2I
þ
ðQÞg
and the corresponding statement holds for @I
(Q).
Boundaries of futures also have a relatively simple
structure, as is exhibited in the following result (for
which there is also a version with past and future
interchanged):
Lemma Let Q M be closed, and p 2 @I
þ
(Q) Q,
then there exists a null geodesic on @I
þ
(Q) with
future endpoint at p and which either extends along
@I
þ
(Q) indefinitely into the past, or until it reaches a
point of Q. It can only extend into the future along
@I
þ
(Q) if p is not a caustic point of @I
þ
(Q).
Beyond a caustic point, the null geodesic would
enter into the interior of I
þ
(Q), but this also happens
(more commonly) when crossing another region of
null hypersurface on @I
þ
(Q).
We wish to apply this to @I
þ
(S), for a trapped
surface S, but we first need a further assumption that S
lies in the interior of the (future) domain of dependence
D
þ
(H) of some spacelike hypersurface H. This region is
defined as the totality of points q for which every
timelike curve with future endpoint q can be extended
into the past until it meets H. One can consider domains
of dependence for regions H other than smooth space-
like surfaces, but it is usual to assume, more generally,
that H is a closed achronal set, where ‘‘achronal’’ means
that H contains no pair of points a, b for which a b.
We find that every point q in the interior intD
þ
(H)of
D
þ
(H) has the further property that all null curves into
the past from q will also eventually meet H if extended
sufficiently. The physical significance of D
þ
(H)isthat,
for fields with locally Lorentz-invariant and determi-
nistic evolution equations, the (appropriate) initial data
on H will fix the fields throughout D
þ
(H) (and also
Spacetime Topology, Causal Structure and Singularities 621