corresponding to the progress measure

$\displaystyle\mathop{\bf E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\
\sigma,\tau\leftarrow S_{N}\end{subarray}}\left\lVert
E^{R^{\sigma,\tau},x}_{D}\ket{\phi^{\sigma,\tau}}\right\rVert^{2},$

where $R^{\sigma,\tau}$ is the twirled relation defined in (6.1). Note that
$r_{\max}=\max\\{\max_{x\in[N]}\lvert
R^{\sigma,\tau}_{x}\rvert,\max_{y\in[N]}\lvert(R^{\sigma,\tau})^{\mathrm{inv}}_{y}\rvert\\}$.

The main result of this section is the following. It shows that the randomized
test for the twirled relation rarely succeeds for algorithms making not too
many queries, up to an error term that captures the “sparsity” of the database
and that will be bounded in Section 6.3.

######  Proposition 6.6.

Let $\mathcal{A}$ be a unitary query algorithm on registers $AXY$, where $X$
and $Y$ are $N$-dimensional registers, that gets query access to two oracles
that each act on $XY$. Suppose that $\mathcal{A}$ makes in total $q$ queries
to its oracles. For every $\sigma,\tau\in S_{N}$, let
$\ket{\phi^{\sigma,\tau}}_{AXYD}$ be the joint state of algorithm and oracle
defined by running $\mathsf{Init}^{\mathsf{SPO}}_{D}$ and then
$\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$. Let $\mathcal{B}$ be the
query algorithm on registers $BXY$ as in Lemma 4.9, with $B=AZ$ and $Z$
another $N$-dimensional register. Then,

$\displaystyle\mathop{\bf E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\
\sigma,\tau\leftarrow S_{N}\end{subarray}}\left\lVert
E^{R^{\sigma,\tau},x}_{D}\ket{\phi^{\sigma,\tau}}\right\rVert^{2}$
$\displaystyle\leq
384\frac{q^{2}r_{\max}\big{\lparen}\ln(N)+2\big{\rparen}}{N^{2}}+4qr_{\max}\sum_{j=1}^{2q}\mathop{\bf
E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\ \sigma,\tau\leftarrow
S_{N}\end{subarray}}\frac{\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{\sigma,\tau,(j)}}\right\rVert^{2}}{x}$

where $\ket{\phi^{\sigma,\tau,(j)}}_{BXYD}$ is the state given by running
$\mathsf{Init}^{\mathsf{SPO}}_{D}$ and then
$\mathcal{B}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$ until right before the $j$-th
query.

###### Proof.

By Lemma 4.9 for every $\sigma,\tau\in S_{N}$ it holds that

$\displaystyle\mathcal{B}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}=\mathcal{B}_{\sigma,\tau}^{\mathsf{SPO}_{D}}.$

with $\mathcal{B}_{\sigma,\tau}$ defined in the statement of the lemma.
Moreover, the joint state of the algorithm and oracle defined by running
$\mathsf{Init}^{\mathsf{SPO}}_{D}$ and then either of these two algorithms is
given by
$\ket{\chi^{\sigma,\tau}}_{BXYD}=\ket{\phi^{\sigma,\tau}}_{AXYD}\otimes\ket{0}_{Z}$.
Thus we can apply Proposition 6.5 with the relation $R^{\sigma,\tau}$ and the
algorithm $\mathcal{B}_{\sigma,\tau}$, which makes $2q$ queries to the
untwirled standard oracle, to obtain

$\displaystyle\left\lVert
E^{R^{\sigma,\tau},x}_{D}\ket{\phi^{\sigma,\tau}}\right\rVert^{2}=\left\lVert
E^{R^{\sigma,\tau},x}_{D}\ket{\chi^{\sigma,\tau}}\right\rVert^{2}\leq
4q\sum_{j=1}^{2q}\left\lparen\frac{\lvert R^{\sigma,\tau}_{x}\rvert}{x}\
\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\chi^{\sigma,\tau,(j)}}\right\rVert^{2}+16\zeta^{\sigma,\tau,(j)}_{x}\right\rparen,$
(6.9)

where $\ket{\chi^{\sigma,\tau,(j)}}_{BXYD}$ denotes the state right before the
$j$-th query of $\mathcal{B}_{\sigma,\tau}^{\mathsf{SPO}_{D}}$ and

$\displaystyle\zeta^{\sigma,\tau,(j)}_{x}=\begin{cases}\zeta_{\ket{\chi^{\sigma,\tau,(j)}},x}&\text{if
the $j$-th query of\leavevmode\nobreak\ $\mathcal{B}_{\sigma,\tau}$ is a
forward query},\\\
\zeta^{\mathrm{inv}}_{\ket{\chi^{\sigma,\tau,(j)}},x}&\text{if the $j$-th
query of\leavevmode\nobreak\ $\mathcal{B}_{\sigma,\tau}$ is an inverse
query};\end{cases}$

the right-hand side quantities are defined in Lemmas 6.3 and 6.4. In view of
the relation between $\mathcal{B}_{\sigma,\tau}$ and $\mathcal{B}$ in Lemma
4.9, we can express the pre-query states of the former in terms of the pre-
query states of the latter: we have
$\ket{\chi^{\sigma,\tau,(j)}}\in\left\\{V_{X}^{\sigma}\ket{\phi^{\sigma,\tau,(j)}},V_{X}^{\sigma}V_{Y}^{\tau}\ket{\phi^{\sigma,\tau,(j)}}\right\\}$
if the $j$-th query of $\mathcal{B}_{\sigma,\tau}$ is a forward query, and
otherwise
$\ket{\chi^{\sigma,\tau,(j)}}\in\left\\{V_{X}^{\tau}\ket{\phi^{\sigma,\tau,(j)}},V_{X}^{\tau}V_{Y}^{\sigma}\ket{\phi^{\sigma,\tau,(j)}}\right\\}$.
Using the unitary invariance of the norm, we see that

$\displaystyle\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\chi^{\sigma,\tau,(j)}}\right\rVert=\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{\sigma,\tau,(j)}}\right\rVert$
(6.10)

and

$\displaystyle\zeta^{\sigma,\tau,(j)}_{x}=\begin{cases}\zeta_{V_{X}^{\sigma}\,\ket{\phi^{\sigma,\tau,(j)}},x}&\text{if
the $j$-th query of\leavevmode\nobreak\ $\mathcal{B}$ is a forward query},\\\
\zeta^{\mathrm{inv}}_{V_{X}^{\tau}\,\ket{\phi^{\sigma,\tau,(j)}},x}&\text{if
the $j$-th query of\leavevmode\nobreak\ $\mathcal{B}$ is an inverse
query}.\end{cases}$

To prove the proposition, we need to upper bound $\mathop{\bf
E\/}_{x,\sigma,\tau}\zeta^{\sigma,\tau,(j)}_{\ket{\chi^{\sigma,\tau,(j)}},x}$.
We distinguish the two cases:

  1. (i)

If the $j$-th query is a forward query, we have

$\displaystyle\zeta^{\sigma,\tau,(j)}_{x}=\zeta_{V_{X}^{\sigma}\,\ket{\phi^{\sigma,\tau,(j)}},x}=\frac{\lvert
R^{\sigma,\tau}_{x}\rvert}{x}\,\lVert\ket{\phi^{\sigma,\tau,(j)}_{\sigma^{-1}(x)}}\rVert^{2}+\frac{\lvert
R^{\sigma,\tau}_{x}\rvert}{x^{2}N}+\frac{1}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R^{\sigma,\tau}_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi^{\sigma,\tau,(j)}_{\sigma^{-1}(z)}}\Big{\rVert}^{2},$

where
$\ket{\phi^{\sigma,\tau,(j)}_{\xi}}_{BYD}:=\bra{\xi}_{X}\ket{\phi^{\sigma,\tau,(j)}}_{BXYD}$
(as in Lemma 6.3). We will now upper bound the average of the above term by
term, beginning with the first term. Now,
$p^{(j)}_{\xi}:=\lVert\ket{\phi^{\sigma,\tau,(j)}_{\xi}}\rVert^{2}$ is a
function of the reduced state of an algorithm that makes queries to the
twirled standard oracle (the part of $\mathcal{B}$ right up to the $j$-th
query), so it follows from Lemma 4.6 that this quantity is independent of
$\sigma,\tau\in S_{N}$. Thus:

$\displaystyle\mathop{\bf E\/}_{x,\sigma,\tau}\frac{\lvert
R^{\sigma,\tau}_{x}\rvert}{x}\,\lVert\ket{\phi^{\sigma,\tau,(j)}_{\sigma^{-1}(x)}}\rVert^{2}$
$\displaystyle\leq\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{r_{\max}}{x}\,p^{(j)}_{\sigma^{-1}(x)}=\mathop{\bf
E\/}_{x}\frac{r_{\max}}{x}\,\mathop{\bf
E\/}_{\sigma,\tau}p^{(j)}_{\sigma^{-1}(x)}=\mathop{\bf
E\/}_{x}\frac{r_{\max}}{x}\,\mathop{\bf E\/}_{x^{\prime}}p^{(j)}_{x^{\prime}}$
$\displaystyle=r_{\max}\left\lparen\frac{1}{N}\sum_{x=1}^{N}\frac{1}{x}\right\rparen\left\lparen\frac{1}{N}\sum_{x^{\prime}=1}^{N}p^{(j)}_{x^{\prime}}\right\rparen\leq
r_{\max}\frac{\ln(N)+1}{N}\frac{1}{N}$
$\displaystyle=\left\lparen\ln(N)+1\right\rparen\frac{r_{\max}}{N^{2}}$ (6.11)

since
$\sum_{x^{\prime}=1}^{N}p^{(j)}_{x^{\prime}}=\lVert\ket{\phi^{\sigma,\tau,(j)}}\rVert^{2}=1$.
The second term can be bounded straightforwardly:

$\displaystyle\mathop{\bf E\/}_{x,\sigma,\tau}\frac{\lvert
R^{\sigma,\tau}_{x}\rvert}{x^{2}N}\leq\frac{r_{\max}}{N}\mathop{\bf
E\/}_{x}\frac{1}{x^{2}}=\frac{r_{\max}}{N^{2}}\sum_{x=1}^{N}\frac{1}{x^{2}}\leq\frac{\pi^{2}}{6}\frac{r_{\max}}{N^{2}}\leq
2\frac{r_{\max}}{N^{2}}.$ (6.12)

We defer bounding the third term to Lemma 6.7 (i), where we get

$\displaystyle\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R^{\sigma,\tau}_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi^{\sigma,\tau,(j)}_{\sigma^{-1}(z)}}\Big{\rVert}^{2}\leq\left\lparen\ln(N)+3\right\rparen\frac{r_{\max}}{N^{2}}.$
(6.13)

Combining Eqs. 6.11, 6.12 and 6.13, we obtain

$\displaystyle\mathop{\bf
E\/}_{x,\sigma,\tau}\zeta^{\sigma,\tau,(j)}_{x}\leq\big{\lparen}2\ln(N)+6\big{\rparen}\frac{r_{\max}}{N^{2}}.$
(6.14)

  2. (ii)

If the $j$-th query is an inverse query, we have

$\displaystyle\zeta^{\sigma,\tau,(j)}_{x}=\zeta^{\mathrm{inv}}_{V_{X}^{\tau}\,\ket{\phi^{\sigma,\tau,(j)}},x}=$
$\displaystyle\frac{\lvert
R^{\sigma,\tau}_{x}\rvert}{x}\,\lVert\ket{\phi^{\sigma,\tau,(j)}_{\tau^{-1}(x)}}\rVert^{2}+\frac{\lvert
R^{\sigma,\tau}_{x}\rvert}{x^{2}N}+\frac{1}{x}\sum_{z\in
R^{\sigma,\tau}_{x}}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)<x}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi^{\sigma,\tau,(j)}_{\tau^{-1}(z)}}\Big{\rVert}^{2}$
$\displaystyle+\frac{1}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)=x}\lvert[x]\cap\pi_{>x}^{-1}(R^{\sigma,\tau}_{x})\rvert\,\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi^{\sigma,\tau,(j)}_{\tau^{-1}(z)}}\Big{\rVert}^{2},$

where
$\ket{\phi^{\sigma,\tau,(j)}_{\xi}}_{BYD}:=\bra{\xi}_{X}\ket{\phi^{\sigma,\tau,(j)}}_{BXYD}$
(as in Lemma 6.4). The average can again be bounded term by term. For the
first two terms we proceed as above and for the last two we use Lemma 6.7 (ii)
and (iii). Altogether we obtain

$\displaystyle\mathop{\bf E\/}_{x,\sigma,\tau}\zeta^{\sigma,\tau,(j)}_{x}$
$\displaystyle\leq\left\lparen\ln(N)+1\right\rparen\frac{r_{\max}}{N^{2}}+2\frac{r_{\max}}{N^{2}}+\left\lparen\ln(N)+1\right\rparen\frac{r_{\max}}{N^{2}}+\left\lparen\ln(N)+1\right\rparen\frac{r_{\max}}{N^{2}}$
(6.15)
$\displaystyle=\big{\lparen}3\ln(N)+5\big{\rparen}\frac{r_{\max}}{N^{2}}.$

From Eqs. 6.14 and 6.15 we see that in both the forward and the inverse case,
we can bound

$\displaystyle\mathop{\bf E\/}_{x,\sigma,\tau}\zeta^{\sigma,\tau,(j)}_{x}\leq
3\big{\lparen}\ln(N)+2\big{\rparen}\frac{r_{\max}}{N^{2}}$

We can now use the above and Eq. 6.10 to further bound Eq. 6.9 and obtain

$\displaystyle\mathop{\bf E\/}_{x,\sigma,\tau}\left\lVert
E^{R^{\sigma,\tau},x}_{D}\ket{\phi^{\sigma,\tau}}\right\rVert^{2}$
$\displaystyle\leq 64q\sum_{j=1}^{2q}\mathop{\bf
E\/}_{x,\sigma,\tau}\zeta^{\sigma,\tau,(j)}_{x}+4q\sum_{j=1}^{2q}\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{\lvert R^{\sigma,\tau}_{x}\rvert}{x}\
\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\chi^{\sigma,\tau,(j)}}\right\rVert^{2}$
$\displaystyle\leq
384q^{2}\big{\lparen}\ln(N)+2\big{\rparen}\frac{r_{\max}}{N^{2}}+4q\sum_{j=1}^{2q}\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{\lvert R^{\sigma,\tau}_{x}\rvert}{x}\
\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{\sigma,\tau,(j)}}\right\rVert^{2}$
$\displaystyle=384\frac{q^{2}r_{\max}\big{\lparen}\ln(N)+2\big{\rparen}}{N^{2}}+4qr_{\max}\sum_{j=1}^{2q}\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{\sigma,\tau,(j)}}\right\rVert^{2}}{x},$

which is the desired result. ∎

######  Lemma 6.7.

In the situation of Proposition 6.6 and with
$\ket{\phi^{\sigma,\tau,(j)}_{\xi}}_{BYD}:=\bra{\xi}_{X}\ket{\phi^{\sigma,\tau,(j)}}_{BXYD}$,
we have:

  1. (i)

$\mathop{\bf E\/}_{x\leftarrow[N],\;\sigma,\tau\leftarrow
S_{N}}\frac{1}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R^{\sigma,\tau}_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi^{\sigma,\tau,(j)}_{\sigma^{-1}(z)}}\Big{\rVert}^{2}\leq\left\lparen\ln(N)+3\right\rparen\frac{r_{\max}}{N^{2}}$.

  2. (ii)

$\mathop{\bf E\/}_{x\leftarrow[N],\;\sigma,\tau\leftarrow
S_{N}}\frac{1}{x}\sum_{z\in
R^{\sigma,\tau}_{x}}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)<x}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi^{\sigma,\tau,(j)}_{\tau^{-1}(z)}}\Big{\rVert}^{2}\leq\left\lparen\ln(N)+1\right\rparen\frac{r_{\max}}{N^{2}}$.

  3. (iii)

$\mathop{\bf E\/}_{x\leftarrow[N],\;\sigma,\tau\leftarrow
S_{N}}\frac{1}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)=x}\lvert[x]\cap\pi_{>x}^{-1}(R^{\sigma,\tau}_{x})\rvert\,\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi^{\sigma,\tau,(j)}_{\tau^{-1}(z)}}\Big{\rVert}^{2}\leq\left\lparen\ln(N)+1\right\rparen\frac{r_{\max}}{N^{2}}$.

###### Proof.

Note that the quantity

$\displaystyle
q_{\omega,\xi}:=\Big{\lVert}\bra{\tau\omega\sigma^{-1}}_{D}\ket{\phi^{\sigma,\tau,(j)}_{\xi}}\Big{\rVert}^{2}=\Big{\lVert}\bra{\tau\omega\sigma^{-1}}_{D}\bra{\xi}_{X}\ket{\phi^{\sigma,\tau,(j)}}\Big{\rVert}^{2}$

can be interpreted as the joint probability of the outcomes of the following
procedure: initialize the database, run an algorithm (namely, $\mathcal{B}$ up
to right before its $j$-th query) that makes queries to the twirled standard
oracle, measure the $X$ register to obtain an outcome $\xi\in[N]$, and also
apply the recovery operation to the database to obtain an outcome $\omega\in
S_{N}$. Accordingly, Lemma 4.6 shows that $q_{\omega,\xi}$ does not depend on
the choice of $\sigma,\tau\in S_{N}$ (which justifies the notation) and that
the marginal distribution of $\omega$ with respect to $q_{\omega,\xi}$ is
uniform, i.e., $\sum_{\xi\in[N]}q_{\omega,\xi}=\frac{1}{N!}$ for all
$\omega\in S_{N}$. This observation will be used to establish all three parts
of the lemma.

  1. (i)

We start by writing

$\displaystyle\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R^{\sigma,\tau}_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi^{\sigma,\tau,(j)}_{\sigma^{-1}(z)}}\Big{\rVert}^{2}=\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z=1}^{x-1}\sum_{\pi:\pi_{x^{c}}(z)\in
R^{\sigma,\tau}_{x}}q_{\tau^{-1}\pi\sigma,\sigma^{-1}(z)}.$ (6.16)

Recall that $\pi=\pi_{>x}\left(x\;t_{x}\right)\pi_{>x}$ for some
$t_{x}\in[x]$, as in Eqs. 3.1 and 3.4. We will write $t_{x}(\pi):=t_{x}$ to
make explicit the dependency of $t_{x}$ on the permutation. Because $z<x$, we
have

$\displaystyle\pi_{x^{c}}(z)=\begin{cases}\pi(z)&\text{ if }\pi_{<x}(z)\neq
t_{x}(\pi),\\\ \pi(x)&\text{ if }\pi_{<x}(z)=t_{x}(\pi),\end{cases}$

so we can write the right-hand side of Eq. 6.16 as a sum of two terms,

$\displaystyle\quad\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z=1}^{x-1}\sum_{\pi:\pi_{x^{c}}(z)\in
R^{\sigma,\tau}_{x}}q_{\tau^{-1}\pi\sigma,\sigma^{-1}(z)}$
$\displaystyle=\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z=1}^{x-1}\sum_{\pi:\pi(z)\in
R^{\sigma,\tau}_{x}}\bm{1}_{\pi_{<x}(z)\neq
t_{x}(\pi)}\,q_{\tau^{-1}\pi\sigma,\sigma^{-1}(z)}+\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z=1}^{x-1}\sum_{\pi:\pi(x)\in
R^{\sigma,\tau}_{x}}\bm{1}_{\pi_{<x}(z)=t_{x}(\pi)}\,q_{\tau^{-1}\pi\sigma,\sigma^{-1}(z)}$
$\displaystyle=\mathop{\bf
E\/}_{x^{\prime},\sigma,\tau}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(z^{\prime})\in
R_{x^{\prime}}}\bm{1}_{\pi_{<\sigma(x^{\prime})}(\sigma(z^{\prime}))\neq
t_{\sigma(x^{\prime})}(\tau\pi^{\prime}\sigma^{-1})}\,q_{\pi^{\prime},z^{\prime}}$
$\displaystyle+\mathop{\bf
E\/}_{x^{\prime},\sigma,\tau}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}}}\bm{1}_{\pi_{<\sigma(x^{\prime})}(\sigma(z^{\prime}))=t_{\sigma(x^{\prime})}(\tau\pi^{\prime}\sigma^{-1})}\,q_{\pi^{\prime},z^{\prime}},$

where the last step follows by substituting $x=\sigma(x^{\prime})$,
$z=\sigma(z^{\prime})$, and $\pi=\tau\pi^{\prime}\sigma^{-1}$, noting that
$(x^{\prime},\sigma,\tau)$ is still uniformly random, and using the relation
$\pi(\xi)\in R^{\sigma,\tau}_{x}\Leftrightarrow\tau^{-1}(\pi(\xi))\in
R_{\sigma^{-1}(x)}$. As $\tau$ only appears in the indicator functions, we can
rewrite and bound this as

$\displaystyle\quad\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(z^{\prime})\in
R_{x^{\prime}}}\Pr_{\tau}\left(\pi_{<\sigma(x^{\prime})}(\sigma(z^{\prime})\right)\neq
t_{\sigma(x^{\prime})}(\tau\pi^{\prime}\sigma^{-1}))\,q_{\pi^{\prime},z^{\prime}}$
$\displaystyle+\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}}}\Pr_{\tau}\left(\pi_{<\sigma(x^{\prime})}(\sigma(z^{\prime})\right)=t_{\sigma(x^{\prime})}(\tau\pi^{\prime}\sigma^{-1}))\,q_{\pi^{\prime},z^{\prime}}$
$\displaystyle=\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(z^{\prime})\in
R_{x^{\prime}}}\Pr_{t^{\prime}\leftarrow[\sigma(x^{\prime})]}\left(\pi_{<\sigma(x^{\prime})}(\sigma(z^{\prime}))\neq
t^{\prime}\right)\,q_{\pi^{\prime},z^{\prime}}$ $\displaystyle+\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}}}\Pr_{t^{\prime}\leftarrow[\sigma(x^{\prime})]}\left(\pi_{<\sigma(x^{\prime})}(\sigma(z^{\prime}))=t^{\prime}\right)\,q_{\pi^{\prime},z^{\prime}}$
$\displaystyle\leq\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(z^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}+\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}}}\frac{1}{\sigma(x^{\prime})}q_{\pi^{\prime},z^{\prime}}$
$\displaystyle=\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(z^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}+\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{(\sigma(x^{\prime}))^{2}}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}},$

since, for any fixed $x^{\prime},z^{\prime},\sigma,\pi^{\prime}$, the
permutation $\tau\pi^{\prime}\sigma^{-1}$ is uniformly random in $S_{N}$, so
$t_{\sigma(x^{\prime})}(\tau\pi^{\prime}\sigma^{-1})$ is uniformly random in
$[\sigma(x^{\prime})]$ (by Corollary 3.2) and hence equal to any fixed integer
in this interval with probability $\frac{1}{\sigma(x^{\prime})}$. We can
finally upper bound the above by

$\displaystyle\quad\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(z^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}+\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{(\sigma(x^{\prime}))^{2}}\sum_{z^{\prime}\in\sigma^{-1}([1,\sigma(x^{\prime})])}\sum_{\pi^{\prime}:\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}$ $\displaystyle\leq\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}=1}^{N}\sum_{\pi^{\prime}:\pi^{\prime}(z^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}+\mathop{\bf
E\/}_{x^{\prime},\sigma}\frac{1}{(\sigma(x^{\prime}))^{2}}\sum_{z^{\prime}=1}^{N}\sum_{\pi^{\prime}:\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}$ $\displaystyle=\mathop{\bf
E\/}_{x^{\prime}}\left\lparen\mathop{\bf
E\/}_{\sigma}\frac{1}{\sigma(x^{\prime})}\right\rparen\sum_{z^{\prime}=1}^{N}\sum_{\pi^{\prime}:\pi^{\prime}(z^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}+\mathop{\bf
E\/}_{x^{\prime}}\left\lparen\mathop{\bf
E\/}_{\sigma}\frac{1}{{\sigma(x^{\prime})}^{2}}\right\rparen\sum_{z^{\prime}=1}^{N}\sum_{\pi^{\prime}:\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}$ $\displaystyle=\mathop{\bf
E\/}_{x^{\prime}}\left\lparen\mathop{\bf
E\/}_{\sigma}\frac{1}{\sigma(x^{\prime})}\right\rparen\sum_{z^{\prime}=1}^{N}\sum_{\pi^{\prime}:\pi^{\prime}(z^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}+\mathop{\bf
E\/}_{x^{\prime}}\left\lparen\mathop{\bf
E\/}_{\sigma}\frac{1}{{\sigma(x^{\prime})}^{2}}\right\rparen\sum_{z^{\prime}=1}^{N}\sum_{\pi^{\prime}:\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}$
$\displaystyle\leq\frac{\ln(N)+1}{N}\mathop{\bf
E\/}_{x^{\prime}}\sum_{z^{\prime}=1}^{N}\sum_{\pi^{\prime}:\pi^{\prime}(z^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}+\frac{\pi^{2}}{6}\frac{1}{N}\mathop{\bf
E\/}_{x^{\prime}}\sum_{z^{\prime}=1}^{N}\sum_{\pi^{\prime}:\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}}}q_{\pi^{\prime},z^{\prime}}$
$\displaystyle=\frac{\ln(N)+1}{N}\sum_{\pi^{\prime}\in
S_{N}}\sum_{z^{\prime}=1}^{N}\Pr_{x^{\prime}}\left(x^{\prime}\in
R^{\mathrm{inv}}_{\pi^{\prime}(z)}\right)q_{\pi^{\prime},z^{\prime}}+\frac{\pi^{2}}{6}\frac{1}{N}\mathop{\bf
E\/}_{x^{\prime}}\Pr_{\pi^{\prime}}(\pi^{\prime}(x^{\prime})\in
R_{x^{\prime}})$
$\displaystyle\leq\frac{\ln(N)+1}{N}\frac{r_{\max}}{N}+\frac{\pi^{2}}{6}\frac{1}{N}\frac{r_{\max}}{N}$
$\displaystyle\leq\left\lparen\ln(N)+3\right\rparen\frac{r_{\max}}{N^{2}},$

where we first enlarging the sum over $z^{\prime}$ to all of $[N]$, then we
bounded the expectation over $\sigma$ by using that $\sigma(x^{\prime})\in[N]$
is uniformly random for any fixed $x^{\prime}$; in the last equality we also
used that the marginal distribution of $\pi^{\prime}$ with respect to
$q_{\pi^{\prime},z^{\prime}}$ is uniform as discussed above.

  2. (ii)

Similarly as above, we begin by writing

$\displaystyle\mathop{\bf E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z\in
R^{\sigma,\tau}_{x}}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)<x}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi^{\sigma,\tau,(j)}_{\tau^{-1}(z)}}\Big{\rVert}^{2}=\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z\in
R^{\sigma,\tau}_{x}}\sum_{\pi:\pi_{>x}^{-1}(z)<x}q_{\tau^{-1}\pi\sigma,\tau^{-1}(z)}$

We can upper-bound this by omitting the constraint on $\pi$, which gives the
bound

$\displaystyle\quad\mathop{\bf E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z\in
R^{\sigma,\tau}_{x}}\sum_{\pi:\pi_{>x}^{-1}(z)<x}q_{\tau^{-1}\pi\sigma,\tau^{-1}(z)}$
$\displaystyle\leq\mathop{\bf E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z\in
R^{\sigma,\tau}_{x}}q_{\tau^{-1}(z)}=\mathop{\bf
E\/}_{x^{\prime},\sigma,\tau}\frac{1}{\sigma(x^{\prime})}\sum_{z^{\prime}\in
R_{x^{\prime}}}q_{z^{\prime}}$ $\displaystyle=\mathop{\bf
E\/}_{x^{\prime}}\left\lparen\mathop{\bf
E\/}_{\sigma}\frac{1}{\sigma(x^{\prime})}\right\rparen\sum_{z^{\prime}\in
R_{x^{\prime}}}q_{z^{\prime}}\leq\frac{\ln(N)+1}{N}\mathop{\bf
E\/}_{x^{\prime}}\sum_{z^{\prime}\in R_{x^{\prime}}}q_{z^{\prime}}$
$\displaystyle=\frac{\ln(N)+1}{N}\sum_{z^{\prime}=1}^{N}\Pr_{x^{\prime}}\left(x^{\prime}\in
R^{\mathrm{inv}}_{z^{\prime}}\right)q_{z^{\prime}}\leq\left\lparen\ln(N)+1\right\rparen\frac{r_{\max}}{N^{2}},$

where we use the notation $q_{\xi}:=\sum_{\omega\in S_{N}}q_{\omega,\xi}$ for
the marginal distribution of $\xi$ with respect to $q_{\omega,\xi}$; the
second step follows by substituting $x=\sigma(x^{\prime})$ and
$z=\tau(z^{\prime})$.

  3. (iii)

Again we begin with

$\displaystyle\quad\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)=x}\lvert[x]\cap\pi_{>x}^{-1}(R^{\sigma,\tau}_{x})\rvert\,\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi^{\sigma,\tau,(j)}_{\tau^{-1}(z)}}\Big{\rVert}^{2}$
$\displaystyle=\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z=x+1}^{N}\sum_{\pi:\pi_{>x}^{-1}(z)=x}\lvert[x]\cap\pi_{>x}^{-1}(R^{\sigma,\tau}_{x})\rvert\,q_{\tau^{-1}\pi\sigma,\tau^{-1}(z)}$
$\displaystyle\leq r_{\max}\mathop{\bf
E\/}_{x,\sigma,\tau}\frac{1}{x}\sum_{z=x+1}^{N}\sum_{\pi:\pi_{>x}^{-1}(z)=x}q_{\tau^{-1}\pi\sigma,\tau^{-1}(z)}$
$\displaystyle=r_{\max}\mathop{\bf
E\/}_{x^{\prime},\sigma,\tau}\frac{1}{\tau(x^{\prime})}\sum_{z^{\prime}\in\tau^{-1}(\\{\tau(x^{\prime})+1,\dots,N\\})}\sum_{\pi^{\prime}}\bm{1}_{((\tau\pi^{\prime}\sigma^{-1})_{>\tau(x^{\prime})})^{-1}(\tau(z^{\prime}))=\tau(x^{\prime})}q_{\pi^{\prime},z^{\prime}},$

where the last step follows by substituting $x=\tau(x^{\prime})$,
$z=\tau(z^{\prime})$, and $\pi=\tau\pi^{\prime}\sigma^{-1}$. As $\sigma$ only
occurs in the indicator function, we can rewrite and bound this as

$\displaystyle\quad r_{\max}\mathop{\bf
E\/}_{x^{\prime},\tau}\frac{1}{\tau(x^{\prime})}\sum_{z^{\prime}\in\tau^{-1}(\\{\tau(x^{\prime})+1,\dots,N\\})}\sum_{\pi^{\prime}}\Pr_{\sigma}\left(((\tau\pi^{\prime}\sigma^{-1})_{>\tau(x^{\prime})})^{-1}(\tau(z^{\prime}))=\tau(x^{\prime})\right)q_{\pi^{\prime},z^{\prime}}$
$\displaystyle=r_{\max}\mathop{\bf
E\/}_{x^{\prime},\tau}\frac{1}{\tau(x^{\prime})}\sum_{z^{\prime}\in\tau^{-1}(\\{\tau(x^{\prime})+1,\dots,N\\})}\sum_{\pi^{\prime}}\Pr_{\sigma}\left(\sigma_{>\tau(x^{\prime})}(\tau(x^{\prime}))=\tau(z^{\prime})\right)q_{\pi^{\prime},z^{\prime}}$
(6.17)

since, for any fixed $\tau$ and $\pi^{\prime}$, the permutation
$\tau\pi^{\prime}\sigma^{-1}$ is again uniformly random. Using part (iii) of
Lemma 3.3, we see that the inner probability is simply equal to $\frac{1}{N}$.
Hence the above is equal to

$\displaystyle\frac{r_{\max}}{N}\mathop{\bf
E\/}_{x^{\prime},\tau}\frac{1}{\tau(x^{\prime})}\sum_{z^{\prime}\in\tau^{-1}(\\{\tau(x^{\prime})+1,\dots,N\\})}\sum_{\pi^{\prime}}q_{\pi^{\prime},z^{\prime}}\leq\frac{r_{\max}}{N}\mathop{\bf
E\/}_{x^{\prime},\tau}\frac{1}{\tau(x^{\prime})}=\frac{r_{\max}}{N}\mathop{\bf
E\/}_{x^{\prime}}\frac{1}{x^{\prime}}\leq\left\lparen\ln(N)+1\right\rparen\frac{r_{\max}}{N^{2}}.$

∎

###  6.3 Sparsity Analysis

The goal of this section is to upper bound the term

$\displaystyle\mathop{\bf E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\
\sigma,\tau\leftarrow
S_{N}\end{subarray}}\frac{\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{\sigma,\tau,(j)}}\right\rVert^{2}}{x},$
(6.18)

which remains to be estimated in the right-hand side of Proposition 6.6.
Intuitively, this quantifies the extent to which a random database register
$D_{x}$ has been queried by the algorithm, weighted by $1/x$-.

To analyze Eq. 6.18, recall that $\ket{\phi^{\sigma,\tau,(j)}}_{AXYD}$ denotes
the joint state of the algorithm and database right before the $j$-th query
when run with the twirled oracle. By Lemma 4.8, we have

$\displaystyle\ket{\phi^{\sigma,\tau,(j)}}_{AXYD}=L^{\tau}_{D}R^{\sigma}_{D}\ket{\phi^{(j)}}_{AXYD},$

where $\ket{\phi^{(j)}}$ denotes the state right before the $j$-th query when
the same algorithm is run with the _untwirled_ oracle. We can thus express Eq.
6.18 as follows:

$\displaystyle\mathop{\bf E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\
\sigma,\tau\leftarrow
S_{N}\end{subarray}}\frac{\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{\sigma,\tau,(j)}}\right\rVert^{2}}{x}$
$\displaystyle=\bra{\phi^{(j)}}\Gamma_{D}\ket{\phi^{(j)}},$ (6.19)

where we have introduced the operator

$\displaystyle\Gamma_{D}$ $\displaystyle:=\mathop{\bf
E\/}_{x\leftarrow[N]}\frac{1}{x}\mathop{\bf E\/}_{\sigma,\tau\leftarrow
S_{N}}(L^{\tau}_{D}R^{\sigma}_{D})^{\dagger}\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}(L^{\tau}_{D}R^{\sigma}_{D})$
(6.20)

where we recall that $H_{N}$ denotes the harmonic numbers, see Eq. 2.1.

To upper bound the quantity of interest, we now observe that that we can upper
bound its growth with each additional query as follows, in terms of the norm
of a commutator:

$\displaystyle\braket{\phi^{(j+1)}}{\Gamma_{D}}{\phi^{(j+1)}}-\braket{\phi^{(j)}}{\Gamma_{D}}{\phi^{(j)}}$
$\displaystyle=\braket{\phi^{(j)}}{Q_{XYD}^{\dagger}\Gamma_{D}Q_{XYD}-\Gamma_{D}}{\phi^{(j)}}$
$\displaystyle=\braket{\phi^{(j)}}{Q_{XYD}^{\dagger}[\Gamma_{D},Q_{XYD}]}{\phi^{(j)}}$
$\displaystyle\leq\left\lVert[\Gamma_{D},Q_{XYD}]\right\rVert$ (6.21)

where
$Q_{XYD}\in\\{O^{\mathsf{SPO}}_{XYD},O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\\}$,
depending on whether the $j$-th query is a forward or an inverse query. The
first equality holds because the unitary that the algorithm performs inbetween
the two queries does not act on the oracle’s database register $D$.

We now calculate the operator $\Gamma_{D}$ explicitly and use the result to
estimate the norm of the commutator.

######  Lemma 6.8.

We have

$\displaystyle\Gamma_{D}=\frac{H_{N}-H_{N}^{(2)}}{N}I_{D}-2\frac{H_{N}^{(2)}-H_{N}^{(3)}}{N}W^{(2)}_{D}-\frac{H_{N}-3H_{N}^{(2)}+2H_{N}^{(3)}}{N}W^{(3)}_{D},$

where we denote $H_{N}^{(\ell)}:=\sum_{\ell=1}^{N}\frac{1}{x^{\ell}}$ and
$W^{(\ell)}:=\mathop{\bf E\/}_{\gamma\text{
$\ell$-cycle}}R^{\gamma}=\mathop{\bf E\/}_{\gamma\text{
$\ell$-cycle}}L^{\gamma}$.999To see this, note that $\mathop{\bf
E\/}_{\gamma}R^{\gamma}\ket{\pi}=\mathop{\bf
E\/}_{\gamma}\ket{\pi\gamma^{-1}}=\mathop{\bf
E\/}_{\gamma}\ket{\pi\gamma^{-1}\pi^{-1}\pi}=\mathop{\bf
E\/}_{\gamma}\ket{\gamma\pi}=\mathop{\bf E\/}_{\gamma}L_{\gamma}\ket{\pi}$,
since if $\gamma$ is a uniformly random $\ell$-cycle then so is
$\pi\gamma^{-1}\pi^{-1}$, for any permutation $\pi\in S_{N}$.

###### Proof.

We first compute the action of $\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}$
in the permutation basis. For any $\pi\in S_{N}$, we have

$\displaystyle\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\pi}_{D}$
$\displaystyle=\mathop{\bf
E\/}_{s\leftarrow[x]}\ket{\pi_{>x}\left(x\;s\right)\pi_{<x}}$
$\displaystyle=\mathop{\bf
E\/}_{s\leftarrow[x]}\ket{\pi_{>x}\left(x\;t_{x}\right)\pi_{<x}\,\pi_{<x}^{-1}\left(x\;t_{x}\right)\pi_{<x}\,\pi_{<x}^{-1}\left(x\;s\right)\pi_{<x}}$
$\displaystyle=\mathop{\bf
E\/}_{s\leftarrow[x]}\ket{\pi\left(x\;\pi_{<x}^{-1}(t_{x})\right)\left(x\;\pi_{<x}^{-1}(s)\right)}$
$\displaystyle=\mathop{\bf
E\/}_{s\leftarrow[x]}R^{\left(x\;s\right)}_{D}R^{\left(x\;\pi_{<x}^{-1}(t_{x}(\pi))\right)}_{D}\ket{\pi}_{D},$

where we denote by $t_{x}\in[x]$ the number in the decomposition (3.1) of
$\pi$, i.e., $\pi=\pi_{>x}\left(x\;t_{x}\right)\pi_{<x}$; in the last line we
write $t_{x}(\pi)$ to make the dependence on $\pi$ explicit. Thus,

$\displaystyle\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}=\sum_{\pi\in
S_{N}}\mathop{\bf
E\/}_{s\leftarrow[x]}R^{\left(x\;s\right)}_{D}R^{\left(x\;\pi_{<x}^{-1}(t_{x}(\pi))\right)}_{D}\ket{\pi}_{D}\bra{\pi}_{D}.$

We first average this over the left action, which commutes with the right
action, and obtain

$\displaystyle\mathop{\bf E\/}_{\tau\leftarrow
S_{N}}(L^{\tau}_{D})^{\dagger}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}L^{\tau}_{D}$
$\displaystyle=\sum_{\pi\in S_{N}}\mathop{\bf
E\/}_{s\leftarrow[x]}R^{\left(x\;s\right)}_{D}R^{\left(x\;\pi_{<x}^{-1}(t_{x}(\pi))\right)}_{D}\underbrace{\mathop{\bf
E\/}_{\tau\leftarrow
S_{N}}\ket{\tau^{-1}\pi}_{D}\bra{\tau^{-1}\pi}_{D}}_{=\frac{1}{N!}I_{D}}$
$\displaystyle=\mathop{\bf E\/}_{\pi\in S_{N}}\mathop{\bf
E\/}_{s\leftarrow[x]}R^{\left(x\;s\right)}_{D}R^{\left(x\;\pi_{<x}^{-1}(t_{x}(\pi))\right)}_{D}=\mathop{\bf
E\/}_{s,t\leftarrow[x]}R^{\left(x\;s\right)}_{D}R^{\left(x\;t\right)}_{D}=\mathop{\bf
E\/}_{s,t\leftarrow[x]}R^{\left(x\;s\right)\left(x\;t\right)}_{D}.$

If we now average over the right action, the permutation
$\left(x\;s\right)\left(x\;t\right)$ is conjugated into a random permutation
of the same type (either the identity, a transposition, or a 3-cycle,
depending on the cardinality of $\\{x,s,t\\}$):

$\displaystyle\mathop{\bf E\/}_{\sigma,\tau\leftarrow
S_{N}}(L^{\tau}_{D}R^{\sigma}_{D})^{\dagger}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}(L^{\tau}_{D}R^{\sigma}_{D})$
$\displaystyle=\mathop{\bf E\/}_{s,t\leftarrow[x]}\mathop{\bf
E\/}_{\sigma\leftarrow
S_{N}}R^{\left(\sigma^{-1}(x)\;\sigma^{-1}(s)\right)\left(\sigma^{-1}(x)\;\sigma^{-1}(t)\right)}_{D}$
$\displaystyle=\sum_{\ell=1}^{3}\Pr_{s,t\leftarrow[x]}\bigl{(}\lvert\\{s,t,x\\}\rvert=\ell\bigr{)}\,W^{(\ell)}_{D}$
$\displaystyle=\frac{1}{x}I_{D}+\frac{2(x-1)}{x^{2}}W^{(2)}_{D}+\frac{(x-1)(x-2)}{x^{2}}W^{(3)}_{D}.$

and finally, using Eq. 6.20 and $\mathop{\bf
E\/}_{x\leftarrow[N]}\frac{1}{x^{\ell}}=H_{N}^{(\ell)}/N$,

$\displaystyle\Gamma_{D}$ $\displaystyle=\mathop{\bf
E\/}_{x\leftarrow[N]}\frac{1}{x}\left\lparen I_{D}-\mathop{\bf
E\/}_{\sigma,\tau\leftarrow
S_{N}}(L^{\tau}_{D}R^{\sigma}_{D})^{\dagger}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}(L^{\tau}_{D}R^{\sigma}_{D})\right\rparen$
$\displaystyle=\mathop{\bf
E\/}_{x\leftarrow[N]}\left\lparen\left\lparen\frac{1}{x}-\frac{1}{x^{2}}\right\rparen
I_{D}-\frac{2(x-1)}{x^{3}}W^{(2)}_{D}-\frac{(x-1)(x-2)}{x^{3}}W^{(3)}_{D}\right\rparen.\qed$

######  Lemma 6.9.

For
$Q_{XYD}\in\\{O^{\mathsf{SPO}}_{XYD},O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\\}$,
we have
$\left\lVert[\Gamma_{D},Q_{XYD}]\right\rVert\leq\frac{6(\ln(N)+1)}{N^{2}}$.

###### Proof.

We prove the bound in the case that $Q_{XYD}\in\\{O^{\mathsf{SPO}}_{XYD}$ –
the other case is identical except for using the formula $W^{(\ell)}$ in terms
of the left instead of the right action. We first observe that since
$O^{\mathsf{SPO}}_{XYD}$ is controlled on $X$,

$\displaystyle\left\lVert[\Gamma_{D},O^{\mathsf{SPO}}_{XYD}]\right\rVert=\max_{x\in[N]}\left\lVert[\Gamma_{D},O^{\mathsf{SPO},x}_{YD}]\right\rVert$

where $O^{\mathsf{SPO},z}_{YD}:=\bra{z}_{X}O^{\mathsf{SPO}}_{XYD}\ket{z}_{X}$.
Next, note that if $\gamma\in S_{N}$ is any permutation such that
$\gamma(x)=x$, then

$\displaystyle[R^{\gamma}_{D},O^{\mathsf{SPO},x}_{YD}]=0.$

since for any $y\in[N]$ and $\pi\in S_{N}$ we have
$O^{\mathsf{SPO},x}_{YD}R^{\gamma}_{D}\ket{y,\pi}_{YD}=\ket{y\oplus\pi(\gamma^{-1}(x)),\pi\gamma^{-1}}_{YD}=\ket{y\oplus\pi(x),\pi\gamma^{-1}}_{YD}=R^{\gamma}_{D}O^{\mathsf{SPO},x}_{YD}\ket{y,\pi}_{YD}$.
Otherwise, if $\gamma(x)\neq x$ then it still holds that $\lVert
R^{\gamma}_{D},O^{\mathsf{SPO},x}_{YD}]\rVert\leq 2$ since the commutator of
any two unitaries has operator norm at most two. Accordingly,

$\displaystyle\left\lVert[W^{(2)}_{D},O^{\mathsf{SPO},x}_{YD}]\right\rVert\leq
2\Pr_{\gamma\text{ 2-cycle}}(\gamma(x)\neq x)=\frac{4}{N},$
$\displaystyle\left\lVert[W^{(3)}_{D},O^{\mathsf{SPO},x}_{YD}]\right\rVert\leq
2\Pr_{\gamma\text{ 3-cycle}}(\gamma(x)\neq x)=\frac{6}{N}.$

and hence, using Lemma 6.8, the fact that $H_{N}\geq H_{N}^{(2)}\geq
H_{N}^{(3)}\geq 0$, and Eq. 2.2,

$\displaystyle\left\lVert[\Gamma_{D},O^{\mathsf{SPO},x}_{YD}]\right\rVert$
$\displaystyle\leq
2\frac{H_{N}^{(2)}-H_{N}^{(3)}}{N}\left\lVert[W^{(2)}_{D},O^{\mathsf{SPO},x}_{YD}]\right\rVert+\frac{H_{N}-3H_{N}^{(2)}+2H_{N}^{(3)}}{N}\left\lVert[W^{(3)}_{D},O^{\mathsf{SPO},x}_{YD}]\right\rVert$
$\displaystyle\leq
8\frac{H_{N}^{(2)}-H_{N}^{(3)}}{N^{2}}+6\frac{H_{N}-3H_{N}^{(2)}+2H_{N}^{(3)}}{N^{2}}$
$\displaystyle=\frac{6H_{N}-10H_{N}^{(2)}+4H_{N}^{(3)}}{N^{2}}\leq\frac{6H_{N}}{N^{2}}\leq\frac{6(\ln(N)+1)}{N^{2}}.$

∎

######  Corollary 6.10.

For all $j$, it holds that

$\displaystyle\mathop{\bf E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\
\sigma,\tau\leftarrow
S_{N}\end{subarray}}\frac{\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{\sigma,\tau,(j)}}\right\rVert^{2}}{x}\leq
6\,\frac{j(\ln(N)+1)}{N^{2}}$

and hence

$\displaystyle 4qr_{\max}\sum_{j=1}^{2q}\mathop{\bf
E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\ \sigma,\tau\leftarrow
S_{N}\end{subarray}}\frac{\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{\sigma,\tau,(j)}}\right\rVert^{2}}{x}$
$\displaystyle\leq 72\frac{q^{3}r_{\max}(\ln(N)+1)}{N^{2}}$

###### Proof.

The first formula follows from Eqs. 6.19, 6.21 and 6.9 by using induction,
since
$\bra{\phi^{(0)}}\Gamma_{D}\ket{\phi^{(0)}}=\bra{\Phi_{\mathsf{SPO}}}\Gamma_{D}\ket{\Phi_{\mathsf{SPO}}}=0$.
The second formula follows at once. ∎

###  6.4 Main Theorem

Finally, we can use the preceding analysis, together with the fundamental
lemma, to establish our main theorem (which formalizes Theorem 1.1 announced
in the introduction):

######  Theorem 6.11 (Search).

Let $\mathcal{A}$ be a quantum algorithm with quantum query access to a random
permutation $\pi\in S_{N}$ and its inverse (4.1), which returns an $x\in[N]$,
and let $R\subseteq[N]\times[N]$ be any relation. If $\mathcal{A}$ makes fewer
than $q$ queries, then the probability that it returns an element $x$ such
that $(x,\pi(x))\in R$ is

$\displaystyle\Pr_{\pi\leftarrow
S_{N},\;x\leftarrow\mathcal{A}^{U^{\pi},U^{\pi^{-1}}}}\bigl{[}(x,\pi(x))\in
R\bigr{]}\leq 914\,\frac{q^{3}r_{\max}\big{\lparen}\ln(N)+2\big{\rparen}}{N},$

where we recall $r_{\max}=\max\left\\{\max_{x}\,\lvert
R_{x}\rvert,\max_{y}\,\lvert R^{\mathrm{inv}}_{y}\rvert\right\\}$, with
$R_{x}=\\{y:(x,y)\in R\\}$ and $R^{\mathrm{inv}}_{y}=\\{x:(x,y)\in R\\}$.

###### Proof.

Without loss of generality we can assume that $\mathcal{A}$ is a unitary query
algorithm on registers $AXY$, where $X$ and $Y$ are the two $N$-dimensional
registers that the oracles get applied to such that the classical outcome $x$
can be obtained by measuring the $X$ register. Let $\mathcal{B}$ denote the
unitary query algorithm that first runs $x\leftarrow\mathcal{A}$, then makes
one more query to load $\pi(x)$ into the $Y$ register. Since $\mathcal{A}$
makes fewer than $q$ queries, the algorithm $\mathcal{B}$ makes at most $q$
queries. For every $\sigma,\tau\in S_{N}$, let
$\ket{\phi^{\sigma,\tau}}_{AXYD}$ be the joint state of algorithm and oracle
defined by running $\mathsf{Init}^{\mathsf{SPO}}_{D}$ and then
$\mathcal{B}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$. Then, Propositions 6.6 and
6.10 combine to

$\displaystyle\mathop{\bf E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\
\sigma,\tau\leftarrow S_{N}\end{subarray}}\left\lVert
E^{R^{\sigma,\tau},x}_{D}\ket{\phi^{\sigma,\tau}}\right\rVert^{2}$
$\displaystyle\leq
384\frac{q^{2}r_{\max}\big{\lparen}\ln(N)+2\big{\rparen}}{N^{2}}+72\frac{q^{3}r_{\max}(\ln(N)+1)}{N^{2}}$
$\displaystyle\leq
456\frac{q^{3}r_{\max}\big{\lparen}\ln(N)+2\big{\rparen}}{N^{2}}.$

Using Lemmas 5.3 and 6.1, we can upper bound the quantity $p_{\text{(ii)}}$
defined in the fundamental lemma (Lemma 5.1) as follows:

$\displaystyle p_{\text{(ii)}}\leq N\mathop{\bf
E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\ \sigma,\tau\leftarrow
S_{N}\end{subarray}}\left\lVert
E^{R^{\sigma,\tau},x}_{D}\ket{\phi^{\sigma,\tau}}\right\rVert^{2}\leq
456\frac{q^{3}r_{\max}\big{\lparen}\ln(N)+2\big{\rparen}}{N}.$

Finally, the fundamental lemma states that

$\displaystyle\sqrt{p_{\text{(i)}}}\leq\sqrt{p_{\text{(ii)}}}+\sqrt{\frac{\ln(N)+1}{N}}$

and hence

$\displaystyle p_{\text{(i)}}\leq 2\left\lparen
p_{\text{(ii)}}+\frac{\ln(N)+1}{N}\right\rparen\leq
914\,\frac{q^{3}r_{\max}\big{\lparen}\ln(N)+2\big{\rparen}}{N}$

concluding our proof. ∎

##  7 Application to One-Round Sponge and Unruh’s Conjecture

We can now apply our results to obtain bounds for the hardness of search
problems for algorithms given quantum query access to a random permutation and
its inverse.

We first show a bound on the pre-image search problem for the _sponge
construction_ , instantiated with a random permutation, restricted to one
absorption round and one squeezing round. The sponge function in this special
case, for a permutation $\pi\in S_{\\{0,1\\}^{n}}$ and with capacity $c<n$, is
given by

$f_{\pi}\colon\\{0,1\\}^{n-c}\to\\{0,1\\}^{n-c},\quad
f_{\pi}(x)=\pi\left(x\|0^{c}\right)_{[1,n-c]},$

where $s_{[1,r]}$ denotes the first $r$ bits of a string $s$. The following
result was stated as Corollary 1.2 in the introduction.

######  Corollary 7.1 (One-round sponge).

For any $y\in\\{0,1\\}^{n-c}$, the probability that a quantum algorithm
$\mathcal{A}$ with quantum query access to a random permutation $\pi\in
S_{\\{0,1\\}^{n}}$ and its inverse returns a preimage $x\in\\{0,1\\}^{n-c}$
under the one-round sponge function $f_{\pi}$, by making fewer than $q$
queries, can be upper bounded as

$\displaystyle\Pr_{\pi\leftarrow
S_{\\{0,1\\}^{n}},\;x\leftarrow\mathcal{A}^{U^{\pi},U^{\pi^{-1}}}}\bigl{[}f_{\pi}(x)=y\bigr{]}\leq
914\,\frac{q^{3}(n+2)}{2^{\min(c,n-c)}}.$

###### Proof.

Let $\mathcal{B}$ denote the algorithm that runs $x\leftarrow\mathcal{A}$ and
returns $x^{\prime}:=x\|0^{c}$. Clearly, $f_{\pi}(x)=y$ if and only if
$(x^{\prime},\pi(x^{\prime}))\in R$, where

$\displaystyle
R=\left\\{(x^{\prime},y^{\prime})\in\\{0,1\\}^{n}\times\\{0,1\\}^{n}\;:\;x^{\prime}_{[n-c+1,n]}=0^{c},\
y^{\prime}_{[1,n-c]}=y\right\\}.$

Note that

$\displaystyle r_{\max}=\max\left\\{\max_{x^{\prime}}\,\lvert
R_{x^{\prime}}\rvert,\max_{y^{\prime}}\,\lvert
R^{\mathrm{inv}}_{y^{\prime}}\rvert\right\\}=2^{\max(c,n-c)}.$

Applying Theorem 6.11 to $\mathcal{B}$, which makes the same number of queries
as $\mathcal{A}$, we find that

$\\!\\!\Pr_{\begin{subarray}{c}\pi\leftarrow S_{\\{0,1\\}^{n}},\\\
x\leftarrow\mathcal{A}^{U^{\pi},U^{\pi^{-1}}}\end{subarray}}\\!\\!\bigl{[}f_{\pi}(x)=y\bigr{]}=\\!\\!\Pr_{\begin{subarray}{c}\pi\leftarrow
S_{\\{0,1\\}^{n}},\\\
x^{\prime}\leftarrow\mathcal{B}^{U^{\pi},U^{\pi^{-1}}}\end{subarray}}\\!\\!\bigl{[}(x^{\prime},\pi(x^{\prime}))\in
R\bigr{]}\leq
914\,\frac{q^{3}2^{\max(c,n-c)}(n+2)}{2^{n}}=914\,\frac{q^{3}(n+2)}{2^{\min(c,n-c)}}.\qed$

Next we consider the _double-sided zero-search conjecture_ , which states that
no adversary making polynomially many quantum queries to a permutation $\pi\in
S_{\\{0,1\\}^{2n}}$ and its inverse is able to find $x\in\\{0,1\\}^{n}$ such
that $\pi(x\|0^{n})_{[n+1,2n]}=0^{n}$ with non-negligible probability [Unr23,
Conjecture 1]. The following corollary confirms Unruh’s conjecture and
establishes more generally an upper bound on the success probability for the
problem with an arbitrary number $c$ of zeros. It was stated as Corollary 1.3
in the introduction.

######  Corollary 7.2.

The probability that a quantum algorithm $\mathcal{A}$ with quantum query
access to a random permutation $\pi\in S_{\\{0,1\\}^{2n}}$ and its inverse
returns $x\in\\{0,1\\}^{n}$ such that $\pi(x\|0^{n})_{[n+1,2n]}=0^{n}$, by
making fewer than $q$ queries, can be upper bounded as

$\displaystyle\Pr_{\pi\leftarrow
S_{\\{0,1\\}^{2n}},\;x\leftarrow\mathcal{A}^{U^{\pi},U^{\pi^{-1}}}}\bigl{[}\exists
y\in\\{0,1\\}^{n}:\pi(x\|0^{n})=y\|0^{n}\bigr{]}\leq
1828\,\frac{q^{3}\big{\lparen}n+1\big{\rparen}}{2^{n}}.$

More generally, it holds for any $c\in[2n]$ and any algorithm $\mathcal{A}$
that returns bitstrings $x\in\\{0,1\\}^{2n-c}$ that

$\displaystyle\Pr_{\pi\leftarrow
S_{\\{0,1\\}^{2n}},\;x\leftarrow\mathcal{A}^{U^{\pi},U^{\pi^{-1}}}}\bigl{[}\exists
y\in\\{0,1\\}^{2n-c}:\pi(x\|0^{c})=y\|0^{c}\bigr{]}\leq
1828\,\frac{q^{3}\big{\lparen}n+1\big{\rparen}}{2^{c}}.$

###### Proof.

It suffices to establish the second claim since it implies the first for
$c=n$. Similarly to the proof of Corollary 7.1 we can reduce to a relation,
namely

$\displaystyle
R=\left\\{(x^{\prime},y^{\prime})\in\\{0,1\\}^{2n}\times\\{0,1\\}^{2n}\;:\;x^{\prime}_{[2n-c+1,2n]}=y^{\prime}_{[2n-c+1,2n]}=0^{c}\right\\}.$

Note that $r_{\max}=2^{2n-c}$. Thus, Theorem 6.11 yields, with $N=2^{2n}$,

$\Pr_{\pi\leftarrow
S_{\\{0,1\\}^{2n}},\;x\leftarrow\mathcal{A}^{U^{\pi},U^{\pi^{-1}}}}\bigl{[}\exists
y\in\\{0,1\\}^{2n-c}:\pi(x\|0^{c})=y\|0^{c}\bigr{]}\leq
914\,\frac{q^{3}2^{2n-c}\big{\lparen}2n+2\big{\rparen}}{2^{2n}}=1828\,\frac{q^{3}\big{\lparen}n+1\big{\rparen}}{2^{c}}.\qed$

## Acknowledgments

The authors thank Saliha Tokat for feedback on an earlier version of this
manuscript.

GM and MW acknowledge support by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) under Germany’s Excellence Strategy - EXC 2092
CASA - 390781972. GM also acknowledges support by the European Research
Council through an ERC Starting Grant (grant agreement No. 101077455,
ObfusQation). MW also acknowledges support by the European Research Council
through an ERC Starting Grant (grant agreement No. 101040907, SYMOPTIC), by
the NWO through grant OCENW.KLEIN.267, and by the BMBF through project Quantum
Methods and Benchmarks for Resource Allocation (QuBRA). CM acknowledges
support by the Independent Research Fund Denmark via a DFF Sapere Aude grant
(IM-3PQC, grant ID 10.46540/2064-00034B). MW acknowledges the Simons Institute
for the Theory of Computing at UC Berkeley for its hospitality and support. MW
and CM thank the Leibnitz Center for Informatics for its hospitality.

## References

  * [ABK+] Gorjan Alagic, Chen Bai, Jonathan Katz, Christian Majenz, and Patrick Struck.  Post-quantum security of tweakable Even-Mansour, and applications.  Cryptology ePrint Archive, Paper 2022/1097.  Accepted at EUROCRYPT 2024.  URL: https://eprint.iacr.org/2022/1097.
  * [ABKM22] Gorjan Alagic, Chen Bai, Jonathan Katz, and Christian Majenz.  Post-quantum security of the Even-Mansour cipher.  In Advances in Cryptology—Eurocrypt 2022, Part III, volume 13277 of LNCS, pages 458–487. Springer, 2022.
  * [ABPS23] Gorjan Alagic, Chen Bai, Alexander Poremba, and Kaiyan Shi.  On the two-sided permutation inversion problem.  Cryptology ePrint Archive, Paper 2023/985, 2023.  URL: https://eprint.iacr.org/2023/985.
  * [BBBV97] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani.  Strengths and weaknesses of quantum computing.  SIAM J. Comput., 26(5):1510–1523, 1997.
  * [BDF+11] Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry.  Random oracles in a quantum world.  In Advances in Cryptology–ASIACRYPT 2011, pages 41–69. Springer, 2011.
  * [BHH+19] Nina Bindel, Mike Hamburg, Kathrin Hövelmanns, Andreas Hülsing, and Edoardo Persichetti.  Tighter proofs of CCA security in the quantum random oracle model.  In Theory of Cryptography. TCC 2019, volume 11892 of Lecture Notes in Computer Science, pages 61–90. Springer, 2019.
  * [BR93] Mihir Bellare and Phillip Rogaway.  Random oracles are practical: a paradigm for designing efficient protocols.  In Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS ’93, pages 62–73, New York, NY, USA, 1993. ACM.
  * [CFHL21] Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao.  On the compressed-oracle technique, and post-quantum security of proofs of sequential work.  In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, pages 598–629, Cham, 2021. Springer International Publishing.
  * [CGH04] Ran Canetti, Oded Goldreich, and Shai Halevi.  The random oracle methodology, revisited.  Journal of the ACM, 51:557–594, July 2004.
  * [CMSZ19] Jan Czajkowski, Christian Majenz, Christian Schaffner, and Sebastian Zur.  Quantum lazy sampling and game-playing proofs for quantum indifferentiability.  Cryptology ePrint Archive, Report 2019/428, 2019.  URL: https://eprint.iacr.org/2019/428.
  * [CP24] Joseph Carolan and Alexander Poremba.  Quantum one-wayness of the single-round sponge with invertible permutations.  Cryptology ePrint Archive, Paper 2024/414, 2024.  https://eprint.iacr.org/2024/414.  URL: https://eprint.iacr.org/2024/414.
  * [Cza21] Jan Czajkowski.  Quantum indifferentiability of SHA-3.  Cryptology ePrint Archive, Paper 2021/192, 2021.  URL: https://eprint.iacr.org/2021/192.
  * [DFMS21] Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner.  Online-extractability in the quantum random-oracle model.  Cryptology ePrint Archive, Report 2021/280, 2021.  URL: https://eprint.iacr.org/2021/280.
  * [Dwo15] Morris J Dworkin.  SHA-3 standard: Permutation-based hash and extendable-output functions.  Federal Inf. Process. Stds. (NIST FIPS) 202, 2015.  URL: https://doi.org/10.6028/NIST.FIPS.202.
  * [HHM22] Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz.  Failing gracefully: Decryption failures and the Fujisaki-okamoto transform.  In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, pages 414–443, Cham, 2022. Springer Nature Switzerland.
  * [HM23] Yassine Hamoudi and Frédéric Magniez.  Quantum time-space tradeoff for finding multiple collision pairs.  ACM Trans. Comput. Theory, 15, 2023.
  * [LR88] Michael Luby and Charles Rackoff.  How to construct pseudorandom permutations from pseudorandom functions.  SIAM J. Comput., 17(2):337–386, 1988.
  * [LZ19a] Qipeng Liu and Mark Zhandry.  On finding quantum multi-collisions.  In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 189–218, Cham, 2019. Springer International Publishing.
  * [LZ19b] Qipeng Liu and Mark Zhandry.  Revisiting post-quantum Fiat-Shamir.  In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, pages 326–355, Cham, 2019. Springer International Publishing.
  * [NC00] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2000.
  * [Ros21] Ansis Rosmanis.  Tight bounds for inverting permutations via compressed oracle arguments.  2021\.  arXiv:2103.08975.
  * [Unr21] Dominique Unruh.  Compressed permutation oracles (and the collision-resistance of Sponge/SHA3).  Cryptology ePrint Archive, Paper 2021/062, 2021.  URL: https://eprint.iacr.org/2021/062.
  * [Unr23] Dominique Unruh.  Towards compressed permutation oracles.  In Advances in Cryptology – ASIACRYPT 2023, volume 14441 of Lecture Notes in Computer Science, pages 369–400. Springer, 2023.
  * [Wat18] John Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.
  * [Wil19] Mark M Wilde.  Quantum Information Theory.  Cambridge University Press, second edition, 2019.
  * [Zha19] Mark Zhandry.  How to record quantum queries, and applications to quantum indifferentiability.  In Advances in Cryptology–CRYPTO 2019, pages 239–268. Springer, 2019.


Corresponding author address<EMAIL_ADDRESS>
# A feasibility study of using X-ray Thomson Scattering to diagnose the in-
flight plasma conditions of DT cryogenic implosions

H. Poole1 [  D. Cao2 R. Epstein2 I. Golovkin3 T. Walton3 S. X. Hu2,4 M. Kasim1
S. M. Vinko1,5 J. R. Rygg2,4 V. N. Goncharov2,4 G. Gregori1 S. P. Regan2,4
1Department of Physics, University of Oxford, UK.  2Laboratory for Laser
Energetics, University of Rochester, USA  3Prism Computational Sciences, USA
4Department of Mechanical Engineering, University of Rochester, USA  5Central
Laser Facility, STFC Rutherford Appleton Laboratory

###### Abstract

The design of inertial confinement fusion (ICF) ignition targets requires
radiation-hydrodynamics simulations with accurate models of the fundamental
material properties (i.e., equation of state, opacity, and conductivity).
Validation of these models are required via experimentation. A feasibility
study of using spatially-integrated, spectrally-resolved, X-ray Thomson
scattering (XRTS) measurements to diagnose the temperature, density, and
ionization of the compressed DT shell and hot spot of a laser direct-drive
implosion at two-thirds convergence was conducted. Synthetic scattering
spectra were generated using 1-D implosion simulations from the LILAC code
that were post processed with the X-ray Scattering (XRS) model which is
incorporated within SPECT3D. Analysis of two extreme adiabat capsule
conditions showed that the plasma conditions for both compressed DT shells
could be resolved.

††preprint: APS/123-QED

##  I Introduction

The design of inertial confinement fusion (ICF) targets is a challenging task
that requires, among others, hydrodynamic simulations with knowledge of the
shocked materials’ equation of state (EOS) if ignition conditions are to be
achieved [1, 2, 3, 4, 5]. The theoretical modelling of the extreme matter
properties reached during the capsule implosion is difficult due to the need
of a quantum mechanical treatment of the degenerate electrons, moderate
strongly-coupled ions and many-particle correlations [6, 7, 8, 9]. Uncertainty
in the EOS of matter under this regime results in unconfirmed calculations for
transport properties, ionization balance, and energy and temperature
equilibration [10, 11, 12, 13, 14]. Therefore, experimental validation is
vital for benchmarking and developing reduced models that can be implemented
in radiation hydrodynamic codes.

At present, the diagnosis of the physical properties of dense plasmas produced
in ICF implosions is limited due to the difficulty in achieving the required
accuracy and spatial resolutions [15, 16, 17, 18] for different model
predictions to be tested. Over the past couple of decades there has been a
push to develop new diagnostics that may be able to resolve different regions
of the imploding capsule, particularly the hot spot, the compressed shell and
the coronal plasma. Multi-keV spectrally resolved x-ray Thomson scattering
(XRTS) is one of these techniques [18, 19, 20].

The first experimental observation of noncollective, inelastic x-ray
scattering from shocked liquid deuterium is discussed in Ref. [17]. This
demonstrated the capabilities of inferring the electron temperature,
ionisation and electron density from the shapes and intensities of the elastic
(Rayleigh) and inelastic (Compton) components in the scattering spectra in ICF
dense matter. However, the scattering data had no spatial information, nor did
the analysis performed provide the capability to separate the contribution
from different regions.

Spatial temperature and ionization profiles were determined from a near-solid
density foam using a collimated X-ray beam in Ref. [21]. This data, produced
using the Imaging X-ray Thomson Spectrometer (IXTS) at the Omega laser
facility [22, 23], determined the temperature and ionization state of the
carbon foam at multiple positions along the axis of the flow. Good agreement
was found between the experiment and theoretical predictions with the
exception of the high-temperature, low-density rarefaction region of the blast
wave.

Simultaneous collective and non-collective scattering data for dynamically
compressed deuterium was collected in Ref. [24] using the
$2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ Si Ly-$\mathrm{\alpha}$ line. This
focused on compression states of $\rho/\rho_{0}\sim 2.8-4.05$. The mass
density was determined using the VISAR shock velocity using current EOS data.
This allowed for a restriction on the parameter space when determining the
ionization from the XRTS data.

However, to date, there has been no attempt to field an XRTS diagnostic on a
full laser direct-drive ICF implosion. In this report the feasibility of
utilising spatially integrated XRTS measurements to determine the in-flight
conditions of the compressed DT shell will be investigated. The study involved
analysing the X-ray scattering data produced by targets with very different
adiabats. The adiabat is defined as the ratio of the plasma pressure to the
Fermi-degenerate pressure [25] and for DT fuel is given by [26]

$\Gamma_{DT}\simeq\frac{P_{\mathrm{Shell}}[\mathrm{Mbar}]}{2.2\left[\rho[\mathrm{g/cm^{3}}]\right]^{5/3}}\,.$
(1)

Confinement properties of an ICF capsule depend on the areal density of the
compressed shell and hot-spot, $\rho R$. The areal density is controlled by
varying the entropy of the fuel, which is determined by the fuel adiabat. For
ignition to occur, a large enough areal density (low adiabat),
$>$0.20.5$\,$\mathrm{g}\mathrm{/}\mathrm{c}\mathrm{m}^{2}$$, and hot enough
core, $\sim 5-12\,$\mathrm{k}\mathrm{e}\mathrm{V}$$, are required [27, 28].
However, targets imploded on a low adiabat are susceptible to hydrodynamic
instabilities [29, 30] that drive the rapid growth of nonuniformities.
Therefore, an important part of ICF research involves optimisation of the
adiabat [31, 32, 33]. In experiments, however, direct measurements of the in-
flight fuel adiabat and densities are not yet achievable, instead they are
inferred from the neutron yield and x-ray self-emission [34].

This paper presents dual-channel XRTS as a possible diagnostic to retrieve
spatial information on the in-flight conditions of an ICF implosion. The
analysis is performed by constructing synthetic, spatially integrated, spectra
using the collision-radiative code SPECT3D [35], including the x-ray
scattering simulator [36], which is a post-processor of the 1-D radiation
hydrodynamic code LILAC [37].

##  II Proposed Experimental Setup

Figure 1: The 3D inferred temperature profile from Spect3D using the 1D
simulation data produced by the LILAC code. Schematic of the scattering
events, recorded on the detector by SPECT3D, from different zones throughout
the implosion are shown. The scattering geometry is demonstrative and not
drawn to scale.

XRTS is a powerful diagnostic tool for determining the conditions in plasmas
where the critical density, $n_{c}=\epsilon_{0}m_{e}\omega^{2}/e^{2}$ (where
$m_{e}$ is the mass of an electron, $e$ is the electron charge, $\epsilon_{0}$
is the electric constant and $\omega$ is the frequency of the laser drive),
exceeds what can be probed by any optical source. The first consideration for
an experimental setup, is the power required for the X-ray probe in order to
produce a scattering signal that can be observed above background noise. The
total number of photons scattered into a detector, $N_{d}$, can be estimated
as [18]

$\displaystyle N_{d}=$
$\displaystyle\,\left(\frac{E_{L}}{h\nu}\eta_{x}\right)\left(\frac{\Omega_{\mathrm{plasma}}}{4\pi}\eta_{\mathrm{att}}\right)\left[\frac{n_{e}\sigma_{\mathrm{Th}}\ell}{\left(1+\alpha\right)^{2}}\right]$
(2)
$\displaystyle\times\left(\frac{\Omega_{\mathrm{det}}}{4\pi}\eta_{d}\right)\,,$

where $E_{L}$ is the probe laser energy, $\eta_{x}$ is the conversion
efficiency from the laser energy into the probe X-rays, $\eta_{\mathrm{att}}$
is the attenuation of the probe X-rays through the dense plasma,
$\Omega_{\mathrm{plasma}}$ and $\Omega_{\mathrm{det}}$ are the solid angles
subtended by the plasma and the detector, respectively, $n_{e}$ is the
electron density, $\alpha$ is the scattering parameter, $\sigma_{\mathrm{Th}}$
is the Thomson scattering cross-section, $\ell$ is the path length of the
photons through the plasma, and $\eta_{d}$ is the detector efficiency.

For the plasma conditions investigated here, the scattering fraction,
$n_{e}\sigma_{\mathrm{Th}}\ell$, is approximately equal to $10^{-4}$, where we
have taken representative values for the compressed shell to be $n_{e}\sim
10^{23}\,\,$\mathrm{c}\mathrm{m}^{-3}$$ and $\ell=50\,\,$\mu\mathrm{m}$$. This
small scattering fraction makes fielding XRTS challenging since the signal can
easily be swamped by significant self-emission from the plasma. In this
feasibility study we show that a probe laser energy of
$1\,$\mathrm{k}\mathrm{J}$$ is required, as will be discussed in detail below.

A key benefit of fielding XRTS as a plasma diagnostic, is that XRTS can be
split into two scattering regimes, the collective and the noncollective, as
determined by the scattering parameter,

$\alpha=\frac{1}{k\lambda_{S}}\,,$ (3)

where $k$ is the scattering vector, and $\lambda_{S}$ is the screening length.
In the noncollective regime, the incoming wave ‘probes’ through the screening
sphere and the scattering spectrum therefore reflects the electron velocity
distribution. In contrast, the collective scattering regime reflects the
collective motion of the electrons. Designing an experiment where both regimes
can be recorded can reduce the error on the inferred plasma parameters.

To model the X-ray emissivity, a $1\,$\mathrm{k}\mathrm{J}$$ laser with a
$1\,$\mathrm{p}\mathrm{s}$$ pulse length and a source diameter of
$100\,$\mu\mathrm{m}$$ was used to produce a Gaussian X-ray source, with a
FWHM of $10\,$\mathrm{e}\mathrm{V}$$, $4.5\,$\mathrm{c}\mathrm{m}$$ away from
the imploding target, taking a conservative estimate of $\eta_{x}=0.01\%$. Two
$12.25\,$\mathrm{c}\mathrm{m}^{2}$$ charge-coupled device (CCD) detectors were
used to collect spectrally resolved radiation. The scattering geometry is
shown in Figure 1. The detectors were placed at a distance of
$2.4\,$\mathrm{m}$$ away from the plasma and at scattering angles of
$\theta_{F}=40${}^{\circ}$$ and $\theta_{B}=120${}^{\circ}$$. The two targets
chosen for this investigation are shown in Figures 2 and 3 with adiabats of
$2.8$ and $8.0$ respectively.

Figure 2: (a) Simulated target design, with an adiabat of $2.8$, fired with
laser profile shown in (b). (c) Density and electron temperature conditions in
the ICF implosion across the shock wave at two-thirds compression,
$t=2215\,$\mathrm{p}\mathrm{s}$$, as determined by the LILAC code for the
target. The scattering contributions from the DT in the unshocked fuel,
compressed shell and coronal plasma has been isolated and compared to the
fully integrated spectrum. For a $2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe,
the contribution from each region of the plasma to the overall scattering
spectrum is shown for both the forward ($40${}^{\circ}$$), (d), and backward
($120${}^{\circ}$$) scattering regime, (e). The same breakdown of the plasma
has been performed with a $3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ energy probe
in (f) and (g). Figure 3: As with figure 2 but with an ICF capsule with an
adiabat of $8.0$ and at $t=1901\,$\mathrm{p}\mathrm{s}$$.

Two experimental setups are considered for this paper, one with an X-ray probe
energy of $2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ and the other using a
$3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe. The scattering regime recorded
by each detector in each setup is shown in Figure 4. It should be noted that
the values for the $\alpha$ parameter shown in the figure are calculated for
the densest region in the compressed DT shell, and therefore not
representative of the scattering from the ICF capsule as a whole. To determine
the scattering signals from each region of the implosion, the fully integrated
scattering spectra must be determined.

Figure 4: Scattering parameters, $\alpha$, as calculated for the densest zone
in the compressed DT shell for each adiabat, scattering angle and probe
energy. A dashed line is shown at $\alpha=1$ which is the approximate
separation of collective, $\alpha>1$, and noncollective, $\alpha\leq 1$,
scattering.

The plasmon frequency shift for the high adiabat target is $\sim
27\,$\mathrm{e}\mathrm{V}$$, which increases to $\sim
30\,$\mathrm{e}\mathrm{V}$$ for the low adiabat target. In order to
distinguish this plasmon scattering, a narrow band X-ray probe must be used.
To achieve this in an experimental setup, the source must be chosen carefully.

Previous experiments have successfully used a crystal imaging system with a Si
Heα line at $\sim 1.865\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ [38] to radiograph
OMEGA cryogenic implosions [39] but the required x-ray fluence may not be
enough. Alternatively, Cl Kα at $\sim 2.62\,$\mathrm{k}\mathrm{e}\mathrm{V}$$
or Cl Ly-$\alpha$ at $\sim 2.96\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ could be
used, which would require lasers of energy $650\,$\mathrm{J}$$ and
$300\,$\mathrm{J}$$, respectively [40].

An important consideration to make before extrapolating this work to an
experimental campaign, is predicting the level of noise on the scattering
signal. Many factors can contribute to the noise level such as the self-
emission, the time-gating of the detector, the detector efficiency etc.. For
the sake of simplicity in this paper, these parameters will be collected into
one function, $G$, which we approximate as $10^{-5}$ [41].

##  III Obtaining simulated spatially integrated spectra

Figure 5: Logarithmic fit to background self-emission for 2.8 adiabat target
and a $3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ X-ray probe. The background
self-emission is assumed to fit $A\mathrm{log}^{2}(I)+B\mathrm{log}(I)+C$,
where the constants $A$, $B$ and $C$ are found for each scattering setup.
Figure 6: X-ray scattering data produced by Spect3D for LILAC simulations with
adiabats of $2.8$ and $8.0$. (a) and (b) Forward scattering spectra for a
$2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe and a
$3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe, respectively. (c) and (d)
Backward scattering spectra for a $2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe
and a $3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe, respectively.

The cryogenic DT implosion plasma conditions were calculated using the LILAC
code. The LILAC code is a 1-D spherical lagrangian, radiation-hydrodynamics
code [37] that simulates symmetric, laser direct-drive implosions. It includes
laser ray-tracing with an inverse bremsstrahlung model that can also account
for cross-beam energy transfer [42]. LILAC also includes a nonlocal thermal
transport model that uses a simplified Boltzmann equation with a Krook
collision term [43], multi-group radiation diffusion, and a first-principles
equation-of-state (FPEOS) model [44, 45] and opacity (FPOT) model [46] derived
from molecular dynamics methods.

In this work, the focus is on the time when the capsule is at two-thirds
compression,
$R_{\mathrm{Ablation\,surface}}/R_{\mathrm{Vapor,\,initial}}=2/3$. The
inhomogenity of the plasma results in different scattering signals from
different regions of the plasma. It is paramount that we are able to simulate
fully spatially integrated spectra, accounting for opacity and self-emission
of the plasma in order to determine, for a given scattering geometry, the
dominant scattering features. This provides insightful information to design
the experiments.

SPECT3D is a spectroscopy code produced by Prism Computational Sciences which
post-processes hydrodynamics code output and simulates high-resolution spectra
and images for LTE and non-LTE plasmas in 1-D, 2-D, and 3-D geometries [35].
It computes a variety of diagnostic signatures that can be compared with
experimental measurements including: time-resolved and time-integrated
spectra, space-resolved spectra and streaked spectra, filtered and
monochromatic images, X-ray diode signals. In a SPECT3D simulation, the
radiation incident at a detector is computed by solving the radiative transfer
equation along a series of lines-of-sight (LOSs) through the plasma grid. At
each plasma volume element along a LOS, the frequency-dependent absorption and
emissivity of the plasma is calculated. The scattering cross-section is
computed using local values of the plasma conditions based on the formalism
originally developed in Refs. [47, 48]. Scattered X-ray photons are added to
the local source function, allowing SPECT3D to utilize the same algorithms as
it uses for plasma self-emission. It is assumed that the radiation from a non-
monochromatic, isotropically emitting point-like X-ray source is scattered
within each volume element of the SPECT3D spatial grid. The source is
specified by its photon-energy-dependent intensity and location in 3-D space.
The intensity of the radiation from the source is adjusted for each volume
element based on the distance to the source. It includes attenuation due to
plasma absorption and the change in the solid angle. The radiation flux at
each pixel in the detector plane is calculated by integrating the scattered
radiation along each LOS. The scattering angle is computed for each volume
element based on the LOS and the line that connects the volume element center
and the source [36].

For this paper, an additional feature was added to the original implementation
which allows for certain plasma cells to be excluded from contributing to the
scattered signal. This allows for studying the contribution of particular
plasma regions to the total scattered spectrum. Models for computing self-
emission and absorption coefficients remain the same in each zone regardless
of whether the flag for excluding scattered signal is set or not.

The addition of this feature allows spectra from isolated regions of the
plasma to be compared to the fully integrated spectra in figures 2 and 3. The
inelastic scattering in each detector is dominated by the scattering from the
compressed DT shell. This gives us confidence that an experiment designed to
retrieve scattering spectra at this time during the implosion will be
representative of the conditions in the compressed shell.

Using the output from SPECT3D, simulated experimental data was produced by
first removing the background noise due to the self-emission of the plasma. A
logarithmic fit, was assumed for the background, as shown in Figure 5. Then
random Gaussian noise, with a standard deviation of $7.5\%$ was added to the
signal. The resultant spectrum is shown in figure 6. Note that we have assumed
the noise to be independent of the number of photons per pixel arriving at the
detector. In cases where the signal is weak, the signal will be limited by the
pixel’s photon counts, and in such conditions we would expect the noise to be
larger in the wings of the spectrum. Future work will focus more closely on
the noise error analysis for photon-limited signals.

Utilising XRTS to determine the adiabat of an ICF capsule would be a valuable
diagnostic development. Figure 6 demonstrates that for experimental conditions
with identical scattering setups, the two extreme adiabat conditions
considered here produce notably differing scattering spectra. In both the
$2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ and
$3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ case, the plasmon scattering seen in
the forward scattering detector, can be used to determine the difference in
electron density between the two adiabats. The difference between the
inelastic scattering features from the two adiabats seen in figure 6(c) is a
result of only the low adiabat remaining in the collective scattering regime.
The high adiabat’s inelastic scattering feature has become dominated by
Compton scattering. This is evidenced by the broadening of the inelastic peak
and the lose of a forward plasmon shift peak. This change in scattering
features is evidence of its higher electron temperature.

##  IV Results

Figure 7: MCMC parameter convergence fitting the entire spectrum using equation 4 as a cost function. Variation in DT plasma parameters from; (a) $2.8$ adiabat and $2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe, (b) $8.0$ adiabat and $2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe, (c) $2.8$ adiabat and $3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe, and (d) $8.0$ adiabat and $3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe. The scatter plots show the correlation between each DT parameter. The lower quadrant scatter plots are taken from the $40${}^{\circ}$$ scattering data, whilst the upper quadrant shows the $120${}^{\circ}$$ scattering data. The scatter plots have been coloured to represent the spatial density of points. The diagonal plots show the combined histograms for each parameter from both the scattering regimes. Superimposed on each histogram is a normal distribution of the fits. The mass-averaged parameter values from the LILAC 1-D simulation are highlighted as a green dashed line or cross. Figure 8: As with Figure 7 but for MCMC analysis focused solely on the inelastic scattering using equation 5 as a cost function. As discussed in Section V, the forward scattering analysis has been omitted as the widths of the inelastic scattering features in the forward scattering regime are small relative to the source FWHM. This means, without the elastic scattering feature, MCMC converges around values not representative of the entire spectra. Table 1: The full spectral analysis MCMC DT fitting parameters compared to the mass-weighted parameters from the LILAC 1D simulations, focused on the compressed DT shell, for each adiabat and each probe. DT Parameter | $\mathbf{T_{e}\,($\mathrm{e}\mathrm{V}$)}$ | $\mathbf{n_{e}\,($\mathrm{c}\mathrm{m}^{-3}$)}$ | $\mathbf{Z}$
---|---|---|---
Adiabat $\mathbf{2.8}$
Simulation | $25$ | $5.5\times 10^{23}$ | $0.97$
MCMC $2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ | $26\pm 2$ | $(5.4\pm 0.3)\times 10^{23}$ | $0.94\pm 0.03$
MCMC $3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ | $25\pm 2$ | $(5.4\pm 0.4)\times 10^{23}$ | $0.94\pm 0.03$
Adiabat $\mathbf{8.0}$
Simulation | $38$ | $3.7\times 10^{23}$ | $0.97$
MCMC $2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ | $48\pm 9$ | $(3.1\pm 0.4)\times 10^{23}$ | $0.94\pm 0.04$
MCMC $3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ | $35\pm 3$ | $(3.1\pm 0.5)\times 10^{23}$ | $0.95\pm 0.03$
Table 2:  The inelastic scattering analysis MCMC DT fitting parameters compared to the mass-weighted parameters from the LILAC 1D simulations, focused on the compressed DT shell, for each adiabat and each probe. DT Parameter | $\mathbf{T_{e}\,($\mathrm{e}\mathrm{V}$)}$ | $\mathbf{n_{e}\,($\mathrm{c}\mathrm{m}^{-3}$)}$ | $\mathbf{Z}$
---|---|---|---
Adiabat $\mathbf{2.8}$
Simulation | $25$ | $5.5\times 10^{23}$ | $0.97$
MCMC $2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ | $28\pm 1$ | $(4.7\pm 0.3)\times 10^{23}$ | $0.97\pm 0.02$
MCMC $3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ | $21\pm 1$ | $(5\pm 1)\times 10^{23}$ | $0.95\pm 0.03$
Adiabat $\mathbf{8.0}$
Simulation | $38$ | $3.7\times 10^{23}$ | $0.97$
MCMC $2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ | $44\pm 3$ | $(3.0\pm 0.6)\times 10^{23}$ | $0.97\pm 0.01$
MCMC $3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ | $36\pm 4$ | $(4\pm 2)\times 10^{23}$ | $0.94\pm 0.04$

Before extracting the plasma parameters from the spatially integrated
simulated spectra, the inverse problem instability must first be addressed,
which implies that the same measured spectra could be fitted equally well by
very different plasma parameters [49]. Bayesian inference, using Markov-Chain
Monte Carlo (MCMC) to sample the multidimensional space, is a more robust
approach to explore the behaviour of the complex multiparameter simulations
[50].

Two MCMC explorations that walked through defined parameter spaces to find the
ionization, temperature and density that best fit the forward and backward
scattering spectra individually are presented in this paper. The parameter
space assumed a uniform distribution with linear sampling for the electron
temperature, $1\leq T_{e}(\mathrm{eV})\leq 1e3$, and ionization, $0\leq Z\leq
1$, whilst taking a logarithmic sampling for the electron density,
$1\mathrm{e}20\leq n_{e}(\mathrm{1/cc})\leq 5\mathrm{e}24$. A large sampling
space was used so no bias was placed on the resultant parameters. One
exploration fit the entire spectra, assuming two weighted uniform plasma
regions, one containing DT and the other CH. The cost function used to
determine the appropriateness of each MCMC scattering spectra,
$I_{\mathrm{fit}}$, in this case is

$\beta_{\mathrm{cost}}=\textrm{max}{\left(\frac{I_{\mathrm{fit}}-I_{\mathrm{raw}}}{I_{\mathrm{raw}}}\frac{1}{\sqrt{2}\sigma}\right)^{2}}\,,$
(4)

where $I_{\mathrm{raw}}$ is the synthetic scattering spectra shown in Figure 6
and $\sigma$ is the standard deviation representative of the noise of the
synthetic scattering spectra. In an actual experiment this quantity is not
known a priori and it must be chosen for MCMC to be able to explore a
sufficiently wide parameter space. For the full spectrum analysis we use
$\sigma=0.075$. This cost function allowed for equal weighting of the fit to
the elastic and inelastic peaks.

The alternate MCMC analysis focused solely on the inelastic scattering
features. As previously discussed, the inelastic scattering for all detectors
was dominated by the contribution from the compressed DT shell. Therefore,
this MCMC analysis assumed a single uniform plasma condition containing only
DT. A soft boundary cost function was used in this case as there was no need
to apply weighting to the inelastic scattering,

$\beta_{\mathrm{cost}}=\textrm{max}{\left(\frac{I_{\mathrm{fit}}-I_{\mathrm{raw}}}{\sqrt{2}\sigma}\right)^{2}}\,.$
(5)

For this analysis, a value of $0.0005$ was used for $\sigma$ as this is
representative of the noise when focused on the inelastic scattering region.
The forward likelihood of each fit, $P(I_{\mathrm{fit}}|I_{\mathrm{raw}})$,
was determined as

$P(I_{\mathrm{fit}}|I_{\mathrm{raw}})=\mathrm{e}^{-\beta_{\mathrm{cost}}}\,.$
(6)

To analyse the MCMC data, the DT parameters were plotted on a combined matrix
shown in Figures 7 and 8. The scatter plots for each scattering angle are
shown separately and have been coloured to represent the spatial density of
points. In Figure 7, the histograms along the diagonal are the combined
histograms for both the forward and backward scattering parameters. The mean
and standard deviation on each parameter was calculated by fitting a normal
distribution to the histograms.

The MCMC parameters were compared to the mass-weighted parameters from the 1-D
LILAC simulations. The mass-weighted simulation values were calculated using

$\mathrm{\left<F\right>}=\frac{\sum F_{i}\rho_{i}4\pi
r_{i}^{2}\mathrm{d}r_{i}}{\sum\rho_{i}4\pi r_{i}^{2}\mathrm{d}r_{i}}\,,$ (7)

where $F_{i}$ is the desired parameter in zone $i$. The mass-weighted
parameters were determined for each region of the implosion. It can be seen in
Tables 1 and 2, that the MCMC values were in close agreement with the mass-
weighted parameters from the compressed DT shell. As discussed previously,
this was an expected result, as the high density in the compressed shell meant
it dominated the inelastic scattering features.

##  V Discussion

There is good agreement between the mass-averaged simulation parameter values
and the MCMC distributions. The forward scattering fits tend to converge
around lower densities, higher temperatures and broader ionisations. This
results in either broader or slightly skewed distributions on the DT
parameters. This differing convergence occurs because the ratio between the
source FWHM and the width of the inelastic scattering feature in the forward
scattering case is very small, particularly for the
$2\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe. It would therefore be possible to
obtain information on the compressed DT conditions solely using a backward
scattering detector. In order to improve the fit in the forward scattering
regime, either a narrower bandwidth or a higher energy source should be used.

The forward scattering spectra have not been used to contribute to the MCMC
distributions in Figure 8. As the widths of the inelastic scattering features
in the forward scattering regime are small relative to the source FWHM,
convergence around values representative of the compressed DT shell under
these conditions are highly improbable. This exclusion of the forward
scattering results in much narrower parameter distributions, particularly for
the electron temperature and ionisation. One reason for the tighter fits is
because the low weighting on the CH plasma in the full scattering fits means
MCMC assumes the conditions from the uniform DT plasma region are generating
both the inelastic and the elastic scattering features. However, from Figures
2 and 3 we can see the Rayleigh scattering is dominated by the conditions in
the CH coronal plasma. Therefore, for the electron temperature and ionisation,
better convergence on the compressed shell DT conditions is seen when the
fitting to the elastic scattering feature is ignored.

In contrast, the full spectrum MCMC analysis produces more statistically
accurate results on the electron density. This is due to the inclusion of the
predominately collective scattering forward detector. Inelastic scattering in
the collective scattering spectrum is very sensitive on the electron plasma
frequency (which determines its overall shift), meaning the collective
scattering case is best used to determine the electron density. However, it
should also be noted that removal of the elastic scattering feature leads to
uncertainty as to the magnitude of the inelastic shift. This operation would
therefore be difficult to justify under experimental conditions.

Overall the best agreement between the MCMC analysis on the synthetic
scattering data and the simulations is obtained with the full spectrum
analysis using a $3.5\,$\mathrm{k}\mathrm{e}\mathrm{V}$$ probe. Better
agreement may be achieved when focusing on the inelastic scattering if a
narrower bandwidth probe beam could be used, meaning the forward scattering
does not need to be omitted from the analysis. In fact, this is what it would
feasible with a Free Electron Laser [51].

##  VI Conclusions

In summary, spatially-integrated XRTS spectra for 1-D LILAC simulated
conditions of low- and high-adiabat, DT cryogenic implosions have been
calculated at two-thirds convergence. Markov-Chain Monte Carlo analysis was
performed for two different scattering setups. Information on the compressed
shell conditions was obtained as it has been shown to be possible to use the
spectral resolution in a spatially integrated measurement to discriminate
between different regions in the plasma. Fielding two detectors, one in the
collective and one in the noncollective scattering regime, produced the best
agreement with the compressed shell mass-averaged parameters from the
simulation. This technique can be used to resolve both the low- and high-
adiabat implosions.

In the future, similar analysis will be performed on the conditions at
stagnation as well as investigations into 2-D and 3-D simulations using DRACO
[52] and ASTER [53].

##  VII Acknowledgements

This material is based upon work supported by the Department of Energy
National Nuclear Security Administration under Award Number DE-NA0003856.

M.F.K. and S.M.V. acknowledge support from the UK EPSRC grant EP/P015794/1 and
the Royal Society. S.M.V. is a Royal Society University Research Fellow.

##  VIII AIP Publishing Data Sharing Policy

The data that supports the findings of this study are available from the
corresponding author, H.P., upon reasonable request.

## References

  * Lindl  _et al._ [2004] J. D. Lindl, P. Amendt, R. L. Berger, S. G. Glendinning, S. H. Glenzer, S. W. Haan, R. L. Kauffman, O. L. Landen, and L. J. Suter, Phys. Plasmas 11, 339 (2004).
  * Hurricane  _et al._ [2014] O. A. Hurricane, D. A. Callahan, D. T. Casey, P. M. Celliers, C. Cerjan, E. L. Dewald, T. R. Dittrich, T. Döppner, D. E. Hinkel, L. F. B. Hopkins, J. L. Kline, S. L. Pape, T. Ma, A. G. MacPhee, J. L. Milovich, A. Pak, H.-S. Park, P. K. Patel, B. A. Remington, J. D. Salmonson, and P. T. S. . R. Tommasini, Nature 506, 343 (2014).
  * Regan  _et al._ [2018] S. P. Regan, V. N. Goncharov, T. C. Sangster, E. M. Campbell, R. Betti, J. W. Bates, K. Bauer, T. Bernat, S. Bhandarkar, T. R. Boehly, M. J. Bonino, A. Bose, D. Cao, L. Carlson, R. Chapman, T. Chapman, G. W. Collins, T. J. B. Collins, R. S. Craxton, J. A. Delettrez, D. H. Edgell, R. Epstein, M. Farrell, C. J. Forrest, R. K. Follett, J. A. Frenje, D. H. Froula, M. G. Johnson, C. R. Gibson, L. Gonzalez, C. Goyon, V. Y. Glebov, V. Gopalaswamy, A. Greenwood, D. R. Harding, M. Hohenberger, S. X. Hu, H. Huang, J. Hund, I. V. Igumenshchev, D. W. Jacobs-Perkins, R. T. Janezic, M. Karasik, J. H. Kelly, T. J. Kessler, J. P. Knauer, T. Z. Kosc, R. Luo, S. J. Loucks, J. A. Marozas, F. J. Marshall, M. Mauldin, R. L. McCrory, P. W. McKenty, D. T. Michel, P. Michel, J. D. Moody, J. F. Myatt, A. Nikroo, P. M. Nilson, S. P. Obenschain, J. P. Palastro, J. Peebles, R. D. Petrasso, N. Petta, P. B. Radha, J. E. Ralph, M. J. Rosenberg, S. Sampat, A. J. Schmitt, M. J. Schmitt, M. Schoff, W. Seka, R. Shah, J. R. Rygg, J. G. Shaw, R. Short, W. T. Shmayda, M. J. Shoup, A. Shvydky, A. A. Solodov, C. Sorce, M. Stadermann, C. Stoeckl, W. Sweet, C. Taylor, R. Taylor, W. Theobald, D. P. Turnbull, J. Ulreich, M. D. Wittman, K. M. Woo, K. Youngblood, , and J. D. Zuegel, Nucl. Fusion 59, 3 (2018).
  * Goncharov  _et al._ [2017] V. N. Goncharov, S. P. Regan, E. M. Campbell, T. C. Sangster, P. B. Radha, J. F. Myatt, D. H. Froula, R. Betti, T. R. Boehly, J. A. Delettrez, D. H. Edgell, R. Epstein, C. J. Forrest, V. Y. Glebov, D. R. Harding, S. X. Hu, I. V. Igumenshchev, F. J. Marshall, R. L. McCrory, D. T. Michel, W. Seka, A. Shvydky, C. Stoeckl, W. Theobald, , and M. Gatu-Johnson, Nucl. Fusion 59, 014008 (2017).
  * Campbell  _et al._ [2017] E. M. Campbell, V. N. Goncharov, T. C. Sangster, S. P. Regan, P. B. Radha, R. Betti, J. F. Myatt, D. H. Froula, M. J. Rosenberg, I. V. Igumenshchev, W. Seka, A. A. Solodov, A. V. Maximov, J. A. Marozas, T. J. B. Collins, D. Turnbull, F. J. Marshall, A. Shvydky, J. P. Knauer, R. L. McCrory, A. B. Sefkow, M. Hohenberger, P. A. Michel, T. Chapman, L. Masse, C. Goyon, S. Ross, J. W. Bates, M. Karasik, J. Oh, J. Weaver, A. J. Schmitt, K. Obenschain, S. P. Obenschain, S. Reyes, and B. V. Wonterghem, Nucl. Fusion 2, 37 (2017).
  * Gaffney  _et al._ [2018] J. A. Gaffney, S. X. Hu, P. Arnault, A. Becker, L. X. Benedict, T. R. Boehly, P. M. Celliers, D. M. Ceperley, O. Čertík, J. Clérouin, G. W. Collins, L. A. Collins, J.-F. Danel, N. Desbiens, M. W. C. Dharma-wardana, Y. H. Ding, A. Fernandez-Pañella, M. C. Gregor, P. E. Grabowski, S. Hamel, S. B. Hansen, L. Harbour, X. T. He, D. D. Johnson, W. Kang, V. V. Karasiev, L. Kazandjian, M. D. Knudson, T. Ogitsu, C. Pierleoni, R. Piron, R. Redmer, G. Robert, D. Saumon, A. Shamp, T. Sjostrom, A. V. Smirnov, C. E. Starrett, P. A. Sterne, A. Wardlow, H. D. Whitley, B. Wilson, P. Zhang, and E. Zurek, High Energy Density Phys. 28, 7 (2018).
  * Hu  _et al._ [2010] S. X. Hu, B. Militzer, V. N. Goncharov, and S. Skupsky, Phys. Rev. Lett. 104, 235003 (2010).
  * Hu  _et al._ [2018] S. X. Hu, L. A. Collins, T. R. Boehly, Y. H. Ding, P. B. Radha, V. N. Goncharov, V. V. Karasiev, G. W. Collins, S. P. Regan, and E. M. Campbell, Phys. Plasmas 25, 056306 (2018).
  * Hu [2017] S. X. Hu, Phys. Rev. Lett. 119, 065001 (2017).
  * Wang  _et al._ [2013] C. Wang, Y. Long, X. He, J.-F. Wu, W.-H. Ye, and P. Zhang, Phys. Rev. E 88, 013106 (2013).
  * Vinko  _et al._ [2013] S. M. Vinko, O. Ciricosta, and J. S. Wark, Nature Comms. 5, 3533 (2013).
  * Chapman  _et al._ [2015] D. A. Chapman, J. Vorberger, L. B. Fletcher, R. A. Baggott, L. Divol, T. Döppner, R. W. Falcone, S. H. Glenzer, G. Gregori, T. M. Guymer, A. L. Kritcher, O. L. Landen, T. Ma, A. E. Pak, and D. O. Gericke, Nature Comms. 6, 6839 (2015).
  * White  _et al._ [2014] T. G. White, N. J. Hartley, B. Borm, B. J. B. Crowley, J. W. O. Harris, D. C. Hochhaus, T. Kaempfer, K. Li, P. Neumayer, L. K. Pattison, F. Pfeifer, S. Richardson, A. P. L. Robinson, I. Uschmann, , and G. Gregori, Phys. Rev. Lett. 112, 145005 (2014).
  * Grabowski  _et al._ [2020] P. Grabowski, S. Hansen, M. Murillo, L. Stanton, F. Graziani, A. Zylstra, S. Baalrud, P. Arnault, A. Baczewski, L. Benedict, C. Blancard, O. Čertík, J. Clérouin, L. Collins, S. Copeland, A. Correa, J. Dai, J. Daligault, M. Desjarlais, M. Dharma-wardana, G. Faussurier, J. Haack, T. Haxhimali, A. Hayes-Sterbenz, Y. Hou, S. Hu, D. Jensen, G. Jungman, G. Kagan, D. Kang, J. Kress, Q. Ma, M. Marciante, E. Meyer, R. Rudd, D. Saumon, L. Shulenburger, R. Singleton, T. Sjostrom, L. Stanek, C. Starrett, C. Ticknor, S. Valaitis, J. Venzke, and A. White, High Energy Density Physics 37, 100905 (2020).
  * Hurricane  _et al._ [2019] O. A. Hurricane, P. T. Springer, P. K. Patel, D. A. Callahan, K. Baker, D. T. Casey, L. Divol1, T. Döppner, D. E. Hinkel, M. Hohenberger, L. F. B. Hopkins, C. Jarrott, A. Kritcher, S. L. Pape, S. Maclaren, L. Masse, A. Pak, J. Ralph, C. Thomas, P. Volegov, , and A. Zylstra, Phys. Plasmas 26, 052704 (2019).
  * Glebov  _et al._ [2010] V. Y. Glebov, T. C. Sangster, C. Stoeckl, J. P. Knauer, W. Theobald, K. L. Marshall, M. J. S. III, T. Buczek, M. Cruz, T. Duffy, M. Romanofsky, M. Fox, A. Pruyne, M. J. Moran, R. A. Lerche, J. McNaney, J. D. Kilkenny, M. J. Eckart, D. Schneider, D. Munro, W. Stoeffl, R. Zacharias, J. J. Haslam, T. Clancy, M. Yeoman, D. Warwas, C. J. Horsfield, J.-L. Bourgade, O. Landoas, L. Disdier, G. A. Chandler, , and R. J. Leeper, Rev. Sci. Instrum. 81, 10D325 (2010).
  * Regan  _et al._ [2012] S. P. Regan, K. Falk, G. Gregori, P. B. Radha, S. X. Hu, T. R. Boehly, B. J. B. Crowley, S. H. Glenzer, O. L. Landen, D. O. Gericke, T. Döppner, D. D. Meyerhofer, C. D. Murphy, T. C. Sangster, , and J. Vorberger, Phys. Rev. Letters 109, 265003 (2012).
  * Glenzer and Redmer [2009] S. H. Glenzer and R. Redmer, Rev. of Modern Phys. 81, 1625 (2009).
  * Gregori  _et al._ [2008] G. Gregori, S. H. Glenzer, K. B. Fournier, K. M. Campbell, E. L. Dewald, O. S. Jones, J. H. Hammer, S. B. Hansen, R. J. Wallace, , and O. L. Landen, Phys. Rev. Lett. 101, 045003 (2008).
  * Chapman  _et al._ [2014] D. A. Chapman, D. Kraus, A. L. Kritcher, B. Bachmann, G. W. Collins, R. W. Falcone, J. A. Gaffney, D. O. Gericke, S. H. Glenzer, T. M. Guymer, J. A. Hawreliak, O. L. Landen, S. L. Pape, T. Ma, P. Neumayer, J. Nilsen, A. Pak, R. Redmer, D. C. Swift, J. Vorberger, and T. Döppner, Phys. Plasmas 21, 082709 (2014).
  * Gamboa  _et al._ [2014] E. J. Gamboa, P. A. Keiter, R. P. Drake, K. Falk, D. S. Montgomery, and J. F. Benage, High Energy Density Physics 11, 75 (2014).
  * Boehly  _et al._ [1997] T. R. Boehly, D. L. Brown, R. S. Craxton, R. L. Keck, J. P. Knauer, J. H. Kelly, T. J. Kessler, S. A. Kumpan, S. J. Loucks, S. A. Letzring, F. J. Marshall, R. L. McCrory, S. F. B. Morse, W. Seka, J. M. Soures, and C. P. Verdon, Optics Communications 133, 495 (1997).
  * Gamboa  _et al._ [2012] E. J. Gamboa, C. M. Huntington, M. R. Trantham, P. A. Keiter, R. P. Drake, D. S. Montgomery, J. F. Benage, and S. A. Letzring, Rev. of Sci. Instrum. 83, 10E108 (2012).
  * Davis  _et al._ [2016] P. Davis, T. Döppner, J. R. Rygg, C. Fortmann, L. Divol, A. Pak, L. Fletcher, A. Becker, B. Holst, P. Sperling, R. Redmer, M. P. Desjarlais, P. Celliers, G. W. Collins, O. L. Landen, and R. W. F. . S. H. Glenzer, Nature Comm. 7, 11189 (2016).
  * Lindl [1998] J. Lindl,  _Inertial Confinement Fusion_ (Springer, New York, 1998).
  * Craxton  _et al._ [2015] R. S. Craxton, K. S. Anderson, T. R. Boehly, V. N. Goncharov, D. R. Harding, J. P. Knauer, R. L. McCrory, P. W. McKenty, D. D. Meyerhofer, J. F. Myatt, A. J. Schmitt, J. D. Sethian, R. W. Short, S. Skupsky, W. Theobald, W. L. Kruer, K. Tanaka, R. Betti, T. J. B. Collins, J. A. Delettrez, S. X. Hu, J. A. Marozas, A. V. Maximov, D. T. Michel, P. B. Radha, S. P. Regan, T. C. Sangster, W. Seka, A. A. Solodov, J. M. Soures, C. Stoeckl, and J. D. Zuegel, Phys. Plasmas 22, 110501 (2015).
  * Betti and Hurricane [2016] R. Betti and O. Hurricane, Nature Phys. 12, 435 (2016).
  * Atzeni and Meyer-Ter-Vehn [2004] S. Atzeni and J. Meyer-Ter-Vehn,  _The Physics of Inertial Fusion_ (Oxford University Press, 2004).
  * Landen  _et al._ [2020] O. L. Landen, D. T. Casey, J. M. DiNicola, T. Doeppner, E. P. Hartouni, D. E. Hinkel, L. F. B. Hopkins, M. Hohenberger, A. L. Kritcher, S. L. Pape, B. J. MacGowan, S. Maclaren, K. D. Meaney, M. Millot, P. K. Patel, J. Park, L. A. Pickworth, H. F. Robey, J. S. Ross, S. T. Yang, A. B. Zylstra, K. L. Baker, D. A. Callahan, P. M. Celliers, M. J. Edwards, O. A. Hurricane, J. D. Lindl, J. D. Moody, J. Ralph, V. A. Smalyuk, C. A. Thomas, B. M. V. Wonterghem, and C. R. Weber, High Energy Density Phys. 36, 100755 (2020).
  * Edwards  _et al._ [2013] M. J. Edwards, P. K. Patel, J. D. Lindl, L. J. Atherton, S. H. Glenzer, S. W. Haan, J. D. Kilkenny, O. L. Landen, E. I. Moses, A. Nikroo, R. Petrasso, T. C. Sangster, P. T. Springer, S. Batha, R. Benedetti, L. Bernstein, R. Betti, D. L. Bleuel, T. R. Boehly, D. K. Bradley, J. A. Caggiano, D. A. Callahan, P. M. Celliers, C. J. Cerjan, K. C. Chen, D. S. Clark, G. W. Collins, E. L. Dewald, L. Divol, S. Dixit, T. Doeppner, D. H. Edgell, J. E. Fair, M. Farrell, R. J. Fortner, J. Frenje, M. G. G. Johnson, E. Giraldez, V. Y. Glebov, G. Grim, B. A. Hammel, A. V. Hamza, D. R. Harding, S. P. Hatchett, N. Hein, H. W. Herrmann, D. Hicks, D. E. Hinkel, M. Hoppe, W. W. Hsing, N. Izumi, B. Jacoby, O. S. Jones, D. Kalantar, R. Kauffman, J. L. Kline, J. P. Knauer, J. A. Koch, B. J. Kozioziemski, G. Kyrala, K. N. LaFortune, S. L. Pape, R. J. Leeper6, R. Lerche, T. Ma, B. J. MacGowan, A. J. MacKinnon, A. Macphee, E. R. Mapoles, M. M. Marinak, M. Mauldin, P. W. McKenty, M. Meezan, P. A. Michel, J. Milovich, J. D. Moody, M. Moran, D. H. Munro, C. L. Olson6, K. Opachich, A. E. Pak, T. Parham, H.-S. Park, J. E. Ralph, S. P. Regan, B. Remington, H. Rinderknecht, H. F. Robey, M. Rosen, S. Ross, J. D. Salmonson, J. Sater, D. H. Schneider, F. H. Séguin, S. M. Sepke, D. A. Shaughnessy, V. A. Smalyuk, B. K. Spears, C. Stoeckl, W. Stoeffl, L. Suter, C. A. Thomas, R. Tommasini, R. P. Town, S. V. Weber, P. J. Wegner, K. Widman, M. Wilke, D. C. Wilson, C. B. Yeamans, , and A. Zylstra3, Phys. Plasmas 20, 070501 (2013).
  * Anderson and Betti [2004] K. Anderson and R. Betti, Phys. Plasmas 11, 5 (2004).
  * Melvin  _et al._ [2015] J. Melvin, H. Lim, V. Rana, B. Cheng, J. Glimm, D. H. Sharp, and D. C. Wilson, Phys. Plasmas 22, 022708 (2015).
  * Dittrich  _et al._ [2014] T. R. Dittrich, O. A. Hurricane, D. A. Callahan, E. L. Dewald, T. Döppner, D. E. Hinkel, L. F. B. Hopkins, S. L. Pape, T. Ma, J. L. Milovich, J. C. Moreno, P. K. Patel, H.-S. Park, B. A. Remington, J. D. Salmonson, , and J. L. Kline, Phys. Rev. Letters 112, 055002 (2014).
  * Cerjan  _et al._ [2013] C. Cerjan, P. T. Springer, and S. M. Sepke, Phys. Plasmas 20, 056319 (2013).
  * MacFarlane  _et al._ [2007] J. J. MacFarlane, I. Golovkin, P. Wang, P. R. Woodruff, and N. A. Pereyra, High Energy Density Phys. 3, 181 (2007).
  * Golovkin  _et al._ [2013] I. Golovkin, J. J. MacFarlane, P. Woodruff, I. Hall, G. Gregori, J. Bailey, E. Harding, T. Ao, and S. Glenzer, High Energy Density Phys. 9, 510 (2013).
  * Delettrez  _et al._ [1987] J. Delettrez, R. Epstein, M. Richardson, P. A. Jaanimagi, and B. L. Henke, Phys. Rev. A 36, 3926 (1987).
  * Stoeckl  _et al._ [2014] C. Stoeckl, M. Bedzyk, G. Brent, R. Epstein, G. Fiksel, D. Guy, V. N. Goncharov, S. X. Hu, S. Ingraham, D. W. Jacobs-Perkins, R. K. Jungquist, F. J. Marshall, C. Mileham, P. M. Nilson, T. C. Sangster, M. J. Shoup, and W. Theobald, Rev. Sci. Instrum. 85, 11E501 (2014).
  * Stoeckl  _et al._ [2017] C. Stoeckl, R. Epstein, R. Betti, W. Bittle, J. A. Delettrez, C. J. Forrest, V. Y. Glebov, V. N. Goncharov, D. R. Harding, I. V. Igumenshchev, D. W. Jacobs-Perkins, R. T. Janezic, J. H. Kelly, T. Z. Kosc, R. L. McCrory, D. T. Michel, C. Mileham, P. W. McKenty, F. J. Marshall, S. F. B. Morse, S. P. Regan, P. B. Radha, B. Rice, T. C. Sangster, M. J. Shoup, W. T. Shmayda, C. Sorce, W. Theobald, J. Ulreich, M. D. Wittman, D. D. Meyerhofer, J. A. Frenje, M. G. Johnson, and R. D. Petrasso, Physics of Plasmas 24, 056304 (2017).
  * Urry  _et al._ [2006] M. K. Urry, G. Gregori, O. L. Landen, A. Pak, and S. H. Glenzer, J. Quant. Spectroscopy and Rad. Transfer 99, 636 (2006).
  * Pak  _et al._ [2004] A. Pak, G. Gregori, J. Knight, K. Campbell, D. Price, B. Hammel, O. L. Landen, , and S. H. Glenzer, Rev. of Sci. Instrum. 75, 3747 (2004).
  * Igumenshchev  _et al._ [2010] I. V. Igumenshchev, D. H. Edgell, V. N. Goncharov, J. A. Delettrez, A. V. Maximov, J. F. Myatt, W. Seka, A. Shvydky, S. Skupsky, and C. Stoeckl, Physics of Plasmas 17, 122708 (2010).
  * Goncharov  _et al._ [2006] V. N. Goncharov, O. V. Gotchev, E. Vianello, T. R. Boehly, J. P. Knauer, P. W. McKenty, P. B. Radha, S. P. Regan, T. C. Sangster, S. Skupsky, V. A. Smalyuk, R. Betti, R. L. McCrory, D. D. Meyerhofer, and C. Cherfils-Clérouin, Physics of Plasmas 13, 012702 (2006).
  * [44] S. X. Hu, B. Militzer, V. N. Goncharov, and S. Skupsky, Phys. Rev. B 84, 224109.
  * Hu  _et al._ [2015] S. X. Hu, L. A. Collins, V. N. Goncharov, J. D. Kress, R. L. McCrory, and S. Skupsky, Phys. Rev. E 92, 043104 (2015).
  * Hu  _et al._ [2014] S. X. Hu, L. A. Collins, V. N. Goncharov, T. R. Boehly, R. Epstein, R. L. McCrory, and S. Skupsky, Phys. Rev. E 90, 033111 (2014).
  * Gregori  _et al._ [2003] G. Gregori, S. H. Glenzer, W. Rozmus, R. W. Lee, and O. L. Landen, Phys. Rev. E 67, 026412 (2003).
  * Crowley and Gregori [2013] B. J. B. Crowley and G. Gregori, New J. of Phys. 15, 015014 (2013).
  * Kasim  _et al._ [2019] M. Kasim, T. P. Galligan, J. Topp-Mugglestone, G. Gregori, and S. M. Vinko, Phys. Plasmas 26, 112706 (2019).
  * Andrieu  _et al._ [2003] C. Andrieu, N. de Freitas, A. Doucet, and M. Jordan, Mach. Learn. 50, 5 (2003).
  * Fletcher  _et al._ [2015] L. B. Fletcher, H. J. Lee, T. Döppner, E. Galtier, B. Nagler, P. Heimann, C. Fortmann, S. LePape, T. Ma, M. Millot, A. Pak, D. Turnbull, D. A. Chapman, D. O. Gericke, J. Vorberger, T. White, G. Gregori, M. Wei, B. Barbrel, R. W. Falcone, C.-C. Kao, H. Nuhn, J. Welch, U. Zastrau, P. Neumayer, J. B. Hastings, and S. H. Glenzer, Nature Photonics 9, 274 (2015).
  * Radha  _et al._ [2005] P. B. Radha, T. J. B. Collins, J. A. Delettrez, Y. Elbaz, R. Epstein, V. Y. Glebov, V. N. Goncharov, R. L. Keck, J. P. Knauer, J. A. Marozas, F. J. Marshall, R. L. McCrory, P. W. McKenty, D. D. Meyerhofer, S. P. Regan, T. C. Sangster, W. Seka, D. Shvarts, S. Skupsky, Y. Srebro, and C. Stoeckl, Phys. Plasmas 12, 056307 (2005).
  * Igumenshchev  _et al._ [2016] I. V. Igumenshchev, V. N. Goncharov, F. J. Marshall, J. P. Knauer, E. M. Campbell, C. J. Forrest, D. H. Froula, V. Y. Glebov, R. L. McCrory, S. P. Regan, T. C. Sangster, S. Skupsky, and C. Stoeckl, Phys. Plasmas 23, 052702 (2016).