# Order $p$ quantum Wasserstein distances from couplings

Emily Beatty<EMAIL_ADDRESS>Univ Lyon, ENS Lyon, UCBL, CNRS, Inria,
LIP, F-69342, Lyon Cedex 07, France  Daniel Stilck França
<EMAIL_ADDRESS>Univ Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP,
F-69342, Lyon Cedex 07, France

###### Abstract

Optimal transport provides a powerful mathematical framework with applications
spanning numerous fields. A cornerstone within this domain is the
$p$-Wasserstein distance, which serves to quantify the cost of transporting
one probability measure to another. While recent attempts have sought to
extend this measure to the realm of quantum states, existing definitions often
present certain limitations, such as not being faithful. In this work, we
present a new definition of quantum Wasserstein distances. This definition,
leveraging the coupling method and a metric applicable to pure states, draws
inspiration from a property characterising the classical Wasserstein distance
— its determination based on its value on point masses. Subject to certain
continuity properties, our definition exhibits numerous attributes expected of
an optimal quantum rendition of the Wasserstein distance. Notably, our
approach seamlessly integrates metrics familiar to quantum information theory,
such as the trace distance. Moreover, it provides an organic extension for
metrics, like Nielsen’s complexity metric, allowing their application to mixed
states with a natural operational interpretation. Furthermore, we analyze this
metric’s attributes in the context of random quantum states and unveil phase
transitions concerning the complexity of subsystems of random states.

###### Contents

  1. I Introduction
  2. II Basic concepts and notation
    1. II.1 Classical optimal transport
    2. II.2 Quantum information framework
  3. III Motivations and definitions
    1. III.1 Other approaches
  4. IV General properties
    1. IV.1 Dual picture
  5. V Special instances
    1. V.1 $W_{1}^{H}$ distance on $n$-qudit systems
    2. V.2 Trace distance
    3. V.3 Complexity geometry
  6. VI Applications
    1. VI.1 Results for random quantum states
    2. VI.2 Operational interpretation in terms of classical-quantum sources
    3. VI.3 Hypercontractivity and noise
  7. VII Conclusion
  8. VIII Acknowledgements
  9. A Comparison to other proposed definitions of a quantum Wasserstein distance
  10. B Development of the proposed definition
    1. B.1 Definition of a transport plan
    2. B.2 Entangled couplings and transport plans
  11. C Towards the triangle inequality
  12. D Auxiliary proofs
    1. D.1 Proof of Proposition 17 on the continuity of $W_{p}^{d}$
    2. D.2 Proof of Corollary 32 on the approximate gate complexity of random pure states

##  I Introduction

Optimal transport has established itself as a powerful tool in various areas
of science and pure mathematics, such as machine learning [20], information
theory [44], partial differential equations [49] and economics [21]. In light
of this, it should come as no surprise that the last years have seen a surge
of interest in the quantum generalisation of optimal transport [36, 11, 14,
23, 38, 19, 17, 22, 18, 4].

One of the central concepts of classical optimal transport is the
$p$-Wasserstein distances $\mathcal{W}_{p}$, which are a family of distances
on the set of probability measures on a metric space. Roughly speaking, if we
imagine a probability measure as describing a distribution of mass, these
distances measure the cost of transporting one measure onto another in terms
of a cost function on the underlying metric space. They can recover many
widely studied metrics in probability spaces in a unified way. For instance,
the total variation distance corresponds to the Wasserstein distance obtained
when we equip the space with the discrete metric. In the classical setting
[49], they admit many different equivalent characterisations, which we can
broadly categorise into a _geometrical formulation_ , a _dual formulation_ and
a _coupling formulation_.

There now exist many different proposals of quantum Wasserstein distances that
take one of the approaches mentioned above [36, 40, 38, 11, 13, 42, 9, 19,
23]. Important examples of definitions that follow the geometric route are the
definitions by Carlen and Maas [11, 12], which have been extensively studied
in a series of works [42, 13, 18]. Roughly speaking, the geometric framework
gives a natural generalisation of $\mathcal{W}_{2}$ in terms of a Riemannian
metric on the set of full rank states such that the relative entropy with
respect to a reference state arises as a gradient flow. However, it has the
undesirable feature of depending on an underlying semigroup converging to a
reference state.

A good example of a distance that is based on a dual approach is the
definition of de Palma et al [36]. Whereas the geometric approach is well-
suited to generalise the case $p=2$, this approach works well for $p=1$, and
the authors were able to define a natural quantum generalisation of
$\mathcal{W}_{1}$ with respect to the Hamming distance on the hypercube. The
dual approach works by first defining a good generalisation of a so-called
Lipschitz constant of observables, which in some sense measures how much the
expectation value of the observable can change between two points when
normalised by the underlying metric. From this, defining the distance induced
by such observables is straightforward through duality. This generalisation
has also found numerous applications in quantum information and computation
[37, 17, 43, 27, 40, 35].

Finally, some works have followed the coupling approach [9, 19, 38, 14].
Recall that given two random variables, a coupling is a joint distribution
whose marginals are the two random variables. In the classical setting, the
Wasserstein distance can be defined as the infimum of the expected cost of
transporting one random variable onto the other, where the infimum is taken
over all couplings of the two random variables. The main advantage of the
coupling approach is that it yields a definition of $W_{p}$ for all values of
$p$. Existing approaches that attempt to quantise the coupling approach have
significant downsides and usually do not satisfy one or more of the key
properties expected from the Wasserstein distance. For example, the definition
of [9] is not a semidistance, and the definition of [38] is not faithful.

In this work, we propose a new definition of the quantum Wasserstein distance
based on the coupling approach. Our novel definition departs from the
observation that, classically, the Wasserstein distance is completely
determined by its value on point masses. As pure states are quantum analogues
of point masses, we propose a coupling definition of the quantum
$p$-Wasserstein distance induced by a metric on pure states and then consider
an optimisation over all separable couplings of the underlying states.

We show that, as long as the metric on pure states satisfies some simple
continuity properties, the induced quantum $p$-Wasserstein has many desirable
properties expected from a good quantisation of the Wasserstein distance. In
particular, we show that our definition recovers widely studied metrics on the
set of quantum states, such as the trace distance, and is closely related to
de Palma’s quantum Wasserstein distance of order $1$. Furthermore, we show
that it offers a natural way of extending distances from pure to mixed states
in a way that preserves all the symmetries of the original metric and recovers
its value on pure states. We also discuss some interesting ways in which our
quantised distance behaves differently from its classical counterpart.

As an application of our new definition, we give a generalisation of Nielsen’s
complexity geometry [32] to mixed states that has a natural operational
interpretation of measuring the complexity of mapping one mixed state to
another. We then study the behaviour of this metric for various ensembles of
random quantum states and identify phase transitions in the expected
Wasserstein distance between them. More concretely, we show that if we look at
reduced density matrices of regions whose size is at most one-ninth of the
total size, then the complexity distance is exponentially small. In contrast,
for large enough subsystems, the distance is maximal. This result can be
interpreted as formalizing the intuitive notion that small enough subsystems
of random states are essentially maximally mixed and trivial from a complexity
point of view, whereas large enough subsystems are highly entangled and
complex.

We also study De Palma et al’s $W_{1}^{H}$ distance under random quantum
states, showing that they are essentially maximally far apart. Previous works
[43] hinted at the possibility that the $W_{1}^{H}$ captures how well states
can be distinguished by local observables. However, as random states cannot be
distinguished by local observables, and as our results show that random states
can be distinguished by the $W_{1}^{H}$ distance, we see that this original
intuition is false. This mirrors a result found concurrently in [35]. This
shows that the $W_{1}^{H}$ distance, and in turn the set of Lipschitz
observables defined from its dual, have a significantly richer structure than
previously expected.

Finally, we discuss an operational interpretation of our newly introduced
distance and quantify the noise of a channel in terms of its
hypercontractivity under the $W_{p}^{d}$ distance.

##  II Basic concepts and notation

###  II.1 Classical optimal transport

In the classical setting, the domain of optimal transport introduced in [29]
is well-developed and finds applications in a wide variety of areas. The focus
is to understand the cost of transporting one measure onto another and find
the minimal cost of such transportation. More formally, for measurable spaces
$\mathcal{X},\mathcal{Y}$ with probability measures $\mu,\nu$ respectively, we
assign a cost $c:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}_{\geq 0}$ which
represents the cost $c(x,y)$ of moving one unit of measure from $x$ to $y$.
From here we optimise the total cost of transporting $\mu$ onto $\nu$ for each
coupling [25] $\gamma$ of $\mu$ and $\nu$.

######  Definition 1.

Let $\mu,\nu$ be probability measures on measurable spaces
$\mathcal{X},\mathcal{Y}$ respectively. A coupling of $\mu$ and $\nu$ is a
measure $\gamma$ on $\mathcal{X}\times\mathcal{Y}$ such that for all
measurable sets $\mathcal{A}\subseteq\mathcal{X}$, we have
$\gamma(\mathcal{A}\otimes\mathcal{Y})=\mu(\mathcal{A})$, and all measurable
sets $\mathcal{B}\subseteq\mathcal{Y}$ we have
$\gamma(\mathcal{X}\otimes\mathcal{B})=\nu(\mathcal{B})$. Denote by
$\mathcal{C}(\mu,\nu)$ the set of couplings of $\mu$ with $\nu$.

In other words, a coupling is a measure $\gamma$ on
$\mathcal{X}\otimes\mathcal{Y}$ with marginals $\mu$ and $\nu$. For a cost
function $c$ on $\mathcal{X}\times\mathcal{Y}$, we can then define the
transport cost of a coupling $\gamma$ as

$\mathcal{T}(\gamma)=\int_{\mathcal{X}\times\mathcal{Y}}c(x,y)\mathrm{d}\gamma(x,y).$
(1)

The optimal transport cost of transporting $\mu$ and $\nu$ is then given by
minimising (1) over all couplings $\gamma$. Throughout we will only consider
the case where $\mathcal{X}=\mathcal{Y}$, $\mathcal{X}$ is equipped with a
metric $d$, and the cost function $c$ is a power of the metric $d$. This leads
to the definition of a classical Wasserstein distance [48, p. 207].

######  Definition 2.

Let $(\mathcal{X},d)$ be a measurable metric space with probability measures
$\mu$, $\nu$. Given $p\geq 1$, the $p^{\text{th}}$-order Wasserstein distance
between $\mu$ and $\nu$ is given by

$\mathcal{W}_{p}(\mu,\nu)=\left(\inf_{\gamma\in\mathcal{C}(\mu,\nu)}\int_{\mathcal{X}\times\mathcal{X}}d(x,y)^{p}\mathrm{d}\gamma(x,y)\right)^{1/p}.$
(2)

This notion also extends to $p=\infty$ in the following way:

######  Definition 3.

Let $(\mathcal{X},d)$ be a measurable metric space with probability measures
$\mu$, $\nu$. The infinite-order Wasserstein distance between $\mu$ and $\nu$
is given by

$\mathcal{W}_{\infty}(\mu,\nu)=\inf_{\gamma\in\mathcal{C}(\mu,\nu)}\sup_{(x,y)\in\text{{\em
supp}}(\gamma)}d(x,y).$ (3)

It is desirable to generalise these distances to quantities on quantum states
to mirror many of their classical applications. We’re particularly interested
in generalisations of the case where the underlying metric $d$ is the discrete
metric, for which $\mathcal{W}_{p}$ is the total variation distance, and the
case where the underlying metric is the Hamming distance on the hypercube, for
which $\mathcal{W}_{1}$ is Ornstein’s $\bar{d}$-distance [34]. These are
arguably the most widely used distances in this context so far and a good
generalisation should also recover them.

###  II.2 Quantum information framework

We represent a quantum system by a Hilbert space $\mathcal{H}$ of finite
dimension. Pure states on this system are modelled as elements $\ket{\psi}$ of
the projective space $\mathbb{P}\mathcal{H}$. We notate the Hermitian
conjugate of such a pure state by $\bra{\psi}$, and then in a slight abuse of
notation we write $|\psi\rangle\langle\psi|$ for the projection onto
$\ket{\psi}$, taking the convention $\text{Tr}[|\psi\rangle\langle\psi|]=1$.

Mixed states on this system are then convex combinations of pure states,
written as a finite sum

$\rho=\sum_{j}q_{j}|\psi_{j}\rangle\langle\psi_{j}|$ (4)

where $\sum_{j}q_{j}=1$ and $q_{j}>0$. Equivalently, the set of mixed states
on $\mathcal{H}$ is defined as the set of Hermitian positive semidefinite
linear operators of trace $1$, otherwise known as density operators, and we
will denote this set by $\mathcal{D}(\mathcal{H})$.

Note that in the case $\rho=|\psi\rangle\langle\psi|$, we will also refer to
$\rho$ as a pure state. It will be clear from context whether the term ‘pure
state’ refers to an element of the projective Hilbert space or a density
operator. Similarly, the term ‘state’ could refer to either a pure state
$\ket{\psi}$ or a mixed state $\rho$, and the meaning will be clear from the
context.

The combination of two systems $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ is
represented by their tensor product $\mathcal{H}_{1}\otimes\mathcal{H}_{2}$.
Their projective space is then
$\mathbb{P}(\mathcal{H}_{1}\otimes\mathcal{H}_{2}$. Similarly, the set of
density operators on this bipartite system is
$\mathcal{D}(\mathcal{H}_{1}\otimes\mathcal{H}_{2})$.

The quantum equivalent of taking the marginal is the partial trace operation.
Using this, we can define a quantum coupling of states $\rho$, $\sigma$.

######  Definition 4.

Let $\rho$, $\sigma$ be quantum states on Hilbert spaces
$\mathcal{H}_{1},\mathcal{H}_{2}$ respectively. A quantum coupling of $\rho$
with $\sigma$ is a quantum state $\tau$ on
$\mathcal{H}_{1}\otimes\mathcal{H}_{2}$ such that

$\text{{\em Tr}}_{2}\tau=\rho\qquad\text{and}\qquad\text{{\em
Tr}}_{1}\tau=\sigma.$ (5)

Once again, in this manuscript, we only consider the case where
$\mathcal{H}_{1}=\mathcal{H}_{2}$. Throughout this work, we will also
reference a few key objects from quantum information theory and quantum
computation.

######  Definition 5.

For states $\rho$ and $\sigma$ on Hilbert space $\mathcal{H}$, their trace
distance is half the trace norm of their difference, defined by

$d_{1}(\rho,\sigma)=\frac{1}{2}\left\|\rho-\sigma\right\|_{1}=\frac{1}{2}\text{{\em
Tr}}\left[\sqrt{(\rho-\sigma)^{\dagger}(\rho-\sigma)}\right].$ (6)

We also have the equivalence

$d_{1}(\rho,\sigma)=\sup_{P^{\dagger}=P,0\leq P\leq I}\text{{\em
Tr}}[P(\rho-\sigma)].$ (7)

######  Definition 6.

Let $\mathcal{U}(n)$ be the group of $n\times n$ unitary matrices. The Haar
measure on $\mathcal{U}(n)$, denoted $\mu_{\text{{\em Haar}}}$, is the unique
measure on the group $\mathcal{U}(n)$ which is invariant under left-
multiplication and for which $\mu_{\text{{\em Haar}}}(\mathcal{U}(n))=1$.

######  Definition 7.

The $2\times 2$ Pauli operators $\sigma_{x},\sigma_{y},\sigma_{z}$ are given
by the matrices

$\sigma_{x}=\begin{pmatrix}0&1\\\
1&0\end{pmatrix}\qquad\sigma_{y}=\begin{pmatrix}0&-i\\\
i&0\end{pmatrix}\qquad\sigma_{z}=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}$ (8)

seen as unitary transformations with respect to the computational basis. On
the $n$-fold tensor product of $\mathbb{C}^{2}$, a Pauli string is a product
$\sigma_{1}\otimes\dots\sigma_{n}$ where each
$\sigma_{i}\in\\{\mathbb{I},\sigma_{x},\sigma_{y},\sigma_{z}\\}$. The weight
of such a string is the number of indices for which
$\sigma_{i}\neq\mathbb{I}$, so the weight of
$\mathbb{I}\otimes\sigma_{x}\otimes\mathbb{I}$ is one and the weight of
$\sigma_{x}\otimes\sigma_{y}\otimes\sigma_{z}$ is three.

##  III Motivations and definitions

To generalise the Wasserstein distances to the quantum setting in a way that
is useful, it is desirable to replicate as many basic properties of the
classical definition as possible. To allow this, we note a key property of the
classical Wasserstein distances. For all orders $p\geq 1$ and all
$x,y\in\mathcal{X}$, the $\mathcal{W}_{p}$ distance between point masses
agrees with the metric distance. That is, for Dirac measures $\delta_{x}$ and
$\delta_{y}$, we have

$\mathcal{W}_{p}(\delta_{x},\delta_{y})=d(x,y).$ (9)

It follows, therefore, that the classical Wasserstein distances are determined
by their values on point masses. We also see that we can recover the
underlying metric $d$ from the Wasserstein distance.

This property of determination by point masses is the key motivation of this
work. For any quantum Wasserstein distance which is defined for general order
$p$, the distances between the quantum versions of point masses (pure states)
should be independent of $p$, and should agree with the underlying metric on
the space if one exists.

To replicate this property, consider a Hilbert space $\mathcal{H}$ with
projective space $\mathbb{P}\mathcal{H}$, equipped with metric $d$. In this
setting, for all orders $p\geq 1$ and states $\ket{\psi}$ and $\ket{\varphi}$
we would expect a quantum Wasserstein distance $W_{p}^{d}$ to satisfy

$W_{p}^{d}(|\psi\rangle\langle\psi|,|\varphi\rangle\langle\varphi|)=d(\ket{\psi},\ket{\varphi})$
(10)

taking the convention that $|\psi\rangle\langle\psi|$ and
$|\varphi\rangle\langle\varphi|$ both have unit trace. Given this motivation
for a property the distance should satisfy, it remains to generalise the
definition of a transport cost in (1) to the quantum setting. One possible
generalisation is given in the definition below.

######  Definition 8.

Let $\mathcal{H}$ be a finite-dimensional Hilbert space with projective space
$\mathbb{P}\mathcal{H}$, and let $\rho,\sigma\in\mathcal{D}(\mathcal{H})$. We
define a quantum transport plan between $\rho$ and $\sigma$ as any finite set
of triples $\\{(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}})\\}_{j}$ such that

$\sum_{j}q_{j}|\psi_{j}\rangle\langle\psi_{j}|=\rho\qquad\text{\em
and}\qquad\sum_{j}q_{j}|\varphi_{j}\rangle\langle\varphi_{j}|=\sigma.$ (11)

where $q_{j}>0$, and taking convention $\text{{\em
Tr}}|\psi_{j}\rangle\langle\psi_{j}|=\text{{\em
Tr}}|\varphi_{j}\rangle\langle\varphi_{j}|=1$. This is equivalent to an
expression of a separable quantum coupling $\tau$ of $\rho$ and $\sigma$ as a
convex combination of pure bipartite states

$\tau=\sum_{j}q_{j}|\psi_{j}\rangle\langle\psi_{j}|\otimes|\varphi_{j}\rangle\langle\varphi_{j}|.$
(12)

We denote the set of all quantum transport plans between $\rho$ and $\sigma$
by $\mathcal{Q}(\rho,\sigma)$. By convention, we say that two elements
$(q,\ket{\psi},\ket{\varphi})$, $(q^{\prime},\ket{\psi},\ket{\varphi})$ never
appear in the same transport plan: any plan written as such is implied to
contain the element $(q+q^{\prime},\ket{\psi},\ket{\varphi})$ in their place.

This equivalence between transport plans and ways of writing couplings
reflects the classical case, although we note that one quantum coupling could
give rise to multiple quantum transport plans. For example, the separable
quantum coupling $\tau=|0\rangle\langle 0|\otimes\frac{\mathbb{I}}{2}$ between
$|0\rangle\langle 0|$ and $\frac{\mathbb{I}}{2}$ on a two-qubit space gives
rise to transport plans $\\{(1/2,\ket{0},\ket{0}),(1/2,\ket{0},\ket{1})\\}$
and $\\{(1/2,\ket{0},\ket{+}),(1/2,\ket{0},\ket{-})\\}$.

In building quantum transport plans, we can also refer to partial quantum
transport plans. This is a quantum transport plan where $\rho$ and $\sigma$
are instead positive semidefinite operators of equal trace at most $1$, and
the partial plan transports the ‘partial state’ $\rho$ onto the ‘partial
state’ $\sigma$.

We can then use this notion of a quantum transport plan to replicate the
classical definitions of transport cost and Wasserstein distance in the
quantum setting.

######  Definition 9.

Let $\mathcal{H}$ be a finite-dimensional Hilbert space and let $d$ be a
distance on $\mathbb{P}\mathcal{H}$. Let $p\geq 1$. For any transport plan
$Q=\\{(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}})\\}_{j}$ we define its
$p^{\textbf{th}}$-order quantum transport cost as

$T_{p}^{d}(Q)=\sum_{j}q_{j}d\left(\ket{\psi_{j}},\ket{\varphi_{j}}\right)^{p}.$
(13)

The $p^{\textbf{th}}$-order quantum Wasserstein distance on
$\mathcal{D}(\mathcal{H})$ is then defined as

$W_{p}^{d}(\rho,\sigma)=\left(\inf_{Q\in\mathcal{Q}(\rho,\sigma)}T_{p}^{d}(Q)\right)^{1/p}.$
(14)

We will see in Proposition 16 that the infimum in this definition is
equivalent to the minimum, in the case that $d$ is continuous. Note that we
have restricted to separable couplings above. This is because it is not
obvious how to extend the transportation cost for entangled pure states. In
Appendix B.2 we discuss one possible way and then argue that at, at least for
$p=1$, entangled couplings are not advantageous and we can restrict to
separable couplings without loss of generality.

As with many other ordered distances, we can also define the infinite-order
quantum Wasserstein distance.

######  Definition 10.

Let $\mathcal{H}$ be a finite-dimensional Hilbert space and let $d$ be a
distance on $\mathbb{P}\mathcal{H}$. For any states
$\rho,\sigma\in\mathcal{D}(\mathcal{H})$, we define their infinite-order
quantum Wasserstein distance as

$W_{\infty}^{d}(\rho,\sigma)=\inf_{Q\in\mathcal{Q(\rho,\sigma)}}\sup_{j}d(\ket{\psi_{j}},\ket{\varphi_{j}})$
(15)

for quantum transport plans
$Q=\\{(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}})\\}_{j}$.

As a natural consequence of the convex nature of these definitions, we see
that this family of Wasserstein distances is monotone in $p$. Indeed, for any
transport plan $Q$ between $\rho$ and $\sigma$ we have for $p_{1}<p_{2}$ that

$\displaystyle T_{p_{1}}(Q)^{1/{p_{1}}}$
$\displaystyle=\left(\sum_{j}q_{j}d(\ket{\psi_{j}},\ket{\varphi_{j}})^{p_{1}}\right)^{1/{p_{1}}}$
(16)
$\displaystyle\leq\left(\left(\sum_{j}q_{j}\left(d(\ket{\psi_{j}},\ket{\varphi_{j}})^{p_{1}}\right)^{p_{2}/p_{1}}\right)^{1/{p_{1}}}\right)^{p_{1}/p_{2}}$
(17)
$\displaystyle=\left(\sum_{j}q_{j}d(\ket{\psi_{j}},\ket{\varphi_{j}})^{p_{2}}\right)^{1/{p_{2}}}$
(18) $\displaystyle=T_{p_{2}}(Q)^{1/{p_{2}}}$ (19)

by an application of Jensen’s inequality. Taking the infimum over
$Q\in\mathcal{Q}(\rho,\sigma)$, we get

$W_{p_{1}}^{d}(\rho,\sigma)\leq W_{p_{2}}^{d}(\rho,\sigma).$ (20)

The same applies when $p_{2}=\infty$, as
$T_{p_{1}}(Q)^{1/p_{1}}\leq\max_{j}d(\ket{\psi_{j}},\ket{\varphi_{j}})$.

This definition is given for all $1\leq p\leq\infty$. However, at least in the
classical case, the most important cases to consider for interesting
applications are $p=1,2,\text{ and }\infty$ [41, 49, 47].

Although many desirable properties of these $W_{p}^{d}$ are proven in Sec. IV,
establishing a triangle inequality remains a difficult open problem. This is
true of many attempts to establish a quantum generalisation of the classical
Wasserstein distances, and further discussion of attempts to establish this
are discussed in Appendix C. However, by looking at the dual picture in Sec.
IV.1, we establish a closely related norm on the space of traceless Hermitian
operators for which $W_{1}^{d}$ is an upper bound, and which agrees with the
original distance $d$ on differences between pure states. For order $p=1$ this
norm allows a trade-off between ease of proving the triangle inequality, and
operational interpretation in terms of moving mass. This dual formulation
closely mirrors the Kantorovich-Rubinstein theorem in the classical case [48,
p. 34]. Furthermore, we show in Sec. V that it allows us to essentially
recover the trace distance and the definition of [36], thus our results on the
dual definition give strong evidence that this $W_{p}^{d}$ a good quantum
generalisation.

###  III.1 Other approaches

Many proposals have been suggested for generalisations of the classical
Wasserstein distance to quantum states, in various contexts, to varying
degrees of success. Arguably the most desirable classical metrics to
generalise are the discrete metric on a finite space and the Hamming distance
on the hypercube.

The most prominent example is perhaps the first-order distance defined in [36]
which generalises the $\mathcal{W}_{1}$ distance on the hypercube whose
underlying geometry is the Hamming distance. They define states $\rho,\sigma$
on $(\mathbb{C}^{d})^{\otimes n}$ to be neighbouring if there exists some
qudit $i$ for which $\text{Tr}_{i}[\rho-\sigma]=0$. In other words, $\rho$ and
$\sigma$ are the same when qudit $i$ is traced out. The norm
$\left\|\cdot\right\|_{W_{1}^{H}}$ traceless Hermitian operators is then
defined such that its unit ball is the convex hull of all differences between
neighbouring states. This means $\left\|\rho-\sigma\right\|_{W_{1}^{H}}$ can
be written as

$\left\|\rho-\sigma\right\|_{W_{1}^{H}}=\min\left\\{\sum_{i=1}^{n}c_{i}:c_{i}>0,\sum_{i=1}^{n}(\rho^{(i)}-\sigma^{(i)})=\rho-\sigma,\text{Tr}_{i}[\rho^{(i)}-\sigma^{(i)}]=0\right\\}.$
(21)

This is a true metric and it has led to many applications such as in quantum
spin systems [40] and variational quantum algorithms [17]. However, the
approach taken is very specific to the Hamming distance and does not lend
itself to general transport costs.

For order $p=2$, a number of definitions have been proposed in various
contexts, such as [23] which defines a second-order optimal transport cost in
the context of mean field limits that was shown in [10] to have links with the
Brenier formulation of classical optimal transport [48, p. 238].

More precisely, for a set of Hermitian operators $\\{R_{1},\dots,R_{K}\\}$ on
$\mathcal{H}$, the second-order transport cost of a coupling $\Pi$ on
$\mathcal{H}\otimes\mathcal{H}$ by

$\mathcal{C}(\Pi)=\sum_{i=1}^{K}\text{Tr}[(R_{i}\otimes\mathbb{I}-\mathbb{I}\otimes
R_{i})\Pi(R_{i}\otimes\mathbb{I}-\mathbb{I}\otimes R_{i})]$ (22)

from which a second-order Wasserstein distance is derived by taking the square
root of the infimum of the cost of all couplings between $\rho$ and $\sigma$
in the usual way. Defining quantity
$d(\ket{\psi},\ket{\varphi})=\sum_{i=1}^{K}\left\|R_{i}\ket{\psi}\right\|^{2}+\left\|R_{i}\ket{\varphi}\right\|^{2}-2\braket{\psi}{R_{i}}{\psi}\braket{\varphi}{R_{i}}{\varphi}$,
we see that this is a variation of our definition above, although with a
specific $d$ which is not a true metric, and with the infimum taken over all
couplings as opposed to just those which are separable.

Following the Brenier formulation more closely, the distance in [11] is also a
second-order distance and has been used [18] to prove a quantum version of the
HWI inequality. Specifically, the 2-Wasserstein distance is defined here as
the geodesic distance on the set of full-rank states equipped with a
Riemannian metric defined by the continuity equation. This definition is a
world away from our framework, as it leans heavily into the intricacies of the
classical dynamical formulation.

We should also mention the definition in [14] and refined in [28] which
defines a second-order cost based on couplings with a specific cost function
given by an asymmetric projection. While it is conjectured that this gives a
true distance, we show in Appendix A that this definition cannot be extended
to other underlying geometries, such as analogues of the Hamming distance on
multipartite spaces. Further approaches include the more flexible [38], an
alternative to [23], which defines a second-order distance based on couplings
that is not faithful. It has been conjectured [39] that a natural modification
of this quantity is a true distance, though this remains an open problem. A
similarly flexible approach appears in [19], following a naïve translation of
the classical formulation into the quantum setting. This definition takes a
cost matrix $C$ on $\mathcal{H}\otimes\mathcal{H}$, and defines a Wasserstein
distance by

$W_{p}(\rho,\sigma)=\left(\inf_{\tau\in\mathcal{C}(\rho,\sigma)}\text{Tr}[C^{p}\tau]\right)^{1/p}$
(23)

where $\mathcal{C}(\rho,\sigma)$ is the set of quantum couplings of $\rho$
with $\sigma$. The particular case of $C$ being the projection onto the
asymmetric subspace is studied in detail and coincides with the definition in
[14]. In the general case, however, this is not shown to be a semidistance.

Each of the approaches seems to be generalising one particular aspect or
application of Wasserstein distances to the noncommutative setting, be it
obtaining a distance for a given value of $p$ or a given underlying geometry
of the Hilbert space. However, it is not clear how they relate to each other
or how to extend them beyond their original setting. The definition in this
work adapts to any order $p$ and any underlying metric $d$ on the set of pure
states of the Hilbert space provided that $d$ satisfies a few basic continuity
properties. This broad flexibility allows us to talk about the moments of the
cost of moving between classical-quantum sources in great generality (Sec.
VI.2) and also allows us to talk about the noise of an operator by comparing
transport distances of different orders in an analogue of hypercontractivity
(Sec. VI.3).

To avoid confusion, we give in Table 1 a summary of all relevant Wasserstein
distances used throughout this work.

Notation |  Definition
---|---
$\mathcal{W}_{p}^{d}(\mu,\nu)$ |  The classical Wasserstein distance of order $p$ between measures $\mu$, $\nu$ on metric space $(X,d)$; see Equations (2) and (3).
$W_{p}^{d}(\rho,\sigma)$ |  The classical Wasserstein distance of order $p$ between measures $\mu$, $\nu$ on Hilbert space $\mathcal{H}$ and metric $d$ on $\mathbb{P}\mathcal{H}$; see Equations (14) and (15).
$\left\|\rho-\sigma\right\|_{W_{1}^{H}}$ |  The quantum Wasserstein norm of order one from [36]; see Equation (22).
$W_{p}^{H}(\rho,\sigma)$ |  The quantum Wasserstein distance of order $p$ on on $\mathcal{H}=(\mathbb{C}^{d})^{\otimes n}$ defined by metric $d_{H}(\ket{\psi},\ket{\varphi})=\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{W_{1}^{H}}$; see Sec. V.1. Write $W_{p=1}^{H}$ when $p=1$ to avoid confusion with norm $\left\|\cdot\right\|_{W_{1}^{H}}$.
$W_{p}^{1}(\rho,\sigma)$ |  The quantum Wasserstein distance of order $p$ on on $\mathcal{H}=\mathbb{C}^{D}$ defined by the trace distance $d_{1}(\ket{\psi},\ket{\varphi})=\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{1}$; see Sec. V.2.
$W_{p}^{C}(\rho,\sigma)$ |  The quantum Wasserstein distance of order $p$ on $\mathcal{H}=(\mathbb{C}^{2})^{\otimes n}$ defined by the complexity geometry metric $d_{C}$ [32]; see Sec. V.3.
Table 1: An overview of the Wasserstein distances used in this work, and the
relevant notation.

##  IV General properties

The goals of this section are to prove some fundamental attributes of
$W_{p}^{d}$ which will give an idea of how it behaves in the case of general
$d$. Throughout we will require some basic regularity conditions on $d$. As we
will see in more detail in the discussion following Cor. 13, not every metric
$d$ on the set of pure states induces a faithful Wasserstein distance. Thus,
we will restrict to metrics with respect to which the $2$-norm on the set of
traceless self-adjoint operators is Hölder continuous. In other words, we
require that there exists $\alpha\in(0,1]$ and $C>0$ for which for all
$\ket{\psi},\ket{\varphi}\in\mathbb{P}\mathcal{H}$ we have

$Cd(\ket{\psi},\ket{\varphi})^{\alpha}\geq\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{2}.$
(24)

Note that as we work in finite dimension, the $2$-norm is chosen here without
loss of generality. In the case $\alpha=1$, this is equivalent to the 2-norm
being Lipschitz with respect to $d$. The constant $C$ is a function of the
metric space $(\mathbb{P}\mathcal{H},d)$ and so can depend on the dimension of
$\mathcal{H}$. For some other properties such as continuity, we will require
that $d$ be continuous, noting that on $\mathcal{H}$ of finite dimension this
is equivalent to $d$ being uniformly continuous.

Given the main philosophical motivation of this definition, that the transport
distance between point masses in the classical setting is given by the
underlying metric, it’s important to show the quantum equivalent here. That
is, for all orders $p$ the quantum Wasserstein distance between pure states
agrees with the underlying metric.

######  Proposition 11.

Let $\mathcal{H}$ be a finite-dimensional Hilbert space with distance $d$ on
$\mathbb{P}\mathcal{H}$. Then for pure states
$|\psi\rangle\langle\psi|,|\varphi\rangle\langle\varphi|$, we have

$W_{p}^{d}(|\psi\rangle\langle\psi|,|\varphi\rangle\langle\varphi|)=d(\ket{\psi},\ket{\varphi}).$
(25)

###### Proof.

As $|\psi\rangle\langle\psi|$ and $|\varphi\rangle\langle\varphi|$ are pure,
the only permitted transport plan is $Q=\\{(1,\ket{\psi},\ket{\varphi})\\}$,
which has cost

$T_{p}^{d}(Q)=d(\ket{\psi},\ket{\varphi})^{p}$ (26)

and therefore we have
$W_{p}^{d}(|\psi\rangle\langle\psi|,|\varphi\rangle\langle\varphi|)=d(\ket{\psi},\ket{\varphi})$.
∎

######  Proposition 12.

Let $\mathcal{H}$ be a finite-dimensional Hilbert space with distance $d$ on
$\mathbb{P}\mathcal{H}$ with respect to which the $2$-norm is Hölder
continuous with constant $C>0$ and exponent $\alpha\in(0,1]$. Then for all
$\rho,\sigma\in\mathcal{D}(\mathcal{H})$, we have

$W_{p}^{d}(\rho,\sigma)\geq\frac{1}{C}\left\|\rho-\sigma\right\|_{2}^{1/\alpha}.$
(27)

###### Proof.

We have
$Cd(\ket{\psi},\ket{\varphi})^{\alpha}\geq\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{2}$
on $\mathbb{P}\mathcal{H}$, for $C>0$ and $\alpha\in(0,1]$. Let
$\left\\{\left(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}}\right)\right\\}$ be a
quantum transport plan between $\rho$ and $\sigma$. The functions $x\mapsto
x^{p}$ and $X\mapsto\left\|X\right\|_{2}^{1/\alpha}$ for traceless $X$ are
both convex. Hence

$\displaystyle\sum_{j}q_{j}d(\ket{\psi_{j}},\ket{\varphi_{j}})^{p}$
$\displaystyle\geq\left(\sum_{j}q_{j}d(\ket{\psi_{j}},\ket{\varphi_{j}})\right)^{p}$
(28)
$\displaystyle\geq\left(\sum_{j}q_{j}\frac{1}{C}\left\||\psi_{j}\rangle\langle\psi_{j}|-|\varphi_{j}\rangle\langle\varphi_{j}|\right\|_{2}^{1/\alpha}\right)^{p}$
(29)
$\displaystyle\geq\left(\frac{1}{C}\left\|\sum_{j}q_{j}(|\psi_{j}\rangle\langle\psi_{j}|-|\varphi_{j}\rangle\langle\varphi_{j}|)\right\|_{2}^{1/\alpha}\right)^{p}$
(30) $\displaystyle=\frac{1}{C^{p}}\left\|\rho-\sigma\right\|_{2}^{p/\alpha}.$
(31)

Hence taking the infimum and the $p^{\text{th}}$ root, we have
$W_{p}^{d}(\rho,\sigma)\geq\frac{1}{C}\left\|\rho-\sigma\right\|_{2}^{1/\alpha}$.
∎

This allows us to prove some of the metric properties of the $W_{p}^{d}$
distance, namely nondegeneracy and zero self-distance. Symmetry in this
definition is clear. Note that these fundamental properties have not always
been present in previous definitions such as in [38] where the definition has
non-zero self-distance.

######  Corollary 13.

Let $d$ be a distance on $\mathbb{P}\mathcal{H}$ with respect to which the
$2$-norm is Hölder continuous. For all
$\rho,\sigma\in\mathcal{D}(\mathcal{H})$, we have $W_{p}^{d}(\rho,\sigma)\geq
0$ with equality iff $\rho=\sigma$.

###### Proof.

$W_{p}^{d}(\rho,\sigma)\geq 0$ is clear, and equality when $\rho=\sigma$ can
be obtained from the taking transport plan
$\\{(c_{j},\ket{\psi_{j}},\ket{\psi_{j}}\\}$ where
$\rho=\sum_{j}c_{j}|\psi_{j}\rangle\langle\psi_{j}|$ is a spectral
decomposition. Faithfulness is a direct consequence of Proposition 12. ∎

For a general distance $d$, not necessarily satisfying property (24), we get
from the same proof above that $W_{p}^{d}(\rho,\sigma)\geq 0$ and
$W_{p}^{d}(\rho,\rho)=0$. It is not guaranteed, however, that a general
distance on $\mathbb{P}\mathcal{H}$ leads to a nondegenerate $W_{p}^{d}$. For
example, let $\mathcal{H}=\mathbb{C}^{2}$ with the standard basis
$\\{\ket{0},\ket{1}\\}$. For any non-negative real-valued function $f$ on
$\mathbb{P}\mathcal{H}$ with $f(\ket{0})=0$ and $f$ positive elsewhere, we can
define a metric $d$ as follows:

$d(\ket{\psi},\ket{\varphi})=\begin{cases}0&\text{if
}\ket{\psi}=\ket{\varphi}\\\
f(\ket{\psi})+f(\ket{\varphi})&\text{otherwise}.\\\ \end{cases}$ (32)

This forms a version of the SNCF metric, also known as the centralised railway
metric [15, p. 327], with $\ket{0}$ at the centre. This is a metric in which
travel is only permitted along rays emanating from a central point. We will
consider $f$ such that

$f\left(\sqrt{\frac{n-1}{n}}\ket{0}+\sqrt{\frac{1}{n}}\ket{1}\right)=f\left(\sqrt{\frac{n-1}{n}}\ket{1}-\sqrt{\frac{1}{n}}\ket{0}\right)=\frac{1}{n}$
(33)

for $n\in\mathbb{N}$ and $f(\ket{\psi})=2$ otherwise. This gives
$W_{1}^{d}\left(\ket{0},\frac{\mathbb{I}}{2}\right)=0$ by the sequence of
transport plans

$\left\\{\left(\frac{1}{2},\ket{0},\sqrt{\frac{n-1}{n}}\ket{0}+\sqrt{\frac{1}{n}}\ket{1}\right),\left(\frac{1}{2},\ket{0},\sqrt{\frac{n-1}{n}}\ket{1}-\sqrt{\frac{1}{n}}\ket{0}\right)\right\\}$
(34)

for $n\in\mathbb{N}$, each with cost $\frac{1}{n}$. We have shown that the
Hölder continuity condition is sufficient for $W_{p}^{d}$ to be nondegenerate,
but it is not immediately obvious whether or not it is necessary.

Furthermore, all symmetries of $(\mathbb{P}\mathcal{H},d)$ are inherited by
the quantum Wasserstein distances.

######  Proposition 14.

Let $1\leq p\leq\infty$ and $d$ be a metric on $\mathbb{P}\mathcal{H}$. The
group of unitary symmetries of the underlying metric $d$ is exactly the group
of conjugational symmetries of $W_{p}^{d}$.

###### Proof.

Let $U$ be a symmetry of $d$. $U$ is invertible, therefore there’s a direct
correspondence

$\\{(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}})\\}\longleftrightarrow\\{(q_{j},U\ket{\psi_{j}},U\ket{\varphi_{j}})\\}$
(35)

between quantum transport plans from $\rho$ to $\sigma$ and from $U\rho
U^{\dagger}$ to $U\sigma U^{\dagger}$. The distance $d$ is invariant under $U$
so cost is preserved under this correspondence, therefore the optimal cost is
also preserved.

Conversely, let unitary $V$ be a conjugational symmetry of $W_{p}^{d}$. Then
for all $\ket{\psi},\ket{\varphi}\in\mathbb{P}\mathcal{H}$, we have

$d(\ket{\psi},\ket{\varphi})=W_{p}^{d}(|\psi\rangle\langle\psi|,|\varphi\rangle\langle\varphi|)=W_{p}^{d}(V|\psi\rangle\langle\psi|V^{\dagger},V|\varphi\rangle\langle\varphi|V^{\dagger})=d(V\ket{\psi},V\ket{\varphi})$
(36)

and so $V$ is a symmetry of $d$. ∎

This allows us to prove a result on data processing for mixed unitary
channels. The data processing inequality is a central concept in both
classical and quantum information theory, and represents the idea that you
can’t create new information by processing old data: all the information you
have about an object is encoded in the rawest data you have. This concept also
exists in classical optimal transport: for measures $\mu$ on a metric space
$(X,d)$, measurable sets $A,B$ and a measurable map $f:X\to X$, we define the
pushforward $f_{*}\mu$ by $f_{*}\mu(B)=\mu(f_{-1}(B))$. If $f$ is
$1$-Lipschitz, then
$\mathcal{W}_{p}^{d}(\mu,\nu)\geq\mathcal{W}_{p}^{d}(f_{*}\mu,f_{*}\nu)$. We
can also recover this idea for mixed unitary channels of symmetries of the
space as follows:

######  Proposition 15.

Suppose $\Phi$ is a mixed unitary channel written as

$\Phi(\rho)=\sum_{k\in K}a_{k}U_{k}\rho U_{k}^{\dagger}\qquad a_{k}\geq
0,\sum_{k\in K}a_{k}=1$ (37)

for which each $U_{k}$ is a symmetry of $d$. Then for all orders $1\leq
p\leq\infty$ and all states $\rho$, $\sigma$, we have
$W_{p}^{d}(\rho,\sigma)\geq W_{p}^{d}(\Phi(\rho),\Phi(\sigma))$.

###### Proof.

Let $Q=\\{(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}})\\}_{j\in J}$ be any
$p^{\text{th}}$-order transport plan between $\rho$ and $\sigma$. We can then
define a transport plan
$Q^{\prime}=\\{(q_{j}a_{k},U_{k}\ket{\psi_{j}},U_{k}\ket{\varphi_{j}})\\}_{j\in
J,k\in K}$ between $\Phi(\rho)$ and $\Phi(\sigma)$ which has the same
$p^{\text{th}}$-order transport cost as $Q$. Taking the infimum over $Q$ gives
the result. ∎

It is also possible to guarantee the existence of an optimal transport plan
when the underlying distance $d$ is continuous and to bound the number of
elements of an optimal transport plan. This applies in particular when $d$ is
induced by a norm: that is to say, that there exists a norm
$\left\|\cdot\right\|_{d}$ on the self-adjoint traceless operators on
$\mathcal{H}$ such that
$d(\ket{\psi},\ket{\varphi})=\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{d}$
everywhere.

######  Proposition 16.

Let $d$ be a continuous distance on $\mathbb{P}{\mathcal{H}}$ and let
$\mathcal{H}$ have dimension $D$. The infimum in (14) is attained with a
transport plan containing at most $2D^{2}$ elements.

###### Proof.

Suppose $\\{(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}}\\}_{j\in J}$ is a
transport plan between $\rho$ and $\sigma$ with more than $2D^{2}$ elements.
Let $\mathcal{M}_{D}^{\text{sa}}$ be the space of self-adjoint operators on
$D$ dimensions. The space
$\mathcal{M}^{\text{sa}}_{D}\times\mathcal{M}_{D}^{\text{sa}}$ has real
dimension $2D^{2}$. Therefore among the elements
$(|\psi_{j}\rangle\langle\psi_{j}|,|\varphi_{j}\rangle\langle\varphi_{j}|)$ of
$\mathcal{M}^{\text{sa}}_{D}\times\mathcal{M}_{D}^{\text{sa}}$ we can find a
nontrivial linear relation

$\sum_{j\in
J}c_{j}(|\psi_{j}\rangle\langle\psi_{j}|,|\varphi_{j}\rangle\langle\varphi_{j}|)=0.$
(38)

Define subsets $K$, $L$ of $J$ by $K=\\{k\in J:c_{k}>0\\}$ and $L=\\{l\in
J:c_{l}<0\\}$. We can then rewrite this as

$\sum_{k\in
K}c_{k}(|\psi_{k}\rangle\langle\psi_{k}|,|\varphi_{k}\rangle\langle\varphi_{k}|)=\sum_{l\in
L}(-c_{l})(|\psi_{l}\rangle\langle\psi_{l}|,|\varphi_{l}\rangle\langle\varphi_{l}|)$
(39)

so that the coefficients $c_{k}$ and $-c_{l}$ are strictly positive. Without
loss of generality, we may assume that

$\sum_{k\in K}c_{k}d(\ket{\psi_{k}},\ket{\varphi_{k}})^{p}\geq\sum_{l\in
L}(-c_{l})d(\ket{\psi_{l}},\ket{\varphi_{l}})^{p}.$ (40)

We will aim to replace a portion of the transport plan corresponding to the
left-hand side, with a portion corresponding to the right-hand side.

Let $m=\min_{k\in K}\left\\{\frac{q_{k}}{c_{k}}\right\\}$, and let
$k^{\prime}$ be a minimiser. We can then form a new transport plan

$Q^{\prime}=\\{(q_{j},\ket{\psi_{j}},\ket{\varphi}_{j})\\}_{j\notin K\cup
L}\cup\\{(q_{k}-mc_{k},\ket{\psi_{k}},\ket{\varphi_{k}})\\}_{k\in
K}\cup\\{(q_{l}-mc_{l},\ket{\psi_{l}},\ket{\varphi_{l}})\\}_{l\in L}$ (41)

replacing $m$ times the left hand side of (39) with $m$ times the right hand
side. $k^{\prime}$ attains the minimum in the definition of $m$ so any
multiple of $(\ket{\psi_{k^{\prime}}},\ket{\varphi_{k^{\prime}}})$ is removed
from the plan. The linear relation means that the resulting plan is still a
transport plan between $\rho$ and $\sigma$, and (40) means that the cost is
not increased. Hence we can find a transport plan between $\rho$ and $\sigma$
with fewer elements, without increasing the transport cost.

We may then optimise the transport cost over all transport plans of size at
most $2D^{2}$. This set is compact and the $p^{\text{th}}$-order cost (13) of
a transport plan is a continuous function of the transport plan $Q$ for $d$
continuous, so the infimum is attained. ∎

The existence of an optimal transport plan will be particularly useful later
when looking at examples, applications, and further properties.

Another key property of this $W_{p}^{d}$ is continuity, which we can prove
provided that $d$ is continuous. This will be necessary for a coherent
definition of a dual in Sec. IV.1.

######  Proposition 17.

Suppose $d$ is continuous on $\mathbb{P}\mathcal{H}$ and let $1\leq p<\infty$.
Then $W_{p}^{d}$ is uniformly continuous.

###### Proof.

The proof is quite technical and not particularly instructive, so has been
placed in Appendix D.1 for the convenience of the reader.

∎

For $p=1$ specifically, we furthermore have joint convexity.

######  Proposition 18.

$W_{1}^{d}$ is jointly convex.

###### Proof.

Suppose $\rho_{1}$, $\sigma_{1}$, $\rho_{2}$, and $\sigma_{2}$ are quantum
states, and let $r_{1}+r_{2}=1$, $r_{i}\geq 0$. Let
$Q_{1}=\\{(q_{1,j},\ket{\psi_{1,j}},\ket{\varphi_{1,j}})\\}_{j}$ be any
transport plan between $\rho_{1}$ and $\sigma_{1}$, and
$Q_{2}=\\{(q_{2,k},\ket{\psi_{2,k}},\ket{\varphi_{2,k}})\\}_{k}$ any transport
plan between $\rho_{2}$ and $\sigma_{2}$. Then $Q=r_{1}Q_{1}\cup
r_{2}Q_{2}\coloneqq\\{(r_{1}q_{1,j},\ket{\psi_{1,j}},\ket{\varphi_{1,j}})\\}_{j}\cup\\{(r_{2}q_{2,k},\ket{\psi_{2,k}},\ket{\varphi_{2,k}})\\}_{k}$
is a transport plan between $r_{1}\rho_{1}+r_{2}\rho_{2}$ and
$r_{1}\sigma_{1}+r_{2}\sigma_{2}$.

Then we have

$\displaystyle
T_{1}^{d}(Q)=\sum_{j}r_{1}q_{1,j}d(\ket{\psi_{1,j}},\ket{\varphi_{1,j}})+\sum_{k}r_{2}q_{2,k}d(\ket{\psi_{2,k}},\ket{\varphi_{2,k}})=r_{1}T_{1}^{d}(Q_{1})+r_{2}T_{1}^{d}(Q_{2}).$
(42)

Taking the infimum over $Q_{1}$ and $Q_{2}$ shows that
$W_{1}^{d}(r_{1}\rho_{1}+r_{2}\rho_{2},r_{1}\sigma_{1}+r_{2}\sigma_{2})\leq
r_{1}W_{1}^{d}(\rho_{1},\sigma_{1})+r_{2}W_{1}^{d}(\rho_{2},\sigma_{2})$. ∎

###  IV.1 Dual picture

We can now take a look at the dual picture for the first-order transport
distance, with some regularity conditions on the underlying metric $d$ which
allow the dual to be well-defined. As we will see later, this will then allow
us to define a version of the Wasserstein distance for $p=1$ that satisfies
the triangle inequality and inherits many of the properties of the original
$W_{1}^{d}$.

######  Definition 19.

Let $d$ be a metric on $\mathbb{P}\mathcal{H}$. Suppose $d$ is continuous and
that the 2-norm is Lipschitz with respect to $d$. We define the dual constant
of a self-adjoint operator $O$ as

$L_{d}(O)=\sup_{\rho\neq\sigma}\frac{\text{{\em
Tr}}[O(\rho-\sigma)]}{W_{1}^{d}(\rho,\sigma)}.$ (43)

We refer to this as the $d$-Lipschitz constant. Usually, in the classical
case, the Lipschitz constant of a function with respect to a metric is defined
by taking the supremum only with respect to point masses, not probability
distributions. As we see below in Proposition 20, we can also take w.l.o.g.
the supremum only with respect to pure states and only define it with mixed
states for convenience.

######  Proposition 20.

Let $d$ be a metric on $\mathbb{P}\mathcal{H}$. Suppose $d$ is continuous and
that the 2-norm is Lipschitz with respect to $d$. Then

$L_{d}(O)=\sup_{\ket{\psi}\neq\ket{\varphi}}\frac{\text{{\em
Tr}}[O(|\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|)]}{d(\ket{\psi},\ket{\varphi})}.$
(44)

###### Proof.

For any $\rho$ and $\sigma$, let
$Q=\\{(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}})\\}$ be an optimal transport
plan between them. Then

$\displaystyle L_{d}(O)$
$\displaystyle=\sup_{\rho\neq\sigma}\frac{\text{Tr}[O(\rho-\sigma)]}{W_{1}^{d}(\rho,\sigma)}$
(45)
$\displaystyle=\sup_{\rho\neq\sigma}\frac{\sum_{j}q_{j}\text{Tr}[O(|\psi_{j}\rangle\langle\psi_{j}|-|\varphi_{j}\rangle\langle\varphi_{j}|)]}{\sum_{j}q_{j}d(\ket{\psi},\ket{\varphi})}$
(46)
$\displaystyle\leq\sup_{\rho\neq\sigma}\max_{j}\frac{\text{Tr}[O(|\psi_{j}\rangle\langle\psi_{j}|-|\varphi_{j}\rangle\langle\varphi_{j}|)]}{d(\ket{\psi},\ket{\varphi})}$
(47)
$\displaystyle\leq\sup_{\ket{\psi}\neq\ket{\varphi}}\frac{\text{Tr}[O(|\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|)]}{d(\ket{\psi},\ket{\varphi})}$
(48)
$\displaystyle=\sup_{\ket{\psi}\neq\ket{\varphi}}\frac{\text{Tr}[O(|\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|)]}{W_{1}^{d}(|\psi\rangle\langle\psi|,|\varphi\rangle\langle\varphi|)}\leq
L_{d}(O)$ (49)

and so this is a chain of equalities. ∎

Importantly, this means that this $L_{d}$ is a function of the metric $d$ and
is independent of our definition of $W_{p}^{d}$. It also means that our choice
of $p=1$ in the definition is arbitrary: defining
$L_{d,p}(O)=\sup_{\rho\neq\sigma}\text{Tr}[O(\rho-\sigma)]/W_{p}^{d}(\rho,\sigma)$
gives the same quantity as $L_{d}(O)$. It is also important to note that under
the regularity conditions already established on $d$, this quantity is a norm.

######  Proposition 21.

Let $d$ be a continuous metric on $\mathbb{P}\mathcal{H}$ such that the 2-norm
is Lipschitz with respect to $d$. Then $L_{d}(O)$ is a norm on the space of
traceless self-adjoint operators.

###### Proof.

For finiteness, we use $\text{Tr}[O(\rho-\sigma)]\leq
2\left\|O\right\|_{\infty}\left\|\rho-\sigma\right\|_{1}$ together with
Proposition 12.

To show nondegeneracy, suppose $O$ is nonzero and let $\ket{\psi}$,
$\ket{\varphi}$ be eigenstates of $O$ with positive and negative eigenvalues
respectively, which must exist as $O$ is traceless. Then
$\rho=|\psi\rangle\langle\psi|$, $\sigma=|\varphi\rangle\langle\varphi|$ gives
$\text{Tr}[O(\rho-\sigma)]/W_{1}^{d}(\rho,\sigma)>0$.

For the other norm properties, clearly $L_{d}(\lambda O)=|\lambda|L_{d}(O)$.
And suppose we have Hermitian self-adjoint operators $O_{1}$ and $O_{2}$. Let
the supremum in $L_{d}(O_{1}+O_{2})$ be achieved by $\rho$ and $\sigma$, then

$L_{d}(O_{1}+O_{2})=\text{Tr}[(O_{1}+O_{2})(\rho-\sigma)]/W_{1}^{d}(\rho,\sigma)=\text{Tr}[O_{1}(\rho-\sigma)]/W_{1}^{d}(\rho,\sigma)+\text{Tr}[O_{2}(\rho-\sigma)]/W_{1}^{d}(\rho,\sigma)\leq
L_{d}(O_{1})+L_{d}(O_{2})$ (50)

which proves the triangle inequality for $L_{d}$. ∎

We can then dualise one more time and consider the norm

$\displaystyle\|\rho-\sigma\|_{DW_{1}^{d}}=\sup\limits_{L_{d}(O)\leq
1}\text{Tr}[O(\rho-\sigma)].$ (51)

######  Proposition 22.

Let $\left\|\cdot\right\|_{DW_{1}^{d}}$ be defined by
$\left\|X\right\|_{DW_{1}^{d}}=\sup\limits_{L_{d}(O)\leq 1}\text{\em{Tr}}[OX]$
on the space of traceless Hermitian operators. Then this is a norm, and on
quantum states $\rho,\sigma$ we have

$W_{1}^{d}(\rho,\sigma)\geq\left\|\rho-\sigma\right\|_{DW_{1}^{d}}.$ (52)

###### Proof.

For the norm, it is clear that when $X=0$ we have
$\left\|X\right\|_{WD_{1}^{d}}$ equal to zero. The fact that $\left\|\lambda
X\right\|_{DW_{1}^{d}}=|\lambda|\left\|X\right\|_{DW_{1}^{d}}$ is clear from
the definition, and the triangle inequality holds as

$\left\|X_{1}+X_{2}\right\|_{DW_{1}^{d}}=\sup_{L_{d}(O)\leq
1}\text{Tr}[O(X_{1}+X_{2})]\leq\sup_{L_{d}(O_{1})\leq
1}\text{Tr}[O_{1}X_{1}]+\sup_{L_{d}(O_{2})\leq
1}\text{Tr}[O_{2}X_{2}]=\left\|X_{1}\right\|_{DW_{1}^{d}}+\left\|X_{2}\right\|_{DW_{1}^{d}}.$
(53)

For nondegeneracy, take $O$ to be the projector onto the positive part of $X$
normalised to $L_{d}(O)=1$, which gives $\text{Tr}[OX]>0$.

On states $\rho,\sigma$, let $O$ be any operator with $L_{d}(O)\leq 1$. Then

$1\geq
L_{d}(O)=\sup_{\rho^{\prime}\neq\sigma^{\prime}}\frac{\text{Tr}[O(\rho^{\prime}-\sigma^{\prime})]}{W_{1}^{d}(\rho^{\prime},\sigma^{\prime})}\geq\frac{\text{Tr}[O(\rho-\sigma)]}{W_{1}^{d}(\rho,\sigma)}$
(54)

and so $\text{Tr}[O(\rho-\sigma)]\leq W_{1}^{d}(\rho,\sigma)$. Taking the
supremum over $O$ gives $\left\|\rho-\sigma\right\|_{DW_{1}^{d}}\leq
W_{1}^{d}(\rho,\sigma)$. ∎

The inequality
$W_{1}^{d}(\rho,\sigma)\geq\left\|\rho-\sigma\right\|_{DW_{1}^{d}}$ is
important in our understanding of these quantities. It is as yet unclear
whether or not equality holds in this equation, and establishing the
conditions for equality is an important open problem, not least because this
would allow us to recover the triangle inequality for $W_{1}^{d}$. There are
some simple necessary conditions for equality in this equation, namely that
$W_{1}^{d}$ depends only on $\rho-\sigma$, and that it scales like a norm.

However, we can consider the case where there exists a metric
$\left\|\cdot\right\|_{d}$ such that
$d(\ket{\psi},\ket{\varphi})=\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{d}$.
Replacing $\left\|\cdot\right\|_{2}$ with $\left\|\cdot\right\|_{d}$ in the
proof of Proposition 12, and using
$d(\ket{\psi},\ket{\varphi})=\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{d}$,
we get that $W_{1}^{d}(\rho,\sigma)\geq\left\|\rho-\sigma\right\|_{d}$. This
allows us to recover even more properties of
$\left\|\cdot\right\|_{DW_{1}^{d}}$:

######  Proposition 23.

Suppose that there exists norm $\left\|\cdot\right\|_{d}$ such that
$d(\ket{\psi},\ket{\varphi})=\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{d}$.
Then:

  1. 1.

$W_{1}^{d}(\rho,\sigma)\geq\left\|\rho-\sigma\right\|_{DW_{1}^{d}}\geq\left\|\rho-\sigma\right\|_{d}.$

  2. 2.

When $\rho$ and $\sigma$ are pure, this becomes an equality.

  3. 3.

For all $1\leq q\leq\infty$, we have $W_{q}^{d}=W_{q}^{DW_{1}^{d}}$.

###### Proof.

As discussed above, we know that $\left\|\rho-\sigma\right\|_{d}\leq
W_{1}^{d}(\rho,\sigma)$. Letting $\left\|\cdot\right\|_{D}$ be the dual to
$\left\|\cdot\right\|_{d}$ on the space of traceless Hermitian operators, we
have then that $\left\|O\right\|_{D}\geq L_{d}(O)$. Dualising once more, and
noting that the double dual of a norm is the norm itself, we know for all $X$
that $\left\|X\right\|_{d}\leq\left\|X\right\|_{DW_{1}^{d}}$. Combining this
with Proposition 22 gives the chain

$W_{1}^{d}(\rho,\sigma)\geq\left\|\rho-\sigma\right\|_{DW_{1}^{d}}\geq\left\|\rho-\sigma\right\|_{d}.$
(55)

If $\rho,\sigma$ are pure then by Proposition 11 we have
$W_{1}^{d}(\rho,\sigma)=\left\|\rho-\sigma\right\|_{d}$, and so the whole
chain (55) is an equality. It follows that for $\ket{\psi},\ket{\varphi}$, we
have

$d(\ket{\psi},\ket{\varphi})=\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{DW_{1}^{d}}.$
(56)

This means in turn that for all $1\leq q\leq\infty$, we have
$W_{q}^{d}=W_{q}^{DW_{1}^{d}}$. ∎

We present this norm here, not as a replacement for $W_{p}^{d}$, but because
the two complement each other nicely. This method of defining
$\left\|\cdot\right\|_{DW_{1}^{d}}$ via a supremum of a trace of the
difference of two states over Lipschitz observables mirrors exactly the
Kantorovich-Rubinstein theorem from classical optimal transport [48, p. 34].
In taking the double dual, we gain an easy proof of the triangle inequality,
albeit at the expense of flexibility of order $p$ and of natural
interpretation in terms of transport plans and couplings. We have seen here
that $W_{p}^{d}$ and $\left\|\cdot\right\|_{DW_{1}^{d}}$ are closely related,
particularly when $d$ is induced by a norm. We will see later in Sec. V.1 and
Sec. V.2 that in many cases $\left\|\cdot\right\|_{DW_{1}^{d}}$ essentially
recovers the original norm $\left\|\cdot\right\|_{d}$.

##  V Special instances

###  V.1 $W_{1}^{H}$ distance on $n$-qudit systems

[36] introduced a quantum Wasserstein distance of order 1 which generalises
the Hamming distance on the discrete hypercube. This is defined on Hilbert
space $\mathcal{H}=\left(\mathbb{C}^{d}\right)^{\otimes n}$. The distance
defined is normed, and we notate it here by
$\left\|\rho-\sigma\right\|_{W_{1}^{H}}$.

$\left\|\cdot\right\|_{W_{1}^{H}}$ has the interesting property that it
recovers the classical first-order Wasserstein distance $\mathcal{W}_{1}^{H}$
on the Hamming cube, for states that are diagonal in the computational basis.
That is, for $r$ and $s$ probability distributions on
$\\{0,1,\dots,d-1\\}^{n}$, and states
$\rho=\sum_{x\in\\{0,1,\dots,d-1\\}^{n}}r(x)|x\rangle\langle x|$ and
$\sigma=\sum_{y\in\\{0,1,\dots,d-1\\}^{n}}|y\rangle\langle y|$ we have

$\left\|\rho-\sigma\right\|_{W_{1}^{H}}=\mathcal{W}_{1}^{H}(r,s).$ (57)

Furthermore, its formulation mirrors the Kantorovich-Rubinstein theorem with
the definition of the quantum Lipschitz constant [36, Definition 8]:

$\left\|O\right\|_{L}=\max\\{\text{Tr}[O(\rho-\sigma)]:\left\|\rho-\sigma\right\|_{W_{1}^{H}}\leq
1\\}.$ (58)

It then induces a metric $d_{H}$ on $\mathbb{P}\mathcal{H}$, given by
$d(\ket{\psi},\ket{\varphi})=\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{W_{1}^{H}}$,
from which we can define a $p^{\text{th}}$ order Wasserstein distance
$W_{p}^{H}$ as above. For the special case $p=1$, we will write $W_{p=1}^{H}$
to avoid confusion.

We might expect that property in equation (57) extends to the $W_{p}^{H}$
distance: that is, that for classical states $\rho$ and $\sigma$ defined by
$r$ and $s$ as above, that

$W_{p}^{H}(\rho,\sigma)=\mathcal{W}_{p}^{H}(r,s).$ (59)

However, in this case, we recover some interesting differences between the
classical and quantum definitions of the $p$-Wasserstein distances, by taking
‘quantum shortcuts’ in our transport plans.

For $p=1$, equality occurs in (59): an optimal classical coupling $\gamma$
between $r$ and $s$ gives us the transport plan
$\\{(\gamma(x,y),\ket{x},\ket{y}\\}_{x,y\in\\{0,1,\dots,d-1\\}^{n}}$ which has
transport cost $\mathcal{W}_{1}^{H}(r,s)$, and we know that
$W_{p=1}^{H}(\rho,\sigma)\geq\left\|\rho-\sigma\right\|_{W_{1}^{H}}=\mathcal{W}_{1}^{H}(r,s)$
from Proposition 12 above and Proposition 6 of [36].

However, for $p>1$, we can find quantum ‘shortcuts’ between classical states.
Indeed, consider the case $n=d=2$ and the states $\rho=|00\rangle\langle 00|$,
$\sigma=\frac{\mathbb{I}^{\otimes 2}}{4}$. Classically, the distributions
$\delta_{00}$ and the uniform distribution have a $\mathcal{W}_{\infty}^{H}$
distance of $2$. However, consider the quantum transport plan

$\left\\{\left(\frac{1}{4},\ket{00},\ket{\varphi^{\pm\pm}}\right)\right\\}$
(60)

for the standard 2-qubit Bell states

$\begin{split}\ket{\varphi^{++}}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})\qquad\ket{\varphi^{+-}}=\frac{1}{\sqrt{2}}(\ket{00}-\ket{11})\\\
\ket{\varphi^{-+}}=\frac{1}{\sqrt{2}}(\ket{01}+\ket{10})\qquad\ket{\varphi^{--}}=\frac{1}{\sqrt{2}}(\ket{01}-\ket{10}).\end{split}$
(61)

This corresponds to the separable coupling

$\tau=\sum_{\pm\pm}\frac{1}{4}|00\rangle\langle
00|\otimes|\varphi^{\pm\pm}\rangle\langle\varphi^{\pm\pm}|$ (62)

of $\rho$ and $\sigma$. Proposition 2 of [36] shows that both

$\left\||00\rangle\langle
00|-|\varphi^{+\pm}\rangle\langle\varphi^{+\pm}|\right\|_{W_{1}^{H}}\leq\sqrt{2}\qquad\text{and}\qquad\left\||00\rangle\langle
00|-|\varphi^{-\pm}\rangle\langle\varphi^{-\pm}|\right\|_{W_{1}^{H}}\leq\frac{\sqrt{5}+3}{4}.$
(63)

This in turn gives us
$W_{\infty}^{H}(\rho,\sigma)\leq\max\left\\{\sqrt{2},\frac{\sqrt{5}+3}{4}\right\\}=\sqrt{2}$.

However, from Proposition 14 we see that $W_{p}^{H}$ does inherit the
invariance properties of $\left\|\cdot\right\|_{W_{1}^{H}}$, namely invariance
under local unitaries and qubit swaps.

We also can relate the double-dual norm $\left\|\cdot\right\|_{DW_{1}^{H}}$ to
the norm $\left\|\cdot\right\|_{W_{1}^{H}}$ as follows.

######  Proposition 24.

Let $\rho,\sigma$ be states on
$\mathcal{H}=\left(\mathbb{C}^{d}\right)^{\otimes n}$. Then

$2\left\|\rho-\sigma\right\|_{W_{1}^{H}}\geq\left\|\rho-\sigma\right\|_{DW_{1}^{H}}\geq\left\|\rho-\sigma\right\|_{W_{1}^{H}}.$
(64)

###### Proof.

The lower bound comes from equation (55). For the upper bound, we refer to the
dual $\left\|O\right\|_{L}$, and show that $\left\|O\right\|_{L}\leq
2L_{d}(O)$. Taking the dual of this equation will give the upper bound
required.

We have from [36, Proposition 15], that

$2\max_{1\leq i\leq
n}\left\|O-\text{Tr}_{i}O\otimes\mathbb{I}_{i}\right\|_{\infty}\geq\left\|O\right\|_{L}.$
(65)

So we will show that $L_{d}(O)\geq\max_{1\leq i\leq
n}\left\|O-\text{Tr}_{i}O\otimes\mathbb{I}_{i}\right\|_{\infty}$.

Fix $i$, and let $\ket{\psi}$ be an eigenvector of
$O-\text{Tr}_{i}O\otimes\mathbb{I}_{i}$ with an eigenvalue which is maximal in
absolute value, assuming without loss of generality that this is positive. Let
$\mu_{\text{Haar}}$ be the Haar measure on the unitary group $\mathcal{U}(d)$
acting on the $i^{\text{th}}$ qudit. Writing $U_{i}$ for a unitary on the
$i^{\text{th}}$ qubit, $\mathbb{I}_{i}$ for the identity on the
$i^{\text{th}}$ qubit, and $\mathbb{I}_{\hat{i}}$ for the identity acting on
all except the $i^{\text{th}}$ qubit, we note that

$\mathbb{E}_{U_{i}\sim\mu_{\text{Haar}}}\text{Tr}[(O-\text{Tr}_{i}O\otimes\mathbb{I}_{i})U_{i}\otimes\mathbb{I}_{\hat{i}}|\psi\rangle\langle\psi|U^{\dagger}\otimes\mathbb{I}_{\hat{i}}]=\text{Tr}[(O-\text{Tr}_{i}O\otimes\mathbb{I}_{i})\text{Tr}_{i}|\psi\rangle\langle\psi|\otimes\mathbb{I}_{i}/d]=0.$
(66)

Therefore taking any $U_{i}\in\mathcal{U}(d)$ such that $U_{i}\ket{\psi}$ has
$\text{Tr}[(O-\text{Tr}_{i}O\otimes\mathbb{I}_{i})U_{i}\otimes\mathbb{I}_{\hat{i}}|\psi\rangle\langle\psi|U_{i}^{\dagger}\otimes\mathbb{I}_{\hat{i}}]<0$,
let this $U_{i}\otimes\mathbb{I}_{\hat{i}}\ket{\psi}$ be $\ket{\varphi}$. Note
that
$\text{Tr}_{i}[|\psi\rangle\langle\psi|]=\text{Tr}_{i}[|\varphi\rangle\langle\varphi|]$.
This gives

$\displaystyle\frac{\text{Tr}[O(|\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|)]}{\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{W_{1}^{H}}}$
$\displaystyle\geq\frac{\text{Tr}[O(|\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|)]}{1}$
(67)
$\displaystyle=\text{Tr}[O(|\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|)]+\text{Tr}[\text{Tr}_{i}O(\text{Tr}_{i}|\psi\rangle\langle\psi|-\text{Tr}_{i}|\psi\rangle\langle\psi|])]$
(68)
$\displaystyle=\text{Tr}[(O-\text{Tr}_{i}O\otimes\mathbb{I}_{i})(|\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|)]$
(69)
$\displaystyle\geq\left\|O-\text{Tr}_{i}O\otimes\mathbb{I}_{i}\right\|_{\infty}$
(70)

which concludes the proof. ∎

###  V.2 Trace distance

In this section, we consider the case where $d$ is induced by the trace
distance (that is, half the trace norm). For pure states
$\ket{\psi},\ket{\varphi}$, we have

$d(\ket{\psi},\ket{\varphi})=\frac{1}{2}\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{1}=\sqrt{1-\left\lvert\braket{\psi}{\varphi}\right\rvert^{2}}.$
(71)

The trace distance, when applied to pure states on a $D$-dimensional space, is
a direct analogue of the discrete metric on a space with $D$ elements. This
means that it is the simplest case to consider in terms of optimal transport.
The trace distance on mixed states can also be considered as a quantum
generalisation of the total variation distance
$d_{TV}(\mu,\nu)=\sum_{i=1}^{D}|\mu(i)-\nu(i)|$, which is the classical
$\mathcal{W}_{1}$ distance on this discrete space.

We write the $p^{\text{th}}$-order transport cost associated with this
distance as $T_{p}^{1}$ and the associated quantum Wasserstein distance as
$W_{p}^{1}$. We note from Proposition 2 of [38] that this agrees with
$W_{p}^{H}$ in the case of a single qudit. From this we inherit all the
properties of $W_{p}^{H}$, notably Proposition 24 which gives us
$\left\|\rho-\sigma\right\|_{1}\geq\left\|\rho-\sigma\right\|_{DW_{1}^{1}}\geq\frac{1}{2}\left\|\rho-\sigma\right\|_{1}$.
However, we can go one step further.

######  Proposition 25.

Let $\rho,\sigma$ be states on $\mathbb{C}^{d}$. Then

$\left\|\rho-\sigma\right\|_{DW_{1}^{1}}=\frac{1}{2}\left\|\rho-\sigma\right\|_{1}.$
(72)

###### Proof.

That
$\left\|\rho-\sigma\right\|_{DW_{1}^{1}}\geq\frac{1}{2}\left\|\rho-\sigma\right\|_{1}$
is a direct consequence of Proposition 12. For the other direction, we once
again consider the dual. The double dual of the $1$-norm is itself, and so to
show inequality in the other direction we need only show for any traceless
Hermitian operator $O$ that

$\sup_{\rho\neq\sigma}\frac{\text{Tr}[O(\rho-\sigma)]}{\frac{1}{2}\left\|\rho-\sigma\right\|_{1}}\leq
L_{1}(O)$ (73)

as taking the dual of this equation would give the inequality in the other
direction.

For any $\rho\neq\sigma$, let $\rho-\sigma=\rho^{\prime}-\sigma^{\prime}$ for
$\rho^{\prime},\sigma^{\prime}$ positive semidefinite operators with
$\rho^{\prime}\perp\sigma^{\prime}$. Then write
$\rho^{\prime}=\sum_{j}\mu_{j}|\psi_{j}\rangle\langle\psi_{j}|$ and
$\sigma^{\prime}=\sum_{k}\nu_{k}|\varphi_{k}\rangle\langle\varphi_{k}|$ in
spectral decompositions. Let $\gamma$ be a classical coupling of the measures
$\mu$ and $\nu$. It then follows that

$\frac{1}{2}\left\|\rho-\sigma\right\|_{1}=\frac{1}{2}\sum_{j,k}\gamma_{j,k}\left\||\psi_{j}\rangle\langle\psi_{j}|-|\varphi_{k}\rangle\langle\varphi_{k}|\right\|_{1}$
(74)

and so

$\frac{\text{Tr}[O(\rho-\sigma)]}{\frac{1}{2}\left\|\rho-\sigma\right\|_{1}}=\frac{\sum_{j,k}\gamma_{j,k}\text{Tr}[O(|\psi_{j}\rangle\langle\psi_{j}|-|\varphi_{k}\rangle\langle\varphi_{k}|)]}{\sum_{j,k}\gamma_{j,k}\left\||\psi_{j}\rangle\langle\psi_{j}|-|\varphi_{k}\rangle\langle\varphi_{k}|\right\|_{1}}\leq\sup_{\ket{\psi}\neq\ket{\varphi}}\frac{\text{Tr}[O(|\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|)]}{\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{1}}=L_{1}(O)$
(75)

which concludes the proof. ∎

###  V.3 Complexity geometry

A distance $d(I,U)$ giving lower bounds for the complexity of synthesising a
unitary $U\in\mathcal{SU}(2^{n})$ from a universal one- and two-qubit gate set
was defined in [32] and refined in [16, 31]. This distance $d$ on
$\mathcal{SU}(2^{n})$ is a geodesic distance of a Riemannian manifold, where
the Riemannian metric is chosen such that local travel is fast in directions
corresponding to multiplication by low-weight unitaries, and slow in
directions corresponding to multiplication by high-weight unitaries.

This idea of expressing quantum gate complexity in terms of Riemannian
geometry has seen renewed interest in recent years, from applications in black
hole thermodynamics [6, 24] to rigid bodies [7] and the complexity of typical
unitaries [5]. However, this metric is originally defined as a distance
between unitaries, with the complexity of unitary expressed in terms of its
distance from the identity. This extends naturally to distances between pure
states as the lowest complexity of a unitary which transforms one into the
other. Our optimal transport formulation allows for a natural extension of
this metric to mixed states, in a way that can be considered as quantifying
the lowest possible complexity of transforming one mixed state into another. A
related approach in [45] extends a variation of this complexity geometry
metric, one in which multiplication by a unitary is independent of weight, to
mixed states using purification methods described in [1].

Formally, [32] defines a right-invariant Riemannian metric $g$ on
$\mathcal{SU}(2^{n})$ given by the following inner product on
$T_{I}\mathcal{SU}(2^{n})$. A vector $X$ in the tangent space
$T_{U}\mathcal{SU}(2^{n})$ to $\mathcal{SU}(2^{n})$ at $U$ is identified with
its Hamiltonian representation $H$, given by
$X=\left[\frac{\text{d}}{\text{d}t}e^{-iHt}U\right]_{t=0}$. $H$ can be
decomposed as $H_{P}+H_{Q}$, where $H_{P}$ is a linear combination of Pauli
matrices of weight at most $2$, and $H_{Q}$ is a linear combination of Pauli
matrices of weight at least $3$. Defining operations $\mathcal{P}$ and
$\mathcal{Q}$ by $\mathcal{P}(H)=H_{P}$ and $\mathcal{Q}(H)=H_{Q}$, the inner
product on $T_{U}\mathcal{SU}(2^{n})$ is then defined by

$\langle
H,J\rangle=\frac{\text{Tr}(H\mathcal{P}(J))+q\text{Tr}(H\mathcal{Q}(J))}{2^{n}}$
(76)

where $q>4^{n}$ is a penalty parameter. The length $\sqrt{\langle H,H\rangle}$
will then be of order $1$ for 2-local Hamiltonians, and of order $q$
otherwise. $q>4^{n}$ is chosen such that for any geodesic, the associated
Hamiltonian path has an approximately low-weight decomposition.

The length of a curve $U(t)$ defined by evolution $\dot{U}(t)=-iH(t)U(t)$ is
then defined as standard by

$\int\sqrt{\langle H(t),H(t)\rangle}\text{d}t$ (77)

and the distance $d(I,U)$ is simply the geodesic distance on this Riemannian
manifold.

The main purpose of $d$ is to find a geometric interpretation of gate
complexity, and [16, Equation 3] gives bounds for $d$ in terms of gate
complexity. Let $G(U)$ be the exact gate complexity of $U$, i.e. the minimal
number of one- and two-qubit gates required to synthesise $U$ exactly. For
$\epsilon\geq 0$, let $G(U,\epsilon)$ be the minimal number of one- and two-
qubit gates required to synthesise a gate $V$ such that
$\left\|U-V\right\|_{\infty}\leq\epsilon$, also known as the
$\epsilon$-approximate gate complexity. We then have bounds

$\frac{\kappa G(U,\epsilon)^{1/3}\epsilon^{2/3}}{n^{2}}\leq d(I,U)\leq G(U)$
(78)

for some constant $\kappa>0$.

With these unitaries acting on the $n$-qubit space
$\mathcal{H}=(\mathbb{C}^{2})^{\otimes n}$, we can define a metric $d_{C}$ on
$\mathbb{P}\mathcal{H}$ by

$d_{C}(\ket{\psi},\ket{\varphi})=\min\left\\{d(I,U):U\in\mathcal{SU}(2^{n}),U\ket{\psi}=\ket{\varphi}\right\\}.$
(79)

The metric properties of $d_{C}$ come directly from the metric properties and
right-invariance of $d$. Operationally, this gives a lower bound for the
minimum circuit complexity required to synthesise $\ket{\varphi}$ from
$\ket{\psi}$. Indeed,

$\frac{\kappa(\min\\{G(U,\epsilon):U\ket{\psi}=\ket{\varphi}\\})^{1/3}\epsilon^{2/3}}{n^{2}}\leq
d_{C}(\ket{\psi},\ket{\varphi})\leq\min\\{G(U):U\ket{\psi}=\ket{\varphi}\\}.$
(80)

In order to say anything useful about the quantum Wasserstein distance induced
by this metric $d_{C}$, we must demonstrate some basic continuity properties.
Continuity of $d_{C}$ is inherent from the fact that $d$ is a geodesic
distance on a Riemannian manifold and Hölder continuity of the 2-norm with
respect to $d_{C}$ comes from the following proposition.

######  Proposition 26.

Let $U\in\mathcal{SU}(2^{n})$. Then

$d(I,U)\geq 2^{-n/2}\left\|U-I\right\|_{2}.$ (81)

###### Proof.

Suppose $U(t)$ is a geodesic curve in $\mathcal{SU}(2^{n})$ with $U(t)=I$ and
$U(T)=U$, generated by Hamiltonian $H(t)$ satisfying $\dot{U}(t)=-iH(t)U(t)$.
Then for any $N$, we have

$\displaystyle\left\|U-I\right\|_{2}$
$\displaystyle\leq\sum_{j=0}^{N-1}\left\|U\left((j+1)T/N\right)-U\left(jT/N\right)\right\|_{2}$
(82)
$\displaystyle\leq\sum_{j=0}^{N-1}\left\|i(T/N)H\left(jT/N\right)U\left(jT/N\right)+o\left(T/N\right)\right\|_{2}$
(83) $\displaystyle\to\int_{0}^{T}\left\|H(t)\right\|_{2}\text{d}t\qquad\text{
as }N\to\infty$ (84) $\displaystyle\leq 2^{n/2}\int_{0}^{T}\sqrt{\langle
H(t),H(t)\rangle}\text{d}t$ (85)

using the inequality $2^{-n/2}\left\|H\right\|_{2}\leq\sqrt{\langle
H,H\rangle}$ in the last line. The required regularity to bound $o(T/N)$
uniformly comes from the smoothness of the metric.

Taking the infimum over such curves gives $d(I,U)\geq
2^{-n/2}\left\|U-I\right\|_{2}$. ∎

######  Corollary 27.

Let $\ket{\psi},\ket{\varphi}\in\mathbb{P}\mathcal{H}$. Then

$2^{(n+1)/2}d_{C}(\ket{\psi},\ket{\varphi})\geq\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{2}.$
(86)

###### Proof.

Let $U\in\mathcal{SU}(2^{n})$ have $U\ket{\psi}=\ket{\varphi}$. Then

$\displaystyle\left\|U-I\right\|_{2}^{2}$
$\displaystyle=\text{Tr}[(U-I)^{\dagger}(U-I)]$ (87)
$\displaystyle\geq\braket{\psi}{(U-I)^{\dagger}(U-I)}{\psi}$ (88)
$\displaystyle\geq 2(1-|\braket{\psi}{\varphi}|).$ (89)

Using the formula
$\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{2}^{2}=2(1-|\braket{\psi}{\varphi}|)^{2}$,
we get

$\displaystyle\left\|U-I\right\|_{2}^{2}$ $\displaystyle\geq
2\left(1-\sqrt{1-\frac{1}{2}\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{2}^{2}}\right)$
(90)
$\displaystyle\geq\frac{1}{2}\left\||\psi\rangle\langle\psi|-|\varphi\rangle\langle\varphi|\right\|_{2}^{2}.$
(91)

Combining this with Proposition 26 gives the result. ∎

It follows from Proposition 12 that all $W_{p}^{C}$ defined from this $d_{C}$
are nondegenerate. This gives a natural extension of the ideas of state
complexity to mixed states, to which we can apply results such as Proposition
33 on cq sources.

Looking at $\rho$ and $\sigma$ in their eigenbases, we can give a concrete
interpretation of these values. Indeed, let

$\rho=\sum_{b\in\\{0,1\\}^{n}}r_{b}|\psi_{b}\rangle\langle\psi_{b}|\qquad\sigma=\sum_{c\in\\{0,1\\}^{n}}s_{c}|\varphi_{c}\rangle\langle\varphi_{c}|$
(92)

for $r$ and $s$ some classical probability distributions on $\\{0,1\\}^{n}$.
Letting $U$ be any unitary such that all $U\ket{\psi_{b}}=\ket{b}$, $V$ any
unitary such that all $V\ket{\varphi_{c}}=\ket{c}$, and $q$ be an optimal
$p^{\text{th}}$-order classical coupling of the distributions $r$ and $s$, we
can consider transport plan

$Q=\\{(q_{bc},\ket{\psi_{b}},\ket{\varphi_{c}})\\}_{b,c\in\\{0,1\\}^{n}}$ (93)

which has a first-order transport cost of at most
$C(U)+C(V)+\mathcal{W}_{1}^{H}(r,s)$. This allows us to conclude that

$W_{1}^{C}(\rho,\sigma)\leq C(U)+C(V)+\mathcal{W}_{1}^{H}(r,s).$ (94)

This splits the quantum transport distance arising from complexity geometry
into two parts: the classical transport cost between the states, and their
quantum complexity as a whole.

##  VI Applications

###  VI.1 Results for random quantum states

To understand these quantities in general, it is useful to look at how they
behave on random quantum states. We will look at both the versions stemming
from $\left\|\cdot\right\|_{W_{1}^{H}}$ and from complexity geometry.

We look at a few regimes in the definition of ‘random’ states. For random pure
states, we generate $\ket{\psi}$ according to the uniform measure on the unit
sphere in $\mathcal{H}$, and take $\rho=|\psi\rangle\langle\psi|$. For mixed
states, we adjoin an auxiliary system $\mathcal{A}$ of dimension $s$, generate
a random pure state $\ket{\psi}$ on $\mathcal{H}\otimes\mathcal{A}$, then take
$\rho=\text{Tr}_{\mathcal{A}}|\psi\rangle\langle\psi|$. The distribution of
$\rho$ depends entirely on the values of $s$ and $\text{dim}\mathcal{H}$
chosen.

Note that for the two versions studied, the underlying space $\mathcal{H}$ is
a qudit space $\mathcal{H}=(\mathbb{C}^{d})^{\otimes n}$. It is convenient, in
this case, to write $s=d^{m}$, as this allows us to consider the qudit ratio
$c=\frac{m}{n}$ between the auxiliary and base systems. Note that while $s$ is
always an integer, $m$ need not be, i.e. we will also consider auxiliary
dimensions that are not a power of $d$. We can then consider the regime $c<1$
as ‘low rank’, and regime $c>1$ as ‘high rank’.

For mixed states in the high-rank regime, we see exponential decay in the
expected $W_{1}^{d}$ distance between two i.i.d. states, no matter the
underlying metric $d$. This is summarised in the following proposition. Note
that while it is phrased for qudit systems, it applies for any
$\mathcal{H},\mathcal{A}$ where
$c=\frac{\log\dim\mathcal{A}}{\log\dim\mathcal{H}}$ and
$d^{n}=\dim\mathcal{H}$. We write $\text{diam}_{d}(\mathbb{P}\mathcal{H})$ for
the diameter of $\mathbb{P}\mathcal{H}$ under metric $d$.

######  Proposition 28.

Let $\mathcal{H}=(\mathbb{C}^{d})^{\otimes n}$ with i.i.d. random mixed states
$\rho,\sigma$ generated by a auxiliary system of $\mathcal{A}$ of dimension
$s=d^{m}$. Let $c=\frac{m}{n}$, and suppose $c>1$. Then for any $\beta>0$, we
have

$\mathbb{P}\left[W_{1}^{d}(\rho,\sigma)\geq\beta d^{-(c-3)n/2}\text{{\em
diam}}(\mathbb{P}\mathcal{H})\right]\leq\frac{1}{\beta^{2}}.$ (95)

###### Proof.

For random $\rho,\sigma$ generated from large auxiliary systems, we generally
expect both to be close to maximally mixed. And so letting the minimum
eigenvalue among $\rho$ and $\sigma$ be $\frac{1}{d^{n}}-\delta$, we can split
up $\rho$ into parts $\rho-\left(\frac{1}{d^{n}}-\delta\right)\mathbb{I}$ and
$\left(\frac{1}{d^{n}}-\delta\right)\mathbb{I}$, both of which are positive
semidefinite. We can do the same for $\sigma$. We can then transport
$\left(\frac{1}{d^{n}}-\delta\right)\mathbb{I}$ onto
$\left(\frac{1}{d^{n}}-\delta\right)\mathbb{I}$ at zero cost, and transport
$\rho-\left(\frac{1}{d^{n}}-\delta\right)\mathbb{I}$ onto
$\sigma-\left(\frac{1}{d^{n}}-\delta\right)\mathbb{I}$ via any partial
transport plan, at a maximum cost of
$\text{Tr}\left[\rho-\left(\frac{1}{d^{n}}-\delta\right)\mathbb{I}\right]\text{diam}_{d}(\mathbb{P}\mathcal{H})=\delta
d^{n}\text{diam}_{d}(\mathbb{P}\mathcal{H})$. We will show that this is most
likely very small.

Focusing on $\rho$, we know from [46] that

$\mathbb{E}[S(\rho)]\geq n\log d-\frac{1}{2}d^{-(c-1)n}.$ (96)

Knowing also that $S(\rho)\leq n\log d$, and using the top-down Markov
inequality, we get that for any $\alpha>0$ we have

$\mathbb{P}\left[S(\rho)\geq n\log d-\frac{\alpha}{2}d^{-(c-1)n}\right]\geq
1-\frac{1}{\alpha}.$ (97)

Using then that $D\left(\rho||\frac{I}{d^{n}}\right)=n\log d-S(\rho)$, and the
quantum Pinsker’s inequality, we have

$\mathbb{P}\left[\left\|\rho-\frac{I}{d^{n}}\right\|_{1}\leq\sqrt{\frac{\alpha}{2}}d^{-(c-1)n/2}\right]\geq
1-\frac{1}{\alpha}$ (98)

and so

$\mathbb{P}\left[\left\|\rho-\frac{I}{d^{n}}\right\|_{\infty}\leq\sqrt{\frac{\alpha}{2}}d^{-(c-1)n/2}\right]\geq
1-\frac{1}{\alpha}.$ (99)

Reintroducing $\sigma$, we then get that

$\mathbb{P}\left[\max\left\\{\left\|\rho-\frac{I}{d^{n}}\right\|_{\infty},\left\|\sigma-\frac{I}{d^{n}}\right\|_{\infty}\right\\}\leq\sqrt{\frac{\alpha}{2}}d^{-(c-1)n/2}\right]\geq\left(1-\frac{1}{\alpha}\right)^{2}\geq
1-\frac{2}{\alpha}.$ (100)

Note that for any $\rho,\sigma$ with
$\max\left\\{\left\|\rho-\frac{I}{d^{n}}\right\|_{\infty},\left\|\sigma-\frac{I}{d^{n}}\right\|_{\infty}\right\\}\leq\sqrt{\frac{\alpha}{2}}d^{-(c-1)n/2}$,
we can take $\delta=\sqrt{\frac{\alpha}{2}}d^{-(c-1)n/2}$. Then setting
$\beta=\sqrt{\alpha/2}$, and applying the transport plan described above, we
have

$\mathbb{P}\left[W_{1}^{d}(\rho,\sigma)\geq\sqrt{\frac{\alpha}{2}}d^{-(c-1)n/2}\cdot
d^{n}\text{diam}_{d}(\mathbb{P}\mathcal{H})\right]\leq\frac{2}{\alpha}$ (101)

and so

$\mathbb{P}\left[W_{1}^{d}(\rho,\sigma)\geq\beta
d^{-(c-3)n/2}\text{diam}_{d}(\mathbb{P}\mathcal{H})\right]\leq\frac{1}{\beta^{2}}.$
(102)

∎

This result can be easily applied to the two underlying distances mentioned
above. For qudit ratios
$c>3+\frac{2}{n}\log_{d}\text{diam}_{d}(\mathbb{P}\mathcal{H})$ we can define
$\beta$ by, for any $\lambda\in(0,1)$, value

$\log_{d}\beta=\lambda\left(c-3-\frac{2}{n}\log_{d}\text{diam}_{d}(\mathbb{P}\mathcal{H})\right)\frac{n}{2}$
(103)

to show that the probability of an exponentially small deviation falls
exponentially as the number $n$ of qudits increases.

For the $W_{1}^{H}$ case, we know $\text{diam}_{d}(\mathbb{P}\mathcal{H})=n$,
and so this exponential decay applies for qubit ratio $c>3$ and large enough
$n$. Applying this to the expectation gives, taking $\lambda=1/3$ for an
optimal decay rate,

$\displaystyle\mathbb{E}_{\rho,\sigma}\left[W_{1}^{H}(\rho,\sigma)\right]$
$\displaystyle\leq\left(1-\frac{1}{\beta^{2}}\right)\beta
d^{-(c-3)n/2}\text{diam}_{d}(\mathbb{P}\mathcal{H})+\frac{1}{\beta^{2}}\text{diam}_{d}(\mathbb{P}\mathcal{H})$
(104) $\displaystyle\leq
n^{1-\lambda}\exp_{d}\left(-\frac{1}{2}(1-\lambda)(c-3)n\right)+\exp_{d}n^{1+2\lambda}\left(\lambda(c-3)n\right)$
(105)
$\displaystyle=\exp_{d}\left(-\frac{1}{3}(c-3)n+\frac{2}{3}\log_{d}n\right)+\exp_{d}\left(-\frac{1}{3}(c-3)n+\frac{5}{3}\log_{d}n\right)$
(106)
$\displaystyle=\left(n^{2/3}+n^{5/3}\right)\exp_{d}\left(-\frac{1}{3}(c-3)n\right)$
(107)

For the $W_{1}^{C}$ case, any $n$-qudit gate can be synthesised in at most
$2^{n}(2^{n}-1)$ one- and two-qubit gates [30], and so the metric space
$\mathbb{P}\mathcal{H}$ has diameter at most $2^{2n}$. It then follows that
for any qudit ratio $c>7$, the probability of an exponentially large deviation
becomes exponentially small.

Applying equation (95) to the expectation gives, taking
$\lambda=\frac{c-3}{3(c-7)}$ for an optimal decay rate,

$\displaystyle\mathbb{E}_{\rho,\sigma}\left[W_{1}^{C}(\rho,\sigma)\right]$
$\displaystyle\leq\left(1-\frac{1}{\beta^{2}}\right)\beta
2^{-(c-3)n/2}\text{diam}_{d}(\mathbb{P}\mathcal{H})+\frac{1}{\beta^{2}}\text{diam}_{d}(\mathbb{P}\mathcal{H})$
(108) $\displaystyle\leq
2^{-(1-\lambda)(c-3)n/2}2^{(1-\lambda)2n}+2^{-\lambda(c-3)n}2^{(1+2\lambda)2n}$
(109) $\displaystyle=2^{-(1-\lambda)(c-7)n/2}+2^{-(\lambda(c-7)-2)n}$ (110)
$\displaystyle=2\cdot 2^{(c-9)n/3}$ (111)

giving exponential decay in expectation for qubit ratios $c>9$.

For the low-rank setting, we look first at the $W_{1}^{H}$ distance. There are
two lines of intuition here. The first is that $W_{1}^{H}$ generalises the
Hamming distance, and the Hamming distance quantifies the local
distinguishability of $d$-nary strings. If this property propagated to the
quantum setting, we’d expect $W_{1}^{H}$ to be small on average as random pure
states are generally locally indistinguishable. The second is that the average
Hamming distance between two $d$-nary strings of length $n$ is $n(1-1/d)$, and
so we might also expect the average $W_{1}^{H}$ distance between random pure
strings to grow linearly with the number of qudits.

Let $\mathcal{H}=(\mathbb{C}^{d})^{\otimes n}$ and let $m=\log_{d}s$, noting
again that, while $s$ is an integer, $m$ need not be. In the case $m<n$, we
can apply Theorem 9.1 of [40] to lower bound the expected distance between two
low-rank random mixed states. This result was noted independently in [35].

######  Proposition 29.

Let $\rho$, $\sigma$ be two i.i.d. random mixed states on
$\mathcal{H}=(\mathbb{C}^{d})^{\otimes n}$ generated using an auxiliary system
of dimension $s=d^{m}$ for $m<n$. Write $c=\frac{m}{n}$. Then

$\mathbb{E}_{\rho,\sigma}\left[W_{p=1}^{H}(\rho,\sigma)\right]\geq\lambda_{c}n$
(112)

where $\lambda_{c}$ satisfies $\left(1-c\right)\log
d=h_{2}(\lambda)+\lambda\log(d^{2}-1)$ for $h_{2}$ the binary entropy.

###### Proof.

First note from Proposition 12 that
$W_{p=1}^{H}(\rho,\sigma)\geq\left\|\rho-\sigma\right\|_{W_{1}^{H}}$, and so
we prove that
$\mathbb{E}_{\rho,\sigma}\left[\left\|\rho-\sigma\right\|_{W_{1}^{H}}\right]\geq\lambda
n$.

Fix $\rho$, and note that averaging over $\sigma$ and using convexity of the
norm we have

$\displaystyle\mathbb{E}_{\sigma}\left[\left\|\rho-\sigma\right\|_{W_{1}^{H}}\right]$
$\displaystyle\geq\left\|\rho-\mathbb{E}_{\sigma}\sigma\right\|_{W_{1}^{H}}$
(113) $\displaystyle=\left\|\rho-\frac{\mathbb{I}_{d}^{\otimes
n}}{d^{n}}\right\|_{W_{1}^{H}}.$ (114)

Applying Theorem 9.1 of [40] then gives, for $S$ the von Neumann entropy of a
state,

$\left(1-c\right)\log
d\leq\frac{1}{n}\left|S(\rho)-S\left(\frac{\mathbb{I}_{d}^{\otimes
n}}{d^{n}}\right)\right|\leq
h_{2}\left(\frac{\left\|\rho-\mathbb{I}_{d}^{\otimes
n}/d^{n}\right\|_{W_{1}^{H}}}{n}\right)+\frac{\left\|\rho-\mathbb{I}_{d}^{\otimes
n}/d^{n}\right\|_{W_{1}^{H}}}{n}\log(d^{2}-1).$ (115)

Noting then that the function $g(t)=h_{2}(t)+t\log(d^{2}-1)$ takes the value
$\left(1-c\right)\log d$ at exactly one value $\lambda\in[0,1]$, and that for
for $t<\lambda$ we have $g(t)<g(\lambda)$ and for $t>\lambda$ we have
$g(t)>g(\lambda)$, we conclude that $\left\|\rho-\mathbb{I}_{d}^{\otimes
n}/d^{n}\right\|_{W_{1}^{H}}>\lambda n$. Averaging over $\rho$ gives the
result. ∎

For $\rho,\sigma$ random pure states, we simply take the case $m=0$. In
general, this shows that the expected $W_{p=1}^{H}$ distance between two
random states generated using small auxiliary systems grows linearly with the
number $n$ of qubits.

Turning our attention to the $W_{1}^{C}$ distance generated from complexity
geometry on $\mathbb{P}\left((\mathbb{C}^{2})^{\otimes n}\right)$, we see a
similar picture for pure states. As noted earlier, for the approximate gate
complexity $G(U,\epsilon)$ and the gate complexity $G(U)$, we have the bound

$\frac{\kappa G(U,\epsilon)^{1/3}\epsilon^{2/3}}{n^{2}}\leq d(I,U)\leq G(U)$
(116)

for some constant $\kappa>0$.

For pure states we also know that
$W_{p}^{C}(\ket{\psi}\bra{\psi},|\varphi\rangle\langle\varphi|)=d_{C}(\ket{\psi},\bra{\psi})$.
And so to show the behaviour of $W_{p}^{C}$ distances on pure states, we look
at $d_{C}$.

######  Lemma 30.

Let $\mathcal{H}=(\mathbb{C}^{2})^{\otimes n}$ be an $n$-qudit space, and let
$\mathcal{S}\subseteq{\mathcal{SU}(4)}$ be a finite universal gate set with
inverses. Letting $G_{\mathcal{S}}(U,\epsilon)$ be the $\epsilon$-approximate
gate complexity of $U$ from set $\mathcal{S}$ viewed as a set of gates on 2
qubits, and $G(U,\epsilon)$ the $\epsilon$-approximate gate complexity of $U$
using any one- or two-qubit gates, we have

$G(U,\epsilon)\text{{\em poly}}(\log(G(U,\epsilon))+\log(\epsilon^{-1}))\geq
G_{\mathcal{S}}(U,2\epsilon)$ (117)

###### Proof.

Let $V_{1},\dots,V_{G(U,\epsilon)}$ be any circuit of one- and two-qubit gates
to synthesise $V$ such that $\left\|U-V\right\|_{\infty}\leq\epsilon$. Using
Solovay-Kitaev, each of these can be approximated to within error
$\epsilon/G(U,\epsilon)$ in
$\text{poly}(\log\left(G(U,\epsilon)/\epsilon\right))$ gates from
$\mathcal{S}$. Compounding errors linearly, these form a circuit of length
$G(U,\epsilon)\text{ poly}(\log(G(U,\epsilon))+\log(\epsilon^{-1}))$ of gates
from $\mathcal{S}$ which synthesises $U$ to within operator norm $2\epsilon$.
∎

######  Lemma 31.

Let $\mathcal{S}\subseteq{\mathcal{SU}(4)}$ be a finite universal gate set
with inverses. Fix $\ket{\psi}$. Sampling $\ket{\varphi}$ from the Haar
measure on $\mathbb{P}\mathcal{H}$, let
$U_{\ket{\psi}\to\ket{\varphi}}^{\text{{\em opt}}}\in\mathcal{SU}(2^{n})$ have
$U_{\ket{\psi}\to\ket{\varphi}}^{\text{{\em opt}}}\ket{\psi}=\ket{\varphi}$
and suppose it has minimum $\epsilon$-approximate complexity among all such
unitaries in $\mathcal{SU}(2^{n})$. We have that for all $\delta$,

$\mathbb{P}_{\ket{\varphi}}\left[G_{\mathcal{S}}(U_{\ket{\psi}\to\ket{\varphi}}^{\text{{\em
opt}}},2\epsilon)\leq 2^{(1-\delta)n}\right]\leq
e^{-\Omega(2^{n}\log((2\epsilon)^{-1}))}$ (118)

###### Proof.

There are $|\mathcal{S}|^{2^{(1-\delta)n}}$ circuits of length
$2^{(1-\delta)n}$ made from gates in $|\mathcal{S}|$, and
$\mathbb{P}\mathcal{H}$ has real dimension $2^{n+1}-2$. Therefore there are
$e^{\Omega(2^{n}\log((2\epsilon)^{-1}))}$ $2\epsilon$-balls in
$\mathbb{P}\mathcal{H}$. It follows then that the $2\epsilon$-balls around
outputs of length-$2^{(1-\delta)n}$ circuits cover a proportion
$e^{\mathcal{O}(2^{(1-\delta)n}\log|\mathcal{S}|)-\Omega(2^{n}\log((2\epsilon)^{-1}))}\leq
e^{-\Omega(2^{n}\log((2\epsilon)^{-1}))}$ of possible output states in
$\mathbb{P}\mathcal{H}$. ∎

Combining these two propositions with equation (78) gives the result.

######  Corollary 32.

Fix state $\ket{\psi}$ on $n$ qubits, and let $\ket{\varphi}$ be sampled from
the Haar measure on $\mathbb{P}\mathcal{H}$. For all $\delta>0$,

$\mathbb{P}_{\ket{\varphi}}\left[d(\ket{\psi},\ket{\varphi})\leq\epsilon^{2/3}n^{-1}\kappa\left(\frac{2^{(1-\delta)n}}{\text{{\em
poly}}(n,\log\epsilon^{-1})}\right)^{1/3}\right]\leq
e^{-\Omega(2^{n}\log((2\epsilon)^{-1}))}.$ (119)

###### Proof.

The proof is technical and not particularly instructive, so has been placed in
Appendix D.2. ∎

In other words, the chance of two Haar-random pure states on $n$ qubits being
less than exponentially far apart in the complexity geometry distance becomes
exponentially small as $n$ tends towards infinity.

###  VI.2 Operational interpretation in terms of classical-quantum sources

In this section, we show that the $W_{p}^{d}$ distances have an operational
significance for distances between classical-quantum (cq) states and
classical-quantum (cq) sources. Indeed, let $R$ and $S$ be two cq sources,
each controlled by a classical random variable $X$ on $\\{1,\dots,N\\}$ with
probabilities $p_{i}$. On input $i$, let $R$ output
$|\psi_{i}\rangle\langle\psi_{i}|$ and $S$ output
$|\varphi_{i}\rangle\langle\varphi_{i}|$. Let the output have dimension $D$.
These sources can be simulated by measuring the first (classical) register of
the following cq states in the standard basis:

$\tilde{\rho}=\sum_{i=1}^{N}p_{i}|i\rangle\langle
i|\otimes|\psi_{i}\rangle\langle\psi_{i}|\qquad\tilde{\sigma}=\sum_{i=1}^{N}p_{i}|i\rangle\langle
i|\otimes|\varphi_{i}\rangle\langle\varphi_{i}|.$ (120)

Letting then $\rho=\sum_{i=1}^{N}p_{i}|\psi_{i}\rangle\langle\psi_{i}|$ and
$\sigma=\sum_{i=1}^{N}p_{i}|\psi_{i}\rangle\langle\psi_{i}|$, these $\rho$ and
$\sigma$ are the expected outputs of $R$ and $S$ respectively. The $W_{1}^{d}$
distance provides a lower bound between the expected distance between the
outputs. Broadly speaking, we interpret the distance as the cost of moving
between $R$ and $S$.

######  Proposition 33.

Let $R$ and $S$ be cq sources with expected outputs $\rho$ and $\sigma$
respectively of dimension $D$, and let $1\leq p<\infty$. Given access to the
output register and classical control register, the expected distance $d$
between the outputs $r$ and $s$ satisfies

$\mathbb{E}_{X}[d(r,s)^{p}]\geq W_{p}^{d}(\rho,\sigma)^{p}$ (121)

and this bound is sharp.

###### Proof.

For the lower bound, consider quantum transport plan
$Q=\\{(p_{i},\ket{\psi_{i}},\ket{\varphi_{i}})\\}_{i=1}^{N}$ between $\rho$
and $\sigma$. The $p^{\text{th}}$-order cost of this transport plan is

$T_{p}^{d}(Q)=\sum_{i=1}^{N}p_{i}d(\ket{\psi_{i}},\ket{\varphi_{i}})^{p}=\mathbb{E}_{X}[d(r,s)^{p}]$
(122)

which is lower bounded by the optimal $p^{\text{th}}$-order quantum transport
cost $W_{p}^{d}(\rho,\sigma)$.

For sharpness, let $Q=\\{(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}})\\}_{j}$ be
any transport plan between $\rho$ and $\sigma$. The sources

$R=\sum_{j\in J}q_{j}|j\rangle\langle
j|\otimes|\psi_{j}\rangle\langle\psi_{j}|\qquad S=\sum_{j\in
J}q_{j}|j\rangle\langle j|\otimes|\varphi_{j}\rangle\langle\varphi_{j}|$ (123)

controlled by random variable $Y$ taking values in $J$ with probabilities
$q_{j}$ then have $p^{\text{th}}$ moment

$\mathbb{E}_{Y}[d(r,s)^{p}]=\sum_{j\in
J}q_{j}d(\ket{\psi_{j}},\ket{\varphi_{j}})^{p}.$ (124)

Taking the infimum over all transport plans gives sharpness.

∎

We also get from Proposition 16 that when $d$ is continuous, we can take the
first register to have size at most $2D^{2}$ in the equality case.

In the case where $d$ is the complexity geometry metric $d_{C}$, this means
that $W_{p}^{C}$ effectively quantifies the $p^{\text{th}}$ moment of the gate
complexity of transforming one source into another, post-output. Indeed, for
sources $R$ and $S$ as above, and
$U_{\ket{\psi}\to\ket{\varphi}}^{\text{opt}}\in\mathcal{SU}(2^{n})$ a unitary
with $U_{\ket{\psi}\to\ket{\varphi}}^{\text{opt}}\ket{\psi}=\ket{\varphi}$,
and minimal complexity among all such $U$, we know that

$\mathbb{E}_{X}[G(U_{r\to s}^{\text{opt}})^{p}]\geq
W_{p}^{C}(\rho,\sigma)^{p}.$ (125)

Similarly, the $W_{\infty}^{d}$ distance gives a lower bound for the highest
possible value of $d(r,s)$. It follows from the definition of $W_{\infty}^{d}$
that

$\max_{i}d(\ket{\psi_{i}},\ket{\varphi_{i}})\geq W_{\infty}^{d}(\rho,\sigma)$
(126)

and taking the infimum of the left-hand side over $\mathcal{Q}(\rho,\sigma)$
shows that the bound is sharp. Operationally, for the $W_{\infty}^{C}$
distance, this means $W_{\infty}^{C}(\rho,\sigma)$ is a lower bound for the
worst-case scenario cost of transforming $R$ into $S$, post-output.

###  VI.3 Hypercontractivity and noise

In the hierarchy of $W_{p}^{d}$ in order $p$, we saw in equation (20) that if
$p_{1}<p_{2}$ then $W_{p_{1}}^{d}(\rho,\sigma)\leq
W_{p_{2}}^{d}(\rho,\sigma)$. This hierarchy mirrors the hierarchy in the
standard $L^{p}$ norms, for which the notion of hypercontractivity [3, 2, 26]
has been used in various ways to quantify the noise of an operation [26, 33].
Broadly speaking, an operator $T$ on a space of functions is hypercontractive
if, for some $p_{2}>p_{1}$, we have for all functions $f$ that
$\left\|Tf\right\|_{p_{2}}\leq\left\|f\right\|_{p_{1}}$. Hypercontractivity
and the noise of an operator are most closely linked in the hypercontractivity
theorem [3, Chapter 7], which demonstrates the hypercontractive properties of
the standard Boolean noise operator.

We will show that this idea carries over to the quantum $W_{p}^{d}$ distances,
and that the ratio
$\frac{W_{p_{1}}^{d}(\rho,\sigma)}{W_{p_{2}}^{d}(N(\rho),N(\sigma))}$ can be
considered as a measure of noise in the channel $N$. In this setting, the
‘standard’ noise channels are the replacement channel $R_{\delta,x}$, given by

$R_{\delta,x}(\rho)=(1-\delta)\rho+\delta|x\rangle\langle x|$ (127)

and the depolarising channel $S_{\delta}$ given by

$S_{\delta}(\rho)=(1-\delta)\rho+\delta\mathbb{I}/D$ (128)

where $D=\dim\mathcal{H}$.

######  Proposition 34.

Let $\rho$, $\sigma$ be two quantum states on $\mathcal{H}$ and let $1\leq
p_{1}<\infty$, and suppose $W_{p_{1}}^{d}(\rho,\sigma)=M$. For $p_{2}>p_{1}$,
let $1-\delta\leq(M/\text{{\em
diam}}_{d}(\mathbb{P}\mathcal{H}))^{p_{2}-p_{1}}$. Then the replacement
channel $R_{\delta,x}$ and the depolarising channel $S_{\delta}(\rho)$ have

$W_{p_{2}}^{d}(R_{\delta,x}(\rho),R_{\delta,x}(\sigma))\leq
W_{p_{1}}^{d}(\rho,\sigma)$ (129)

and

$W_{p_{2}}^{d}(S_{\delta}(\rho),S_{\delta}(\sigma))\leq
W_{p_{1}}^{d}(\rho,\sigma).$ (130)

###### Proof.

Let $Q=\\{(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}}\\}_{j}$ be an optimal
${p_{1}}^{\text{th}}$-order transport plan from $\rho$ to $\sigma$, and let

$Q^{\prime}=(1-\delta)Q\cup\\{(\delta,\ket{x},\ket{x}\\}\qquad\text{for
channel {\hbox{R_{\delta,x}}}}$ (131)

or

$Q^{\prime}=(1-\delta)Q\cup\\{(\delta/D,\ket{i},\ket{i}\\}_{i=1}^{D}\qquad\text{for
channel {\hbox{S_{\delta}}}}$ (132)

for $\ket{1},\dots,\ket{D}$ an orthonormal basis of $\mathcal{H}$. These are
transport plans from $R_{\delta,x}(\rho)$ to $R_{\delta,x}(\sigma)$ and from
$S_{\delta}(\rho)$ to $S_{\delta}(\sigma)$ respectively. In both cases,

$T_{p_{2}}^{d}(Q^{\prime})=\left((1-\delta)\sum_{j}q_{j}d(\ket{\psi_{j}},\ket{\varphi_{j}})^{p_{2}}\right)^{1/{p_{2}}}=(1-\delta)^{1/{p_{2}}}T_{p_{2}}^{d}(Q)^{1/{p_{2}}}\leq\left(\frac{M}{\text{diam}_{d}(\mathbb{P}\mathcal{H})}\right)^{1-{p_{1}}/{p_{2}}}T_{p_{2}}^{d}(Q)^{1/{p_{2}}}.$
(133)

So it remains to show that

$T_{p_{1}}^{d}(Q)^{1/{p_{1}}}\geq\left(\frac{M}{\text{diam}_{d}(\mathbb{P}\mathcal{H})}\right)^{1-{p_{1}}/{p_{2}}}T_{p_{2}}^{d}(Q)^{1/{p_{2}}}.$
(134)

Given quantities $\\{A_{j}\\}_{j}$ subject to constraints

$\sum_{j}q_{j}A_{j}^{p_{1}}=M^{p_{1}}$ (135) $0\leq
A_{j}\leq\text{diam}_{d}(\mathbb{P}\mathcal{H}),$ (136)

the maximum value of $\sum_{j}q_{j}A_{j}^{q}$ is achieved when all $A_{j}$ are
either $\text{diam}_{d}(\mathbb{P}\mathcal{H})$ or $0$, with values
$q_{1}=(M/\text{diam}_{d}(\mathbb{P}\mathcal{H}))^{p_{1}}$ and
$q_{2}=1-q_{1}$. This gives

$T_{p_{2}}^{d}(Q)\leq(M/\text{diam}_{d}(\mathbb{P}\mathcal{H}))^{p_{1}}\text{diam}_{d}(\mathbb{P}\mathcal{H})^{p_{2}}$
(137)

and therefore that

$\frac{T_{p_{1}}^{d}(Q)^{1/{p_{1}}}}{T_{p_{2}}^{d}(Q)^{1/{p_{2}}}}\geq\frac{M}{\text{diam}_{d}(\mathbb{P}\mathcal{H})}\left(\frac{\text{diam}_{d}(\mathbb{P}\mathcal{H})}{M}\right)^{{p_{1}}/{p_{2}}}=\left(\frac{M}{\text{diam}_{d}(\mathbb{P}\mathcal{H})}\right)^{1-{p_{1}}/{p_{2}}}.$
(138)

∎

We note from the condition
$1-\delta\leq(M/\text{diam}_{d}(\mathbb{P}\mathcal{H}))^{p_{2}-p_{1}}$ that
this result is applicable only when $W_{p_{1}}^{d}$ is close to
$\text{diam}_{d}(\mathbb{P}\mathcal{H})$ or when $p_{2}-p_{1}$ is small.
Otherwise, we would require $\delta$ so large that the channels are no longer
of practical use. Our results on random states from Sec. VI.1 demonstrate that
this is indeed a relevant case, as for random low-rank states, $W_{p}^{H}$ and
$W_{p}^{C}$ are generally high.

Particularly in the case of complexity geometry, this shows that channel noise
reduces complexity. These results also demonstrate the value of considering
arbitrary $p$ in our construction of the $W_{p}^{d}$ distances. Such
consideration is not possible without being able to relate Wasserstein
distances of different orders to one another. In general, for arbitrary
$p_{1},p_{2}$, this shows that
$\frac{W_{p_{1}}^{d}(\rho,\sigma)}{W_{p_{2}}^{d}(N(\rho),N(\sigma))}$ can be
well considered as a measure of noise in the channel $N$.

##  VII Conclusion

In this work, we have introduced a novel definition of the quantum Wasserstein
distance by combining the coupling method and a metric on the set of pure
states. This novel definition successfully captures the essence of the
classical Wasserstein distance. A significant aspect of our approach is its
inherent adaptability, effortlessly incorporating established metrics on
quantum states such as trace distance and naturally extending pure-state
metrics, for instance, Nielsen’s complexity metric, to cater to mixed states.

Furthermore, we established various properties of this new definition. While
we acknowledge that these properties are not exhaustive, they nevertheless
offer advantages compared to other recent generalisations, such as the fact
that one definition can cover several examples in the literature in a unified
way. A significant challenge remains: establishing the triangle inequality in
its generality. Our findings, though, hint at the possibility that under
suitable conditions the dual approach yields a proof of the triangle
inequality.

Our exploration of specific cases reveals the $W_{1}^{1}$ distance as a
potentially powerful tool for bounding the trace distance between quantum
states, drawing parallels with classical approaches for determining total
variation distance and mixing time bounds. Additionally, our work enriches the
understanding of the complexity geometry of quantum states, offering a new
lens through which to view and quantify the complexity of transformations
within quantum ensembles.

Our examination of the behaviour of the Wasserstein distance under random
quantum states unveils various phase transitions. These results, derived from
entropic inequalities and continuity bounds, debunk some existing speculations
(e.g. that $\left\|\cdot\right\|_{W_{1}^{H}}$ captures local
distinguishability) while affirming others (the complexity of small subsystems
of random quantum states is low).

In conclusion, our research represents a significant stride forward in the
pursuit of understanding optimal transport in quantum mechanics. The novel
quantum Wasserstein distance that we have proposed holds great promise, not
only as an analytical tool but also as a medium for further exploration and
discovery in quantum computation and information. While our work has paved the
way, many challenges and open problems remain, especially when it comes to
finding new applications of the methods laid out here.

##  VIII Acknowledgements

DSF and EB would like to thank Alexander Müller-Hermes, Raul García-Patrón,
Philippe Faist, Fanch Coudreuse, and Guillaume Aubrun for interesting
discussions. This project received support from the PEPR integrated project
EPiQ ANR-22-PETQ-0007 part of Plan France 2030.

## References

  * AHS [19] Cesar A. Agón, Matthew Headrick, and Brian Swingle.  Subsystem complexity and holography.  Journal of High Energy Physics, 2019(2), February 2019.
  * Bis [11] Punyashloka Biswal.  Hypercontractivity and its applications.  arXiv preprint arXiv:1101.2913, January 2011.
  * Bon [70] Aline Bonami.  Étude des coefficients de Fourier des fonctions de $l^{p}(g)$.  Annales de l’Institut Fourier, 20(2):335–402, 1970.
  * BPTV [24] Gergely Bunth, József Pitrik, Tamás Titkos, and Dániel Virosztek.  On the metric property of quantum Wasserstein divergences.  arXiv preprint arXiv:2402.13150, February 2024.
  * Bro [23] Adam R. Brown.  A quantum complexity lower bound from differential geometry.  Nature Physics, 19:401–406, December 2023.
  * BRS+ [16] Adam R. Brown, Daniel A. Roberts, Leonard Susskind, Brian Swingle, and Ying Zhao.  Complexity, action, and black holes.  Phys. Rev. D, 93:086006, April 2016.
  * BS [19] Adam R. Brown and Leonard Susskind.  Complexity geometry of a single qubit.  Phys. Rev. D, 100:046020, August 2019.
  * CD [08] Philippe Clement and Wolfgang Desch.  An elementary proof of the triangle inequality for the Wasserstein metric.  Proceedings of The American Mathematical Society, 136:333–340, January 2008.
  * CEFZ [23] Sam Cole, Michał Eckstein, Shmuel Friedland, and Karol Życzkowski.  On quantum optimal transport.  Mathematical Physics, Analysis and Geometry, 26(14), June 2023.
  * CGP [21] Emanuele Caglioti, Franccois Golse, and Thierry Paul.  Towards optimal transport for quantum densities.  Annali Scuola Normale Superiore - Classe di Scienze, January 2021\.
  * CM [14] Eric A. Carlen and Jan Maas.  An analog of the 2-Wassertein metric in non-commutative probability under which the Fermionic Fokker–Planck equation is gradient flow for the entropy.  Communications in Mathematical Physics, 331(3):887–926, July 2014\.
  * CM [17] Eric A. Carlen and Jan Maas.  Gradient flow and entropy inequalities for quantum Markov semigroups with detailed balance.  Journal of Functional Analysis, 273(5):1810–1869, September 2017\.
  * CM [19] Eric A. Carlen and Jan Maas.  Non-commutative calculus, optimal transport and functional inequalities in dissipative quantum systems.  Journal of Statistical Physics, 178(2):319–378, November 2019.
  * CYL+ [19] Shouvanik Chakrabarti, Huang Yiming, Tongyang Li, Soheil Feizi, and Xiaodi Wu.  Quantum Wasserstein generative adversarial networks.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., December 2019\.
  * DD [13] Michel Marie Deza and Elena Deza.  Encyclopedia of Distances.  Springer Berlin Heidelberg, 2013.
  * DN [08] M.R. Dowling and M.A. Nielsen.  The geometry of quantum computation.  Quantum Information and Computation, 8(10):861–899, November 2008\.
  * DPMRF [23] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, and Daniel Stilck França.  Limitations of variational quantum algorithms: A quantum optimal transport approach.  PRX Quantum, 4(1), January 2023.
  * DR [20] Nilanjana Datta and Cambyse Rouzé.  Relating relative entropy, optimal transport and Fisher information: a quantum HWI inequality.  Annales Henri Poincaré, 21(7):2115–2150, July 2020.
  * FECZ [22] Shmuel Friedland, Michał Eckstein, Sam Cole, and Karol Życzkowski.  Quantum Monge-Kantorovich problem and transport distance between density matrices.  Physical Review Letters, 129(11), September 2022.
  * FZM+ [15] Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya-Polo, and Tomaso A. Poggio.  Learning with a Wasserstein loss.  In Advances in Neural Information Processing Systems (NIPS) 28, 2015\.
  * Gal [18] Alfred Galichon.  Optimal transport methods in economics.  Princeton University Press, 2018.
  * GJL [21] Li Gao, Marius Junge, and Haojian Li.  Geometric approach towards complete logarithmic sobolev inequalities.  arXiv preprint arXiv:2102.04434, February 2021.
  * GMP [15] François Golse, Clément Mouhot, and Thierry Paul.  On the mean field and classical limits of quantum mechanics.  Communications in Mathematical Physics, 343:165–205, April 2015\.
  * Hel [23] Michal P. Heller.  Geometry and complexity scaling.  Nature Physics, 19:312–313, March 2023.
  * Kan [42] L. V. Kantorovich.  On the translocation of masses.  Doklady Akademii Nauk SSSR, 37(7-8):227–229, 1942.
  * KLLM [21] Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer.  Global hypercontractivity and its applications.  arXiv preprint arXiv:2103.04604, March 2021.
  * KPM+ [22] Bobak Toussi Kiani, Giacomo De Palma, Milad Marvian, Zi-Wen Liu, and Seth Lloyd.  Learning quantum data with the quantum earth mover’s distance.  Quantum Science and Technology, 7(4):045002, July 2022.
  * MH [22] Alexander Müller-Hermes.  On the monotonicity of a quantum optimal transport cost, November 2022\.
  * Mon [81] G. Monge.  Mémoire sur la théorie des déblais et des remblais.  Imprimerie royale, 1781.
  * NC [10] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 2010.
  * NDGD [06] Michael A. Nielsen, Mark R. Dowling, Mile Gu, and Andrew C. Doherty.  Quantum computation as geometry.  Science, 311(5764):1133–1135, February 2006.
  * Nie [06] Michael A. Nielsen.  A geometric approach to quantum circuit lower bounds.  Quantum Info. Comput., 6(3):213–262, May 2006.
  * O’D [14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * Orn [73] Donald S. Ornstein.  An application of ergodic theory to probability theory.  The Annals of Probability, 1(1):43–58, 1973.
  * PKP [23] Giacomo De Palma, Tristan Klein, and Davide Pastorello.  Classical shadows meet quantum optimal mass transport.  arXiv preprint arXiv:2309.08426, September 2023.
  * PMTL [21] Giacomo De Palma, Milad Marvian, Dario Trevisan, and Seth Lloyd.  The Quantum Wasserstein Distance of Order 1.  IEEE Transactions on Information Theory, 67:6627–6643, October 2021.
  * PR [22] Giacomo De Palma and Cambyse Rouzé.  Quantum concentration inequalities.  Annales Henri Poincaré, 23(9):3391–3429, April 2022.
  * PT [21] Giacomo De Palma and Dario Trevisan.  Quantum optimal transport with quantum channels.  Annales Henri Poincaré, 22(10):3199–3234, March 2021.
  * PT [22] Giacomo De Palma and Dario Trevisan.  Quantum optimal transport: Quantum channels and qubits.  In Summer School on Optimal Transport on Quantum Structures, Erdős Center, Rényi Institute, Budapest, Hungary, https://arxiv.org/abs/2307.16268, September 2022.
  * PT [23] Giacomo De Palma and Dario Trevisan.  The Wassertein distance of order 1 for quantum spin systems on infinite lattices.  Annales Henri Poincaré, June 2023.
  * PZ [19] Victor M. Panaretos and Yoav Zemel.  Statistical aspects of Wassertein distances.  Annual Review of Statistics and Its Application, 6(1):405–431, March 2019.
  * RD [19] Cambyse Rouzé and Nilanjana Datta.  Concentration of quantum states from quantum functional and transportation cost inequalities.  Journal of Mathematical Physics, 60(1):012202, January 2019.
  * RF [21] Cambyse Rouzé and Daniel Stilck França.  Learning quantum many-body systems from a few copies.  arXiv preprint arXiv:2107.03333, July 2021.
  * RS [15] Maxim Raginsky and Igal Sason.  Concentration of measure inequalities and their communication and information-theoretic applications.  arXiv preprint arXiv:1510.02947, October 2015.
  * Rua [21] Shan-Ming Ruan.  Circuit Complexity of Mixed States.  Phd thesis, University of Waterloo, 2021.
  * SR [95] Jorge Sánchez-Ruiz.  Simple proof of Page’s conjecture on the average entropy of a subsystem.  Phys. Rev. E, 52:5653–5655, November 1995.
  * Tra [18] José Trashorras.  Large deviations for a matching problem related to the infinity-Wasserstein distance.  Lat. Am. J. Probab. Math. Stat, 15:247–278, 2018.
  * Vil [03] C. Villani.  Topics in Optimal Transportation.  Graduate Studies in Mathematics. American Mathematical Society, 2003.
  * Vil [08] Cédric Villani.  Optimal transport: old and new, volume 338.  Springer Science & Business Media, 2008.

##  Appendix A Comparison to other proposed definitions of a quantum
Wasserstein distance

Until now, finding a coherent way to define a quantum optimal transport cost,
regardless of the underlying metric on the Hilbert space, has proved elusive.
Some definitions (such as in [38], [11] and [23]) work well for specific
orders $p$, and specific underlying metrics. A further definition was proposed
recently in [14] using standard quantum couplings and using projection onto
the asymmetric subspace as a cost function, with the motivation of mimicking
the definition of total variation distance as the Wasserstein distance
corresponding to the trivial metric.

Originally, [14] defined a second-order Wasserstein semi-distance $W$ on
states on $\mathcal{H}=\mathbb{C}^{d}$ as follows. Letting
$\mathbb{F}\ket{a}\otimes\ket{b}=\ket{b}\otimes\ket{a}$ define the flip
operator on $\mathcal{H}\otimes\mathcal{H}$, we can then define the symmetric
projector $P_{\text{sym}}(d)$ as the projector onto the $1$-eigenspace of
$\mathbb{F}$, and $P_{\text{asym}}(d)$ the projector onto its
$(-1)$-eigenspace. Note
$P_{\text{sym}}(d)+P_{\text{asym}}(d)=\mathbb{I}_{\mathbb{C}^{d}\otimes\mathbb{C}^{d}}$.

They then define the quantum optimal transport cost

$T(\rho,\sigma)=\min_{\tau_{AB}\in\mathcal{D}(\mathbb{C}^{d}\otimes\mathbb{C}^{d}),\tau_{A}=\rho,\tau_{B}=\sigma}\text{Tr}[\tau_{AB}P_{\text{asym}}(d)]$
(139)

and $W(\rho,\sigma)=\sqrt{T(\rho,\sigma)}$. This definition was further
studied in [19] and [9], and refined in [28] to give data processing. It gives
a 2-Wasserstein semi-distance which is equivalent to the trace distance.

[28] then showed that this original definition does not satisfy a data-
processing inequality, so it does not mirror the original trace distance in
this regard. The definition in Eq. (139) was then refined to give the data
processing inequality by considering a complete version:

$T_{s}(\rho,\sigma)=T(\rho\otimes\mathbb{I}/2,\sigma\otimes\mathbb{I}/2)$
(140)

and $W_{s}(\rho,\sigma)=\sqrt{T_{s}(\rho,\sigma)}$. Note that in general, the
complete version of a quantity requires an optimisation over auxiliary systems
of arbitrary size, however [28] shows that the maximally mixed state of one
qubit suffices.

There are two main differences between this path to obtaining a generalisation
of the Wasserstein distance and ours. First, in this path, the cost of
transforming one state into another is given by the expectation value of an
observable on the bipartite system. In our case, we depart from a metric on
the set of point masses/pure states. Although the metric version is in direct
analogy with the classical version, optimising over the expectation value of
an observable certainly has a more operational interpretation. Second, in the
definition of Eq. (139) we see that we indeed optimise over all couplings,
including separable ones. In our definition, we only optimise over separable
ones, which gives the definition in Eq. (139) a more quantum flavor.
Furthermore, computing Eq. (139) corresponds to an SDP, so it can be computed
efficiently in the dimension, whereas it is unclear if we can efficiently
compute our version in general. However, one of the main motivations for our
work was to obtain a unified way of obtaining various versions of $W_{p}$
present in the literature, including the definition of [36]. However, it
appears that approaches like that of Eq. (139) cannot mimic the behaviour of
the Wasserstein distance of de Palma et al. Consider, for example, the
potential extension to an $n$-qudit space given by

$T(\rho,\sigma)=\min\left\\{\text{Tr}\left[\tau_{AB}\left(\sum_{i=1}^{n}P_{i,\text{asym}}(d)\right)\right]:\tau_{AB}\in\mathcal{D}\left((\mathbb{C}^{d})^{\otimes
n}\otimes(\mathbb{C}^{d})^{\otimes
n}\right):\tau_{A}=\rho,\tau_{B}=\sigma\right\\}$ (141)

where $P_{i,\text{asym}}(d)$ is the projection onto the asymmetric subspace of
the $i^{\text{th}}$ qudits (and is the identity on the other qudits). In
stabilising, it makes little difference whether we stabilise each qudit
individually with its own copy of $\mathbb{I}/2$ or share one, so we stabilise
this definition to

$\displaystyle T_{s}(\rho,\sigma)=\min\Bigg{\\{}\text{Tr}$
$\displaystyle\left[\tau_{AB}\left(\sum_{i=1}^{n}P_{i,\text{asym}}(d\otimes
2)\right)\right]:$ (142)
$\displaystyle\tau_{AB}\in\mathcal{D}\left((\mathbb{C}^{d}\otimes\mathbb{C}^{2})^{\otimes
n}\otimes(\mathbb{C}^{d}\otimes\mathbb{C}^{2})^{\otimes
n}\right),\tau_{A}=\rho\otimes(\mathbb{I}/2)^{\otimes
n},\tau_{B}=\sigma\otimes(\mathbb{I}/2)^{\otimes n}\Bigg{\\}}$ (143)

and $W_{s}(\rho,\sigma)=\sqrt{T_{s}(\rho,\sigma)}$.

We’ll show, however, that any such type of generalisation leads to some states
$\rho$ with $T_{s}(\rho,\rho)>0$. Take, in this example, $n=d=2$ and $\rho$ to
be a Bell state $|\psi^{+}\rangle\langle\psi^{+}|$. As $\rho$ is pure, the set
of possible couplings $\tau$ is very limited. In the non-stabilised
definition, $\tau$ can only be
$|\psi^{+}\rangle\langle\psi^{+}|\otimes|\psi^{+}\rangle\langle\psi^{+}|$. In
the stabilised definition, $\tau$ must have form
$|\psi^{+}\rangle\langle\psi^{+}|\otimes|\psi^{+}\rangle\langle\psi^{+}|\otimes\omega$
for some coupling $\omega$ of $\mathbb{I}^{\otimes 2}/4$ and
$\mathbb{I}^{\otimes 2}/4$.

However, when looking at applying $P_{\text{asym}}$ to the individual qubits,
we note that as the Bell state has qubit marginals $\mathbb{I}/2$, we will
have nonzero transport cost from $\rho$ to itself. Indeed in the non-
stabilised case,

$\displaystyle T(\rho,\sigma)$
$\displaystyle=\sum_{i=1}^{2}\text{Tr}\left[|\psi^{+}\rangle\langle\psi^{+}|\otimes|\psi^{+}\rangle\langle\psi^{+}|\left(P_{i,\text{asym}}(2)\right)\right]$
(144)
$\displaystyle=2\text{Tr}\left[\left(\frac{\mathbb{I}}{2}\otimes\frac{\mathbb{I}}{2}\right)P_{\text{asym}}(2)\right]$
(145) $\displaystyle=\frac{1}{2}\text{Tr}[P_{\text{asym}}(2)]=\frac{1}{2}.$
(146)

In the stabilised case, we still have for any $\tau$, that

$\displaystyle\text{Tr}\left[\tau_{AB}\left(\sum_{i=1}^{2}P_{i,\text{asym}}(2\otimes
2)\right)\right]$ (147)
$\displaystyle=\sum_{i=1}^{2}\text{Tr}\left[|\psi^{+}\rangle\langle\psi^{+}|\otimes|\psi^{+}\rangle\langle\psi^{+}|\otimes\omega\left(P_{i,\text{asym}}(2\otimes
2)\right)\right]$ (148)
$\displaystyle=\sum_{i=1}^{2}\text{Tr}\left[\left(\frac{\mathbb{I}}{2}\otimes\frac{\mathbb{I}}{2}\otimes\omega_{i}\right)P_{\text{asym}}(2\otimes
2)\right]$ (149)
$\displaystyle=\sum_{i=1}^{2}\text{Tr}\left[\left(\frac{\mathbb{I}}{2}\otimes\frac{\mathbb{I}}{2}\otimes\omega_{i}\right)(P_{\text{asym}}(2)\otimes
P_{\text{sym}}(2)+P_{\text{sym}}(2)\otimes P_{\text{asym}}(2))\right]$ (150)
$\displaystyle=\sum_{i=1}^{2}\frac{1}{4}\text{Tr}\left[\omega_{i}P_{\text{sym}}(2)\right]+\frac{3}{4}\text{Tr}\left[\omega_{i}P_{\text{asym}}(2)\right]$
(151)
$\displaystyle\geq\sum_{i=1}^{2}\frac{1}{4}\big{(}\text{Tr}\left[\omega_{i}P_{\text{sym}}(2)\right]+\text{Tr}\left[\omega_{i}P_{\text{asym}}(2)\right]\big{)}=\sum_{i=1}^{2}\frac{1}{4}\text{Tr}[\omega_{i}]=\frac{1}{2}$
(152)

where in line (149), $\omega_{i}$ is a coupling of $\mathbb{I}/2$ with itself,
on the $i^{\text{th}}$ stabilising qubits.

We see from the details of this example that, no matter whether or not we
stabilise using many qubits or a single qubit, and no matter the size of the
space, any attempt to put a $P_{\text{asym}}$ projector on a subspace of
$\mathcal{H}$ will result in highly entangled pure states, those which have
marginals close to maximally mixed on subspaces where $P_{\text{asym}}$ is
placed, having nonzero self-distance. This is largely because the coupling of
a pure state with itself is forced to be the product of the state with itself,
and because the identity on $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ has a
nonzero asymmetric and a nonzero symmetric component. Thus, it appears that a
version of the Wasserstein distance that is not based on a single observable,
like ours, is more suited to obtain generalisations of quantities like the one
of de Palma et al.

##  Appendix B Development of the proposed definition

###  B.1 Definition of a transport plan

During the development of this proposal, many different ways of defining a
transport plan were considered. They all had different versions of the
conditions

$\sum_{j}q_{j}|\psi_{j}\rangle\langle\psi_{j}|=\rho,\sum_{j}q_{j}|\varphi_{j}\rangle\langle\varphi_{j}|=\sigma,q_{j}>0.$
(153)

As in the definition of the $W_{1}$ norm in [36], a first proposal was simply
the condition

$\sum_{j}q_{j}(|\psi_{j}\rangle\langle\psi_{j}|-|\varphi_{j}\rangle\langle\varphi_{j}|)=\rho-\sigma,q_{j}>0.$
(154)

It quickly becomes clear, that using a transport plan of this form containing
telescoping sums, could lead to the degeneracy of $W_{p}^{d}$ when $p>1$. The
main stumbling block here centred on the unboundedness of $\sum_{j}q_{j}$.

Two proposals for restricting $\sum_{j}q_{j}$ were then considered, the first
being

$\sum_{j}q_{j}=1$ (155)

and the second

$\sum_{j}q_{j}=\frac{1}{2}\left\|\rho-\sigma\right\|_{1}.$ (156)

Both of these were discounted when considering the transport plans that were
allowed under these regimes, and their impact on the norm $W_{\infty}^{H}$.

For transport plans of the form (155), consider the $W_{\infty}^{H}$ distance
on $\mathcal{H}=\left(\mathbb{C}^{3}\right)^{\otimes 2}$, and the states
$\rho=\frac{1}{2}|00\rangle\langle 00|+\frac{1}{2}|22\rangle\langle 22|$,
$\sigma=\frac{1}{2}|11\rangle\langle 11|+\frac{1}{2}|22\rangle\langle 22|$.
Classically, the infinite-order transport distance between the measures
$\mu=\frac{1}{2}\delta_{00}+\frac{1}{2}\delta{22}$ and
$\nu=\frac{1}{2}\delta_{11}+\frac{1}{2}\delta{22}$ on the Hamming cube
$\\{0,1,2\\}^{2}$ is $2$. With the definition from (155) however, we could
define a transport plan

$Q=\left\\{\left(\frac{1}{2},\ket{00},\ket{01}\right),\left(\frac{1}{2},\ket{01},\ket{11}\right)\right\\}$
(157)

with a maximum $d(\ket{\psi_{j}},\ket{\varphi_{j}})$ of $1$. Though as in (60)
we are perfectly happy that the $W_{\infty}^{H}$ distance might not match
Ornstein’s $\bar{d}$-distance for classical measures, it certainly should not
differ because of a transport plan of a classical nature such as this one.

The picture for condition (156) is very similar. Consider $W_{\infty}^{H}$ on
$\mathcal{H}=\left(\mathbb{C}^{2}\right)^{\otimes 2}$, with states
$\rho=\frac{1}{2}|00\rangle\langle 00|+\frac{1}{2}|01\rangle\langle 01|$,
$\sigma=\frac{1}{2}|01\rangle\langle 01|+\frac{1}{2}|11\rangle\langle 11|$.
Classically, these have an infinite-order transport distance of $1$ on the
Hamming cube $\\{0,1\\}^{2}$. However, because
$\frac{1}{2}\left\|\rho-\sigma\right\|_{1}$ is small in this case, the only
permitted transport plan is

$Q=\left\\{\left(\frac{1}{2},\ket{00},\ket{11}\right)\right\\}$ (158)

with a maximum $d(\ket{\psi_{j}},\ket{\varphi_{j}})$ of $2$. The condition
(156) does not permit quantum versions of the standard classical transport
plans, and so this definition of a transport plan seems strictly worse than
the one we propose in this work.

###  B.2 Entangled couplings and transport plans

The main reason we need to restrict to separable couplings is the fact that it
is not obvious at first how to attribute a distance to an entangled state
starting from a distance on $\mathbb{P}\mathcal{H}$ and then attribute a
transportation cost to transport plans that include entangled pure states and
satisfy the marginal constraints.

One possibility is as follows: given a state $\ket{\psi}$ in
$\mathbb{P}(\mathcal{H}\otimes\mathcal{H})$ and $SD(\ket{\psi})$ the set of
Schmidt decompositions of $\ket{\psi}$, we define $d(\ket{\psi})$ as:

$\displaystyle
d(\ket{\psi})=\inf\limits_{\sum_{i}\sqrt{p_{i}}\ket{\phi_{1}}\otimes\ket{\phi_{2}}\in
SD(\ket{\psi})}\sum_{i}p_{i}d(\ket{\phi_{1}},\ket{\phi_{2}}).$ (159)

It is then easy to see that we recover the original distance when considering
product states. However, it is also easy to see that, at least for the case
$p=1$, enlarging the set of possible states to include entangled states offers
no advantage. Indeed, given any Schmidt decomposition of an entangled
$\ket{\psi}=\sum_{i}\sqrt{p_{i}}\ket{\phi_{1}}\otimes\ket{\phi_{2}}$, adding
instead $\\{(p_{i},\ket{\phi_{1}},\ket{\phi_{2}})\\}_{i}$ to the transport
plan will give the same cost and still satisfy the marginal constraints. Thus,
at least for this possible generalisation of the distance to entangled states,
there is no advantage in considering entangled couplings.

##  Appendix C Towards the triangle inequality

As with many other attempts to generalise the classical Wasserstein distances
to the quantum setting, the triangle inequality eludes us. The central barrier
to the triangle inequality is the quantum marginal problem: even in the case
where we do not require our couplings to be separable, there is no coherent
way to build a coupling $\tau_{13}$ from coupling $\tau_{12}$ of $\rho_{1}$
and $\rho_{2}$ and coupling $\tau_{23}$ of $\rho_{2}$ and $\rho_{3}$.

All known proofs of the triangle inequality for the classical
$\mathcal{W}_{p}$ distances rely on this idea: given a coupling $\gamma_{12}$
of measures $\mu_{1}$ and $\mu_{2}$, and coupling $\gamma_{23}$ of $\mu_{2}$
and $\mu_{3}$, we can find measure $\gamma_{123}$ with $(1,2)$-marginal
$\gamma_{12}$ and $(2,3)$-marginal $\gamma_{23}$. We can then take the
$(1,3)$-marginal $\gamma_{13}$ of this overarching measure, and show that [8]

$T_{p}(\gamma_{13})^{1/p}\leq
T_{p}(\gamma_{12})^{1/p}+T_{p}(\gamma_{23})^{1/p}$ (160)

via Minkowski’s inequality. Without an equivalent $\tau_{123}$ in the quantum
setting from which to form coupling $\tau_{13}$, there is as of yet no clear
path to a triangle inequality.

For the case $p=1$, we can focus on the case where
$\left\|\rho-\sigma\right\|_{DW_{1}^{d}}=W_{1}^{d}(\rho,\sigma)$, as
$\left\|\cdot\right\|_{DW_{1}^{d}}$ does satisfy the triangle inequality. As
mentioned in Sec. IV.1, this remains a key open problem of our work.

##  Appendix D Auxiliary proofs

###  D.1 Proof of Proposition 17 on the continuity of $W_{p}^{d}$

Proposition 17. Suppose $d$ is continuous on $\mathbb{P}\mathcal{H}$ and let
$1\leq p<\infty$. Then $W_{p}^{d}$ is uniformly continuous.

Proof. Take $\epsilon>0$. Let $\rho,\sigma,\rho^{\prime},\sigma^{\prime}$ be
states on $\mathbb{P}\mathcal{H}$ with
$\left\|\rho-\rho^{\prime}\right\|_{\infty}\leq\delta$ and
$\left\|\sigma-\sigma^{\prime}\right\|_{\infty}\leq\delta$, for some $\delta$
to be chosen later. For any transport plan from $\rho$ to $\sigma$, we will
form a transport plan from $\rho^{\prime}$ to $\sigma^{\prime}$ with a similar
cost. Note that as $\mathcal{H}$ is finite-dimensional,
$\mathbb{P}\mathcal{H}$ is compact and so $d$ is uniformly continuous.

Let $c\gg 1$ (also to be chosen later, but note scale $1\gg c\delta$) and let
$S_{\rho^{\prime}}$, $S_{\sigma^{\prime}}$ respectively be the span of the
eigenvectors of $\rho^{\prime},\sigma^{\prime}$ whose eigenvalues are at least
$c\delta$. Let $\Pi_{\rho^{\prime}}$, $\Pi_{\sigma^{\prime}}$ be the
projectors onto $S_{\rho^{\prime}},S_{\sigma^{\prime}}$ respectively.

Let

$Q=\\{(q_{j},\ket{\psi_{j}},\ket{\varphi_{j}})\\}$ (161)

be any $p^{\text{th}}$-order transport plan from $\rho$ to $\sigma$. Define
then $\ket{\psi_{j}}=\ket{\psi_{j}^{\rho^{\prime}}}+\ket{\psi_{j}^{\perp}}$
where $\ket{\psi_{j}^{\rho^{\prime}}}=\Pi_{\rho^{\prime}}\ket{\psi_{j}}$ and
$\ket{\psi_{j}^{\perp}}$ is perpendicular to $S_{\rho^{\prime}}$. Define
$\ket{\varphi_{j}^{\sigma^{\prime}}}$ and $\ket{\varphi_{j}^{\perp}}$
analogously.

We can then begin to define a transport plan from $\rho^{\prime}$ to
$\sigma^{\prime}$. Let

$\tilde{\rho}=\Pi_{\rho^{\prime}}\rho\Pi_{\rho^{\prime}}=\sum_{j}q_{j}\ket{\psi_{j}^{\rho^{\prime}}}\bra{\psi_{j}^{\rho^{\prime}}}$
(162)

and define $\tilde{\sigma}$ analogously. Note that
$\left\|\Pi_{\rho^{\prime}}(\rho-\rho^{\prime})\Pi_{\rho^{\prime}}\right\|_{\infty}\leq\left\|\rho-\rho^{\prime}\right\|_{\infty}<\delta$.
Therefore

$\tilde{\rho}\leq\Pi_{\rho^{\prime}}\rho^{\prime}\Pi_{\rho^{\prime}}+\delta\mathbb{I}_{S_{\rho^{\prime}}}\leq\left(1+\frac{1}{c}\right)\Pi_{\rho^{\prime}}\rho^{\prime}\Pi_{\rho^{\prime}}\leq\left(1+\frac{1}{c}\right)\rho^{\prime}$
(163)

and so $\frac{c}{c+1}\tilde{\rho}\leq\rho^{\prime}$.

The same holds for $\sigma$, so
$\frac{c}{c+1}\tilde{\sigma}\leq\sigma^{\prime}$.

We may then begin to build our new transport plan starting with the partial
transport plan

$Q_{1}=\left\\{\left(q_{j}^{\prime},\frac{\ket{\psi_{j}^{\rho^{\prime}}}}{\sqrt{\braket{\psi_{j}^{\rho^{\prime}}}{\psi_{j}^{\rho^{\prime}}}}},\frac{\ket{\varphi_{j}^{\sigma^{\prime}}}}{\sqrt{\braket{\varphi_{j}^{\sigma^{\prime}}}{\varphi_{j}^{\sigma^{\prime}}}}}\right)\right\\}$
(164)

where
$q_{j}^{\prime}=\frac{c}{c+1}q_{j}\min\\{\braket{\psi_{j}^{\rho^{\prime}}}{\psi_{j}^{\rho^{\prime}}},\braket{\varphi_{j}^{\sigma^{\prime}}}{\varphi_{j}^{\sigma^{\prime}}}\\}$.
Note then that

$\rho^{\prime}\geq\frac{c}{c+1}\tilde{\rho}\geq\sum_{j}q_{j}^{\prime}\frac{\ket{\psi_{j}^{\rho^{\prime}}}\bra{\psi_{j}^{\rho^{\prime}}}}{\braket{\psi_{j}^{\rho^{\prime}}}{\psi_{j}^{\rho^{\prime}}}}\qquad\text{and}\qquad\sigma^{\prime}\geq\frac{c}{c+1}\tilde{\sigma}\geq\sum_{j}q_{j}^{\prime}\frac{\ket{\varphi_{j}^{\sigma^{\prime}}}\bra{\varphi_{j}^{\sigma^{\prime}}}}{\braket{\varphi_{j}^{\sigma^{\prime}}}{\varphi_{j}^{\sigma^{\prime}}}}.$
(165)

We can then transport the positive semidefinite operator
$\rho^{\prime}-\sum_{j}q_{j}^{\prime}\frac{\ket{\psi_{j}^{\rho^{\prime}}}\bra{\psi_{j}^{\rho^{\prime}}}}{\braket{\psi_{j}^{\rho^{\prime}}}{\psi_{j}^{\rho^{\prime}}}}$
onto
$\sigma^{\prime}-\sum_{j}q_{j}^{\prime}\frac{\ket{\varphi_{j}^{\sigma^{\prime}}}\bra{\varphi_{j}^{\sigma^{\prime}}}}{\braket{\varphi_{j}^{\sigma^{\prime}}}{\varphi_{j}^{\sigma^{\prime}}}}$
via any partial transport plan. Let these transport plan elements form set
$Q_{2}$. It follows that $Q_{1}\cup Q_{2}$ is a transport plan from
$\rho^{\prime}$ to $\sigma^{\prime}$.

We can now attempt bounding the cost of this transport plan. We will show that
$Q_{2}$ has a very small cost and that $Q_{1}$ has a cost very close to
$T_{p}^{d}(Q)$. Starting with the $Q_{2}$ part, we know that

$T_{p}^{d}(Q_{2})\leq\text{Tr}\left[\rho^{\prime}-\sum_{j}q_{j}^{\prime}\frac{\ket{\psi_{j}^{\rho^{\prime}}}\bra{\psi_{j}^{\rho^{\prime}}}}{\braket{\psi_{j}^{\rho^{\prime}}}{\psi_{j}^{\rho^{\prime}}}}\right]\text{diam}_{d}(\mathbb{P}\mathcal{H})^{d}.$
(166)

We will show that this trace part is very small. Indeed

$\displaystyle\text{Tr}\left[\rho^{\prime}-\sum_{j}q_{j}^{\prime}\frac{\ket{\psi_{j}^{\rho^{\prime}}}\bra{\psi_{j}^{\rho^{\prime}}}}{\braket{\psi_{j}^{\rho^{\prime}}}{\psi_{j}^{\rho^{\prime}}}}\right]$
$\displaystyle=\left\|\rho^{\prime}-\sum_{j}q_{j}^{\prime}\frac{\ket{\psi_{j}^{\rho^{\prime}}}\bra{\psi_{j}^{\rho^{\prime}}}}{\braket{\psi_{j}^{\rho^{\prime}}}{\psi_{j}^{\rho^{\prime}}}}\right\|_{1}$
(167)
$\displaystyle\leq\left\|\rho-\rho^{\prime}\right\|_{1}+\left\|\rho-\sum_{j}q_{j}^{\prime}\frac{\ket{\psi_{j}^{\rho^{\prime}}}\bra{\psi_{j}^{\rho^{\prime}}}}{\braket{\psi_{j}^{\rho^{\prime}}}{\psi_{j}^{\rho^{\prime}}}}\right\|_{1}$
(168)
$\displaystyle\leq\delta\text{dim}\mathcal{H}+\left\|\rho-\sum_{j}q_{j}^{\prime}\frac{\ket{\psi_{j}^{\rho^{\prime}}}\bra{\psi_{j}^{\rho^{\prime}}}}{\braket{\psi_{j}^{\rho^{\prime}}}{\psi_{j}^{\rho^{\prime}}}}\right\|_{1}$
(169)

Choose $M>0$ (again to be determined later), and select $L>0$ such that
whenever
$\text{Tr}|\psi_{j}^{\rho^{\prime}}\rangle\langle\psi_{j}^{\rho^{\prime}}|\geq
1-L$ and
$\text{Tr}|\varphi_{j}^{\sigma^{\prime}}\rangle\langle\varphi_{j}^{\sigma^{\prime}}|\geq
1-L$ we have
$d(\ket{\psi_{j}^{\rho^{\prime}}},\ket{\varphi_{j}^{\sigma^{\prime}}})^{p}<d(\ket{\psi_{j}},\ket{\varphi_{j}})^{p}+M$.
This is possible by uniform continuity of $d$. We then split the set of $j$
into those for which the projections onto $S_{\rho^{\prime}}$ and
$S_{\sigma^{\prime}}$ are large, and those for which they are not.

Let

$\mathcal{J}=\left\\{j:\text{Tr}|\psi_{j}^{\rho^{\prime}}\rangle\langle\psi_{j}^{\rho^{\prime}}|,\text{Tr}|\varphi_{j}^{\sigma^{\prime}}\rangle\langle\varphi_{j}^{\sigma^{\prime}}|>1-L\right\\}.$
(170)

and we can split up these $1$-norm terms into $j\in\mathcal{J}$ and
$j\notin\mathcal{J}$. For $j\in\mathcal{J}$, we have