Francoise J.-P., Naber G.L., Tsun T.S. (editors) Encyclopedia of Mathematical Physics
Подождите немного. Документ загружается.
Extensions
Caustics in Spaces of Higher Dimension
The local classification of Lagrangian singularities
has been extended in spaces of higher dimension.
For n = 4, in addition to the preceding ones, two
new singularities app ear: the butterfly A
5
and the
parabolic umbilic D
5
. For n = 5, in addition to A
6
and D
6
, one has a new type of umbilic: E
6
.
However, in higher dimensions, the classification
becomes more complex. In addition to stable
singularities, like those of the series A
i
, D
i
, E
i
, one
encounters unstable generic singularities which
depend on arbitrary parameters (moduli). Despite
this difficulty, there exists a classification of generic
Lagrangian singulariti es up to the dimension n = 10.
The Maslov index has been extended in spaces of
higher dimension and has led to the discovery of
invariants associated with particular types of singu-
larities (Vassilyev 1988). These invariants control
the number of some types of singularities. For
instance, in dimension n = 4, the number of A
5
(taking account of sign) is equal to zero.
Symmetrical Caustics
Another extension consists in imposing some
constraint, for instance, a symmetry (Janeczko and
Roberts 1993). Symmetrical caustics are not merely
the symmetrized usual caustics. Many of them result
from the stabilization of unstable singularities of
higher codimension by the symmetry. For example,
in the 3D space, the butterfly A
5
is unstable, but the
symmetrical butterfly is a generic singularity in the
class of Lagrangian singularities having the mirror
symmetry.
Nonoptical Caustics
Caustics, as locus of focalization, are not restricted
to the usual optics. They are also observed in
electronic optics or in gravitational optics and the
preceding results apply to these waves. They also
appear in nonelectromagnetic waves, for instance,
acoustic waves, seismic waves, etc. Propagation
always generates caustics.
Optical caustics are now understood as Lagran-
gian singularities and, as singularities, their interest
is not restricted to optics. They became indispen-
sable for understanding other domains of mathema-
tical physics, for inst ance, the variational calculus,
the classical mechanics, the Hamilton–Jacobi equa-
tions, the control theory, the field theory, etc.
See also: Billiards in Bounded Convex Domains; Normal
Forms and Semiclassical Approximation; Stationary
Phase Approximation; Singularity and Bifurcation Theory.
Further Reading
Arnol’d VI (1972) Normal forms for functions near degenerate
critical points, the Weyl groups A
k
; D
k
; E
k
and Lagrangian
singularities. Functional Analysis and its Applications 6:
254–272.
Arnol’d VI (1983) Singularities of systems of rays. Uspekhi
Matematicheskykh Nauk 38: 77–147.
Arnol’d VI (1990) Singularities of Caustics and Wave Fronts,
Math. Appl. (Soviet Series), vol. 62. Dordrecht: Kluwer
Academic.
Arnol’d VI, Gusein-Zade SM, and Varchenko AN (1985)
Singularities of Differentiable Maps, Volume I, Monographs
in Mathematics, vol. 82. Boston: Birkha¨ user.
Bennequin D (1986) Caustique Mystique, Sie´minaire Bourbaki,
37e anne´e, no. 634, S.M.F., Aste´risque 133–134, pp. 19–56.
Berry MV and Upstill C (1980) Catastrophe optics: morphologies
of caustics and their diffraction patterns. In: Wolf E (ed.)
Progress in Optics XVIII, pp. 257–346. Amsterdam: North-
Holland Publishing Company.
Chekanov Yu V (1986) Caustics in geometrical optics. Functional
Analysis and its Applications 6: 223–226.
Guillemin V and Sternberg S (1977) Geometric Asymptotics,
Mathematical Surveys and Monographs, vol. 14. Providence:
American Mathematical Society.
Janeczko S and Roberts M (1993) Classification of symmetric
caustics II: caustic equivalence. Journal of the London
Mathematical Society 48: 178–192.
Joets A and Ribotta R (1995) Structure of caustics studied using the
global theory of singularities. Europhysics Letters 29: 593–598.
Joets A and Ribotta R (1996) Experimental determination of a
topological invariant in a pattern of optical singularities.
Physical Review Letters 77: 1755–1758.
Kravtsov Yu A and Orlov Yu I (1993) Caustics, Catastrophes and
Wave Fields, Wave Phenomena, vol. 15. Berlin: Springer.
Maslov VP and Fedoriuk MV (1981) Semi-classical approxima-
tion in quantum mechanics. In: Mathematical Physics and
Applied Mathematics, vol. 7. Dordrecht: D Reidel Publishing
Company.
Nye JF (1999) Natural Focusing and Fine Structure of Light.
Bristol: Institute of Physics Publishing.
Thom R (1956) Les singularite´s des applications diffe´rentiables.
Annales de l’Institut Fourier 6: 43–87.
Thom R (1969) Topological models in biology. Topology 8:
313–335.
Vassilyev VA (1988) Lagrange and Legendre characteristic classes.
Advanced Studies in Contemporary Mathematics,vol.3.New
York: Gordon and Breach Science Publishers.
Whitney H (1955) On singularities of mappings of Euclidean
spaces. I. Mappings of the plane into the plane. Annals of
Mathematics 62: 374–410.
Optical Caustics 627
Optimal Cloning of Quantum States
M Keyl, Universita
`
di Pavia, Pavia, Italy
ª 2006 Elsevier Ltd. All rights reserved.
Introduction
According to the well-known ‘‘no-cloning theorem’’
(Wootters and Zurek 1982) perfect copying of
quantum information is impossible, that is, there is
no machine which takes a quantum system in an
unknown state as input and produces two systems of
the same kind, such that none of them is distinguish-
able from the input by a statistical experiment. In
this qualitative form, however, the theorem is not
very useful, because in the presence of noise classical
information cannot be copied perfectly as well.
Therefore, the crucial point is that even under ideal
conditions the errors produced in the clones cannot
be made arbitrarily small. The best we can hope for
is to find an optimal cloning device which makes
these errors as small as possible.
More generally, we can consider cloning devices,
which take as input a certain number, N,of
identically prepared systems, and produce a larger
number, M, of systems as output. Again, the
cloning task is to make the output state resemble
as much as possible a state of M systems all
prepared in the same state as the inputs. This
variant of the problem is of interest as a ‘‘quantum
amplifier.’’ It also has a better chance of reasonable
success than a cloning device operating on single-
input systems: in the limit of many-input systems,
the device can make a good statistical estimate of
the input density matrix and hence produce
arbitrarily good clones.
Figures of Merit
To get a precise mathematical description of the
problem, let us consider a one-particle Hilbert
space H (which is assumed to be finite dimen-
sional, H= C
d
, if nothing else is explicitly stated)
and the algebras B(H
N
), B(H
M
) of (bounded)
operators on the N-fold, respectively M-fold,
tensor product of H. A quantum operation which
takes N particles as input and produces M output
particles is then described, in the Heisenberg
picture, by a completely positive, unital map (a
completely positive, unital and normal map if H is
infinite dimensional):
T : BðH
M
Þ!BðH
N
Þ½1
while the Schro¨ dinger picture representation is given
in terms of the (pre-)dual of T, that is,
T
: B
ðH
N
Þ!B
ðH
M
Þ½2
where B
( ) denotes the space of trace-class
operators. Hence, if T operates on input systems in
the (joint) state
N
, the output systems (i.e., the
‘‘clones’’) are in the state T
(
N
). We will call each
such T a cloning map.
Now our aim is to find an operation T such that
the output state T
(
N
) approximates the product
state
M
as well as possible. The quality of the
approximation is measured by a distance function
on the convex set S(H
M
) B
(H
M
) of density
operators on H
M
and, since it is impossible to
minimize (T
(
N
),
M
) for all simultaneously,
we are looking only for the worst case. Hence, the
quality of a cloning map T is measured by a figure
of merit of the form
X;
ðTÞ¼sup
2X
T
ð
N
Þ;
M
½3
Here X S(H) is a set of ‘‘preferred’’ density
operators whose role will be explained in the next
section. An optimal cloning device is described by a
cloning map
^
T which minimizes
X,
, that is,
X;
ð
^
TÞ
X;
ðTÞ½4
should hold for each cloning map T.
The Preferred Set of States
The set X S(H) of density operators introduced in
the last equation describe a priori knowledge about
the one-particle input state ; for example, if we
want to clone only signal states
1
, ...,
k
used to
transmit classical information through a quantum
channel, the choice for X is {
1
, ...,
k
}. Other
possibilities include: X = S(H) if nothing is known
about , the set of pure states, the states in the
‘‘equatorial plane’’ of the Bloch sphere, or Gaussian
states if H is infinite dimensional. Each different
choice for X leads to a different variant of the
cloning problem, and we will summarize the most
relevant cases treated in the literature in the section
‘‘Examples.’’
A different kind of a priori knowledge is a priori
measures, that is, instead of knowing that all
possible input states lie in a special set X, we know
for each measurable set X S(H) the probability
(X) for 2 X. Such a situation typically arises
when we are trying to clone states of systems which
628 Optimal Cloning of Quantum States
originate from a source with known characteristics.
In this case, we can use mean errors,
;
ðTÞ¼
Z
SðHÞ
T
ð
N
Þ;
M
ðdÞ½5
as a figure of merit. Sometimes these are easier to
compute than maximal errors as in eqn [3]. Often,
however, leads to stronger results than
,
therefore we will concentrate our discussion on
maximal rather than mean errors.
The Distance Measure
The remaining freedom in eqn [3] is the distance
measure and there are mainly two physically
different choices: we can either check the quality of
each clone separately or we can test, in addition, the
correlations between output systems. The most
common choice for a figure of merit for the first
type is given by (where
^
tr
j
denotes partial trace over
all but the jth tensor factor)
1
ðTÞ¼sup
2X;j
1 F
^
tr
j
T
ð
N
Þ;
½6
Here F(, ) denotes the (quadratic) fidelity of and
, that is,
Fð; Þ¼tr
1=2
1=2
1=2
2
½7
and the supremum is taken over all 2 X and
j = 1, ..., N.
1
measures the worst one-particle
error of the output state T
(
N
), and we will refer
to it in the following as the local error. If we are
interested in correlations too, we have to choose
all
ðTÞ¼sup
2X
1 F T
ð
N
Þ;
M
½8
all
measures again a ‘‘worst-case’’ error, but now
of the full output with respect to M uncorrelated
copies of the input . We will call it the global error.
Alternative figures of merit arise if we replace the
fidelity in eqns [6] and [8] by other distance
measures like the trace norm, the Hilbert–Schmidt
norm, or the relative entropy. If X consists only of
pure states, the operations T which minimize
1
or
all
are usually not altered by such different choices.
If X is a set of mixed states, however, the correct
choice is unclear and might depend on the precise
physical context (there is, in particular, no reason to
prefer fidelities).
General Properties
Before we consider more special examples in the
next section, let us discuss some general properties
of the figure of merit
X,
from eqn [3] and the
corresponding optimization problem.
Existence of Solutions
If the distance measure is continuous in the first
argument, the optimization problem [4] has a
solution, that is, optimal cloning machines exist:
the set T of cloning maps [1] is compact and the
quantity
X,
is – as a supremum over continuous
functions – lower-semicontinuous. Hence, the
statement follows from the fact that a lower-
semicontinuous function on a compact set always
admits a minimizer.
This argument can be generalized to the infinite-
dimensional case, if we choose the set T of allowed
cloning maps more carefully (the restriction to
normal channels proposed above is most probably
not sufficient for this purpose) and if we equip it
with an appropriate topology. The latter should be
weak enough for T to be compact, and strong
enough for
X,
to be lower-semicontinuous. A
typical choice is the weak
-topology arising from an
embedding of T into the dual of a Banach space
(such that we can apply the Banach–Alaoglu
Theorem). Detailed studies in this direction are,
however, not yet available.
Covariant Cloning Maps
To solve the optimization problem [4] is a difficult
and, in many cases, impossible task. However, it can
be simplified significantly if X and admit a
nontrivial symmetry group. Hence, consider again
a distance which is continuous and convex in its
first argument and a closed subgroup G of the group
U(d) of unitary operators on H= C
d
, such that
UXU
X;U
M
U
M
; U
M
U
M
¼ ð; Þ½9
hold for all U 2 G and , 2S(H
M
). Then
X,
is
invariant under the induced G action on the set T of
cloning maps, that is,
X;
ð
U
TÞ¼
X;
ðTÞ
with ð
U
TÞðAÞ¼U
N
TðU
M
AU
M
ÞU
N
½10
holds for all U 2 G and all T 2T. Convexity of
X,
in T implies (with the Haar measure
H
on G)
X;
ð
TÞ
X;
ðTÞ;
with
T ¼
Z
G
U
ðTÞ
H
ðdUÞ½11
for all T. Hence, we can replace each cloning map
by its group average
T without sacrificing the
Optimal Cloning of Quantum States 629
quality of the clones. This implies that
T is optimal
if T is, and, since
T is G-covariant,
U
ð
TÞ¼
T 8U 2 G ½12
we can conclude, together with the arguments from the
last section, that the optimization problem [4] always
admits covariant solutions. Similarly, we can show that
permutation invariant (sometimes called ‘‘symmetric’’)
solutions exist, that is, cloners which do not prefer a
particular clone or a particular input system.
This is a very useful result, because the set of
covariant and permutation-invariant T is much
smaller than the set of all cloning maps, and it can
be parametrized in terms of irreducible representa-
tions of G and the permutation group. In particular,
the case G = U(d) (such a T is often called
‘‘universal’’ because it does not prefer any direction
in the Hilbert space H) leads to quite general
solutions.
Relationships with Quantum State Estimation
If a procedure to estimate the input state from a
measurement on the N-fold system in the joint state
N
is given, there is a simple way to produce a
cloning machine: we just have to take the estimate
^
for the density matrix and prepare M > N
systems in the state
^
M
.IfX is finite and
estimation (which in this case is called hypothesis
testing) is done in terms of a positive operator
valued measure (E
)
2X
, E
2B(H
N
), the prob-
ability to get the estimate 2 X when the input is
in the state
N
is given by tr(E
N
). Hence, the
cloning map derived from this estimation scheme is
given by
~
E
ð
N
Þ¼
X
2X
tr E
N
M
½13
A generalization to arbitrary X is straightforward,
but requires the use of measure theory. It is easy to
see that the cloning map
~
E from eqn [13] is in
general not optimal, in particular if M is only
slightly bigger than N. However,
~
E has the interest-
ing feature that
X,
(
~
E) depends only on the number
of input systems, N, but not on the number of
clones, M, we want to produce. This observation
leads immediately to the conjecture that
~
E becomes
optimal in the limit M !1. A general proof is
currently not available, in those cases, however,
where optimal cloner and estimater can be explicitly
calculated for all N and M (i.e., the cases treated in
thesections‘‘Universalpure-statecloning’’and
‘‘Phase-covariantpure-statecloning’’)theconjecture
is true. A more detailed discussion of this problem
together with information about its current status
can be found on the web at http://www.imaph.
tu-bs.de/qi/problems/problems-html.
Examples
In this section, we will discuss concrete examples
that arise from different choices of the distance
measure and the set X of preferred states.
Universal Pure-State Cloning
The most frequently discussed case arises if X is the
set of pure states, that is, the input states are pure,
but otherwise unknown. Under this condition, it is
sufficient to consider the symmetric part H
N
þ
of the
tensor product H
N
, and only cloning maps
T : B(H
M
) !B(H
N
þ
), because only this part
affects the local or the global error. A complete
solution for arbitrary N, M and all finite-
dimensional Hilbert spaces is available for
all
in
Werner (1998) and for
1
in Keyl and Werner
(1999). Both cases admit the same (surprisingly
simple) unique solution
^
T
ðÞ¼
d½N
d½M
S
M
1
ðMNÞ
S
M
½14
where S
M
is the projection onto the symmetric
tensor product H
M
þ
and d[M] denotes the dimen-
sion of H
M
þ
. To derive these results, the group-
theoreticmethodssketchedinthesection‘‘Covar-
iantcloningmaps’’areused.Thefactthatglobal
and local figures of merit are minimized by the same
cloning map is surprising and a special feature of
pure-state cloning. It implies that correlations and
entanglement between the clones does not matter
at all.
Phase-Covariant Pure-State Cloning
Consider a fixed basis jji, j = 0, ..., d 1, in H and
let X be the set of states given by
¼j0iþ
X
d1
j¼1
e
i
j
jji½15
where the
j
denote arbitrary phases. Obviously,
this set is invariant under the set of all unitaries
which are diagonal in the given basis (i.e., a
maximal torus in U(d)). Using the methods outlined
inthesection‘‘Covariantcloningmaps,’’the
corresponding cloning problem is (almost) comple-
tely solved in Buscemi et al. (2005). For arbitrary
d = dim H, N and all M = N þ dk,withk 2 N a
630 Optimal Cloning of Quantum States
cloning map which minimizes global as well as
local errors is given in terms of the unitary
^
U : H
N
þ
!H
M
þ
;
^
Ujn
0
; ...; n
d
i
¼jn
0
þ k; ...; n
d
þ ki½16
where jn
1
, ..., n
d
i, n
j
2 N, denotes the number
basis of H
N
associated with the distinguished
basis jji of H.
Cloning Finitely Many States
If X is a finite set of pure states, a general solution
is not available, but there are several important
partial results. The easiest situation arises if the
elements of X are mutually orthogonal pure states.
In this case, ideal cloning is possible in terms of an
appropriately chosen unitary. If the states are
linearly independent but nonorthogonal, ideal
cloning is possible as well if we consider probabil-
istic cloning machines (Duan and Guo 1998); that
is, there is a nonvanishing probability that the
machine fails and does not produce any clones at
all (this means T is not unital). Optimal cloning
(with deterministic operations) of two nonorthog-
onal qubit states
j
= j
j
ih
j
j, j = 1, 2, is considered
for all N, M in (Bruß et al. (1998) and Chefles and
Barnett (1999)) (using averaged global fidelity as
the figure of merit). The crucial observation in this
case is that the optimal clones are pure, that is,
T
(
N
j
) = j
j
ih
j
j and that the
j
lie in the
subspace spanned by the (unattainable) ideal
clones
M
j
.
Universal Mixed-State Cloning
X = S(H) means that absolutely nothing is known a
priori about the input state . If the distance
measure is U(d) and permutation invariant
(which is the case for all possible choices discussed
in the section ‘‘The distance measure’’) the analysis
fromthesection‘‘Covariantcloningmaps’’shows
that a universal and symmetric minimizer exists. An
explicit solution, however, is not known, and even
the physically most appropriate choice for is
unclear. In contrast to the pure-state case, this is a
serious question, because the set of optimal cloners
is, in this case, much more sensitive to changes in .
In particular, correlations among the clones become
crucial, and it is very likely that local and global
figures of merit lead to very different solutions. To
emphasize this difference, an operation which
minimizes only local errors is sometimes called
‘‘broadcasting,’’ rather than cloning. A related
problem with (at least) partial solutions (‘‘purifica-
tion’’) will be discussed in the section ‘‘Purification.’’
Cloning of Gaussian States
If the Hilbert space is infinite dimensional, the restric-
tion to a reasonable small set X of preferred states is
crucial, because otherwise the search for minimizers
becomes hopeless. A physically relevant class with nice
mathematical properties are Gaussian states and in
particular coherent states. Cloning of the latter has been
studied in Cerf et al. (2005) for the case N = 1(andM
arbitrary).Asinthesection‘‘Covariantcloningmaps,’’
it can be shown that the search for optimal cloners can
be restricted to those which are covariant with respect
to phase space translations. This simplifies the problem
significantly and leads to the result that the global error
is minimized by Gaussian cloning maps, while in the
local case the best cloner is non-Gaussian.
Asymmetric Cloning
In all examples discussed up to now, we have
considered symmetric cloners, that is, the quality of
all clones is measured with equal weight. Alternatively,
we can look for asymmetric cloners which produce
clones with different quality and ask for the trade-off
between them. This problem was first discussed in Cerf
(2000) and later in Iblisdir et al. (2005).Itcanbe
regarded as a constraint optimization problem, where
the error of the first M
0
< M clones should be
minimized under the constraint that the error of the
rest is bounded by a fixed value. In Iblisdir et al. (2005),
it is conjectured that for pure input states and local
errors the optimal solution to this problem is given by
T
ðÞ¼V
1
ðMNÞ
V ½17
where V is a linear combination of projections in the
commutant of {U
N
jU 2 U(H)}. This conjecture is
true (at least) for qubits in the case 1 !n þ 1 and
1 !1 þ n.
Related Problems
Instead of cloning, we can also try to approximate
other impossible machines by channels which
operate on multiple inputs. To this end, we only
have to replace the figure of merit [6] by
1;
ðTÞ¼sup
2X;j
1 F
^
tr
j
T
ð
N
Þ;ðÞ
½18
where : S(H) !S(H) is a (possibly nonlinear)
functional which describes the task we want to
approximate. The generalization
all,
of
all
can be
given similarly. If has the appropriate continuity
and symmetry properties, the discussion in the
section ‘‘General properties’’ applies completely,
that is, we can assume covariance and permutation
Optimal Cloning of Quantum States 631
invariance, and we can consider operations which
use state estimation in an intermediate step.
Purification
Consider N quantum systems, all originally prepared in
thesamepurestate, and then subsequently exposed
to the same (known) decoherence process, described by
adepolarizingchannelR. The task of purification is to
produce M output systems which approximate the
original pure input state as well as possible. Hence,
the corresponding figure of merit arises with X =
{R() j pure} and () = R
1
(). This problem is
discussed for qubits in Cirac et al. (1999), Keyl and
Werner (2001) and D’Ariano et al. (2005). The
optimal purifier can be given explicitly for all N, M in
terms of irreducible SU(2) representations. Surpris-
ingly, it turns out that the output purity can be
improved even if the number of outputs, M, is larger
than the number of available input systems, N
(although N should be large enough). If we measure
purity in terms of local errors, it can be shown that, in
the limit N !1, perfectly purified qubits can be
produced at an infinite rate (i.e., the number of output
systems per input system can become infinite). How-
ever, we have to pay for this result with extremely large
correlations between the output systems. Therefore, the
global error does not disappear asymptotically, if we
insist on a nonvanishing rate.
Universal Not
‘‘Universal not’’ (UNOT) is an operation which
sends each pure state to its orthocomplement. This
is a positive but not a completely positive operation.
Hence, it cannot be performed by any physical
device. However, we can try to approximate it by a
cloning map T operating on N input systems. The
corresponding figure of merit [18] arises if X is the
set of pure states and () = 1 .InBuzˇek et al.
(1999), it is shown that the optimal solution to this
problem (for all N and M) is to estimate and
reprepare as described in the section ‘‘Relationships
with quantum state estimation.’’ Approximating
UNOT is, therefore, significantly more difficult
than (pure-state) cloning, where the optimal solution
is always (for finite M) better than estimation.
See also: Channels in Quantum Information Theory;
Compact Groups and Their Representations; Positive
Maps on C*-algebras.
Further Reading
Bruß D, DiVincenzo DP, Ekert A et al. (1998) Optimal universal and
state-dependent cloning. Physical Review A 57(4): 2368–2378.
Buscemi F, D’Ariano GM, and Macchiavello C (2005) Economical
phase-covariant cloning of qudits. Physical Review A 71: 042327.
Buzˇek V, Hillery M, and Werner RF (1999) Optimal manipula-
tions with qubits: universal-not gate. Physical Review A 60(4):
R2626–R2629.
Cerf NJ (2000) Asymmetric quantum cloning machines. Journal
of Modern Optics 47: 187–209.
Cerf NJ, Krueger O, Navez P, Werner RF, and Wolf MM (2005)
Non-Gaussian cloning of quantum coherent states is optimal.
Physical Review Letters 95: 070501.
Chefles A and Barnett SM (1999) Strategies and networks for state-
dependent quantum cloning. Physical Review A 60: 000136.
Cirac JI, Ekert AK, and Macchiavello C (1999) Optimal purifica-
tion of single qubits. Physical Review Letters 82: 4344–4347.
D’Ariano GM, Macchiavello C, and Perinotti P (2005) Super-
broadcasting of mixed states. Physical Review Letters 95: 060503.
Duan L-M and Guo G-C (1998) Probabilistic cloning and
identification of linearly independent quantum states. Physical
Review Letters 80: 4999–5002.
Iblisdir S, Acin A, and Gisin N (2005) Generalised asymmetric
quantum cloning, quant-ph/0505152.
Keyl M and Werner RF (1999) Optimal cloning of pure states, testing
single clones. Journal of Mathematical Physics 40: 3283–3299.
Keyl M and Werner RF (2001) The rate of optimal purification
procedures. Annales Henri Poincare´ 2: 1–26.
Some open problems in quantum information theory, http://
www.imaph.tu-bs.de/qi/problems/problems
–
.html.
Werner RF (1998) Optimal cloning of pure states. Physical
Review A 58: 980–1003.
Wootters WK and Zurek WH (1982) A single quantum cannot be
cloned. Nature 299: 802–803.
Optimal Transportation
Y Brenier, Universite
´
de Nice Sophia Antipolis,
Nice, France
ª 2006 Elsevier Ltd. All rights reserved.
The purpose of this article is to introduce some of the
main ideas of optimal transportation theory. A lot
more can be found in Villani’s book (Villani 2003), in
a somewhat similar spirit. Supplementary information
is also available in Ambrosio et al. (2005), Evans and
Gangbo (1999),andRu¨ schendorf and Rachev (1990).
Transportation Maps
Let us start by a rather abstract definition:
Definition 1 Let X and Y be two topological
spaces with Borel probability measures and ,
respectively. We say that a Borel map T : X ! Y is a
transportation map between (X, ) and (Y, ) if, for
each Borel subset A of Y,
Z
TðxÞ2A
ðdxÞ¼
Z
y2A
ðdyÞ
632 Optimal Transportation
It is customary to say that T pushes forward to
, or to say that is the image of by T.Anabstract
measure-theoretic result asserts that there is always
such a transportation map T,assoonas has no
atom (i.e., the measure of any point x 2 X is zero).
A more concrete situation is when X =
0
, Y =
1
,
where
0
and
1
are two smooth bounded open
subsets of the d-dimensional Euclidean space R
d
.In
such a case, a classical result, due to Moser and
improved by Dacorogna and Moser (1990), reads:
Theorem 1 Let
0
and
1
be two smooth bounded
open sets in R
d
. Let
0
> 0 and
1
> 0 be two
smooth functions on R
d
such that
Z
0
0
ðxÞdx ¼
Z
1
1
ðxÞdx ¼ 1
Then there is a smooth transportation map T
between (
0
,
0
(x)dx) and (
1
,
0
(y)dy). Further-
more, T is an orientation-preserving diffeomorphism
and solves the Jacobian equation:
1
ðTðxÞÞdetðDTðxÞÞ ¼
0
ðxÞ; 8x 2
0
½1
Transportation Maps with Convex
Potentials
An important property of Moser’s construction,
which we did not state, is the possibility of
prescribing the restriction of T along the boundary
@
0
. If one does not care about this latter property,
one can improve Theorem 1 as follows (Caffarelli
1992):
Theorem 2 Assume further that
1
is a uniformly
strictly convex set. Then, there is a transp ortation
map T with a smooth convex potential, namely
TðxÞ¼DðxÞ; 8x 2
0
for some smooth convex function defined on
R
d
and strictly convex on
0
. In addition, among
all Borel maps T transporting (
0
,
0
(x)dx) to
(
1
,
1
(y)dy), D is the unique map that minimizes
inf
T
Z
R
d
jTðxÞxj
2
0
ðxÞdx ½2
where jjdenotes the Euclidean norm on R
d
.
Because of its characterization, T = D is often
called the ‘‘optimal transportation map’’ with respect
to the ‘‘transportation cost’’ [2]. Notice that, because
of the Jacobian equation [1], automatically is a
classical solution to the Monge–Ampe`re equation:
1
ðDðxÞÞdetðD
2
ðxÞÞ ¼
0
ðxÞ; 8x 2
0
½3
(The Monge–Ampe` re equation is a famous geo-
metric PDE, related to the seeking of hypersurfaces
with prescribed Gaussian curvature.) The main gain
with respect to Moser’s construction is the property
that the optimal map T has, at each x 2
0
,a
Jacobian matrix DT(x) = D
2
(x)whichisapositive-
definite symmetric matrix. This property has been
first exploited by McCann (1997) and later by many
authors (see Villani (2003), for many references)
to prove a large series of geometric and functional
inequalities. A very fine example can be found in
Barthe (1998). Let us just consider, as an elementary
illustration, a short and sharp proof of the isoperi-
metric inequality using the optimal transportation
map.
A Proof of the Isoperimetric Inequality
Using Optimal Transportation Maps
Let us recall the isoperimetric inequality:
Theorem 3 Let be a smooth bounded open
subset in R
d
. Then
j@jdjB
1
j
1=d
jj
11=d
holds true where B
1
is the unit ball in R
d
, jj and
j@j, respectively, denote the d-dimensional volume
of and the (d 1)-dimensional Hausdorff measure
of the boundary @. In addition, the inequality
becomes an equality if and only if is a ball.
To prove this result, let us define densities:
0
ðxÞ¼
1
jj
; x 2
1
ðyÞ¼
1
jB
1
j
; y 2 B
1
and consider the associated optimal transportation
map D from (
0
,
0
(x)dx)to(
1
,
0
(y)dy). From
the Monge–Ampe` re equation,
1
ðDðxÞÞdetðD
2
ðxÞÞ ¼
0
ðxÞ
we get:
detðD
2
ðxÞÞ ¼
jB
1
j
jj
; x 2 ½4
Since the range of D on is the unit ball B
1
,we
have
I ¼
Z
@
DðxÞnðxÞdðxÞ
Z
@
dðxÞ¼j@j
where n(x) and d (x) respectively, denote the out-
ward unit normal and the (d 1)-dimensional
Optimal Transportation 633
Hausdorff measure along @. Using the divergence
theorem, we also have:
I ¼
Z
ðxÞdx
where (x) = trace(D
2
(x)) is the Laplacian of .
From the geometric mean inequality, we know that,
for any symmetric matrix A 0,
ðdet AÞ
1=d
1=d trace ðAÞ
holds true, with equality if and only if A is equal to
the identity matrix multiplied by a non-negative
scalar factor. Thus,
I d
Z
ðdetðD
2
ðxÞÞ
1=d
dx
¼ djj
11=d
jB
1
j
1=d
(because of [4]). So, we have obtained the isoperi-
metric inequality:
j@jdjB
1
j
1=d
jj
11=d
Let us now consider the case when this inequality
becomes an equality. Then, necessarily, for each x 2
, A = D
2
(x)satisfiesdetA = (trace(A)=d)
d
and,
therefore, must be the identity matrix multiplied by a
scalar factor >0, possibly depending on x. Because
of [4], the determinant of D
2
(x) is constant over .
Thus, >0 must be constant. It follows that
D(x) = (x a), for some point a in R
d
. Therefore,
must be the ball centered at a of radius 1=.
Monge’s Optimal Transportation Problem
Theorem 2 is one of the numerous avatars of the so-
called optimal transportation theory that goes back to
Monge’s mass transfer problem which addressed in
1781 the ‘me´moire sur la the´orie des de´blais et des
remblais’ and was completely renewed by Kantorovich
in the 1940s (see e.g., Ru¨ schendorf and Rachev (1990)
for instance). Let us quote a typical result, similar to
Theorem 2, but without regularity assumptions on the
data (see Brenier and Caffarelli (1992)):
Theorem 4 Let
0
be a non-negative Lebesgue
integrable function on R
d
, such that
Z
R
d
0
ðxÞdx ¼ 1
Then for any Borel probability measure
1
(dy) with
compact support on R
d
, there is a unique map T
transporting
0
(x)dxto
1
(dy), which minimizes
Z
R
d
jTðxÞxj
2
0
ðxÞdx
where jj denotes the Euclidean norm on R
d
. In
addition, there is a Lipschitz continuous convex
function defined on R
d
such that T(x) = D(x)
for
0
almost every x 2 R
d
, which implies:
Z
R
d
f ðDðxÞÞ
0
ðxÞdx ¼
Z
R
d
f ðyÞ
1
ðdyÞ
for all continuous functions f on R
d
.
Theorem 2, which can be interpreted as a
regularity result with respect to Theorem 4, is the
main output of Caffarelli’s regularity theory for
transportation maps with convex potentials
(Caffarelli 1992). Caffarelli’s analysis starts by a
proof that actually is a weak solution of the
Monge–Ampe` re equation [3] in the sense of Alex-
androv and is strictly convex. Then, Caffarelli shows
that D
2
is Ho¨ lder continuous, as soon as
0
and
1
are Ho¨ lder continuous.
Notice that the convexity assumption for
1
is
crucial to insure the regularity of the convex
potential. Caffarelli provided counter-examples
when
1
is made of two separate balls attached
together by a sufficiently thin pipe.
Surprisingly enough, results such as Theorem 4
are related to concrete applications in, for example,
astrophysics, image processing, etc. (Frisch et al.
2002, Haker and Tannenbaum 2003).
The Kantorovich Optimal Transportation
Problem
The Monge optimal transportation problem can
be solved using the Kantorovich duality method,
based on the key concept of ‘‘generalized transpor-
tation maps,’’ also called ‘‘transportation plans’’ or
‘‘doubly stochastic measures.’’ The abstract defini-
tion is:
Definition 2 Let X and Y be two topological
spaces with Borel probability measures and ,
respectively. We say that a Borel probability
measure on X Y is a generalized transportation
map, or a transportation plan, if its marginals are,
respectively, and , namely
Z
x2A;y2Y
ðdx; dyÞ¼
Z
x2A
ðdxÞ
Z
x2X;y2B
ðdx; dyÞ¼
Z
y2B
ðdyÞ
½5
for all Borel subsets A and B of X and Y,
respectively.
The Monge–Kantorovich (MK) optimal transpor-
tation problem amounts, given a ‘‘transportation
634 Optimal Transportation
cost,’’ that is, a continuous function c : X Y ! R,
to find a minimizer for
I
MK
¼ inf
Z
cðx; yÞð dx; dyÞ½6
where is subject to be a transportation plan
between (X, ) and (Y, ). Notice that this problem
is convex (and can be seen as an infinite-dimensional
linear program) and its dual problem can be easily
computed (using, e.g., Rockafellar’s theorem in
convex analysis and assuming, for simplicity, that
both X and Y are compact).
Theorem 5 We have
I
MK
¼ sup
a;b
Z
aðxÞðdxÞþ
Z
bðyÞðdyÞ
½7
where (a, b) is an y pair of continuous functions,
defined on X and Y, respectively, and subject to:
aðxÞþbðyÞcðx; yÞ; 8x 2 X; 8y 2 Y
Of course, each transportation map T, in the sense
of Definition 1, can be seen as a transportation plan
in the Kantorovich framework, just by setting
ðdx; dyÞ¼ðy TðxÞÞðdxÞ
which means
Z
x2A; y2B
ðdx; dyÞ¼
Z
x2A;TðxÞ2B
ðdxÞ
for all Borel subsets A and B of X and Y,
respectively. Then, we have
Z
cðx; yÞð dx; dyÞ¼
Z
cðx; TðxÞÞðdxÞ
So, the MK problem can be seen as a ‘‘relaxed’’
version of the ‘‘classical’’ optimal transportation
problem a` la Monge:
I
M
¼ inf
T
Z
cðx; TðxÞÞ ðdxÞ½8
where T is subject to be a transportation map
between (X, )and(Y, ). Indeed, we have I
MK
I
M
. It turns out that, in many important situations,
there is no gap between these two values, which
makes the MK problem a perfectly convenient
convex substitute for the original, nonconvex,
Monge transportation problem. This is, in particu-
lar, the case of the situation considered in Theorem
4, when the cost function is just
cðx; yÞ¼jx yj
2
or, more generally, c(x , y) = k(x y), where k is a
uniformly strictly convex function. A typical result is:
Theorem 5 Let
0
be a non-negative Lebesgue
integrable function on R
d
, with unit integral, and
1
(dy) be a Borel probability measure with compact
support on R
d
. Let k be a uniformly strictly convex
function on R
d
. Then the MK problem
I
MK
¼ inf
Z
kðy xÞðdx; dyÞ
where is subject to be a transportation plan
between
0
(x)dx and
1
(dy) on R
d
, has a unique
solution of form
ðdx; dyÞ¼ðy TðxÞÞðdxÞ
where T is the unique minimizer of the Monge
problem:
I
M
¼ inf
T
Z
kðTðxÞxÞ
0
ðxÞdx
among all transportation maps T between
0
(x)dx
and
1
(dy) on R
d
. In addition I
MK
= I
M
.
Proof for Theorem 5 (Sketch) For simplicity, we
assume that
0
and
1
are both compactly supported
in a ball B in R
d
and we limit ourselves to the
simplest cost function k(x) = jxj
2
=2. We first denote
by M the set of all Borel regular probability
measures on B B having
0
(x)dx and
1
(dy)as
marginals, which means
Z
BB
f ðxÞðdx; dyÞ¼
Z
B
f ðxÞ
0
ðxÞdx
Z
BB
f ðyÞðdx; dyÞ¼
Z
B
f ðyÞ
1
ðdyÞ
for all continuous functions f on R
d
. From Theorem 7,
we deduce:
max
2M
Z
BB
x yðdx; dyÞ
¼ inf
Z
B
½ðxÞ
0
ðxÞþðxÞ
1
ðxÞdx
where the infimum is taken over all pairs (, )of
continuous functions on B satisfying
ðxÞþðyÞx y; 8x 2 B; 8y 2 B
Then, it can be established that the infimum is attained
by a pair (, )suchthat is the restriction of a
Lipschitz continuous convex function defined on R
d
,
and for
0
(x)dx almost every point of R
d
, coincides
with the Legendre–Fenchel transform of ,
LFðÞðyÞ¼sup
x2R
d
ðx y ðxÞÞ
Optimal Transportation 635
Moreover, if =
opt
2 M maximizes
R
BB
x y
(dx,dy), then
ðxÞþðyÞ¼x y
holds for
opt
-almost every (x, y) 2 R
d
R
d
. Using
well-known properties of the Legendre–Fenchel
transform in convex analysis, one deduces that
opt
is necessarily of the form
opt
ðdx; dyÞ¼ðy DðxÞÞ
0
ðxÞdx
which implies
Z
R
d
R
d
f ðyÞ
opt
ðdx; dyÞ¼
Z
R
d
f ðDðxÞÞ
0
ðxÞdx
for all continuous functions f on R
d
and achieves the
proof since the second marginal of
opt
is
1
(dy).
The Wasserstein Distance
Optimal transportation theory is strongly related to
the geometric analysis of probability measures. For
simplicity, let us just consider the space Prob(B)of
all Borel probability measures supported by some
fixed ball B in R
d
. This space is compact for the
weak topology of measures. An equivalent definition
of this topology is provided by the distance d,
naturally attached to the MK problem:
dð
0
;
1
Þ¼inf
Z
BB
jx yj
2
ðdx; dyÞ
1=2
½9
where is subject to be a transportation plan
between
0
and
1
on B. (Of course, more general
convex functions k can be used to define the cost
function.) It has become popular to call this distance
as Wasserstein distance (or its generalizations for
various k). It turns out that Prob(B) equipped with
this distance has a formal Riemannian structure
(Otto 2001, Ambrosio et al. 2005). For instance,
given two probability measures
0
(x)dx and
1
(x)dx,
we can define a ‘‘shortest path’’ t ! (t, ) 2
Prob(B) such that (0) =
0
, (1) =
1
, just by setting:
ðt; dxÞ¼
Z
B
ða þðDðaÞaÞt xÞ
0
ðaÞda;
8t 2½0; 1
where D is the optimal transportation map
between
0
and
1
on B. This idea, which is
somewhat related to the geometric analysis of
hydrodynamics and various concepts of generalized
flows Arnol’d and Khesin 1998, Brenier, was
successfully used by McCann (1997) and Otto
(2001). In particular, the concept of convexity
along these geodesic paths on Prob(B) has been
pointed out by McCann (1997) to be a crucial tool
for new proofs of geometric and functional inequal-
ities. Otto, and other contributors (see Ambrosio
et al.(2005)for a comprehensive discussion), observed
that many important parabolic or dissipative evolu-
tion PDEs can be described as ‘‘gradient flows’’ (or
‘‘steepest descent’’) of such functionals, with respect
to the Wasserstein metric.
Further Reading
Ambrosio L, Gigli N, and Savare´ G (2005) Gradient Flows,
ETH Lectures in Mathematics. Birkha¨user.
Arnol’d VI and Khesin B (1998) Topological Methods in
Hydrodynamics. Berlin: Springer.
Barthe F (1998) Inventiones Mathematicae 134: 335–361.
Brenier Y Polar factorization and monotone rearrangement of
vector-valued functions.
Brenier Y (1991) Minimal geodesics on groups of volume-
preserving maps. Communications on Pure and Applied
Mathematics 44: 375–417.
Brenier Y (1999) Minimal geodesics on groups of volume-
preserving maps. Communications on Pure and Applied
Mathematics 52: 411–452.
Caffarelli L (1992) Boundary regularity of maps with convex
potentials. Communications on Pure and Applied Mathe-
matics 45: 1141–1151.
Cullen M, Norbury J, and Purser J (1991) Generalised Lagrangian
solutions for atmospheric and oceanic flows. SIAM Journal of
Applied Mathematics 51: 20–31.
Dacorogna B and Moser J (1990) Ann. Inst. H. Poincare´ Anal.
NL 7: 1–26.
Evans C and Gangbo W (1999) Mem. Amer. Math. Soc. 137: 653.
Frisch U, Matarrese S, Mohayaee R, and Sobolevski A (2002)
Nature 417: 260–262.
Haker S and Tannenbaum A (2003) New Approach to Monge–
Kantorovich with Applications to Computer Vision and
Image Processing, IMA Series on Applied Mathematics.
Springer.
McCann R (1997) Advances in Mathematics 128: 153–179.
Otto F (2001) CPDEs 26: 101–174.
Ru¨ schendorf L and Rachev ST (1990) Journal of Multivariate
Analysis 32: 48–54.
Ru¨ schendorf L and Rachev ST (1998) Mass Transportation
Problems. Berlin: Springer.
Villani C (2003) Topics in Optimal Transportation, AMS
Graduate Studies in Mathematics.
636 Optimal Transportation