We normalise $\bm{S}^{n}$ by taking $S^{n}_{l}:=1-\sum_{j\in B}S^{n}_{j}$ for
some arbitrary $l\notin B$.

##### Majorising distribution $\bm{\tilde{P}}^{n}$.

We now want to prove a result analogous to 24: the existence of a distribution
that simultaneously majorises the total target distribution $\bm{Q}^{n}$ and
is close to $\bm{S}^{n}$ (within each bin).

######  Lemma 28 (Existence of a majorising distribution).

There exists a distribution $\bm{\tilde{P}}^{n}$ such that
$\bm{\tilde{P}}^{n}\succ\bm{Q}^{n}$ and

$\displaystyle\left|{\tilde{P}_{j}^{n}-S_{j}^{n}}\right|\leq 1/K_{n}(y_{i})$
(162)

for all $j\in B_{i}$ and $-I\leq i<I$.

###### Proof.

The proof is analogous to that of 24, with an application of 23 for each pair
$\bm{S}^{n}|_{B_{i}}$ and $\bm{Q}^{n}|_{B_{i}^{\prime}}$, with $-I\leq i<I$.
This gives us $\bm{\tilde{P}}^{n}$ such that for all $-I\leq i<I$ and $j\in
B_{i}$ it is close to $\bm{S}^{n}$

$\displaystyle\left|{\tilde{P}_{j}^{n}-S_{j}^{n}}\right|\leq\max_{j\in
B_{i}^{\prime}}Q_{j}^{n\downarrow}\leq 1/K_{n}(y_{i}),$ (163)

and possesses the majorisation properties

$\displaystyle\bm{\tilde{P}}^{n}|_{B_{i}}$
$\displaystyle\succ\bm{Q}^{n\downarrow}|_{B_{i}^{\prime}}\quad\text{and}\quad\bm{\tilde{P}}^{n}|_{\bar{B}}\succ\bm{Q}^{n\downarrow}|_{\bar{B^{\prime}}}.$
(164)

Splitting the majorisation across the direct sum, as explained in the proof of
24, gives us the desired overall majorisation

$\displaystyle\bm{\tilde{P}}^{n}$
$\displaystyle\succ\bigoplus_{i=-I}^{I-1}\bm{\tilde{P}}^{n}|_{B_{i}}\oplus\bm{\tilde{P}}^{n}|_{\overline{B}}$
$\displaystyle\succ\bigoplus_{i=-I}^{I-1}\bm{Q}^{n\downarrow}|_{B_{i}^{\prime}}\oplus\bm{Q}^{n\downarrow}|_{\overline{B^{\prime}}}\succ\bm{Q}^{n}.$
(165)

∎

##### Infidelity.

The next step involves bounding the fidelity between the total initial state
$\bm{P}^{n}$ and majorising distribution $\bm{\tilde{P}}^{n}$ given by the
above construction. We will start by bounding the fidelity for a fixed set of
parameters $A$, $\lambda$ and $I$.

######  Lemma 29.

For any monotone continuously differentiable function $1\geq A\geq\Phi$,
$\lambda\geq 0$, and $I\in\mathbb{N}$ there exists a sequence of distributions
$\bm{\tilde{P}}^{n}\succ\bm{Q}^{n}$ such that

$\displaystyle\liminf\limits_{n\to\infty}{F\left(\bm{\tilde{P}}^{n},\bm{P}^{n\downarrow}\right)}$
$\displaystyle\qquad\geq\left(\int_{-\lambda}^{\lambda}\sqrt{A^{\prime}\left(x+\frac{\lambda}{I}\right)\Phi_{\mu,\nu}^{\prime}\left(x-\frac{\lambda}{I}\right)}\,\mathrm{d}x\\!\right)^{\\!2}\\!\\!,$
(166)

with the prime superscript in $A^{\prime}$ and $\Phi_{\mu,\nu}^{\prime}$
denoting a derivative.

###### Proof.

The first part of the proof is analogous to the proof of 25. More precisely
using 28 (in place of 24) and employing the fact that $B_{i}$ is gapped away
from $B_{i}^{\prime}$, we can apply the argument presented there to obtain

$\displaystyle\liminf\limits_{n\to\infty}F\left(\bm{\tilde{P}}^{n},\bm{P}^{n}\right)\geq\liminf\limits_{n\to\infty}\left(\sum_{j\in
B}\sqrt{S^{n}_{j}P^{n}_{j}}\right)^{2}.$ (167)

Inserting the definition of the scaled distribution $\bm{S}^{n}$ yields

$\displaystyle\liminf_{n\to\infty}\sqrt{F\left(\bm{\tilde{P}}^{n},\bm{P}^{n\downarrow}\right)}$
$\displaystyle~{}\quad\geq\liminf_{n\to\infty}\sum_{i=-I}^{I-1}\sum_{j\in
B_{i}}\sqrt{S^{n}_{j}P^{n\downarrow}_{j}}$
$\displaystyle~{}\quad=\liminf_{n\to\infty}\sum_{i=-I}^{I-1}\sum_{j\in
B_{i}}\sqrt{\frac{\sum_{k\in B_{i}^{\prime}}Q^{n\downarrow}_{k}}{\sum_{k\in
B_{i}}P^{n\downarrow}_{k}}\cdot
P^{n\downarrow}_{j}}\sqrt{P^{n\downarrow}_{j}}$
$\displaystyle~{}\quad=\liminf_{n\to\infty}\sum_{i=-I}^{I-1}\sqrt{\sum_{j\in
B_{i}^{\prime}}Q^{n\downarrow}_{j}\sum_{k\in B_{i}}P^{n\downarrow}_{k}}.$
(168)

Recalling that $\Phi(y_{i})=A(x_{i+2})$ and applying 17 gives

$\displaystyle\lim\limits_{n\to\infty}\sum_{j\in B_{i}}P^{n\downarrow}_{j}$
$\displaystyle=\Phi_{\mu,\nu}(x_{i+1})-\Phi_{\mu,\nu}(x_{i}),$ (169a)
$\displaystyle\lim\limits_{n\to\infty}\sum_{j\in
B_{i}^{\prime}}Q^{n\downarrow}_{j}$ $\displaystyle=A(x_{i+3})-A(x_{i+2}).$
(169b)

Substituting these into our lower bound on fidelity yields

$\displaystyle\liminf_{n\to\infty}\sqrt{F\left(\bm{\tilde{P}}^{n},\bm{P}^{n\downarrow}\right)}$
$\displaystyle\qquad\quad\geq\sum_{i=-I}^{I-1}\sqrt{A(x_{i+3})-A(x_{i+2})}$
$\displaystyle\qquad\qquad\quad\qquad\times\sqrt{\Phi_{\mu,\nu}(x_{i+1})-\Phi_{\mu,\nu}(x_{i})}$
(170)
$\displaystyle\qquad\quad\geq\sum_{i=-I}^{I-1}\sqrt{A\left(\frac{\lambda(i+2)}{I}\right)-A\left(\frac{\lambda(i+1)}{I}\right)}$
$\displaystyle\qquad\qquad\quad\qquad\times\sqrt{\Phi_{\mu,\nu}\left(\frac{\lambda
i}{I}\right)-\Phi_{\mu,\nu}\left(\frac{\lambda(i-1)}{I}\right)}.$

Using the differentiability of $A$ and $\Phi_{\mu,\nu}$ we can express these
finite differences as integrals

$\displaystyle\liminf_{n\to\infty}\sqrt{F\left(\bm{\tilde{P}}^{n},\bm{P}^{n\downarrow}\right)}$
$\displaystyle\qquad\qquad\geq\sum_{i=-I}^{I-1}{\sqrt{\int_{\lambda\frac{i}{I}}^{\lambda\frac{i+1}{I}}A^{\prime}\left(x+\frac{\lambda}{I}\right)\,\mathrm{d}x}}$
$\displaystyle\qquad\qquad\qquad\qquad\times{\sqrt{\int_{\lambda\frac{i}{I}}^{\lambda\frac{i+1}{I}}\Phi^{\prime}_{\mu,\nu}\left(x-\frac{\lambda}{I}\right)\,\mathrm{d}x}}.$
(171)

Finally, we apply the Schwarz inequality to arrive at the desired bound

$\displaystyle\liminf_{n\to\infty}\sqrt{F\left(\bm{\tilde{P}}^{n},\bm{P}^{n\downarrow}\right)}$
$\displaystyle\qquad\geq\\!\\!\sum_{i=-I}^{I-1}\int_{\lambda\frac{i}{I}}^{\lambda\frac{i+1}{I}}\\!\\!\\!\\!\sqrt{A^{\prime}\left(x+\frac{\lambda}{I}\right)\Phi^{\prime}_{\mu,\nu}\left(x-\frac{\lambda}{I}\right)}\,\mathrm{d}x$
$\displaystyle\qquad=\int_{-\lambda}^{\lambda}\sqrt{A^{\prime}\left(x+\frac{\lambda}{I}\right)\Phi^{\prime}_{\mu,\nu}\left(x-\frac{\lambda}{I}\right)}\,\mathrm{d}x.$
(172)

∎

Now, by taking the appropriate limits of our parameters $A$, $\lambda$ and
$I$, we will get the desired achieveability bound on the optimal infidelity,
and therefore also on the optimal rate.

###### Proof of 27 (achieveability).

By 29 we know that there exists a family of distributions $\bm{\tilde{P}}^{n}$
majorising $\bm{Q}^{n}$ and such that
$\liminf\limits_{n\to\infty}F\left(\bm{\tilde{P}}^{n},\bm{P}^{n\downarrow}\right)$
is lower-bounded by

$\displaystyle\left(\int_{-\lambda}^{\lambda}\sqrt{A^{\prime}\left(x+\frac{\lambda}{I}\right)\Phi_{\mu,\nu}^{\prime}\left(x-\frac{\lambda}{I}\right)}\,\mathrm{d}x\right)^{2}.$
(173)

Due to the equivalence between pre- and post-majorisation, Lemma 12, this
means that there exists a family of distributions $\bm{\tilde{Q}}^{n}$ that is
majorised by the total initial state $\bm{P}^{n}$ and such that their fidelity
with the total target state $\bm{Q}^{n}$ is also lower bounded by the above
expression, which implies a lower bound on the asymptotic ideal fidelity

$\displaystyle\liminf\limits_{n\to\infty}\sqrt{1-\epsilon^{*}_{0}(n,R_{\mu})}$
$\displaystyle~{}~{}\quad\geq\liminf\limits_{n\to\infty}\sqrt{F\left({\bm{\tilde{Q}}^{n}},{\bm{Q}^{n\downarrow}}\right)}$
$\displaystyle~{}~{}\quad\geq\int_{-\lambda}^{\lambda}\sqrt{A^{\prime}\left(x+\frac{\lambda}{I}\right)\Phi_{\mu,\nu}^{\prime}\left(x-\frac{\lambda}{I}\right)}\,\mathrm{d}x.$
(174)

As the left hand side is independent of $I$, $\lambda$ and $A$, we can now
take the desired limits. Note that the order of limits will be important:
first we will take $I\to\infty$, then $\lambda\to\infty$, followed by a
supremum over $A$.

Firstly, we take the limit inferior $I\to\infty$. As a consequence of the fact
that $\lambda$ is still finite, together with the continuous differentiability
of $A$ and $\Phi_{\mu,\nu}$, we have the point-wise limit

$\displaystyle\sqrt{A^{\prime}\left(x+\frac{\lambda}{I}\right)}\sqrt{\Phi_{\mu,\nu}^{\prime}\left(x-\frac{\lambda}{I}\right)}\xrightarrow{I\to\infty}\sqrt{A^{\prime}(x)}\sqrt{\Phi_{\mu,\nu}^{\prime}(x)}.$
(175)

Using the compactness of $[-2\lambda,2\lambda]$ we can apply the dominated
convergence theorem to move this limit inside the integral, which gives

$\displaystyle\liminf\limits_{n\to\infty}\sqrt{1-\epsilon^{*}_{0}(n,R_{\mu})}$
$\displaystyle\qquad\geq\liminf\limits_{I\to\infty}\\!\int_{-\lambda}^{\lambda}\sqrt{A^{\prime}\left(x+\frac{\lambda}{I}\right)\Phi_{\mu,\nu}^{\prime}\left(x-\frac{\lambda}{I}\right)}\,\mathrm{d}x\\!\\!$
$\displaystyle\qquad=\int_{-\lambda}^{\lambda}\lim\limits_{I\to\infty}\sqrt{A^{\prime}\left(x+\frac{\lambda}{I}\right)\Phi_{\mu,\nu}^{\prime}\left(x-\frac{\lambda}{I}\right)}\,\mathrm{d}x$
$\displaystyle\qquad=\int_{-\lambda}^{\lambda}\sqrt{A^{\prime}\left(x\right)\Phi_{\mu,\nu}^{\prime}(x)}\,\mathrm{d}x.$
(176)

Secondly, we want to take $\lambda\to\infty$. The existence of this limit
follows from monotone convergence theorem, which we can apply due to the
monotonicity of $A$ and $\Phi_{\mu,\nu}$, together with the boundedness of the
continuous fidelity. Taking the limit gives us a bound in terms of the
continuous fidelity

$\displaystyle\\!\\!\\!\\!\liminf\limits_{n\to\infty}\sqrt{1-\epsilon^{*}_{0}(n,R_{\mu})}$
$\displaystyle\geq\lim\limits_{\lambda\to\infty}\int_{-\lambda}^{\lambda}\sqrt{A^{\prime}\left(x\right)\Phi_{\mu,\nu}^{\prime}(x)}\,\mathrm{d}x$
$\displaystyle\geq\int_{-\infty}^{\infty}\sqrt{A^{\prime}\left(x\right)\Phi_{\mu,\nu}^{\prime}(x)}\,\mathrm{d}x=\sqrt{\mathcal{F}\left({A^{\prime}},{\Phi_{\mu,\nu}^{\prime}}\right)}.$
(177)

Lastly, we want to take a supremum over all continuously differentiable
monotone functions $1\geq A\geq\Phi$, which gives us the Rayleigh-normal
distribution

$\displaystyle\liminf\limits_{n\to\infty}\epsilon^{*}_{0}(n,R_{\mu})$
$\displaystyle\\!\leq\\!1\\!-\\!\sup_{A\geq\Phi}\mathcal{F}\left({A^{\prime}},{\Phi_{\mu,\nu}^{\prime}}\right)\\!=:\\!Z_{\nu}(\mu).$
(178)

Using the above and the duality property of Rayleigh-normal distributions, Eq.
(45), we obtain the lower bound on the optimal rate

$\displaystyle{R^{*}_{0}(n,\epsilon)\gtrsim\frac{1}{D(\bm{q})}\Biggl{[}D(\bm{p})+\sqrt{\frac{V(\bm{p})}{n}}Z^{-1}_{1/\nu}(\epsilon)\Biggr{]}.}$
(179)

∎

####  6.5.2 Optimality

We now proceed to the proof of the optimality of 27. To this end, we will
employ two lemmas originally proved in Ref. [Kumagai and Hayashi(2017)]. The
idea is to start by showing that, after a particular coarse-graining, the
fidelity between $\Phi$ and $\Phi_{\mu,\nu}$ is close to the optimal fidelity
$\sup_{A\geq\Phi}\mathcal{F}(A^{\prime},\Phi^{\prime}_{\mu,\nu})={1-Z_{\nu}(\mu)}$.

######  Lemma 30 (Lemma 17 of Ref. [Kumagai and Hayashi(2017)]).

For any $\zeta>0$, there exist real numbers $s\leq t\leq t^{\prime}\leq
s^{\prime}$ such that ${\Phi^{\prime}(x)}/{\Phi^{\prime}_{\mu,\nu}(x)}$ is
strictly monotone decreasing for $x\in(s,s^{\prime})$ and

$\displaystyle\frac{\Phi(t)}{\Phi_{\mu,\nu}(t)}$
$\displaystyle=\frac{\Phi^{\prime}(s)}{\Phi^{\prime}_{\mu,\nu}(s)},$ (180a)
$\displaystyle\frac{1-\Phi(t^{\prime})}{1-\Phi_{\mu,\nu}(t^{\prime})}$
$\displaystyle=\frac{\Phi^{\prime}(s^{\prime})}{\Phi^{\prime}_{\mu,\nu}(s^{\prime})}.$
(180b)

Moreover, if we define $\mathcal{F}_{t,t^{\prime}}(\cdot,\cdot)$ to be the
fidelity of distributions which have been coarse-grained on $x\leq t$ and
$x\geq t^{\prime}$, specifically

$\displaystyle{\mathcal{F}_{t,t^{\prime}}(p,q)}:=$
$\displaystyle\Bigg{(}\sqrt{\int_{-\infty}^{t}p(x)\,\mathrm{d}x\int_{-\infty}^{t}q(x)\,\mathrm{d}x}$
$\displaystyle\quad+\int_{t}^{t^{\prime}}\sqrt{p(x)q(x)}\,\mathrm{d}x$
$\displaystyle\quad+\sqrt{\int_{t^{\prime}}^{\infty}p(x)\,\mathrm{d}x\int_{t}^{\infty}q(x)\,\mathrm{d}x}\,\,\Bigg{)}^{2}\\!,$
(181)

then this coarse-grained fidelity has an upper bound

$\displaystyle\mathcal{F}_{t,t^{\prime}}(\Phi^{\prime},\Phi_{\mu,\nu}^{\prime})-\zeta$
$\displaystyle\leq\sup_{A\geq\Phi}\mathcal{F}(A^{\prime},\Phi_{\mu,\nu}^{\prime}).$
(182)

Notice that $\Phi$ and $\Phi_{\mu,\nu}$ are exactly the distributions that
appear in central limit theorem, 17. Thus, we would like to relate the
fidelity $F(\bm{P}^{n},\bm{\tilde{P}}^{n})$ back to the Rayleigh-normal
distribution via this coarse-grained fidelity between Gaussians. To be able to
argue this for _any_ $\bm{\tilde{P}}^{n}\succ\bm{Q}^{n}$, we will first give a
sufficient condition for a distribution $\bm{a}$ to have the highest possible
fidelity with respect to a second distribution $\bm{b}$ among all
distributions satisfying a majorisation-like condition.

######  Lemma 31 (Lemma 15 of Ref. [Kumagai and Hayashi(2017)]).

Let $\bm{a}$ and $\bm{b}$ be probability distributions such that $a_{i}/b_{i}$
is strictly decreasing for all $i$. Then, for any distribution $\bm{c}$ such
that

$\displaystyle\sum_{i=1}^{k}a_{i}\leq\sum_{i=1}^{k}c_{i}\quad\forall k,$ (183)

we have

$\displaystyle F({\bm{c}},{\bm{b}})\leq F({\bm{a}},{\bm{b}}),$ (184)

with equality if and only if $\bm{c}=\bm{a}$.

We are now ready for the optimality proof.

###### Proof of 27 (optimality).

To prove optimality we need to show that for any
$\bm{\tilde{P}}^{n}\succ\bm{Q}^{n}$, the infidelity between
$\bm{\tilde{P}}^{n}$ and $\bm{P}^{n}$ can be lower bounded by the Rayleigh-
normal distribution. This, through Lemma 12, will yield a lower bound on the
infidelity between any final state $\bm{\tilde{Q}}^{n}$ (i.e., any
distribution majorised by the total initial state $\bm{P}^{n}$) and the total
target state $\bm{Q}^{n}$. We will start by using the monotonicity of fidelity
under coarse-graining to bound the fidelity between $\bm{\tilde{P}}^{n}$ and
$\bm{P}^{n}$ by the fidelity between their coarse-grained versions (with
coarse-graining over particularly chosen bins of indices). We will then use 31
(along with the monotonicity properties of 30) to bound the fidelity between
coarse-grained versions of $\bm{P}^{n}$ and $\bm{\tilde{P}}^{n}$ by the
fidelity between coarse-grained versions of $\bm{P}^{n}$ and $\bm{Q}^{n}$.
Next, by applying 17, we will show that this coarse-grained fidelity
asymptotes to a fidelity between Gaussians. We will conclude by returning to
the last part of 30, which will allow us to give a final bound in terms of the
Rayleigh-normal distribution.

Fix $\zeta>0$ and $I\in\mathbb{N}$. Let $t,t^{\prime}\in\mathbb{R}$ be those
given by 30 and introduce

$\displaystyle z_{i}:=t(1-i/I)+t^{\prime}(i/I)$ (185)

for $0\leq i\leq I$. Define a set of bins

$\displaystyle B_{i}$
$\displaystyle:=\\{K_{n}(z_{i}),\dots,K_{n}(z_{i+1})-1\\}$ (186)

for $0\leq i<I$, as well as two end bins

$\displaystyle B_{-1}$ $\displaystyle:=\\{1,\dots,K_{n}(t)-1\\},$ (187a)
$\displaystyle B_{I}$ $\displaystyle:=\\{K_{n}(t^{\prime}),\dots,\infty\\},$
(187b)

so that $\\{B_{i}\\}$ now gives a partition of all indices. Using the
monotonicity of fidelity under coarse-graining we get

$\displaystyle\sqrt{F(\bm{\tilde{P}}^{n},\bm{P}^{n})}$
$\displaystyle=\sum_{i=-1}^{I}\sum_{j\in
B_{i}}\sqrt{\tilde{P}^{n\downarrow}_{j}P^{n\downarrow}_{j}}$
$\displaystyle\leq\sum_{i=-1}^{I}\sqrt{\sum_{j\in
B_{i}}\tilde{P}^{n\downarrow}_{j}\sum_{j\in
B_{i}}P^{n\downarrow}_{j}}=:r_{n}.$ (188)

We now define the limiting coarse-grained versions of total initial and target
distributions

$\displaystyle a_{i}$ $\displaystyle:=\lim\limits_{n\to\infty}\sum_{j\in
B_{i}}Q^{n\downarrow}_{j},$ (189a) $\displaystyle b_{i}$
$\displaystyle:=\lim\limits_{n\to\infty}\sum_{j\in B_{i}}P^{n\downarrow}_{j},$
(189b)

for $-1\leq i\leq I$. We note that the above limits all exist by 17,
specifically

$\displaystyle a_{-1}$ $\displaystyle=\Phi(t),$ (190a) $\displaystyle a_{i}$
$\displaystyle=\Phi(z_{i+1})-\Phi(z_{i}),$ (190b) $\displaystyle a_{I}$
$\displaystyle=1-\Phi(t^{\prime}),$ (190c) $\displaystyle b_{-1}$
$\displaystyle=\Phi_{\mu,\nu}(t),$ (190d) $\displaystyle b_{i}$
$\displaystyle=\Phi_{\mu,\nu}(z_{i+1})-\Phi_{\mu,\nu}(z_{i}),$ (190e)
$\displaystyle b_{I}$ $\displaystyle=1-\Phi_{\mu,\nu}(t^{\prime}).$ (190f)

We would also like to analogously define a distribution $\bm{c}$ that would be
a coarse-grained version of $\bm{\tilde{P}}^{n}$, but we have no guarantees
that the corresponding limits exist. In lieu of this, we will use the
vectorial Bolzano-Weirestrass Theorem555Start with a subset of indices
$\\{m_{l}^{(-2)}\\}_{l}\subseteq\mathbb{N}$ on which $\\{r_{n}\\}_{n}$
converges to its limit superior. The scalar version of Bolzano-Weirestrass
gives a subset $\\{m^{(i)}_{l}\\}_{l}\subseteq\\{m^{(i-1)}_{l}\\}_{l}$ on
which $c_{i}$ exists. Applying this for each $-1\leq i\leq I$, one obtains a
set of indices $\\{m_{l}\\}_{l}:=\\{m_{l}^{(I)}\\}_{l}$ with the desired
property., which gives that there exists a strictly increasing set of indices
$\\{m_{l}\\}_{l}\subset\mathbb{N}$ such that $\\{r_{n}\\}$ limits to its limit
superior

$\displaystyle\lim\limits_{l\to\infty}r_{m_{l}}=\limsup\limits_{n\to\infty}r_{n},$
(191)

_and_ that all the limits

$\displaystyle c_{i}$ $\displaystyle:=\lim\limits_{l\to\infty}\sum_{j\in
B_{i}}\tilde{P}^{m_{l}\downarrow}_{j}$ (192)

exist, for all $-1\leq i\leq I$.

We now want to apply 31 to bound the fidelity $F(\bm{c},\bm{b})$ with
$F(\bm{a},\bm{b})$, but first we must show that $a_{i}/b_{i}$ is strictly
decreasing. 30 allows us to relate this ratio at the ends, $i=-1$ and $i=I$,
to the ratio of Gaussian derivatives,

$\displaystyle\frac{a_{-1}}{b_{-1}}=\frac{\Phi(t)}{\Phi_{\mu,\nu}(t)}=\frac{\Phi^{\prime}(s)}{\Phi^{\prime}_{\mu,\nu}(s)},$
(193a)
$\displaystyle\frac{a_{I}}{b_{I}}=\frac{1-\Phi(t^{\prime})}{1-\Phi_{\mu,\nu}(t^{\prime})}=\frac{\Phi^{\prime}(s^{\prime})}{\Phi^{\prime}_{\mu,\nu}(s^{\prime})}.$
(193b)

For $0\leq i<I$ we can apply Cauchy’s mean value theorem, which gives that
there exists some $s_{i}\in(z_{i},z_{i+1})$ the ratio of finite differences is
given by a ratio of derivatives

$\displaystyle\frac{a_{i}}{b_{i}}=\frac{\Phi(z_{i+1})-\Phi(z_{i})}{\Phi_{\mu,\nu}(z_{i+1})-\Phi_{\mu,\nu}(z_{i})}=\frac{\Phi^{\prime}(s_{i})}{\Phi^{\prime}_{\mu,\nu}(s_{i})}.$
(194)

Given that $\\{s,s_{0},\dots,s_{I-1},s^{\prime}\\}$ is a strictly increasing
sequence, and that $\Phi^{\prime}(x)/\Phi_{\mu,\nu}^{\prime}(x)$ is strictly
decreasing on $(s,s^{\prime})$ by 30, we therefore have that $a_{i}/b_{i}$ is
strictly decreasing as required.

Now that we have shown that $a_{i}/b_{i}$ is strictly decreasing, we can apply
31. This gives us

$\displaystyle\limsup\limits_{n\to\infty}F(\bm{\tilde{P}}^{n},\bm{P}^{n})\leq
F(\bm{c},\bm{b})$ $\displaystyle\leq F(\bm{a},\bm{b}).$ (195)

Expanding this out, we have

$\displaystyle\limsup\limits_{n\to\infty}\sqrt{F(\bm{\tilde{P}}^{n},\bm{P}^{n})}$
$\displaystyle\quad\leq\sqrt{\Phi(z_{0})\Phi_{\mu,\nu}(z_{0})}$
$\displaystyle\qquad+\sum_{i=0}^{I-1}\sqrt{\Phi(z_{i+1})-\Phi(z_{i})}\sqrt{\Phi_{\mu,\nu}(z_{i+1})-\Phi_{\mu,\nu}(z_{i})}$
$\displaystyle\qquad+\sqrt{\left(\vphantom{\frac{num}{den}}1-\Phi(z_{I})\right)\left(1-\Phi_{\mu,\nu}(z_{I})\vphantom{\frac{num}{den}}\right)}.$
(196)

If we take $I\to\infty$, these finite differences above approach derivatives,
and we get a bound in terms of a coarse-grained fidelity

$\displaystyle\limsup\limits_{n\to\infty}\sqrt{F(\bm{\tilde{P}}^{n},\bm{P}^{n})}$
$\displaystyle\qquad\qquad\leq\sqrt{\Phi(t)\Phi_{\mu,\nu}(t)}$
$\displaystyle\qquad\qquad~{}\quad+\int_{t}^{t^{\prime}}\sqrt{\Phi^{\prime}(x)\Phi_{\mu,\nu}^{\prime}(x)}~{}\mathrm{d}x$
$\displaystyle\qquad\qquad~{}\quad+\sqrt{\left(\vphantom{\frac{num}{den}}1-\Phi(t^{\prime})\right)\left(1-\Phi_{\mu,\nu}(t^{\prime})\vphantom{\frac{num}{den}}\right)}.$
(197)

Finally, we apply the last part of 30, which allows us to bound this in terms
of the Rayleigh-normal distribution, giving

$\displaystyle\liminf\limits_{n\to\infty}\delta(\bm{\tilde{P}}^{n},\bm{P}^{n})\geq{Z_{\nu}(\mu)}-\zeta.$
(198)

Taking $\zeta\searrow 0$, we can once more use the equivalence between pre-
and post-majorisation, Lemma 12, to conclude that

$\displaystyle\liminf\limits_{n\to\infty}\epsilon^{*}_{0}(n,R_{\mu})\geq
Z_{\nu}(\mu).$ (199)

Using the above together with the duality property of Rayleigh-normal
distributions, Eq.17 (45), we obtain the upper bound on the optimal rate

$\displaystyle
R^{*}_{0}(n,\epsilon)\lesssim\frac{1}{D(\bm{q})}\Biggl{[}D(\bm{p})+\sqrt{\frac{V(\bm{p})}{n}}Z^{-1}_{1/\nu}(\epsilon)\Biggr{]}.$
(200)

∎

##  7 Outlook

In this paper we have derived the exact second-order asymptotics of state
interconversion under thermal operations between any two energy-incoherent
states. It is then natural to ask whether such a characterisation is also
possible for general, not necessarily energy-incoherent, states. Due to the
fact that thermal operations are time-translation covariant, such that
coherence and athermality form independent resources [Lostaglio  _et
al._(2015b)Lostaglio, Jennings, and Rudolph, Lostaglio  _et
al._(2015a)Lostaglio, Korzekwa, Jennings, and Rudolph], it seems unlikely that
the current approach can be easily generalised. Instead, one would need to
rely on the full power of Gibbs-preserving maps [Faist  _et al._(2015)Faist,
Oppenheim, and Renner, Korzekwa(2017)] that form a superset of the thermal
operations. For such maps, we believe that a reasonable conjecture is in fact
given by Eqs. (1a) and (1b), with the relative entropy and relative entropy
variance replaced by their fully quantum analogues given in Refs.
[Umegaki(1962)] and [Li(2014), Tomamichel and Hayashi(2013)], respectively.

We also provided a physical interpretation of our main result by considering
several thermodynamic scenarios and explaining how our work can be employed to
rigorously address the problem of thermodynamic irreversibility. We derived
optimal values of distillable work and work of formation, and related them to
the infidelity of these processes. This could potentially be used to clarify
the notion of imperfect work [Åberg(2013), Woods  _et al._(2015)Woods, Ng, and
Wehner, Ng  _et al._(2017)Ng, Woods, and Wehner], and to construct a
comparison platform allowing one to continuously distinguish between work-like
and heat-like forms of energy. We also discussed thermodynamic processes with
finite-size working bodies, focusing particularly on the optimal performance
of heat engines. We have shown that there are non-trivial conditions under
which an engine can operate at Carnot efficiency and extract perfect work.
This opens the possibility of engineering finite heat-baths and working bodies
in order to minimise undesirable dissipation of free energy. Moreover, our
formalism is general enough to address other interesting problems involving
finite-size baths, like fluctuation theorems, Landauers’ principle or the
third law of thermodynamics [Campisi  _et al._(2009)Campisi, Talkner, and
Hänggi, Reeb and Wolf(2014), Scharlau and Mueller(2018)].

A number of natural technical extensions to our result suggest themselves. We
have used the infidelity as our error measure, and conjecture that 10 will
also hold when $\epsilon$ is a bound on the total variational distance. Our
second-order expansion falls into a larger class of results known as _small
deviation_ bounds, in which we consider a fixed error threshold $\epsilon$.
Two natural extensions are to the regime of _large deviations_
[Hayashi(2006)], in which a fixed rate is considered, and _moderate
deviations_ [Chubb  _et al._(2017)Chubb, Tan, and Tomamichel, Cheng and
Hsieh(2017)], in which the rate approaches its optimum _and_ the error
vanishes. Last, but not least, we expect that our treatment of approximate
majorisation can be extended to cover other distance measures.

### Acknowledgements

We want to thank Nelly Ng for insightful discussions on the interplay between
smoothing and thermomajorisation, as well as for the comments on the
manuscript; Masahito Hayashi for discussions and feedback on early technical
notes; Matteo Lostaglio for useful discussions on thermodynamic
interpretations of second-order rates; and Joe Renes for helpful comments on
the manuscript. CC and KK acknowledge support from the ARC via the Centre of
Excellence in Engineered Quantum Systems (EQuS), project number CE110001013.
CC also acknowledges support from the Australian Institute for Nanoscale
Science and Technology Postgraduate Scholarship (John Makepeace Bennett Gift).
MT is funded by an ARC Discovery Early Career Researcher Award, project number
DE160100821.

## References

  * [Giles(1964)] Robin Giles,  _Mathematical Foundations of Thermodynamics_ (Pergamon Press, 1964).
  * [Coecke  _et al._(2016)Coecke, Fritz, and Spekkens] Bob Coecke, Tobias Fritz, and Robert W Spekkens, “A mathematical theory of resources,” Inform. Comput. 250, 59–86 (2016).
  * [Horodecki and Oppenheim(2013a)] M. Horodecki and J. Oppenheim, “(Quantumness in the context of) resource theories,” Int. J. Mod. Phys. B 27, 1345019 (2013a).
  * [Horodecki  _et al._(2009)Horodecki, Horodecki, Horodecki, and Horodecki] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki, “Quantum entanglement,” Rev. Mod. Phys. 81, 865–942 (2009).
  * [Baumgratz  _et al._(2014)Baumgratz, Cramer, and Plenio] T Baumgratz, M Cramer, and MB Plenio, “Quantifying coherence,” Phys. Rev. Lett. 113, 140401 (2014).
  * [Marvian and Spekkens(2016)] Iman Marvian and Robert W Spekkens, “How to quantify coherence: distinguishing speakable and unspeakable notions,” Phys. Rev. A 94, 052324 (2016).
  * [Winter and Yang(2016)] Andreas Winter and Dong Yang, “Operational resource theory of coherence,” Phys. Rev. Lett. 116, 120404 (2016).
  * [Marvian and Spekkens(2013)] I. Marvian and R. W. Spekkens, “The theory of manipulations of pure state asymmetry: I. Basic tools, equivalence classes and single copy transformations,” New J. Phys. 15, 033001 (2013).
  * [Marvian(2012)] Iman Marvian,  _Symmetry, Asymmetry and Quantum Information_ , Ph.D. thesis, University of Waterloo (2012).
  * [Janzing  _et al._(2000)Janzing, Wocjan, Zeier, Geiss, and Beth] D. Janzing, P. Wocjan, R. Zeier, R. Geiss, and Th. Beth, “Thermodynamic cost of reliability and low temperatures: tightening Landauer’s principle and the second law,” Int. J. Theor. Phys. 39, 2717–2753 (2000).
  * [Horodecki and Oppenheim(2013b)] M. Horodecki and J. Oppenheim, “Fundamental limitations for quantum and nanoscale thermodynamics,” Nat. Commun. 4, 2059 (2013b).
  * [Brandão  _et al._(2013)Brandão, Horodecki, Oppenheim, Renes, and Spekkens] Fernando G. S. L. Brandão, Michał Horodecki, Jonathan Oppenheim, Joseph M. Renes, and Robert W. Spekkens, “Resource theory of quantum states out of thermal equilibrium,” Phys. Rev. Lett. 111, 250404 (2013).
  * [Lostaglio  _et al._(2015a)Lostaglio, Korzekwa, Jennings, and Rudolph] Matteo Lostaglio, Kamil Korzekwa, David Jennings, and Terry Rudolph, “Quantum coherence, time-translation symmetry, and thermodynamics,” Phys. Rev. X 5, 021001 (2015a).
  * [Ćwikliński  _et al._(2015)Ćwikliński, Studziński, Horodecki, and Oppenheim] Piotr Ćwikliński, Michał Studziński, Michał Horodecki, and Jonathan Oppenheim, “Limitations on the evolution of quantum coherences: towards fully quantum second laws of thermodynamics,” Phys. Rev. Lett. 115, 210403 (2015).
  * [Narasimhachar and Gour(2015)] V. Narasimhachar and G. Gour, “Low-temperature thermodynamics with quantum coherence,” Nat. Commun. 6, 7689 (2015).
  * [Gour  _et al._(2017)Gour, Jennings, Buscemi, Duan, and Marvian] Gilad Gour, David Jennings, Francesco Buscemi, Runyao Duan, and Iman Marvian, “Quantum majorization and a complete set of entropic conditions for quantum thermodynamics,” arXiv:1708.04302 (2017).
  * [Nielsen(1999)] Michael A Nielsen, “Conditions for a class of entanglement transformations,” Phys. Rev. Lett. 83, 436 (1999).
  * [Bennett  _et al._(1996)Bennett, Bernstein, Popescu, and Schumacher] Charles H Bennett, Herbert J Bernstein, Sandu Popescu, and Benjamin Schumacher, “Concentrating partial entanglement by local operations,” Phys. Rev. A 53, 2046 (1996).
  * [Horodecki  _et al._(2017)Horodecki, Oppenheim, and Sparaciari] Michał Horodecki, Jonathan Oppenheim, and Carlo Sparaciari, “Approximate majorization,” arXiv:1706.05264 (2017).
  * [Kumagai and Hayashi(2017)] Wataru Kumagai and Masahito Hayashi, “Second-order asymptotics of conversions of distributions and entangled states based on Rayleigh-normal probability distributions,” IEEE Trans. Inf. Theory 63, 1829–1857 (2017).
  * [Tomamichel and Hayashi(2013)] Marco Tomamichel and Masahito Hayashi, “A hierarchy of information quantities for finite block length analysis of quantum tasks,” IEEE Trans. Inf. Theory 59, 7693–7710 (2013).
  * [Li(2014)] Ke Li, “Second-order asymptotics for quantum hypothesis testing,” Ann. Stat. 42, 171–189 (2014).
  * [Tomamichel and Tan(2015)] Marco Tomamichel and Vincent Y. F. Tan, “Second-order asymptotics for the classical capacity of image-additive quantum channels,” Commun. Math. Phys. 338, 103–137 (2015).
  * [Datta  _et al._(2016)Datta, Tomamichel, and Wilde] Nilanjana Datta, Marco Tomamichel, and Mark M. Wilde, “On the second-order asymptotics for entanglement-assisted communication,” Quantum Inf. Process. 15, 2569–2591 (2016).
  * [Datta and Leditzky(2015)] Nilanjana Datta and Felix Leditzky, “Second-order asymptotics for source coding, dense coding, and pure-state entanglement conversions,” IEEE Trans. Inf. Theory 61, 582–608 (2015).
  * [Wilde  _et al._(2016)Wilde, Renes, and Guha] Mark M. Wilde, Joseph M. Renes, and Saikat Guha, “Second-order coding rates for pure-loss bosonic channels,” Quantum Inf. Process. 15, 1289–1308 (2016).
  * [Tomamichel  _et al._(2016)Tomamichel, Berta, and Renes] Marco Tomamichel, Mario Berta, and Joseph M. Renes, “Quantum coding with finite resources,” Nat. Commun. 7, 11419 (2016).
  * [Wilde  _et al._(2017)Wilde, Tomamichel, Lloyd, and Berta] Mark M. Wilde, Marco Tomamichel, Seth Lloyd, and Mario Berta, “Gaussian hypothesis testing and quantum illumination,” Phys. Rev. Lett. 119, 120501 (2017).
  * [Goold  _et al._(2016)Goold, Huber, Riera, del Rio, and Skrzypczyk] John Goold, Marcus Huber, Arnau Riera, Lídia del Rio, and Paul Skrzypczyk, “The role of quantum information in thermodynamics – a topical review,” J. Phys. A 49, 143001 (2016).
  * [Åberg(2014)] Johan Åberg, “Catalytic coherence,” Phys. Rev. Lett. 113, 150402 (2014).
  * [Lostaglio  _et al._(2015b)Lostaglio, Jennings, and Rudolph] Matteo Lostaglio, David Jennings, and Terry Rudolph, “Description of quantum coherence in thermodynamic processes requires constraints beyond free energy,” Nat. Commun. 6, 6383 (2015b).
  * [Uzdin  _et al._(2015)Uzdin, Levy, and Kosloff] Raam Uzdin, Amikam Levy, and Ronnie Kosloff, “Equivalence of quantum heat machines, and quantum-thermodynamic signatures,” Phys. Rev. X 5, 031044 (2015).
  * [Korzekwa  _et al._(2016)Korzekwa, Lostaglio, Oppenheim, and Jennings] Kamil Korzekwa, Matteo Lostaglio, Jonathan Oppenheim, and David Jennings, “The extraction of work from quantum coherence,” New J. Phys. 18, 023045 (2016).
  * [Alicki and Fannes(2013)] Robert Alicki and Mark Fannes, “Entanglement boost for extractable work from ensembles of quantum batteries,” Phys. Rev. E 87, 042123 (2013).
  * [Perarnau-Llobet  _et al._(2015)Perarnau-Llobet, Hovhannisyan, Huber, Skrzypczyk, Brunner, and Acín] Martí Perarnau-Llobet, Karen V Hovhannisyan, Marcus Huber, Paul Skrzypczyk, Nicolas Brunner, and Antonio Acín, “Extractable work from correlations,” Phys. Rev. X 5, 041011 (2015).
  * [Brask  _et al._(2015)Brask, Haack, Brunner, and Huber] Jonatan Bohr Brask, Géraldine Haack, Nicolas Brunner, and Marcus Huber, “Autonomous quantum thermal machine for generating steady-state entanglement,” New J. Phys. 17, 113029 (2015).
  * [Umegaki(1962)] H. Umegaki, “Conditional expectation in an operator algebra,” Kodai Math. Sem. Rep. 14, 59–85 (1962).
  * [Uhlmann(1985)] A. Uhlmann, “The transition probability for states of star-algebras,” Ann. Phys. (N. Y). 497, 524–532 (1985).
  * [Ito  _et al._(2015)Ito, Kumagai, and Hayashi] Kosuke Ito, Wataru Kumagai, and Masahito Hayashi, “Asymptotic compatibility between local-operations-and-classical-communication conversion and recovery,” Phys. Rev. A 92, 052308 (2015).
  * [Ng  _et al._(2017)Ng, Woods, and Wehner] Nelly Huei Ying Ng, Mischa Prebin Woods, and Stephanie Wehner, “Surpassing the Carnot efficiency by extracting imperfect work,” New J. Phys. 19, 113005 (2017).
  * [Brandão  _et al._(2015)Brandão, Horodecki, Ng, Oppenheim, and Wehner] F. G. S. L. Brandão, M. Horodecki, N. H. Y. Ng, J. Oppenheim, and S. Wehner, “The second laws of quantum thermodynamics,” Proc. Natl. Acad. Sci. U.S.A. 112, 3275 (2015).
  * [Korzekwa(2016)] Kamil Korzekwa,  _Coherence, thermodynamics and uncertainty relations_ , Ph.D. thesis, Imperial College London (2016).
  * [Bhatia(2013)] Rajendra Bhatia,  _Matrix analysis_ (Springer Science & Business Media, 2013).
  * [Ruch  _et al._(1978)Ruch, Schranner, and Seligman] Ernst Ruch, Rudolf Schranner, and Thomas H. Seligman, “The mixing distance,” J. Chem. Phys. 69 (1978).
  * [Renes(2016)] Joseph M Renes, “Relative submajorization and its use in quantum resource theories,” J. Math. Phys. 57, 122202 (2016).
  * [Van Der Meer  _et al._(2017)Van Der Meer, Ng, and Wehner] Remco Van Der Meer, Nelly Huei Ying Ng, and Stephanie Wehner, “Smoothed generalized free energies for thermodynamics,” Phys. Rev. A 96, 062135 (2017).
  * [Horodecki  _et al._(2003)Horodecki, Horodecki, Horodecki, Horodecki, Oppenheim, Sen(De), and Sen] Michał Horodecki, Karol Horodecki, Paweł Horodecki, Ryszard Horodecki, Jonathan Oppenheim, Aditi Sen(De), and Ujjwal Sen, “Local information as a resource in distributed quantum systems,” Phys. Rev. Lett. 90, 100402 (2003).
  * [Vidal  _et al._(2000)Vidal, Jonathan, and Nielsen] Guifré Vidal, Daniel Jonathan, and MA Nielsen, “Approximate transformations and robust manipulation of bipartite pure-state entanglement,” Phys. Rev. A 62, 012304 (2000).
  * [Tomamichel(2015)] Marco Tomamichel,  _Quantum information processing with finite resources: mathematical foundations_ , Vol. 5 (Springer, 2015).
  * [Åberg(2013)] Johan Åberg, “Truly work-like work extraction via a single-shot analysis,” Nat. Commun. 4, 1925 (2013).
  * [Egloff  _et al._(2015)Egloff, Dahlsten, Renner, and Vedral] Dario Egloff, Oscar CO Dahlsten, Renato Renner, and Vlatko Vedral, “A measure of majorization emerging from single-shot statistical mechanics,” New J. Phys. 17, 073001 (2015).
  * [Perry  _et al._(2015)Perry, Ćwikliński, Anders, Horodecki, and Oppenheim] Chris Perry, Piotr Ćwikliński, Janet Anders, Michał Horodecki, and Jonathan Oppenheim, “A sufficient set of experimentally implementable thermal operations,” arXiv:1511.06553 (2015).
  * [Campisi  _et al._(2009)Campisi, Talkner, and Hänggi] Michele Campisi, Peter Talkner, and Peter Hänggi, “Finite bath fluctuation theorem,” Phys. Rev. E 80, 031145 (2009).
  * [Reeb and Wolf(2014)] David Reeb and Michael M Wolf, “An improved Landauer principle with finite-size corrections,” New J. Phys. 16, 103011 (2014).
  * [Richens  _et al._(2018)Richens, Alhambra, and Masanes] Jonathan G Richens, Álvaro M Alhambra, and Lluis Masanes, “Finite-bath corrections to the second law of thermodynamics,” Phys. Rev. E 97, 062132 (2018).
  * [Scharlau and Mueller(2018)] Jakob Scharlau and Markus P Mueller, “Quantum Horn’s lemma, finite heat baths, and the third law of thermodynamics,” Quantum 2, 54 (2018).
  * [Tajima and Hayashi(2017)] Hiroyasu Tajima and Masahito Hayashi, “Finite-size effect on optimal efficiency of heat engines,” Phys. Rev. E 96, 012128 (2017).
  * [Ito and Hayashi(2016)] Kosuke Ito and Masahito Hayashi, “Optimal performance of generalized heat engines with finite-size baths of arbitrary multiple conserved quantities based on non-iid scaling,” arXiv:1612.04047 (2016).
  * [Woods  _et al._(2015)Woods, Ng, and Wehner] Mischa P Woods, Nelly Ng, and Stephanie Wehner, “The maximum efficiency of nano heat engines depends on more than temperature,” arXiv:1506.02322 (2015).
  * [Faist  _et al._(2015)Faist, Oppenheim, and Renner] P. Faist, J. Oppenheim, and R. Renner, “Gibbs-preserving maps outperform thermal operations in the quantum regime,” New J. of Phys. 17, 043003 (2015).
  * [Korzekwa(2017)] Kamil Korzekwa, “Structure of the thermodynamic arrow of time in classical and quantum theories,” Phys. Rev. A 95, 052318 (2017).
  * [Hayashi(2006)] Masahito Hayashi,  _Quantum Information — An Introduction_ (Springer, 2006).
  * [Chubb  _et al._(2017)Chubb, Tan, and Tomamichel] C.T. Chubb, V.Y.F. Tan, and M. Tomamichel, “Moderate Deviation Analysis for Classical Communication over Quantum Channels,” Commun. Math. Phys. 355 (2017).
  * [Cheng and Hsieh(2017)] Hao-Chung Cheng and Min-Hsiu Hsieh, “Moderate Deviation Analysis for Classical-Quantum Channels and Quantum Hypothesis Testing,”  (2017), arXiv:1701.03195 .

##  Appendix A Work extraction with Carnot efficiency

Here we consider a thermodynamic process involving a heat engine with a finite
working body. Suppose the working body starts at the cold temperature,
$T_{c}$. Then, the heat flowing from the hot bath will steadily increase the
temperature of the working body, from $T_{\mathrm{c}}$ to
$T_{\mathrm{c^{\prime}}}$. We assume that thermalisation happens on a much
shorter time-scale than the heat flow, so that the working body is at all
times in thermal equilibrium. We are now interested in the amount of work that
can be extracted if the engine at each time step operates with the maximal
allowed Carnot efficiency (with respect to the background hot temperature and
the instantaneous temperature of the working body).

By definition, the efficiency of an infinitesimal process involving the flow
of heat $dQ_{\mathrm{in}}$ from the hot bath to the engine,
$dQ_{\mathrm{out}}$ of which flows out to the cold bath, while the remaining
energy is converted into work $dW$, is given by

$\eta:=\frac{\mathrm{d}W}{\mathrm{d}Q_{\mathrm{in}}}=\frac{\mathrm{d}W}{\mathrm{d}W+\mathrm{d}Q_{\mathrm{out}}},$
(201)

where the equality comes from the conservation of energy. Hence, the work
extracted during the infinitesimal flow of heat $dQ_{\mathrm{out}}$ into the
cold bath at temperature $T_{\mathrm{x}}$ that heats it up by
$dT_{\mathrm{x}}$,

$\mathrm{d}Q_{\mathrm{out}}=\frac{\mathrm{d}\langle
E\rangle_{\bm{\gamma}_{\mathrm{x}}}}{\mathrm{d}T_{\mathrm{x}}}\,\mathrm{d}T_{\mathrm{x}},$
(202)

is given by

$\mathrm{d}W=\frac{\eta}{1-\eta}\,\mathrm{d}Q_{\mathrm{out}}.$ (203)

The Carnot efficiency of an engine acting between the hot bath at fixed
temperature $T_{\mathrm{h}}$ and the working body at varying temperature
$T_{\mathrm{x}}$ is given by

$\eta_{\mathrm{c}}(T_{\mathrm{x}})=1-\frac{T_{\mathrm{x}}}{T_{\mathrm{h}}}.$
(204)

Thus, the work produced by an engine working at maximum allowed efficiency is
given by

$\displaystyle\mathrm{d}W=\left(\frac{T_{\mathrm{h}}}{T_{\mathrm{x}}}-1\right)\frac{\mathrm{d}\langle
E\rangle_{\bm{\gamma}_{\mathrm{x}}}}{\mathrm{d}T_{\mathrm{x}}}\,\mathrm{d}T_{\mathrm{x}}.$
(205)

We now want to calculate the total work $W$ extracted by such an optimal
engine while the temperature of the working body changes from $T_{\mathrm{c}}$
to $T_{\mathrm{c^{\prime}}}$,

$\displaystyle W=\int_{T_{\mathrm{c}}}^{T_{\mathrm{c^{\prime}}}}\mathrm{d}W.$
(206)

By simply integrating by parts we get

$\displaystyle\\!\\!W\\!=\\!\left(\frac{T_{\mathrm{h}}}{T_{\mathrm{x}}}-1\right)\langle
E\rangle_{\bm{\gamma}_{\mathrm{x}}}\Biggr{|}_{T_{\mathrm{x}}=T_{\mathrm{c}}}^{T_{\mathrm{x}}=T_{\mathrm{c^{\prime}}}}\\!+T_{\mathrm{h}}\int_{T_{\mathrm{c}}}^{T_{\mathrm{c^{\prime}}}}\frac{\langle
E\rangle_{\bm{\gamma}_{\mathrm{x}}}}{T_{\mathrm{x}}^{2}}\,\mathrm{d}T_{\mathrm{x}}.\\!$
(207)

The second term can be calculated by switching from temperature
$T_{\mathrm{x}}$ to inverse temperature $\beta_{\mathrm{x}}$ and recalling
that the average energy is a negative derivative of $\log{\cal
Z}_{\mathrm{x}}$ over $\beta_{\mathrm{x}}$:

$\displaystyle
T_{\mathrm{h}}\int_{T_{\mathrm{c}}}^{T_{\mathrm{c^{\prime}}}}\frac{\langle
E\rangle_{\bm{\gamma}_{\mathrm{x}}}}{T_{\mathrm{x}}^{2}}\,\mathrm{d}T_{\mathrm{x}}=$
$\displaystyle\frac{1}{\beta_{\mathrm{h}}}\int_{\beta_{\mathrm{c}}}^{\beta_{\mathrm{c^{\prime}}}}\frac{\mathrm{d}\log{\cal
Z}_{\mathrm{x}}}{\mathrm{d}\beta_{\mathrm{x}}}\,\mathrm{d}\beta_{\mathrm{x}}$
$\displaystyle=$ $\displaystyle\frac{1}{\beta_{\mathrm{h}}}\left(\log{\cal
Z}_{\mathrm{c^{\prime}}}-\log{\cal Z}_{\mathrm{c}}\right).$ (208)

By noting that the entropy of a thermal equilibrium state is given by

$\displaystyle H(\bm{\gamma}_{\mathrm{x}})=\beta_{\mathrm{x}}\langle
E\rangle_{\bm{\gamma}_{\mathrm{x}}}+\log{\cal Z}_{\mathrm{x}},$ (209)

we thus have

$\displaystyle W=\left(\langle
E\rangle_{\bm{\gamma}_{\mathrm{c}}}-\frac{H(\bm{\gamma}_{\mathrm{c}})}{\beta_{\mathrm{h}}}\right)-\left(\langle
E\rangle_{\bm{\gamma}_{\mathrm{c^{\prime}}}}-\frac{H(\bm{\gamma}_{\mathrm{c^{\prime}}})}{\beta_{\mathrm{h}}}\right).$
(210)

Finally, comparing the above with Eq. (25) we arrive at

$\displaystyle
W=k_{B}T_{\mathrm{h}}\bigl{(}D(\bm{\gamma}_{\mathrm{c}}||\bm{\gamma}_{\mathrm{h}})-D(\bm{\gamma}_{\mathrm{c^{\prime}}}||\bm{\gamma}_{\mathrm{h}})\bigr{)},$
(211)

which is equal to the change of free energy of the finite bath.

##  Appendix B Proof of Lemma 11

###  B.1 Preliminaries

In Ref. [Vidal  _et al._(2000)Vidal, Jonathan, and Nielsen] an explicit
construction the solution $\tilde{\bm{p}}^{\star}$ to the following
maximisation problem,

$\tilde{\bm{p}}^{\star}=\operatorname*{arg\,max}_{\tilde{\bm{p}}:~{}\tilde{\bm{p}}\succ\bm{q}}F(\bm{p},\tilde{\bm{p}}),$
(212)

was given. We will now describe the construction of this optimal distribution,
as it is crucial for our proof, the second part which will very closely follow
the reasoning presented in Ref. [Vidal  _et al._(2000)Vidal, Jonathan, and
Nielsen]. As explained in Section 3.3, without loss of generality we will
assume that all the distributions are non-increasingly ordered.

First, for any distribution $\bm{a}$ define

$E^{\bm{a}}_{k}:=\sum_{i=k}^{d}a_{i},\quad\Delta_{k_{1}}^{k_{2}}(\bm{a}):=\sum_{i=k_{1}}^{k_{2}-1}a_{i}=E^{\bm{a}}_{k_{1}}-E^{\bm{a}}_{k_{2}}.$
(213)

Note that $\bm{p}\succ\bm{q}$ is equivalent to $E^{\bm{p}}_{k}\leq
E^{\bm{q}}_{k}$ for all $k$. Now, for a given $\bm{p}$ and $\bm{q}$ the
construction of $\tilde{\bm{p}}^{\star}$ is given by the following iterative
procedure. Set $l_{0}=d+1$ and define

$l_{j}:=\operatorname*{arg\,min}_{k<l_{j-1}}\frac{\Delta_{k}^{l_{j-1}}(\bm{q})}{\Delta_{k}^{l_{j-1}}(\bm{p})},\quad
r_{j}:=\frac{\Delta_{l_{j}}^{l_{j-1}}(\bm{q})}{\Delta_{l_{j}}^{l_{j-1}}(\bm{p})}.$
(214)

If the minimisation defining $l_{j}$ does not have a unique solution then
$l_{j}$ is chosen to be the smallest possible. We will also denote by $N$ an
index for which $l_{N}=1$. The $i$-th entry of the optimal vector for
$i\in\\{l_{j},\dots,l_{j-1}-1\\}$ is then given by

$\tilde{p}^{\star}_{i}=r_{j}p_{i}.$ (215)

It is straightforward to verify that $\tilde{\bm{p}}^{\star}$ is normalised,
and $\tilde{\bm{p}}^{\star}\succ\bm{q}$ as the construction guarantees that
$E^{\bm{p}}_{k}\leq E^{\bm{q}}_{k}$ for all $k$. Moreover, the optimal
fidelity between $\bm{p}$ and a distribution that majorises $\bm{q}$ is given
by

$\displaystyle\sqrt{F(\bm{p},\tilde{\bm{p}}^{\star})}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{d}\sqrt{p_{i}\tilde{p}_{i}^{\star}}=\sum_{j=1}^{N}\sum_{i=l_{j}}^{l_{j-1}-1}\sqrt{p_{i}\tilde{p}^{\star}_{i}}$
(216) $\displaystyle=$
$\displaystyle\sum_{j=1}^{N}\left(\frac{\Delta_{l_{j}}^{l_{j-1}}(\bm{q})}{\Delta_{l_{j}}^{l_{j-1}}(\bm{p})}\right)^{\frac{1}{2}}\sum_{i=l_{j}}^{l_{j-1}-1}p_{i}$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{N}\left(\Delta_{l_{j}}^{l_{j-1}}(\bm{q})\Delta_{l_{j}}^{l_{j-1}}(\bm{p})\right)^{\frac{1}{2}}.$

The crucial observation in proving the optimality of the above, which we will
also need in our proof, is that for all $j$ we have

$r_{j}<r_{j+1}.$ (217)

This follows from the definition of $l_{j}$, $r_{j}$ and the fact that for
$a,b,c,d>0$ one has (see Ref. [Vidal  _et al._(2000)Vidal, Jonathan, and
Nielsen] for details)

$\frac{a}{b}\leq\frac{a+c}{b+d}\quad\Longleftrightarrow\quad\frac{a}{b}<\frac{c}{d}.$
(218)

###  B.2 Proper proof

###### Proof.

We will prove the equality in Eq. (87) by showing that the following two
inequalities hold

$\displaystyle\max_{\tilde{\bm{p}}:~{}\tilde{\bm{p}}\succ\bm{q}}F(\bm{p},\tilde{\bm{p}})$
$\displaystyle\leq$
$\displaystyle\max_{\tilde{\bm{q}}:~{}\bm{p}\succ\tilde{\bm{q}}}F(\bm{q},\tilde{\bm{q}}),$
(219a)
$\displaystyle\max_{\tilde{\bm{p}}:~{}\tilde{\bm{p}}\succ\bm{q}}F(\bm{p},\tilde{\bm{p}})$
$\displaystyle\geq$
$\displaystyle\max_{\tilde{\bm{q}}:~{}\bm{p}\succ\tilde{\bm{q}}}F(\bm{q},\tilde{\bm{q}}).$
(219b)

We start with the easier part, Eq. (219a). It is enough to show that the
inequality holds for any $\tilde{\bm{p}}$ within the constraints. Let us then
take any $\tilde{\bm{p}}$ such that it majorises $\bm{q}$. Due to Theorem 3
this is equivalent to the existence of a bistochastic matrix $B_{0}$ such that
$B_{0}\tilde{\bm{p}}=\bm{q}$. This implies that

$\max_{\tilde{\bm{q}}:~{}\bm{p}\succ\tilde{\bm{q}}}F(\bm{q},\tilde{\bm{q}})=\max_{B}F(\bm{q},B\bm{p}),$
(220)

where the maximisation on the right hand side is over all bistochastic
matrices $B$. We now observe that

$\displaystyle\max_{B}F(\bm{q},B\bm{p})$
$\displaystyle=\max_{B}F(B_{0}\tilde{\bm{p}},B\bm{p})$ (221a)
$\displaystyle\geq F(B_{0}\tilde{\bm{p}},B_{0}\bm{p})$ (221b)
$\displaystyle\geq F(\tilde{\bm{p}},\bm{p}),$ (221c)

where in the last step we used the fact that fidelity obeys data processing
inequality. We thus have

$\max_{\tilde{\bm{q}}:~{}\bm{p}\succ\tilde{\bm{q}}}F(\bm{q},\tilde{\bm{q}})\geq
F(\tilde{\bm{p}},\bm{p}),$ (222)

for any $\tilde{\bm{p}}$ majorising $\bm{q}$, and so Eq. (219a) holds.

We now proceed to proving Eq. (219b). It is again enough to show that the
inequality holds for any $\tilde{\bm{q}}$ within the constraints. Let us then
take any $\tilde{\bm{q}}$ such that it is majorised by $\bm{p}$. We now have

$\displaystyle\sqrt{F(\bm{q},\tilde{\bm{q}})}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{d}\sqrt{q_{i}\tilde{q}_{i}}=\sum_{j=1}^{N}\sum_{i=l_{j}}^{l_{j-1}-1}\sqrt{q_{i}\tilde{q}_{i}}$
(223) $\displaystyle\leq$
$\displaystyle\sum_{j=1}^{N}\left(\sum_{i=l_{j}}^{l_{j-1}-1}q_{i}\right)^{\frac{1}{2}}\left(\sum_{i=l_{j}}^{l_{j-1}-1}\tilde{q}_{i}\right)^{\frac{1}{2}}$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{N}\left(\Delta_{l_{j}}^{l_{j-1}}(\bm{q})\Delta_{l_{j}}^{l_{j-1}}(\tilde{\bm{q}})\right)^{\frac{1}{2}},$

where $l_{j}$ and $\Delta_{k_{1}}^{k_{2}}$ are defined as in Eqs. (213)-(214).
We now introduce

$x_{j}:=E_{l_{j}}^{\tilde{\bm{q}}}-E_{l_{j}}^{\bm{p}}\geq 0,$ (224)

where the inequality holds for every $j$ because $\bm{p}\succ\tilde{\bm{q}}$.
Observing that

$\Delta_{l_{j}}^{l_{j-1}}(\tilde{\bm{q}})=\Delta_{l_{j}}^{l_{j-1}}(\bm{p})+x_{j}-x_{j-1}\geq
0$ (225)

we arrive at $\sqrt{F(\bm{q},\tilde{\bm{q}})}\leq f(\bm{x})$ with

$\\!\\!f(\bm{x}):=\sum_{j=1}^{N}\left(\Delta_{l_{j}}^{l_{j-1}}(\bm{q})\left(\Delta_{l_{j}}^{l_{j-1}}(\bm{p})+x_{j}-x_{j-1}\right)\right)^{\frac{1}{2}}\\!\\!\\!\\!.\\!\\!$
(226)

We will now show that $f(\bm{x})$ achieves its maximum within the positive
orthant $x_{j}\geq 0$ when $\bm{x}=\bm{0}$, which will finish the proof. This
is because then

$F(\bm{q},\tilde{\bm{q}})\leq
F(\bm{p},\tilde{\bm{p}}^{\star})=\max_{\tilde{\bm{p}}:~{}\tilde{\bm{p}}\succ\bm{q}}F(\bm{p},\tilde{\bm{p}})$
(227)

for any $\tilde{\bm{q}}$ majorised by $\bm{p}$, which implies Eq. (219b).
First, by direct calculation one can find a matrix $M$ of second derivatives
of $f(\bm{x})$, i.e., $M_{ij}=\frac{\partial^{2}f(\bm{x})}{\partial
x_{i}\partial x_{j}}$. Then, using Gershgorin circle theorem, one can verify
that $M$ is negative definite in the allowed region of $\bm{x}$, so that there
are no local extrema and the maximal value must be obtained at the boundary.
Finally,

$\frac{\partial f(\bm{x})}{\partial
x_{j}}\Bigg{|}_{x_{j}=0}=\frac{1}{2}\left(\sqrt{r_{j}}-\sqrt{r_{j+1}}\right)<0,$
(228)

which means that the maximal value is obtained for $\bm{x}=[0,\dots,0]$, which
finishes the proof. ∎

##  Appendix C Efficient algorithm for calculating interconversion
infidelities

The construction given in Appendix B gives a natural algorithm for calculating
$\max_{\bm{\tilde{p}}:\bm{\tilde{p}}\succ\bm{q}}F(\bm{p},\bm{\tilde{p}})$. The
run-time of this algorithm is $\mathcal{O}(d^{2})$, where $d$ is the size of
the input distributions. We now want to argue that this algorithm can be
adapted for states described by $\bm{p}^{\otimes n}$, such that the optimal
interconversion rates can be numerically calculated in a time which is
efficient in $n$, as is done in Figures 4 and 10.

The key property we will leverage is that whilst distributions such as
$\bm{p}^{\otimes n}$ have an exponential number of entries, they only possess
a polynomial number of _distinct_ entries (in this case
$\mathcal{O}(n^{d-1})$). As majorisation is invariant under permutations, it
is only the distinct entries (and their degeneracies) that are relevant to our
calculation.

Consider taking as input two distributions $\bm{P}$ and $\bm{Q}$ which possess
$D=\exp(\mathcal{O}(n))$ total entries, but each only $\mathrm{poly}(n)$
distinct entries. This means there exists indices
$1=i_{1}<i_{2}<\dots<i_{t}<i_{t+1}=D+1$, where $t=\mathrm{poly}(n)$, such that
$P^{\downarrow}_{i}$ and $Q^{\downarrow}_{i}$ are constant on each interval
$i\in\\{i_{s},\dots,i_{s+1}-1\\}$ for $s\in\\{1,\dots,t\\}$.

The main step in the algorithm, and the bottleneck giving an exponential run-
time, is calculating the pivot indices $\\{l_{j}\\}_{j}$ used to construct
$\bm{\tilde{P}}$. Specifically these take the form

$\displaystyle
l_{j}:=\operatorname*{arg\,max}_{k<l_{j-1}}\frac{\sum_{i=k}^{l_{j-1}-1}Q^{\downarrow}_{i}}{\sum_{i=k}^{l_{j-1}-1}P^{\downarrow}_{i}}.$
(229)

Using the constancy of $P^{\downarrow}_{i}$ and $Q^{\downarrow}_{i}$ on each
of the intervals we can see that, for a fixed $s$, the function being
optimised takes the form

$\displaystyle\frac{\sum_{i=k}^{l_{j-1}-1}Q^{\downarrow}_{i}}{\sum_{i=k}^{l_{j-1}-1}P^{\downarrow}_{i}}=\frac{\alpha
k+\beta}{\gamma k+\delta},$ (230)

for any $k\in\\{i_{s},\dots,i_{s+1}-1\\}$. As this function is monotonic as a
function of $i$, we conclude that the indices $l_{j}$ must lie on the edges of
these intervals, i.e. $\\{l_{j}\\}_{j}\subseteq\\{i_{s}\\}_{s}$. This means
that we can restrict our attention only to the these ‘edge indices’ without
loss of generality, lowering the algorithms run-time down from
$\mathcal{O}(D^{2})$ to $\mathcal{O}(t^{2})$.

Using the above argument, we now have an efficient algorithm for computing
$\epsilon^{*}_{0}(n,R;\bm{p},\bm{q})$. Utilising the idea of embedding, this
also allows us to calculate the thermal variant of this,
$\epsilon^{*}_{\beta}(n,R;\bm{p},\bm{q})$. Finally, by sweeping over $R$, we
can use this to calculate $R^{*}_{\beta}(n,R;\bm{p},\bm{q})$. Examples of this
are shown in Figures 4 and 10.

##  Appendix D Approximate thermomajorisation based on total variation
distance

Here we show how to modify the proofs of Lemmas 12, 13 and 14, so that they
hold for approximate thermomajorisation defined with total variation distance
$\delta(\bm{p},\bm{q})=\frac{1}{2}||\bm{p}-\bm{q}||$. In all three proofs one
needs to replace the statement “embedding is fidelity-preserving” with
“embedding preserves the total variation distance”, and “fidelity is non-
decreasing under stochastic maps” with “total variation distance is non-
increasing under stochastic maps”. This is already enough to prove modified
Lemma 13. In Lemma 14 we additionally need to replace the expression
$\epsilon_{0}=(3-2\sqrt{2})/6$ with $\epsilon_{0}=1/6$. Finally, we replace
the second part of Lemma 12 with the following reasoning.

Assume that $\bm{p}\succ_{\epsilon}\bm{q}$. This means that there exists a
$\bm{\tilde{q}}$ such that $\bm{p}\succ\bm{\tilde{q}}$ and
$\delta(\bm{q},\bm{\tilde{q}})\leq\epsilon$. Define $M$ to be the largest
integer such that

$\displaystyle\sum_{i=1}^{M}p_{i}^{\downarrow}\leq 1-\epsilon,$ (231)

and then define $\bm{\tilde{p}}$ by cutting off the tail of $\bm{p}$, and
placing all of its mass into the largest element

$\displaystyle\tilde{p}_{i}:=\begin{dcases}p_{i}^{\downarrow}+\epsilon&\text{for
}i=1,\\\ p_{i}^{\downarrow}&\text{for }1<i<M,\\\
p_{i}^{\downarrow}+1-\epsilon-\sum_{i=1}^{M}p_{i}^{\downarrow}&\text{for
}i=M,\\\ 0&\text{for }i>M.\end{dcases}$ (232)

By definition of $M$ we can see that $\delta(\bm{p},\bm{\tilde{p}})=\epsilon$.
We now need to show that $\bm{\tilde{p}}\succ\bm{q}$. For $k\geq M$ we have

$\displaystyle\sum_{i=1}^{k}{\tilde{p}}_{i}^{\downarrow}=1\geq\sum_{i=1}^{k}q_{i}^{\downarrow}.$
(233)

For $k<M$, we can use $\bm{p}\succ\bm{\tilde{q}}$ and
$\delta(\bm{q},\bm{\tilde{q}})\leq\epsilon$ to give

$\displaystyle\sum_{i=1}^{k}{\tilde{p}}_{i}^{\downarrow}=\sum_{i=1}^{k}p_{i}^{\downarrow}+\epsilon\geq\sum_{i=1}^{k}\tilde{q}_{i}^{\downarrow}+\epsilon\geq\sum_{i=1}^{k}q_{i}^{\downarrow}.$
(234)

Thus
$\bm{p}\prescript{}{\epsilon}{\succ}~{}\bm{q}\impliedby\bm{p}\succ_{\epsilon}\bm{q}$.

##  Appendix E Proof of Lemma 15

###### Proof.

Consider a discrete random variable $L=-\log a$, such that $\langle
L\rangle_{\bm{a}}=H(\bm{a})$ and $\operatorname{Var}_{\bm{a}}(L)=V(\bm{a})$,
and therefore

$\displaystyle\log k_{n}(x)=n\langle
L\rangle_{\bm{a}}+x\sqrt{n\operatorname{Var}_{\bm{a}}(L)}.$ (235)

If we let $\\{L_{j}\\}_{1\leq j\leq n}$ be i.i.d. copies of $L$, then we can
write the tail bound of $\bm{a}^{\otimes n}$ in terms of tail bounds on the
average of these variables as

$\displaystyle\sum_{i}\left\\{\left(\bm{a}^{\otimes
n}\right)_{i}\middle|\left(\bm{a}^{\otimes n}\right)_{i}\geq
1/k_{n}(x)\right\\}$ (236)
$\displaystyle\quad\quad=\sum_{i_{1},\dots,i_{n}}\left\\{\prod_{j=1}^{n}a_{i_{j}}\middle|\prod_{j=1}^{n}a_{i_{j}}\geq
1/k_{n}(x)\right\\}$ (237)
$\displaystyle\quad\quad=\sum_{i_{1},\dots,i_{n}}\left\\{\prod_{j=1}^{n}a_{i_{j}}\middle|-\sum_{j=1}^{n}\log
a_{i_{j}}\geq\log k_{n}(x)\right\\}$ (238)
$\displaystyle\quad\quad=\Pr\left[\sum_{j=1}^{n}L_{j}\leq n\langle
L\rangle_{\bm{a}}+x\sqrt{n\operatorname{Var}_{\bm{a}}(L)}\right].$ (239)

By applying the standard central limit theorem

$\displaystyle\lim\limits_{n\to\infty}\\!\Pr\left[\sum_{j=1}^{n}\left(\frac{L_{j}-\langle
L\rangle_{\bm{a}}}{\sqrt{\operatorname{Var}_{\bm{a}}(L)}}\right)\leq
x\sqrt{n}\right]=\Phi\left(x\right)\\!,$ (240)

we get the desired bound. ∎