# Classically Spoofing System Linear Cross Entropy Score Benchmarking

Andrew Tanggara<EMAIL_ADDRESS>Centre for Quantum Technologies,
National University of Singapore, 3 Science Drive 2, Singapore 117543.
Nanyang Quantum Hub, School of Physical and Mathematical Sciences, Nanyang
Technological University, Singapore 639673.  Mile Gu
<EMAIL_ADDRESS>Nanyang Quantum Hub, School of Physical and
Mathematical Sciences, Nanyang Technological University, Singapore 639673.
Centre for Quantum Technologies, National University of Singapore, 3 Science
Drive 2, Singapore 117543.  Kishor Bharti<EMAIL_ADDRESS>A*STAR
Quantum Innovation Centre (Q.InC), Institute of High Performance Computing
(IHPC), Agency for Science, Technology and Research (A*STAR), 1 Fusionopolis
Way, #16-16 Connexis, Singapore, 138632, Republic of Singapore.  Centre for
Quantum Engineering, Research and Education, TCG CREST, Sector V, Salt Lake,
Kolkata 700091, India.

(August 28, 2024)

###### Abstract

In recent years, several experimental groups have claimed demonstrations of
“quantum supremacy” or computational quantum advantage. A notable first claim
by Google Quantum AI revolves around a metric called the Linear Cross Entropy
Benchmarking (Linear XEB), which has been used in multiple quantum supremacy
experiments since. The complexity-theoretic hardness of spoofing Linear XEB
has nevertheless been doubtful due to its dependence on the Cross-Entropy
Quantum Threshold (XQUATH) conjecture put forth by Aaronson and Gunn, which
has been disproven for sublinear depth circuits. In efforts on demonstrating
quantum supremacy by quantum Hamiltonian simulation, a similar benchmarking
metric called the System Linear Cross Entropy Score (sXES) holds firm in light
of the aforementioned negative result due to its fundamental distinction with
Linear XEB. Moreover, the hardness of spoofing sXES complexity-theoretically
rests on the System Linear Cross-Entropy Quantum Threshold Assumption
(sXQUATH), the formal relationship of which to XQUATH is unclear. Despite the
promises that sXES offers for future demonstration of quantum supremacy, in
this work we show that it is an unsound benchmarking metric. Particularly, we
prove that sXQUATH does not hold for sublinear depth circuits and present a
classical algorithm that spoofs sXES for experiments corrupted with noise
larger than certain threshold.

## Introduction.—

In $2019$, the Google quantum AI team claimed the first experimental
demonstration of “quantum supremacy,” [1] or computational quantum advantage
using a $53$ qubits superconducting circuit [2], signifying a major leap
forward in practical quantum computing and challenging the extended Church-
Turing thesis [3]. In verifying that their circuit is correctly performing a
task called quantum random circuit sampling (RCS), they tested their samples
using a metric called “Linear Cross-Entropy Benchmarking (Linear XEB)” [4, 5,
6, 7, 8, 9]. Since then, multiple RCS experiments [10, 11, 12] have their
quantum supremacy claims verified by Linear XEB method, or a variant thereof.
Skepticism on these claims have been raised, particularly by classical
simulations of Google’s RCS experiment [13, 14, 15, 16, 17, 18] showing
significantly shorter classical runtime compared to their initial estimation
of $10,000$ years. Moreover, theoretical results on classical simulation of
different RCS variants [19, 20, 21, 22, 23, 24] cast doubts on the complexity-
theoretic hardness of spoofing Linear XEB that rests on the cross entropy
quantum threshold assumption (XQUATH) conjecture proposed by Aaronson and Gunn
[25]. Recent demonstration that XQUATH does not hold for sublinear depth RCS
[23], further diminishes the legitimacy of Linear XEB as a benchmark for
quantum supremacy.

In the ongoing pursuit of quantum supremacy by the way of near-term quantum
Hamiltonian simulation, a variant of Linear XEB called the System Linear Cross
Entropy Score (sXES) has been proposed [26]. Structural difference between the
circuits assessed by sXES and other Linear XEB variants renders it unclear
whether existing Linear XEB spoofing methods such as [19, 21, 23] can be used
for sXES. Moreover the hardness of spoofing sXES lies upon a complexity-
theoretic conjecture known as the System Linear Cross-Entropy Quantum
Threshold Assumption (sXQUATH), the formal relationship of which to XQUATH is
unknown. These fundamental distinctions from other Linear XEB variants thus
renders sXES a promising verification method in future claims of quantum
supremacy experiments. For a more extensive discussion on these nontrivial
relationships, see Appendices A and D.

In this work, we go beyond the technique in [23] to show that there exists an
efficient classical algorithm that approximates the experiment sufficiently
well to refute sXQUATH (see Theorem 1). At the same time, we also show
explicitly that our algorithm spoofs the sXES benchmark (see Theorem 2) for
noisy experiments. Our algorithm approximates the output probability
distribution of a family of quantum circuits known as the Minimal Quantum
Singular Value Transform (mQSVT) circuit [26], which sXES assessed upon. While
the mQSVT circuits bear the power to implement any quantum algorithm that
falls into the Quantum Singular Value Transform (QSVT) framework [27] (such as
Szegedy quantum walk [28] and quantum solver for system of linear equations
[29] and Hamiltonian simulation tasks [30, 31]), our results suggest that a
more robust benchmarking method is necessary for any claim of quantum
supremacy experiment.

## Spoofing mQSVT circuit benchmarking.—

An mQSVT circuit $\mathtt{mQSVT}(U)$ (see Fig. 1) consists of $d$ “blocks”,
each containing a copy of $n+1$ qubit unitary $U$ and a copy of its conjugate
$U^{\dagger}$. Denote the depth of $U$ as $d_{U}$ so that we can write
$U=U_{d_{U}}\dots U_{1}$ where $U_{j}$ is the $j$-th layer of $U$. These
unitaries are interleaved by phase shift gates $R(\varphi)$ at the top
register with carefully chosen phases (as discussed in the supplementary
material of [26]). Samples from an mQSVT circuit are obtained from measuring
the bottom $n$ registers conditioned on measurement of the top register being
$0$. The outcome probability of an $n$-bit string $x$ is therefore
$p(U,x)=|\langle 0x|\mathtt{mQSVT}(U)|0^{n+1}\rangle|^{2}$ (for an explicit
expression of the output probability of an mQSVT circuit, see Appendix C).
Here we consider unitaries $U$ consisting only of two-qubit gates such that in
each layer, every qubit register is evolved by precisely one two-qubit gate
without any geometric locality assumption (hence $n+1$ is even). This is the
unitary architecture assumed for the RCS simulation result in [23].

Figure 1: mQSVT circuit $\mathtt{mQSVT}(U)$ where $U$ is a random $n+1$ qubit
unitary made out of 2 qubit Haar-random unitaries and $R(\varphi)$ is
$Z$-rotation gate with angle $\varphi$.

For a noisy mQSVT Hamiltonian simulation experiment, a benchmarking scheme
similar to XEB benchmarking used in RCS experiment [2, 10, 11], called the
average system linear cross-entropy score (sXES) [26] was proposed. For a
given ideal mQSVT circuit $\mathtt{mQSVT}(U)$ and (empirically approximated)
experimental probability $p_{\mathrm{exp}}(U,x)$ of output $x$, its sXES is
given by

$\displaystyle{\mathbb{E}}_{U}[\mathrm{sXES}(U)]=\sum_{x\neq
0^{n}}{\mathbb{E}}_{U}[p(U,x)\,p_{\mathrm{exp}}(U,x)]\;,$ (1)

where ${\mathbb{E}}_{U}$ is expectation over random $U$. An experiment with
high sXES indicates a high circuit fidelity as it assigns a high probability
$p_{\mathrm{exp}}(U,x)$ to string $x$ with high ideal probability $p(U,x)$,
hence higher sXES.

Computational hardness of classically spoofing sXES can be reduced to the
system linear cross-entropy heavy output generation (sXHOG) sampling problem
[26]. However, the hardness of classically solving sXHOG (with a high
probability and a suitable choice of number of samples) holds only under a
conjecture called the System linear cross-entropy quantum threshold assumption
(sXQUATH) [26]. sXQUATH conjecture states that there is no polynomial-time
classical algorithm taking an efficient description of $n+1$-qubit unitary $U$
and $n$ bit string $x$ as inputs and outputs an approximation $q(U,x)$ of
mQSVT output probability $p(U,x)$ such that

$\displaystyle\textup{sXQ}=\mathcal{E}\Big{(}p(U,X),\frac{1}{2^{n}}\Big{)}-\mathcal{E}\Big{(}p(U,X),q(U,X)\Big{)}\geq
c2^{-3n}$ (2)

for some constant $c$ and large enough $n$. Here,
$\mathcal{E}(f,g):={\mathbb{E}}_{U,X}[(f(U,X)-g(U,X))^{2}]$ is the mean-
squared error (MSE) between functions $f$ and $g$ and ${\mathbb{E}}_{U,X}$ is
expectation over uniformly random variable
$X\in\\{0,1\\}^{n}\backslash\\{0^{n}\\}$ and over Haar-random two-qubit gates
in $n+1$-qubit unitary $U$.

Now we present our main result below in Theorem 1, which states that sXQUATH
generally does not hold. Particularly for a single-block mQSVT circuit (i.e.
with $d=1$) and a sublinear depth unitary $U$, one can construct a classical
algorithm running in time polynomial in $n$ with a non-negligibly less MSE
than the trivial approximation.

######  Theorem 1.

There exists an efficient classical algorithm taking an efficient description
of $n+1$-qubit unitary $U$ with sublinear depth $d_{U}=o(n)$ and $n$ bit
string $x$ as inputs and outputs an approximation $q(U,x)$ of a single-block
mQSVT circuit output probability $p(U,x)$ that satisfies eqn. (2).

We further show that our algorithm spoofs mQSVT circuits with sufficiently
large noise. As mQSVT circuits with completely depolarizing noise have uniform
output probability, its sXES is
${\mathbb{E}}_{U}[\mathrm{sXES}(U)]=2^{-n}\sum_{x\neq
0}{\mathbb{E}}_{U}[p(U,x)]$, indicating no correlation with the ideal
probability $p(U,x)$. Our algorithm spoofs sXES of all mQSVT circuits with
depolarizing noise above a certain threshold (such that it is close to
$2^{-n}\sum_{x\neq 0}{\mathbb{E}}_{U}[p(U,x)]$).

######  Theorem 2.

There exists an efficient classical algorithm spoofing sXES for all noisy
single-block mQSVT circuit with $n+1$-qubit unitary $U$ such that its sXES is
at most $2^{-n}(\sum_{x\neq 0}{\mathbb{E}}_{U}[p(U,x)]+c^{d_{U}})$ for some
constant $c>0$.

If we consider mQSVT circuit corrupted with depolarizing noise with noise
strength $\gamma\in[0,1]$ on each of its register in each layer, then for
sufficiently large $\gamma$ its sXES score is going to be less than
$2^{-n}(\sum_{x\neq 0}{\mathbb{E}}_{U}[p(U,x)]+c^{d_{U}})$. Theorem 2
indicates that the sXES all such noisy mQSVT circuit is spoofed by our
algorithm.

Classical algorithm that refutes sXQUATH and spoofs sXES benchmark in Theorem
1 and Theorem 2 above is from a family of algorithms called the Pauli path
algorithms. The proofs will be given momentarily after we lay out the Pauli
path framework below. We will also discuss how the existing instances of Pauli
path algorithm used to classically simulate quantum circuits [32, 19, 23] are
not directly applicable to mQSVT circuit, mainly due to the existence of
multiple copies of random unitaries.

## Pauli path algorithm.—

Given an $n$-qubit unitary quantum circuit $C=C_{d}C_{d-1}\dots C_{1}$ (where
$C_{j}$ is its $j$-th layer), Pauli path algorithm classically computes its
output probabilities by expanding density matrices at every layer in terms of
normalized $n$-qubit Pauli matrices
$\mathcal{P}_{n}=\\{I/\sqrt{2},X/\sqrt{2},Y/\sqrt{2},Z/\sqrt{2}\\}^{\otimes
n}$. At the input, we get
$|{0^{n}}\rangle\mkern-4.0mu\langle{0^{n}}|=\sum_{s_{1}\in\mathcal{P}_{n}}s_{1}\textup{Tr}(s_{1}|{0^{n}}\rangle\mkern-4.0mu\langle{0^{n}}|)$.
We can substitute this expansion to the density matrix after the first layer,
$\rho_{1}:=C_{1}|{0^{n}}\rangle\mkern-4.0mu\langle{0^{n}}|C_{1}^{\dagger}$
then expand it in the same manner to get
$\rho_{1}=\sum_{s_{1},s_{2}\in\mathcal{P}_{n}}s_{2}\textup{Tr}(s_{2}C_{1}s_{1}C_{1}^{\dagger})\textup{Tr}(s_{1}|{0^{n}}\rangle\mkern-4.0mu\langle{0^{n}}|)$.
Repeating this for the remaining layers and for measurement
$|{x}\rangle\mkern-4.0mu\langle{x}|$, we obtain transition amplitudes defined
by $\llangle
s_{1}|0^{n}\rrangle:=\textup{Tr}(s_{1}|{0^{n}}\rangle\mkern-4.0mu\langle{0^{n}}|)$
and $\llangle
s_{j+1}|C_{j}|s_{j}\rrangle:=\textup{Tr}(s_{j+1}C_{j}s_{j}C_{j}^{\dagger})$
and $\llangle
x|s_{d+1}\rrangle:=\textup{Tr}(|{x}\rangle\mkern-4.0mu\langle{x}|s_{d+1})$.
For transition amplitude $\llangle s_{j+1}|C_{j}|s_{j}\rrangle$, we call
$s_{j}$ an input Pauli and $s_{j+1}$ an output Pauli. A sequence of normalized
$n$-qubit Paulis $\mathbf{s}=s_{1},s_{2},\dots,s_{d+1}$ is called a Pauli
path. Then, the probability of $n$ bit string $x$ is

$\displaystyle|\langle
x|C|0^{n}\rangle|^{2}=\sum_{s_{1},s_{2},\dots,s_{d+1}\in\mathcal{P}_{n}}f(C,\mathbf{s},x)\;,$
(3)

where each Pauli path defines a Fourier coefficient
$f(C,\mathbf{s},x)=\llangle x|s_{d+1}\rrangle\llangle
s_{d+1}|C_{d}|s_{d}\rrangle\dots\llangle s_{2}|C_{1}|s_{1}\rrangle\llangle
s_{1}|0^{n}\rrangle$.

An important property of the Pauli path algorithm in approximating RCS (with
the circuit architecture as mQSVT circuit unitary explained earlier) is the
orthogonality property [33, 23] which states that

$\begin{gathered}{\mathbb{E}}_{C}\Big{[}f(C,\mathbf{s},x)f(C,\mathbf{r},x)\Big{]}=0\;,\end{gathered}$
(4)

for Pauli paths $\mathbf{s}\neq\mathbf{r}$ and ${\mathbb{E}}_{C}$ expectation
over random circuit $C$. This is due to independently sampled two-qubit gates
in $C$ that decomposes the expectation over circuit $C$ as a product of Haar-
random expectations over these two-qubit gates. As each two-qubit gate $V$
appears twice, once in $f(C,\mathbf{s},x)$ and once in $f(C,\mathbf{r},x)$, we
get expressions of the form $\textup{Tr}({\mathbb{E}}_{V}[V^{\otimes
2}s\otimes r(V^{\dagger})^{\otimes 2}]s^{\prime}\otimes r^{\prime})$ which
evaluates to 0 when $s\neq r$ or $s^{\prime}\neq r^{\prime}$.

Unfortunately, orthogonality condition (4) does not hold in general for mQSVT
circuits due to a random unitary $U$ appearing $2d$ number of times in a
$d$-block mQSVT circuit (see Appendix G for the case of $d=1$). This requires
the more complicated analysis of higher moment two-qubit Haar-random
expectation, which unlike the second moment, is negative for some choices of
Paulis.

Now we define an mQSVT Pauli path
$\mathbf{s}=\mathbf{s}^{(1)},\mathbf{s}^{(2)},\dots,\mathbf{s}^{(d)}$ is a
sequence of sub-paths
$\mathbf{s}^{(k)}=s_{1}^{(k)},\dots,s_{d_{U}+1}^{(k)},\tilde{s}_{d_{U}+1}^{(k)},\dots,\tilde{s}_{1}^{(k)}$
that goes through unitary $U$ and $U^{\dagger}$ in the $k$-th block. So,
$s_{j},s_{j+1}$ are the input and output Paulis for layer $U_{j}$,
respectively. Whereas $\tilde{s}_{j+1},\tilde{s}_{j}$ are input and output
Paulis for $U_{j}^{\dagger}$. Since phases $\varphi_{1},\dots,\varphi_{2d+1}$
in an mQSVT circuit are fixed, we can instead simply absorb rotation gates
$R(\varphi_{1})$ and $R(\varphi_{2d+1})$ at the beginning and end of the
circuit into the preparation and measurement, respectively. So for a Pauli
path $\mathbf{s}$ through a mQSVT circuit with unitary $U$, we can define an
mQSVT circuit Fourier coefficient as

$F(U,\mathbf{s},x)=\llangle
0x|\tilde{s}_{1}^{(d)}\rrangle\prod_{k=1}^{d}F_{k}(U,\mathbf{s}^{(k)})\llangle
s_{1}^{(1)}|0^{n+1}\rrangle\;,$ (5)

where $F_{k}(U,\mathbf{s}^{(k)})$ is the $k$-th block Fourier coefficient that
contains the product of transition amplitudes of each layer of $U$ and
$U^{\dagger}$ and rotation gates $R(\varphi_{2k})$ and $R(\varphi_{2k-1})$
(for an explicit expression, see supplementary material F). Hence the
probability of output $x$ from an mQSVT circuit with unitary $U$ is

$p(U,x)=\sum_{\mathbf{s}}F(U,\mathbf{s},x)\;.$ (6)

## Refuting sXQUATH.—

Here we give an outline of the proof of Theorem 1. The detailed, more
technical proof is deferred to Appendix H. For readability, we omit the
normalization factors of the Paulis in the paths, e.g. we write $Z$ when we
mean $Z/\sqrt{2}$.

Consider an mQSVT Pauli path approximation for probability of outcome $x$,

$\displaystyle q(U,x)=\frac{1}{2^{n}}+F(U,\mathbf{r},x)\;,$ (7)

for Pauli path $\mathbf{r}=(Z\otimes I^{\otimes l-1}\otimes Z\otimes
I^{\otimes n-l},Z\otimes I^{\otimes n},\dots,Z\otimes I^{\otimes n})$. Since
there is only a single block, we write
$\mathbf{r}=r_{1},\dots,r_{d_{U}+1},\tilde{r}_{d_{U}+1},\dots,\tilde{r}_{1}$
where the $r_{j}$’s and $\tilde{r}_{j}$ are input/output Paulis in $U$ and
$U^{\dagger}$, respectively. From the second layer onwards, all Paulis in path
$\mathbf{r}$ are identity except for the Pauli $Z$ at the first register.
However, $r_{1}=Z\otimes I^{\otimes l-1}\otimes Z\otimes I^{\otimes n-l}$
depends on the architecture in the first layer of $U$. Namely we set
$l\in\\{2,\dots,n+1\\}$ such that the first qubit is coupled with the $l+1$-th
qubit in the first layer $U_{1}$ by two-qubit unitary $V$. Thus the input
Paulis for this two-qubit gate is $Z\otimes Z$. For example, if in the first
layer the two qubit gate that operates on the first qubit couples it with the
5th qubit then $r_{1}=Z\otimes I^{\otimes 3}\otimes Z\otimes I^{\otimes n-4}$.
We also denote the two-qubit gates in the $j$-th layer of $U$ as $V_{j,i}$,
for some arbitrary indexing $i\in[(n+1)/2]$ (as the coupling by these gates
are arbitrary, i.e. gates $V_{1,1}$ and $V_{2,1}$ may operate on different
pair of registers).

Now by using $q(U,x)$ in sXQUATH eqn. (2) as an approximation to $p(U,x)$ and
by expanding the squares and simplifying the terms we get

$\displaystyle\textup{sXQ}=\frac{1}{2^{n}-1}\sum_{x\neq
0^{n}}\bigg{(}-\underbrace{\frac{2}{2^{n}}{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{r},x)\Big{]}}_{(i)}+\underbrace{{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{r},x)^{2}\Big{]}}_{(ii)}+\underbrace{2\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)}_{(iii)}\Big{]}\bigg{)}\;,$
(8)

where we also expand $p(U,x)$ in terms of the mQSVT Fourier coefficients. For
notational simplicity, from now on we will omit the tensor "$\otimes$" in
denoting two-qubit Paulis that is an input or output to the same two-qubit
gate. For example, by $V^{\otimes 2}(ZZ\otimes II)(V^{\dagger})^{\otimes
2}IZ\otimes II$ we mean $V^{\otimes 2}(Z\otimes Z\otimes I\otimes
I)(V^{\dagger})^{\otimes 2}I\otimes Z\otimes I\otimes I$.

We treat the terms $(i),(ii),(iii)$ separately in eqn (8). However the main
idea is similar. Since the two-qubit gates $\\{V_{j,i}\\}_{j,i}$ in $U$ are
sampled independently, the expectation ${\mathbb{E}}_{U}$ can be decomposed as
a product of expectations over each two-qubit gate ${\mathbb{E}}_{V_{j,i}}$
and the transition amplitudes for the input, output, and the rotation gate
(see Appendix G). More explicitly, this decomposition allows us to express
expectation ${\mathbb{E}}_{U}$ as the product of order-$t$ expectations of
two-qubit Haar unitary

$\textup{Tr}\,{\mathbb{E}}_{V_{j,i}}\Big{[}V_{j,i}^{\otimes
t}p_{j,i}^{(1)}\otimes\dots\otimes p_{j,i}^{(t)}(V_{j,i}^{\dagger})^{\otimes
t}p_{j+1,i}^{(1)}\otimes\dots\otimes p_{j+1,i}^{(t)}\Big{]}\,,$ (9)

for some positive integer $t$ and two-qubit paulis
$p_{j,i}^{(l)},p_{j+1,i}^{(l)}$, where $t=2$ for term $(i)$ and $t=4$ for
terms $(ii)$ and $(iii)$. Note that Paulis in path $\mathbf{r}$ at the second
to $n+1$-th qubit registers are all identity, except for the Paulis at the
input $r_{1}$. Namely, $r_{2},\dots,\tilde{r}_{1}$ equal to $Z\otimes
I^{\otimes n}$. As a consequence, most of these expectations are of the form
$\textup{Tr}{\mathbb{E}}[(VIIV^{\dagger}II)^{\otimes t}]$, which takes the
value of $1$ (up to some normalization). Of course, the only exceptions are
the expectations with respect to the two-qubit gates that are interacting with
the first qubit register, since the first register Paulis are all $Z$. When
there are non-identity Paulis, expectation (9) can take any real values
depending on the choice of Paulis and order $t$. This is precisely where the
non-trivialities occur, thus requiring a more extensive analysis on the terms
$(i),(ii),(iii)$ above. Since the mQSVT circuit that we consider only have one
block, we omit the superscript for the Paulis in $\mathbf{r}$ and simply write
$r_{j}$ and $\tilde{r}_{j}$.

Since in term $(i)$ each two-qubit unitary $V_{j,i}$ appears only two times
(in $U$ and $U^{\dagger}$), we only have second moment expectations, allowing
us to use the results in [33, 23] to determine its values (see Appendix G).
Here we only need to consider transition amplitude for the two-qubit gate $V$
in the first layer operating on the first register and the $l$-th register,
the only gate in the first layer which input pauli is $ZZ$. Since its
transition amplitude $\textup{Tr}\,{\mathbb{E}}_{V}[V^{\otimes 2}ZZ\otimes
ZZ(V^{\dagger})^{\otimes 2}IZ\otimes IZ]=0$, term $(i)$ is 0.

In terms $(ii)$ and $(iii)$, each Haar random two-qubit unitary $V_{j,i}$
appears four times, twice in each Fourier coefficient (as each Fourier
coefficient contains $U$ and $U^{\dagger}$). Hence we consider order $t=4$ of
expectation (9), ${\mathbb{E}}_{V}[V^{\otimes 2}r\otimes\tilde{r}\otimes
s\otimes\tilde{s}(V^{\dagger})^{\otimes
2}r^{\prime}\otimes\tilde{r}^{\prime}\otimes
s^{\prime}\otimes\tilde{s}^{\prime}]$ hence the results [33, 23] are no longer
useful. We instead make a detour to unitary random matrix theory of Weingarten
calculus which studies the expansion of Haar-random unitary moment operation
[34, 35] (for applications in quantum theory, see also [36, 37]). Using the
Weingarten calculus framework, we can express the Haar unitary expectations
(9) in terms of Weingarten functions and permutation operators. By evaluating
the values of the Weingarten functions and analyzing permutations over a
tensor product of four two-qubit Paulis (see Appendix G), we can obtain the
relevant values of expectations (9). As now the expectation (9) can take
negative values, one needs to take great care that term $(ii)$ and $(iii)$ are
sufficiently large in order to obtain $\mathrm{sXQ}=\Omega(2^{-3n})$. We will
show below that our chosen Pauli path $\mathbf{r}$ does this.

For term $(ii)$, the analysis is relatively simple since the expectations (9)
for gates with non-identity input/output Paulis turns out to be all positive
(see supplementary material H). Note that there are precisely $d_{U}$ many
such gates, i.e. those that are operating on the first qubit. By also
accounting for the normalization of $1/\sqrt{2}$ for each Pauli, we get
${\mathbb{E}}_{U}[F(U,\mathbf{r},x)^{2}]\geq 2^{-2n}\alpha^{d_{U}}$ for some
constant $\alpha\in(0,1)$ independent of $n$ and $d_{U}$.

The analysis of term $(iii)$ is the most involved part of the proof since it
involves the Fourier coefficient $F(U,\mathbf{s},x)$ for all Pauli path
$\mathbf{s}$. The trick here is to see for which Pauli path $\mathbf{s}$ the
expectation ${\mathbb{E}}_{U}[F(U,\mathbf{s},x)F(U,\mathbf{r},x)]$ is
negative, positive, and equals to 0. This can be determined by the output
transition amplitude $\llangle 0x|\tilde{s}\rrangle$ in $F(U,\mathbf{s},x)$
and by the two-qubit Haar unitary expectations (9). The analysis of the latter
is made slightly simpler by our choice of Pauli path $\mathbf{r}$ since we
only need to analyze three types of expectations (9), namely those where the
input (output) two-qubit Paulis in $F(U,\mathbf{r},x)$ are either $ZZ$ ($ZI$)
or $ZI$ ($ZI$) or $II$ ($II$). Then we evaluate the expectations using the
Weingarten function expansion (see supplementary material G) to identify the
non-zero values. It turns out that
${\mathbb{E}}_{U}[F(U,\mathbf{s},x)F(U,\mathbf{r},x)]$ is non-zero only if the
input/output two-qubit Paulis of $\mathbf{s}$ to each two qubit gate $V_{j,i}$
must be from the set $\\{II,ZZ,ZI,IZ,PX,PY\\}$ for $P\in\\{I,X,Y,Z\\}$.
Furthermore since $\langle b|P|b\rangle=0$ for $P\in\\{X,Y\\}$ and
$b\in\\{0,1\\}$, the paths $\mathbf{s}$ with Pauli $X$ or $Y$ at the output
transition amplitude has $F(U,\mathbf{s},x)=0$, so we do not need to consider
such Pauli paths. The other complicated analysis comes from the fact that some
output transition amplitude $\llangle 0x|\tilde{s}\rrangle$ can be negative
because $\langle 1|Z|1\rangle=-\frac{1}{2}$. However we can pull the sum
$\sum_{x\neq 0^{n}}$ inside the brackets in eqn. (8) and instead consider
$\sum_{x\neq
0^{n}}\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}[F(U,\mathbf{s},x)F(U,\mathbf{r},x)]$.
From here we can separate out the negative terms and positive terms according
to $x\neq 0^{n}$ and the measurement layer of Paulis in $\mathbf{s}$. The
reader can find the detailed calculation in supplementary material H, but in
short the negative terms from to transition amplitude at the measurement layer
$\llangle 0x|\tilde{s}\rrangle$ and from the expectations (9) either cancel
each other out or small enough with respect to the positive terms in the sum
over $x\neq 0$ and $\mathbf{s}\neq\mathbf{r}$. This rather involved
calculation gives us $\sum_{x\neq
0^{n}}\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}[F(U,\mathbf{s},x)F(U,\mathbf{r},x)]\geq
2^{-n}\beta^{d_{U}}$ for some constant $\beta\in(0,1)$ independent of $n$ and
$d_{U}$.

Finally, we can substitute back in the values we obtained for terms
$(i),(ii),(iii)$ to eqn. (8) to get

$\mathrm{sXQ}\geq\frac{1}{2^{n}-1}\Big{(}(2^{n}-1)2^{-2n}\alpha^{d_{U}}+2^{-n}\beta^{d_{U}}\Big{)}\;.$
(10)

Thus for $U$ with depth sublinear in $n$, i.e. $d_{U}=o(n)$, we get
$\mathrm{sXQ}=\Omega(2^{-2n}(\alpha+\beta)^{n})=\Omega(2^{-3n})$ which refutes
sXQUATH for single-block mQSVT circuit, proving Theorem 1.

## Spoofing sXES benchmark.—

The same Pauli path that we use to refute sXQUATH above can also be used to
spoof the average sXES benchmark (1) as stated in Theorem 2. We use the same
Pauli path approximation $q(U,x)$ (eqn. (7)) in place of experimental
probability $p_{\mathrm{exp}}$. Details are given in Appendix I, but the proof
idea is similar to the proof of Theorem 1 above. First we expand $p(U,x)$ in
terms of fourier coefficients $F(U,\mathbf{s},x)$ to obtain

$\displaystyle\mathrm{sXES}$ $\displaystyle=\sum_{x\neq
0^{n}}{\mathbb{E}}_{U}\Big{[}\frac{p(U,x)}{2^{n}}\Big{]}+\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)\Big{]}\;.$
(11)

Note that the second term above is equal to term $(iii)$ in eqn. (8), which
can be lower bounded as $\sum_{x\neq
0^{n}}\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}[F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)]\leq
2^{-n}c^{d_{U}}$ for some constant $c\in(0,1)$ independent of $n$ and $d_{U}$.
By also noting that ${\mathbb{E}}_{U}[p(U,x)]=\frac{1}{2^{n+1}}$ for all $x$,
we can lower bound sXES score as

$\displaystyle\mathrm{sXES}$
$\displaystyle\geq\frac{2^{n}-1}{2^{2n+1}}+2^{-n}c^{d_{U}}\approx\frac{1+c^{d_{U}}}{2^{n}}$
(12)

for some constant $c\in(0,1)$ independent of $n$ and $d_{U}$.

## Discussions.—

Linear XEB has been the method of choice in verifying sampling-based quantum
supremacy claim in many experiments. However, results on efficient classical
sampling algorithms spoofing Linear XEB and a result that disproves the
complexity-theoretic assumption which hardness of Linear XEB rests upon cast
doubts on its robustness. In an effort for a more robust quantum supremacy
benchmarking scheme, a variant of Linear XEB called sXES has been proposed for
quantum Hamiltonian simulation experiments. Its promise relies upon the
quantum circuit that it samples from being structurally distinct from circuits
used for other Linear XEB, hence preventing current spoofing results to be
applied directly, while also relying on a different complexity-theoretic
foundation. We have shown that sXES benchmarking for experiments corruped by
high amount of noise is susceptible to spoofing. At the same time, our result
also shows the frailty of the complexity-theoretic foundation that sXES rests
upon, particularly for sublinear-depth circuits. Our negative results extend
the seminal result [23] that spoofs Linear XEB for unitary random circuit
sampling and further support the need for a novel benchmarking task with a
stronger complexity-theoretic guarantee for any future quantum supremacy
experiments. In particular, such guarantee needs to rule out any possibility
of spoofing by the state-of-the-art algorithms used in our result as well as
those used in previous spoofing results.

## Acknowledgements.—

The authors thank Dax Koh and Rahul Jain for interesting discussions. AT is
supported by CQT PhD Scholarship. This work is supported by the Agency for
Science, Technology and Research (A*STAR) under its QEP2.0 programme
(NRF2021-QEP2-02-P06), the Singapore Ministry of Education Tier1 Grant RT4/23,
and FQxI under grant no FQXi-RFP-IPW-1903 (“Are quantum agents more
energetically efficient at making predictions?")

## References

  * [1] John Preskill.  Quantum computing and the entanglement frontier.  arXiv preprint arXiv:1203.5813, 2012.
  * [2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, oct 2019.
  * [3] Sanjeev Arora and Boaz Barak.  Computational complexity: a modern approach.  Cambridge University Press, 2009.
  * [4] Scott Aaronson and Lijie Chen.  Complexity-theoretic foundations of quantum supremacy experiments, 2016.
  * [5] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven.  Characterizing quantum supremacy in near-term devices.  Nature Physics, 14(6):595–600, apr 2018.
  * [6] Charles Neill, Pedran Roushan, K Kechedzhi, Sergio Boixo, Sergei V Isakov, V Smelyanskiy, A Megrant, B Chiaro, A Dunsworth, K Arya, et al.  A blueprint for demonstrating quantum supremacy with superconducting qubits.  Science, 360(6385):195–199, 2018.
  * [7] Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin.  Sample complexity of device-independently certified “quantum supremacy”.  Physical review letters, 122(21):210502, 2019.
  * [8] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi.  Quantum certification and benchmarking.  Nature Reviews Physics, 2(7):382–390, 2020.
  * [9] Dominik Hangleiter and Jens Eisert.  Computational advantage of quantum random sampling.  Reviews of Modern Physics, 95(3):035001, 2023.
  * [10] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al.  Strong quantum computational advantage using a superconducting quantum processor.  Physical review letters, 127(18):180501, 2021.
  * [11] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, et al.  Quantum computational advantage via 60-qubit 24-cycle random circuit sampling.  Science bulletin, 67(3):240–245, 2022.
  * [12] Lars S Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani, Fabien Rortais, Trevor Vincent, Jacob FF Bulmer, Filippo M Miatto, Leonhard Neuhaus, Lukas G Helt, Matthew J Collins, et al.  Quantum computational advantage with a programmable photonic processor.  Nature, 606(7912):75–81, 2022.
  * [13] Feng Pan and Pan Zhang.  Simulation of quantum circuits using the big-batch tensor network method.  Physical Review Letters, 128(3):030501, 2022.
  * [14] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, et al.  Classical simulation of quantum supremacy circuits.  arXiv preprint arXiv:2005.06787, 2020.
  * [15] Yong Liu, Xin Liu, Fang Li, Haohuan Fu, Yuling Yang, Jiawei Song, Pengpeng Zhao, Zhen Wang, Dajia Peng, Huarong Chen, et al.  Closing the" quantum supremacy" gap: achieving real-time simulation of a random quantum circuit using a new sunway supercomputer.  In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–12, 2021.
  * [16] Feng Pan, Keyang Chen, and Pan Zhang.  Solving the sampling problem of the sycamore quantum circuits.  Physical Review Letters, 129(9):090502, 2022.
  * [17] Gleb Kalachev, Pavel Panteleev, PengFei Zhou, and Man-Hong Yung.  Classical sampling of random quantum circuits with bounded fidelity.  arXiv preprint arXiv:2112.15083, 2021.
  * [18] Alexis Morvan, B Villalonga, X Mi, S Mandra, A Bengtsson, PV Klimov, Z Chen, S Hong, C Erickson, IK Drozdov, et al.  Phase transition in random circuit sampling.  arXiv preprint arXiv:2304.11119, 2023.
  * [19] Xun Gao and Luming Duan.  Efficient classical simulation of noisy quantum computation.  arXiv preprint arXiv:1810.03176, 2018.
  * [20] Boaz Barak, Chi-Ning Chou, and Xun Gao.  Spoofing linear cross-entropy benchmarking in shallow quantum circuits.  arXiv preprint arXiv:2005.02421, 2020.
  * [21] Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D Lukin, Boaz Barak, and Soonwon Choi.  Limitations of linear cross-entropy as a measure for quantum advantage.  arXiv preprint arXiv:2112.01657, 2021.
  * [22] Changhun Oh, Liang Jiang, and Bill Fefferman.  Spoofing cross-entropy measure in boson sampling.  Physical Review Letters, 131(1):010401, 2023.
  * [23] Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani.  A polynomial-time classical algorithm for noisy random circuit sampling.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 945–957, 2023.
  * [24] Joel Rajakumar, James D Watson, and Yi-Kai Liu.  Polynomial-time classical simulation of noisy iqp circuits with constant depth.  arXiv preprint arXiv:2403.14607, 2024.
  * [25] Scott Aaronson and Sam Gunn.  On the classical hardness of spoofing linear cross-entropy benchmarking, 2020.
  * [26] Yulong Dong, K. Birgitta Whaley, and Lin Lin.  A quantum hamiltonian simulation benchmark.  npj Quantum Information, 8(1), nov 2022.
  * [27] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019.
  * [28] Mario Szegedy.  Quantum speed-up of markov chain based algorithms.  In 45th Annual IEEE symposium on foundations of computer science, pages 32–41. IEEE, 2004.
  * [29] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd.  Quantum algorithm for linear systems of equations.  Physical Review Letters, 103(15), October 2009.
  * [30] Richard P Feynman.  Simulating physics with computers.  In Feynman and computation, pages 133–153. CRC Press, 2018.
  * [31] Seth Lloyd.  Universal quantum simulators.  Science, 273(5278):1073–1078, 1996.
  * [32] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd.  Achieving quantum supremacy with sparse and noisy commuting quantum computations.  Quantum, 1:8, 2017.
  * [33] Aram W Harrow and Richard A Low.  Random quantum circuits are approximate 2-designs.  Communications in Mathematical Physics, 291:257–302, 2009.
  * [34] Yinzheng Gu.  Moments of random matrices and weingarten functions.  PhD thesis, 2013.
  * [35] Benoît Collins, Sho Matsumoto, and Jonathan Novak.  The weingarten calculus.  NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 69(5), 2022.
  * [36] Daniel A Roberts and Beni Yoshida.  Chaos and complexity by design.  Journal of High Energy Physics, 2017(4):1–64, 2017.
  * [37] Yinchen Liu.  Moments of random quantum circuits and applications in random circuit sampling.  Master’s thesis, University of Waterloo, 2021.
  * [38] Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani.  A polynomial-time classical algorithm for noisy random circuit sampling, Nov 2022.

##  Appendix A Further Difficulties in Analyzing Pauli Path for mQSVT circuits

Neither the classical algorithm called Pauli path algorithm that efficiently
approximates RCS output probabilities to refute XQUATH [23], nor its
precursors [32, 19], can be directly used to refute sXQUATH. Essentially, the
Pauli path approximation in Ref. [23] was shown to be sufficiently close to
the RCS probabilities by an analysis of the first and second moment of Haar-
random expectations. The same analysis does not work for mQSVT circuits due to
the use of multiple copies of random gates in the circuit. Particularly, the
“orthogonality property” central in the analysis of RCS Pauli path does not
hold for mQSVT Pauli path. Additionally, how one is required to approximate
all output $n$ bit strings except for the all zeros string $0^{n}$ in sXQUATH
and sXES complicates the analysis even more.

##  Appendix B Spoofing Random Circuit Sampling Benchmarking

Linear XEB benchmarking for an RCS experiment quantifies how close the noisy
circuit implementation is to the ideal circuit. It is done by analyzing
samples taken from the noisy circuit to obtain an empirical estimation of the
circuit’s output probability distribution.

######  Definition 1.

Linear cross-entropy benchmark (XEB) of a noisy implementation of an $n$ qubit
unitary $U$ is defined as

$\displaystyle\mathrm{XEB}(U)=2^{n}\sum_{x\neq
0^{n}}p(U,x)\,p_{\mathrm{exp}}(U,x)-1$ (13)

where $p_{\mathrm{exp}}(U,x)$ is the output probability from the noisy
implementation of circuit $U$.

To argue for the quantum supremacy from an RCS experiment, a noisy circuit
used for the experiment with sufficiently high Linear XEB (on average over
some distribution that circuit $U$ is sampled from) implies its ability to
solve a problem that is supposedly hard for classical computers. Aaronson and
Gunn proposed the XHOG problem [25], which demands an algorithm to output a
set of strings that have sufficiently high probabilities from a given circuit
$U$.

######  Definition 2.

Linear cross-entropy heavy output generation (XHOG) problem: For a given $n$
qubit unitary $U$ and some $b>1$, output $k$ many distinct non-zero $n$ bit
strings $\\{x_{1},\dots,x_{k}\\}\subseteq\\{0,1\\}^{n}\backslash\\{0^{n}\\}$
such that they satisfy

$\displaystyle\frac{1}{k}\sum_{j=1}^{k}p(U,x_{j})>\frac{b}{2^{n}}\;.$ (14)

However, showing the hardness of solving XHOG classically remains a problem.
Aaronson and Gunn have shown that if there is no classical algorithm that can
approximate the output probability of the all zero string $0^{n}$ from a
random circuit $U$ with an error that is slightly less than that of a trivial
algorithm, then XHOG is a hard problem for classical computers to solve with
some high probability for a suitable choice of $k$ and $b$.

######  Definition 3.

Linear cross-entropy quantum threshold assumption (XQUATH): There is no
polynomial-time classical algorithm $\mathtt{C}$ that given a description of
an $n$ qubit quantum circuit $U$ with depth $d$ and input bits $0^{n}$ and
output bits $0^{n}$ computes the output probability $p_{\mathtt{C}}(U,0^{n})$
such that the following holds for all $n\in{\mathbb{N}}$

$\displaystyle\textup{XQ}=2^{2n}\bigg{(}{\mathbb{E}}_{U}\Big{[}\Big{(}p(U,0^{n})-\frac{1}{2^{n}}\Big{)}^{2}\Big{]}-{\mathbb{E}}_{U}\Big{[}\Big{(}p(U,0^{n})-q_{\mathtt{C}}(U,0^{n})\Big{)}^{2}\Big{]}\bigg{)}=\Omega\Big{(}\frac{1}{2^{n}}\Big{)}$
(15)

where and $p(U,0^{n})$ is the probability of output $0^{n}$ on mQSVT circuit
for a given unitary $U$. The expectations are over Haar-random two qubit
unitary gates that makes up $U$ where each qubit goes through a two-qubit gate
at each layer.

The Pauli path algorithm is used in [23] as an efficient classical
approximation to the output probabilities of a random unitary circuit $U$ with
sufficiently low MSE to show that XQUATH does not hold for circuit $U$ of
sublinear depth.

##  Appendix C Hardness of classically spoofing mQSVT circuit benchmarking

Formally, an mQSVT circuit consists of $d$ “blocks”, each containing a copy of
$n+1$ qubit unitary $U$ and a copy of its conjugate $U^{\dagger}$ interleaved
by phase shift gates $R_{z}(\varphi)$ at the first register (see Fig. 1). The
probability of output $x\in\\{0,1\\}^{n}$ from an mQSVT circuit with $d$
layers and unitary $U$ is

$\displaystyle p(U,x)=\Big{|}\langle 0x|\Big{(}R_{z}(\varphi_{2d+1})\otimes
I^{n}\Big{)}\prod_{k=0}^{d}\bigg{(}U^{\dagger}\Big{(}R_{z}(\varphi_{2k+2})\otimes
I^{n}\Big{)}U\Big{(}R_{z}(\varphi_{2k+1})\otimes
I^{n}\Big{)}\bigg{)}|0^{n+1}\rangle\Big{|}^{2}\;,$ (16)

where $R_{z}(\varphi)=e^{i\varphi Z}$. So if $d_{U}$ is depth of circuit $U$,
then the total depth of the mQSVT circuit is
$d_{\mathrm{mQSVT}}=d(2d_{U}+2)+1$.

In an Hamiltonian simulation experiment using a noisy mQSVT circuit, one is
ought to benchmark this noisy implementation with respect to the ideal
(noiseless) mQSVT circuit to determine the simulation performance. Similar to
XEB benchmarking that is used in RCS experiment [2], a benchmarking metric
called the linear cross-entropy score (sXES) has been proposed in [26] to
benchmark a noisy Hamiltonian simulation experiments. The sXES metric can be
used to compute the fidelity between the implemented noisy circuit and ideal
circuit [26, eqn.(4)] by sampling the implemented device and performing some
classical computations.

######  Definition 4.

System linear cross-entropy score (sXES) of a noisy implementation of an mQSVT
circuit given a unitary $U$ is defined as

$\displaystyle\mathrm{sXES}(U)=\sum_{x\neq
0^{n}}p(U,x)\,p_{\mathrm{exp}}(U,x)$ (17)

where $p_{\mathrm{exp}}(U,x)$ is the output probability from the noisy
implementation of mQSVT circuit.

How well the performance of an mQSVT circuit implementation as quantified by
sXES is shown to determine whether it is able to solve a problem called the
system linear cross-entropy heavy output generation (sXHOG). Essentially,
sXHOG problem requires the implemented circuit to output a fixed amount of
distinct $n$-bit strings that have sufficiently large output probabilities
from the ideal mQSVT circuit.

######  Definition 5.

System linear cross-entropy heavy output generation (sXHOG) problem: For a
given mQSVT circuit with $n+1$ qubit unitary $U$ and some $b>1$, output $k$
many distinct non-zero $n$ bit strings
$\\{x_{1},\dots,x_{k}\\}\subseteq\\{0,1\\}^{n}\backslash\\{0^{n}\\}$ such that
they satisfy

$\displaystyle\frac{1}{k}\sum_{j=1}^{k}p(U,x_{j})>\frac{b}{2^{n}}\;.$ (18)

sXHOG can be solved by sampling from an MQSVT implementation with sufficiently
high sXES score (as it implies a sufficiently high circuitsfidelity). However,
the hardness of solving sXHOG with some high probability depending on a
suitable choice of $k$ and $b$ using a classical algorithm has been asserted
under an assumption that any polynomial-time classical algorithm cannot
approximate the ideal mQSVT circuit output probability better (in mean squared
error) than a trivial uniform approximation up to some negligible margin. This
assumption is what is called the System linear cross-entropy quantum threshold
assumption (sXQUATH).

######  Definition 6.

System linear cross-entropy quantum threshold assumption (sXQUATH) conjecture:
There is no polynomial-time classical algorithm $\mathtt{C}$ such that the
following holds for an mQSVT circuit for all $n\in{\mathbb{N}}$

$\displaystyle\textup{sXQ}=2^{2n}\bigg{(}{\mathbb{E}}_{U,X}\Big{[}\Big{(}p(U,X)-\frac{1}{2^{n}}\Big{)}^{2}\Big{]}-{\mathbb{E}}_{U,X}\Big{[}\Big{(}p(U,X)-q_{\mathtt{C}}(U,X)\Big{)}^{2}\Big{]}\bigg{)}=\Omega\Big{(}\frac{1}{2^{n}}\Big{)}$
(19)

where $n$ is the number of input/output qubits, and $p(U,X)$ is the
probability of output $X$ on mQSVT circuit for a given unitary $U$, and
$q_{\mathtt{C}}(U,X)$ is the probability of classical algorithm $\mathtt{C}$
simulating an mQSVT circuit outputting $X$ for a given unitary $U$. The
expectations are over uniformly distributed random variable
$X\in\\{0,1\\}^{n}\backslash\\{0^{n}\\}$ and over $n+1$ qubits Haar random
unitaries $U$.

Similar to XQUATH, sXQUATH conjecture states that there is no classical
algorithm approximation of the output probability of an mQSVT circuit that has
a mean squared error that is $2^{-n}$ less than the mean squared error of a
trivial approximation.

##  Appendix D Reductions between threshold assumptions

Here we discuss the complexity-theoretic relationship between XQUATH, sXQUATH,
and its precursor, QUATH (Quantum threshold assumption). The latter is related
to another sampling-based quantum supremacy verification method called Heavy
Output Generation (HOG) [4], which is a precursor to XHOG and sXHOG. Here we
again consider sampling from $n$ qubit unitary random circuit $U$ with all
zero input and probability of outputting some string $x$ is $p(x,U)=|\langle
x|U|0^{n}\rangle|^{2}$.

######  Definition 7.

Heavy output generation (HOG) problem: For a random $n$ qubit unitary circuit
$U$ drawn from some distribution $\mathcal{D}$, output $k$ many $n$ bit
strings $\\{x_{1},\dots,x_{k}\\}\subseteq\\{0,1\\}^{n}$ such that
$\frac{2}{3}$ of their probabilities $p(x_{1},U),\dots,p(x_{k},U)$ are larger
than the median of all the output probabilities
$\textup{median}_{U\sim\mathcal{D}}\\{p(x,U):x\in\\{0,1\\}^{n}\\}$.

Compared to XHOG and sXHOG, HOG is clearly the most distinct as it requires
that a certain proportion of the output strings to have probability larger
than a value (the median) instead of requiring the sum of the probabilities to
be larger than some value (as in XHOG and sXHOG). However, similarly to XHOG
and sXHOG, the hardness of classically solving HOG is also based on a
conjecture called the Quantum threshold assumption (QUATH) [4], which as
opposed to XQUATH and sXQUATH, is a conjecture for a decision problem.

######  Definition 8.

Quantum threshold assumption (QUATH): For some distribution $\mathcal{D}$ over
$n$ qubit unitary circuit $U$, there is no polynomial-time classical algorithm
taking a description of $U$ as input and outputs "Yes" if $p(0,U)$ is larger
than $\textup{median}_{U\sim\mathcal{D}}\\{p(x,U):x\in\\{0,1\\}^{n}\\}$ and
"No" otherwise, with probability $\frac{1}{2}+\Omega(2^{-n})$ over
$\mathcal{D}$.

To obtain a better understanding on what features does a robust benchmarking
scheme must have, one can gain insights by looking into the relationship
between QUATH and XQUATH and sXQUATH. Namely, whether one can be reduced from
another is unclear. Also, as XQUATH and sXQUATH for sublinear depth random
unitaries has been refuted by using the Pauli path algorithms, it is
interesting to further investigate whether the Pauli path algorithm can also
disprove QUATH.

Even for XQUATH and sXQUATH, which bear most similarity among the three, their
relationship does not seem to be straightforward. As mentioned, the difficulty
here is due to multiple copies of random unitary in an mQSVT circuit. Hence
one would need to find some nontrivial correspondence between algorithms that
approximates output probabilities a circuit containing multiple copies of
random unitary $U$ and those with only a single $U$. If we consider random
unitaries made out of Haar-random two-qubit unitaries used in this work and in
[23], we expect that this relationship between XQUATH and sXQUATH can be
better understood by a deeper investigation into the relationship between two-
qubit Haar-random unitary moment matrices of moment $t=2$ and $t>2$.

##  Appendix E Haar-random unitary moment matrix

As we will see later on how Pauli path algorithm is used to refute XQUATH and
sXQUATH, an important ingredient is the expectation of $t$ Pauli matrices over
product of $t$ Haar-random unitaries

$\displaystyle{\mathbb{E}}_{V}\Big{[}V^{\otimes t}p_{1}\otimes\dots\otimes
p_{t}(V^{\dagger})^{\otimes t}\Big{]}\;,$ (20)

where $V$ is a $l$ qubit unitary matrix and
$p_{1},\dots,p_{t}\in\mathcal{P}_{l}$. This quantity is extensively studied in
[33] and used in [38] to show the properties of the transition amplitudes in
the Fourier coefficients of Pauli paths. For our purposes we focus on the case
where $l=2$, i.e. $p_{1},\dots,p_{t}\in\mathcal{P}_{2}$ are normalized two
qubit Pauli matrices and the unitaries $V$ are two-qubit unitaries.

Now consider a matrix indexed by $t$ two-qubit Paulis

$\displaystyle
G(\mathbf{p};\mathbf{q})=\textup{Tr}\bigg{(}{\mathbb{E}}_{V}\Big{[}V^{\otimes
t}p_{1}\otimes\dots\otimes p_{t}(V^{\dagger})^{\otimes
t}\Big{]}q_{t}\otimes\dots\otimes q_{t}\bigg{)}\;.$ (21)

If one considers a random $N$-qubit circuit $U$ constructed from Haar-random
two-qubit unitaries (as in [23]), then the expectation of Pauli path
transition amplitudes can be expressed as a product of expectation of
transition amplitudes ${\mathbb{E}}_{V}[\llangle
p|V|p^{\prime}\rrangle]={\mathbb{E}}_{V}[\textup{Tr}(VpV^{\dagger}p^{\prime})]=G(p;p^{\prime})$
for two-qubit Haar random unitary $V$ and normalized two-qubit paulis
$p,p^{\prime}$. This is precisely the key analysis being done in analyzing the
Pauli path algorithm for RCS [23]

##  Appendix F Pauli path for mQSVT circuit

We may define a Pauli path $\mathbf{s}$ through an mQSVT circuit as a sequence
of sub-paths $\mathbf{s}^{(k)}=s_{1}^{(k)},\dots,s_{d_{U}+1}^{(k)}$ and
$\tilde{\mathbf{s}}^{(k)}=\tilde{s}_{d_{U}+1}^{(k)},\dots,\tilde{s}_{1}^{(k)}$
that goes through unitary $U$ and $U^{\dagger}$ in the $k$-th block,
respectively. Since phases $\varphi_{1},\dots,\varphi_{2d+1}$ in an mQSVT
circuit are fixed, we can instead simply absorb the rotation gates
$R_{z}(\varphi_{1})$ and $R_{z}(\varphi_{2d+1})$ at the beginning and end of
the circuit into the preparation and measurement, respectively, in the mQSVT
Pauli path simulation. So for a single Pauli path $\mathbf{s}$ through a mQSVT
circuit with unitary $U$ gives us a Fourier coefficient of the form

$\displaystyle F(U,\mathbf{s},x)=\llangle
0x|\tilde{s}_{1}^{(d)}\rrangle\bigg{(}\prod_{k=1}^{d}F_{k}(U,\mathbf{s})\bigg{)}\llangle
s_{1}^{(1)}|0^{n+1}\rrangle$ (22)

where we define

$\begin{gathered}F_{1}(U,\mathbf{s})=f_{2}(U^{\dagger},\mathbf{s})\,\llangle\tilde{s}_{d_{U}+1}^{(k)}|R_{z}(\varphi_{2})|s_{d_{U}+1}^{(k)}\rrangle\,f_{1}(U,\mathbf{s})\;,\\\
F_{k}(U,\mathbf{s})=f_{2k}(U^{\dagger},\mathbf{s})\,\llangle\tilde{s}_{d_{U}+1}^{(k)}|R_{z}(\varphi_{2k})|s_{d_{U}+1}^{(k)}\rrangle\,f_{2k-1}(U,\mathbf{s})\,\llangle
s_{1}^{(k)}|R_{z}(\varphi_{2k-1})|\tilde{s}_{1}^{(k-1)}\rrangle\;,\\\
f_{2k-1}(U,\mathbf{s})=\llangle
s_{d_{U}+1}^{(k)}|U_{d_{U}}|s_{d_{U}}^{(k)}\rrangle\dots\llangle
s_{2}^{(k)}|U_{1}|s_{1}^{(k)}\rrangle\;,\\\
f_{2k}(U^{\dagger},\mathbf{s})=\llangle\tilde{s}_{1}^{(k)}|U_{1}^{\dagger}|\tilde{s}_{2}^{(k)}\rrangle\dots\llangle\tilde{s}_{d_{U}}^{(k)}|U_{d_{U}}^{\dagger}|\tilde{s}_{d_{U}+1}^{(k)}\rrangle\end{gathered}$
(23)

where $U_{j}$ is the $j$-th layer of $U$ for $j\in\\{1,\dots,d_{U}\\}$. Hence
we can explicitly write an mQSVT Pauli path $\mathbf{s}$ in terms of its sub-
paths as

$\displaystyle\mathbf{s}=\mathbf{s}^{(1)},\tilde{\mathbf{s}}^{(1)},\mathbf{s}^{(2)},\tilde{\mathbf{s}}^{(2)},\dots,\mathbf{s}^{(d)},\tilde{\mathbf{s}}^{(d)}\;,$
(24)

which consists of $2d(d_{U}+1)$ many $n+1$-qubit Paulis. Hence in terms of
Pauli paths, the probability of output $x$ from an mQSVT circuit with unitary
$U$ is

$\displaystyle\begin{split}p(U,x)&=\sum_{\mathbf{s}}F(U,\mathbf{s},x)\;.\end{split}$
(25)

##  Appendix G Pauli path for single-block mQSVT circuit

For the special case of $d=1$, the probability of an mQSVT circuit with $n+1$
qubit unitary $U$ outputting string $x$ is

$\displaystyle p(U,x)$ $\displaystyle=\big{|}\langle
0x|\big{(}R(\varphi_{2})\otimes I^{\otimes
n}\big{)}U^{\dagger}\big{(}R(\varphi_{1})\otimes I^{\otimes
n}\big{)}U\big{(}R(\varphi_{0})\otimes I^{\otimes
n}\big{)}|0^{n+1}\rangle\big{|}^{2}$ (26) $\displaystyle=\big{|}\langle
0x|U^{\dagger}\big{(}R(\varphi_{1})\otimes I^{\otimes
n}\big{)}U|0^{n+1}\rangle\big{|}^{2}$
$\displaystyle=\sum_{\mathbf{s}}F(U,\mathbf{s},x)$

where we have Pauli path
$\mathbf{s}=s_{1},\dots,s_{d_{U}+1},\tilde{s}_{d_{U}+1},\dots,\tilde{s}_{1}$
and Fourier coefficient

$\displaystyle F(U,\mathbf{s},x)$ $\displaystyle=\llangle
0x|\tilde{s}_{1}\rrangle\llangle\tilde{s}_{1}|U_{1}^{\dagger}|\tilde{s}_{2}\rrangle\dots\llangle\tilde{s}_{d_{U}}|U_{1}^{\dagger}|\tilde{s}_{d_{U}+1}\rrangle\llangle\tilde{s}_{d_{U}+1}|R(\varphi_{1})|s_{d_{U}+1}\rrangle$
(27) $\displaystyle\quad\llangle
s_{d_{U}+1}|U_{d_{U}}|s_{d_{U}}\rrangle\dots\llangle
s_{2}|U_{1}|s_{1}\rrangle\llangle s_{1}|0^{n+1}\rrangle\;.$

We employ the circuit architecture of the random unitary circuit in [23] to
each copy of random unitary $U$ in the mQSVT circuit. This unitary $U$
consists of two qubit gates, each drawn independently from the two-qubit
unitary Haar measure. Every qubit register goes through exactly one two-qubit
unitary in each layer $U_{1},\dots,U_{d+1}$. No geometric locality on which
two qubit registers any two-qubit gate operates on is assumed in this
architecture. However since each qubit must go through a two-qubit gate in
each layer we assume that the number of qubits $n+1$ is even so that in layer
$U_{j}$ there are $(n+1)/2$ two-qubit gates $V_{j,1},\dots,V_{j,(n+1)/2}$.

First we look at the expectation of a Fourier coefficient for a single Pauli
path for a single-block mQSVT circuit over Haar-random unitary $U$

$\displaystyle{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{s},x)\Big{]}$
$\displaystyle=\llangle
0x|\tilde{s}_{1}\rrangle\llangle\tilde{s}_{d_{U}+1}|R(\varphi_{1})|s_{d_{U}+1}\rrangle\llangle
s_{1}|0^{n+1}\rrangle$ (28)
$\displaystyle\quad\prod_{j=1}^{d_{U}}\prod_{i=1}^{(n+1)/2}{\mathbb{E}}_{V_{j,i}}\Big{[}\textup{Tr}\Big{(}V_{j,i}^{\otimes
2}(s_{j,i}\otimes\tilde{s}_{j,i})(V_{j,i}^{\dagger})^{\otimes
2}(s_{j+1,i}\otimes\tilde{s}_{j+1,i})\Big{)}\Big{]}\;.$

Note that the Haar-random expectation of a Fourier coefficient for the single-
block mQSVT circuit involves a second-order Haar-random unitary moment, as
there are two copies of every two-qubit gate $V_{j,i}$ in the circuit. In
contrast, the expectation of a random unitary circuit involves only the first-
order moment

$\displaystyle{\mathbb{E}}_{U}\Big{[}f(U,\mathbf{s},x)\Big{]}=\llangle
x|s_{d_{U}+1}\rrangle\llangle
s_{1}|0^{n+1}\rrangle\prod_{j=1}^{d_{U}}\prod_{i=1}^{(n+1)/2}{\mathbb{E}}_{V_{j,i}}\Big{[}\textup{Tr}\Big{(}V_{j,i}s_{j,i}V_{j,i}^{\dagger}s_{j+1,i}\Big{)}\Big{]}\;,$
(29)

where $f(U,\mathbf{s},x)$ is the Fourier coefficient of unitary circuit $U$
with output $x$ and Pauli path $\mathbf{s}=s_{1},\dots,s_{d_{U}+1}$. Although
${\mathbb{E}}_{U}[f(U,\mathbf{s},x)]=0$ for any Pauli path $\mathbf{s}$
containing a non-identity Pauli, this is not the case for mQSVT circuits. To
identify the value of ${\mathbb{E}}_{U}[F(U,\mathbf{s},x)]$ we need to look at
the entries of the Haar unitary moment matrix $G$ in (21) for $t=2$ which is
shown in [33] to be

$\displaystyle G(s,\tilde{s};s^{\prime},\tilde{s}^{\prime})$
$\displaystyle={\mathbb{E}}_{V}\Big{[}\textup{Tr}\Big{(}V^{\otimes
2}(s\otimes\tilde{s})(V^{\dagger})^{\otimes
2}(s^{\prime}\otimes\tilde{s}^{\prime})\Big{)}\Big{]}$ (30)
$\displaystyle=\begin{cases}0\quad&\textup{if $s\neq\tilde{s}$ or
$s^{\prime}\neq\tilde{s}^{\prime}$}\\\ 0\quad&\textup{if exactly one of $s$ or
$s^{\prime}$ is $I\otimes I/2$}\\\ 0\quad&\textup{if exactly one of
$\tilde{s}$ or $\tilde{s}^{\prime}$ is $I\otimes I/2$}\\\ 1\quad&\textup{if
$s=\tilde{s}=s^{\prime}=\tilde{s}^{\prime}=I\otimes I/2$}\\\
\frac{1}{15}\quad&\textup{if $s=\tilde{s}\neq I\otimes I/2$ and
$s^{\prime}=\tilde{s}^{\prime}\neq I\otimes I/2$}\end{cases}\;.$

By substituting these values into (28) we can see that
${\mathbb{E}}_{U}[F(U,\mathbf{s},x)]=0$ if and only if (1) there is an input
or output Pauli to some two-qubit gate $V_{j,i}$ that differs in the two
unitaries in the mQSVT circuits, or (2) only either an input or output Pauli
to some two-qubit gate $V_{j,i}$ is identity, i.e. there exists some
$j\in[d_{U}]$ and $i\in[\frac{n+1}{2}]$ such that $s_{j,i}\neq\tilde{s}_{j,i}$
or $s_{j+1,i}\neq\tilde{s}_{j+1,i}$ or only one of $s_{j,i},s_{j+1,i}$ is
identity or only one of $\tilde{s}_{j,i},\tilde{s}_{j+1,i}$ is identity.

Recall that in the Pauli path simulation for random unitary circuit in [23],
Fourier coefficient of different Pauli path are orthogonal, i.e.

$\displaystyle{\mathbb{E}}_{U}\Big{[}f(U,\mathbf{r},x)f(U,\mathbf{s},x)\Big{]}=0$
(31)

for $\mathbf{r}\neq\mathbf{s}$. This Fourier coefficient orthogonality
condition does not hold for mQSVT circuit in general. For a single-block mQSVT
circuit the Fourier coefficient expectation above can be expanded as

$\displaystyle{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{r},x)F(U,\mathbf{s},x)\Big{]}$
(32) $\displaystyle=\llangle 0x|\tilde{r}_{1}\rrangle\llangle
0x|\tilde{s}_{1}\rrangle\llangle\tilde{r}_{d_{U}+1}|R(\varphi_{1})|r_{d_{U}+1}\rrangle\llangle\tilde{s}_{d_{U}+1}|R(\varphi_{1})|s_{d_{U}+1}\rrangle\llangle
r_{1}|0^{n+1}\rrangle\llangle s_{1}|0^{n+1}\rrangle$
$\displaystyle\quad\prod_{j=1}^{d_{U}}\prod_{i=1}^{(n+1)/2}{\mathbb{E}}_{V_{j,i}}\Big{[}\textup{Tr}\Big{(}V_{j,i}^{\otimes
4}(r_{j,i}\otimes\tilde{r}_{j,i}\otimes
s_{j,i}\otimes\tilde{s}_{j,i})(V_{j,i}^{\dagger})^{\otimes
4}(r_{j+1,i}\otimes\tilde{r}_{j+1,i}\otimes
s_{j+1,i}\otimes\tilde{s}_{j+1,i})\Big{)}\Big{]}$

where the expectations are over two qubit unitaries $V_{j,i}$ and
$r_{j,i},\tilde{r}_{j,i},s_{j,i},\tilde{s}_{j,i},r_{j+1,i},\tilde{r}_{j+1,i},s_{j+1,i},\tilde{s}_{j+1,i}$
are normalized two qubit Paulis which at the inputs and outputs of $V_{j,i}$.
The two qubit unitary expectation terms above are the entries of Haar unitary
moment matrix $G$ in (21) for $t=4$ which can be expanded in terms of the
Weingarten functions $\mathrm{Wg}$ as

$\displaystyle
G(r,\tilde{r},s,\tilde{s};r^{\prime},\tilde{r}^{\prime},s^{\prime},\tilde{s}^{\prime})$
$\displaystyle={\mathbb{E}}_{V}\Big{[}\textup{Tr}\Big{(}V^{\otimes
4}(r\otimes\tilde{r}\otimes s\otimes\tilde{s})(V^{\dagger})^{\otimes
4}(r^{\prime}\otimes\tilde{r}^{\prime}\otimes
s^{\prime}\otimes\tilde{s}^{\prime})\Big{)}\Big{]}$ (33)
$\displaystyle=\sum_{\tau,\pi}\mathrm{Wg}(\tau\pi)\textup{Tr}(W_{\tau^{-1}}r\otimes\tilde{r}\otimes
s\otimes\tilde{s})\,\textup{Tr}(W_{\pi}r^{\prime}\otimes\tilde{r}^{\prime}\otimes
s^{\prime}\otimes\tilde{s}^{\prime})\;,$

where $\tau,\pi$ are permutations in $S_{4}$ and $\tau\pi$ is the composition
of permutations $\pi$ and $\tau$.

To determine the value of expectation over the Fourier coefficients of mQSVT
circuit in (32), we need to analyze the terms in the sum in (33). First, we
need to determine for which Paulis the value of (33) is zero. Here we define
the cyclic partition of a permutation $\pi$ on ordered set $B$ as the
partition of $B$ where each partition is a subset of $B$ that is permuted by a
cycle in the cyclic decomposition of $\pi$. For the term
$\textup{Tr}(W_{\pi}r\otimes\tilde{r}\otimes s\otimes\tilde{s})$, the set
being permuted is $\\{r,\tilde{r},s,\tilde{s}\\}$. So, if the cyclic
decomposition is $\pi=(134)(2)$ then its cyclic partition is
$\\{\\{r,s,\tilde{s}\\},\\{\tilde{r}\\}\\}$. For simplicity in what follows,
let us denote the unnormalized two-qubit Paulis by the capital letters of
their corresponding normalized two-qubit Paulis, e.g. $R$ for $r$ and
$\tilde{S}$ for $s$, so we can write eqn (33) as

$\displaystyle
G(r,\tilde{r},s,\tilde{s};r^{\prime},\tilde{r}^{\prime},s^{\prime},\tilde{s}^{\prime})$
$\displaystyle=\frac{1}{2^{8}}\sum_{\tau,\pi}\mathrm{Wg}(\tau\pi)\textup{Tr}(W_{\tau^{-1}}R\otimes\tilde{R}\otimes
S\otimes\tilde{S})\,\textup{Tr}(W_{\pi}R^{\prime}\otimes\tilde{R}^{\prime}\otimes
S^{\prime}\otimes\tilde{S}^{\prime})\;.$ (34)

Now as a first step to evaluate some of the relevant values of (33) we show
the following lemma.

######  Lemma 1.

For $k$ two-qubit Paulis $Q_{1},\dots,Q_{k}$ and permutation operator
$W_{\pi}$ for permutation $\pi\in S_{k}$, we have
$\textup{Tr}(W_{\pi}Q_{1}\otimes\dots\otimes Q_{k})\neq 0$ if and only if the
product of Paulis in each set in the cyclic partition of $\pi$ on
$\\{Q_{1},\dots,Q_{k}\\}$ is equal to $I\otimes I$. Moreover, let the number
of cyclic partition of $\pi$ be $c_{\pi}$. Then, if the product of Paulis in
each partition of $\pi$ is identity then
$\textup{Tr}(W_{\pi}Q_{1}\otimes\dots\otimes Q_{k})=\textup{Tr}(I\otimes
I)^{c_{\pi}}=4^{c_{\pi}}$.

###### Proof.

Suppose that permutation $\pi\in S_{k}$ has $c_{\pi}$ cyclic partitions so we
can express it as $\pi=\pi_{1}\dots\pi_{c_{\pi}}$ where
$\pi_{1},\dots,\pi_{c_{\pi}}$ are disjoint cycles. So we can rewrite
$\textup{Tr}(W_{\pi}Q_{1}\otimes\dots\otimes Q_{k})$ as

$\displaystyle\textup{Tr}(W_{\pi}Q_{1}\otimes\dots\otimes Q_{k})$
$\displaystyle=\prod_{j=1}^{c_{\pi}}\textup{Tr}(W_{\pi_{j}}\bar{Q}_{j})$ (35)

where $\bar{Q}_{j}$ is the product of two-qubit Paulis in
$\\{Q_{1},\dots,Q_{k}\\}$ in the $j$-th partition of $\pi$. For example, if
$\pi_{j}=(1436)$ then $\bar{Q}_{j}=Q_{1}\otimes Q_{3}\otimes Q_{4}\otimes
Q_{6}$. Suppose that the $j$-th cycle is $\pi_{j}=(a_{1},\dots,a_{l})$ where
$a_{1},\dots,a_{l}$ are distinct numbers in $1,\dots,k$ indicating the indices
of the two-qubit Paulis in the $j$-th partition. Then we have

$\displaystyle\textup{Tr}(W_{\pi_{j}}\bar{Q}_{j})=\textup{Tr}\Big{(}Q_{a_{1}}Q_{\pi_{j}(a_{1})}Q_{\pi_{j}^{2}(a_{1})}\dots
Q_{\pi_{j}^{l-1}(a_{1})}\Big{)}$ (36)

which is equal to 0 if $Q_{a_{1}}Q_{\pi_{j}(a_{1})}Q_{\pi_{j}^{2}(a_{1})}\dots
Q_{\pi_{j}^{l-1}(a_{1})}$ is not equal to identity $I\otimes I$ and otherwise
$\textup{Tr}(W_{\pi_{j}}\bar{Q}_{j})=\textup{Tr}(I\otimes I)=4$. The claim in
the lemma follows by following the same argument for each of the $c_{\pi}$
partitions. ∎

Values of the Weingarten function only depends on the cyclic partition of the
permutation $\tau\pi$, particularly thesize of each partition. As we are
interested only in permutations over four elements, there are only five
possible cyclic partitions we denote as $[4]$, $[3,1]$, $[2,2]$, $[2,1,1]$,
and $[1,1,1,1]$, where the numbers inside the square brackets are the size of
each partition. Now for simplicity, we do a slight abuse of notation in
writing the Weingarten function to only denote the cyclic partition of the
permutation in its argument and list its values

$\displaystyle\mathrm{Wg}([4])$ $\displaystyle=\frac{-20}{\Delta}$ (37)
$\displaystyle\mathrm{Wg}([3,1])$ $\displaystyle=\frac{29}{\Delta}$
$\displaystyle\mathrm{Wg}([2,2])$ $\displaystyle=\frac{32}{\Delta}$
$\displaystyle\mathrm{Wg}([2,1,1])$ $\displaystyle=\frac{-48}{\Delta}$
$\displaystyle\mathrm{Wg}([1,1,1,1])$ $\displaystyle=\frac{134}{\Delta}$

where $\Delta=4(4^{2}-1)(4^{2}-4)(4^{2}-9)=20160$. For a more general formula
of the Weingarten function on $\mathcal{S}_{4}$ see the appendix of [36].

For $\mathcal{S},\mathcal{S}^{\prime}\subseteq\mathcal{S}_{4}$, let

$\displaystyle\bar{G}(r,\tilde{r},s,\tilde{s};r^{\prime},\tilde{r}^{\prime},s^{\prime},\tilde{s}^{\prime})$
$\displaystyle=\sum_{\tau\in\mathcal{S},\pi\in\mathcal{S}^{\prime}}\mathrm{Wg}(\tau\pi)\textup{Tr}(W_{\tau^{-1}}r\otimes\tilde{r}\otimes
s\otimes\tilde{s})\,\textup{Tr}(W_{\pi}r^{\prime}\otimes\tilde{r}^{\prime}\otimes
s^{\prime}\otimes\tilde{s}^{\prime})$ (38)
$\displaystyle=\frac{1}{2^{8}}\sum_{\tau\in\mathcal{S},\pi\in\mathcal{S}^{\prime}}\mathrm{Wg}(\tau\pi)\textup{Tr}(W_{\tau^{-1}}R\otimes\tilde{R}\otimes
S\otimes\tilde{S})\,\textup{Tr}(W_{\pi}R^{\prime}\otimes\tilde{R}^{\prime}\otimes
S^{\prime}\otimes\tilde{S}^{\prime})\;,$

where $\mathcal{S}$ and $\mathcal{S}^{\prime}$ are subsets of
$\mathcal{S}_{4}$ defined as

$\displaystyle\mathcal{S}$
$\displaystyle=\Big{\\{}\pi\in\mathcal{S}_{4}:\textup{Tr}(W_{\pi}R\otimes\tilde{R}\otimes
S\otimes\tilde{S})\neq 0\Big{\\}}$ (39) $\displaystyle\mathcal{S}^{\prime}$
$\displaystyle=\Big{\\{}\pi\in\mathcal{S}_{4}:\textup{Tr}(W_{\pi}R^{\prime}\otimes\tilde{R}^{\prime}\otimes
S^{\prime}\otimes\tilde{S}^{\prime})\neq 0\Big{\\}}\;.$

Therefore we get

$G(r,\tilde{r},s,\tilde{s};r^{\prime},\tilde{r}^{\prime},s^{\prime},\tilde{s}^{\prime})=\bar{G}(r,\tilde{r},s,\tilde{s};r^{\prime},\tilde{r}^{\prime},s^{\prime},\tilde{s}^{\prime})$
(40)

hence $\bar{G}$ consist of the non-zero terms in $G$ which we can get by using
Lemma 1, namely the only terms that we need to compute to get the value of $G$
for two qubit Paulis in its argument that we are interested in.

Now we consider the values of $G$ for specific Paulis
$r,\tilde{r},r^{\prime},\tilde{r}^{\prime}$:

  1. 1.

$r=\tilde{r}=r^{\prime}=\tilde{r}^{\prime}=ZI/2$,

  2. 2.

$r=\tilde{r}=r^{\prime}=\tilde{r}^{\prime}=II/2$, and

  3. 3.

$r=ZZ/2$ and $\tilde{r}=r^{\prime}=\tilde{r}^{\prime}=ZI/2$,

which relevance will be clear in our proof that sXQUATH does not hold for
single-block mQSVT. The different values that $G$ can take for the
aforementioned two qubit Paulis are

$\displaystyle
G(ZI/2,ZI/2,s,\tilde{s};ZI/2,ZI/2,s^{\prime},\tilde{s}^{\prime})$
$\displaystyle=\begin{cases}\frac{90048}{2^{8}\Delta}\quad&\textup{if
$s=\tilde{s}=s^{\prime}=\tilde{s}^{\prime}=ZI/2$}\\\
\frac{31680}{2^{8}\Delta}\quad&\textup{if $s=\tilde{s}\notin\\{ZI/2,II/2\\}$
and $s^{\prime}=\tilde{s}^{\prime}\notin\\{ZI/2,II/2\\}$}\\\
\frac{18368}{2^{8}\Delta}\quad&\textup{if $s=\tilde{s}=ZI/2$ and
$s^{\prime}=\tilde{s}^{\prime}\notin\\{ZI/2,II/2\\}$}\\\
\frac{18368}{2^{8}\Delta}\quad&\textup{if $s=\tilde{s}\notin\\{ZI/2,II/2\\}$
and $s^{\prime}=\tilde{s}^{\prime}=ZI/2$}\\\
\frac{602048}{2^{8}\Delta}\quad&\textup{if
$s=\tilde{s}=s^{\prime}=\tilde{s}^{\prime}=II/2$}\\\
0\quad&\textup{otherwise}\end{cases}$ (41) $\displaystyle
G(II/2,II/2,s,\tilde{s};II/2,II/2,s^{\prime},\tilde{s}^{\prime})$
$\displaystyle=\begin{cases}1\quad&\textup{if
$s=\tilde{s}=s^{\prime}=\tilde{s}^{\prime}=II/2$}\\\
\frac{31680}{2^{8}\Delta}\quad&\textup{if $s=\tilde{s}\neq II/2$ and
$s^{\prime}=\tilde{s}^{\prime}\neq II/2$}\\\
0\quad&\textup{otherwise}\end{cases}$ (42) $\displaystyle
G(ZZ/2,ZI/2,s,\tilde{s};ZI/2,ZI/2,s^{\prime},\tilde{s}^{\prime})$
$\displaystyle=\begin{cases}\frac{95232}{2^{8}\Delta}\quad&\textup{if
$\\{s,\tilde{s}\\}=\\{ZZ/2,ZI/2\\}$ and
$s^{\prime}=\tilde{s}^{\prime}=ZI/2$}\\\
\frac{-121920}{2^{8}\Delta}\quad&\textup{if
$\\{s,\tilde{s}\\}=\\{PX/2,PY/2\\}$ and
$s^{\prime}=\tilde{s}^{\prime}=ZI/2$}\\\
\frac{73664}{2^{8}\Delta}\quad&\textup{if $\\{s,\tilde{s}\\}=\\{IZ/2,II/2\\}$
and $s^{\prime}=\tilde{s}^{\prime}=ZI/2$}\\\
\frac{-6656}{2^{8}\Delta}\quad&\textup{if $\\{s,\tilde{s}\\}=\\{ZZ/2,ZI/2\\}$
and $s^{\prime}=\tilde{s}^{\prime}\notin\\{ZI/2,II/2\\}$}\\\
\frac{12224}{2^{8}\Delta}\quad&\textup{if $\\{s,\tilde{s}\\}=\\{PX/2,PY/2\\}$
and $s^{\prime}=\tilde{s}^{\prime}\notin\\{ZI/2,II/2\\}$}\\\
\frac{960}{2^{8}\Delta}\quad&\textup{if $\\{s,\tilde{s}\\}=\\{IZ/2,II/2\\}$
and $s^{\prime}=\tilde{s}^{\prime}\notin\\{ZI/2,II/2\\}$}\\\
0\quad&\textup{otherwise}\end{cases}\;,$ (43)

where $P\in\\{I,X,Y,Z\\}$ in eqn. (43). Note that each of the values above
lies in the interval $[-1,1]$ since $2^{8}\Delta=5160960$.

##  Appendix H sXQUATH does not hold for single-block mQSVT circuit

Consider Pauli path algorithm that gives a classical approximation $q(U,x)$ of
the probability $p(U,x)$ for single-block mQSVT circuit with $n+1$ qubit
unitary $U$ with depth $d_{U}$ outputting an $n$ bit string $x\neq 0^{n}$,
where

$\displaystyle q(U,x)=\frac{1}{2^{n}}+F(U,\mathbf{r},x)\;,$ (44)

for Pauli path $\mathbf{r}=(Z\otimes I^{l}\otimes Z\otimes I^{\otimes
n-l-1},Z\otimes I^{\otimes n},\dots,Z\otimes I^{\otimes n})$ such that the
input Paulis into the two qubit gate in the first layer of unitary $U$ that
operates on the first qubit is $Z\otimes Z$. For example, if in the first
layer the two qubit gate that operates on the first qubit couples it with the
5th qubit then $Z\otimes I^{l}\otimes Z\otimes I^{\otimes n-l-1}=Z\otimes
I^{3}\otimes Z\otimes I^{\otimes n-4}$.

As the architecture that we consider puts every qubit register through a two
qubit gate in each layer $j\in[d_{U}]$, we assume that $n+1$ is even. This is
the same architecture used in [23]. For notational simplicity in the
decomposition of $U$ into two qubit gates
$\\{V_{j,i}:j\in[d_{U}],i\in[(n+1)/2]\\}$ as in the previous section, we
denote the two qubit gate operating on the first qubit register in each layer
$j$ as $V_{j,1}$. So for Pauli path $\mathbf{r}$, these are the only two qubit
gates in $U$ (therefore in the entire mQSVT circuit) that has non-identity
input and output Paulis in the Pauli path approximation.

Now if by using $q(U,x)$ in sXQUATH (Definition 6) as an approximation to
$p(U,x)$ and by expanding the squares and simplifying the terms we get

sXQ
$\displaystyle=2^{2n}\bigg{(}{\mathbb{E}}_{U,X}\Big{[}\Big{(}p(U,X)-\frac{1}{2^{n}}\Big{)}^{2}\Big{]}-{\mathbb{E}}_{U,X}\Big{[}\Big{(}p(U,X)-q(U,X)\Big{)}^{2}\Big{]}\bigg{)}$
(45)
$\displaystyle=2^{2n}{\mathbb{E}}_{U,X}\bigg{[}\frac{1}{2^{2n}}-\frac{2}{2^{n}}p(U,X)-q(U,X)^{2}+2p(U,X)q(U,X)\bigg{]}$
(46) $\displaystyle=\frac{2^{2n}}{2^{n}-1}\sum_{x\neq
0^{n}}{\mathbb{E}}_{U}\bigg{[}\frac{1}{2^{2n}}-\frac{2}{2^{n}}p(U,x)-q(U,x)^{2}+2p(U,x)q(U,x)\bigg{]}$
(47) $\displaystyle=\frac{2^{2n}}{2^{n}-1}\sum_{x\neq
0^{n}}{\mathbb{E}}_{U}\bigg{[}\frac{1}{2^{2n}}-\frac{2}{2^{n}}p(U,x)-q(U,x)^{2}+\frac{2}{2^{n}}p(U,x)+2p(U,x)F(U,\mathbf{r},x)\bigg{]}$
(48) $\displaystyle=\frac{2^{2n}}{2^{n}-1}\sum_{x\neq
0^{n}}{\mathbb{E}}_{U}\bigg{[}\frac{1}{2^{2n}}-\Big{(}\frac{1}{2^{2n}}+\frac{2}{2^{n}}F(U,\mathbf{r},x)+F(U,\mathbf{r},x)^{2}\Big{)}+2p(U,x)F(U,\mathbf{r},x)\bigg{]}$
(49) $\displaystyle=\frac{2^{2n}}{2^{n}-1}\sum_{x\neq
0^{n}}\bigg{(}-\frac{2}{2^{n}}{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{r},x)\Big{]}-{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{r},x)^{2}\Big{]}+2{\mathbb{E}}_{U}\Big{[}p(U,x)F(U,\mathbf{r},x)\Big{]}\bigg{)}\;.$
(50)

Furthermore if we express the probability $p(U,x)$ in terms of Pauli paths,
namely $p(U,x)=\sum_{\mathbf{s}}F(U,\mathbf{s},x)$ we get

$\displaystyle{\mathbb{E}}_{U}\Big{[}p(U,x)F(U,\mathbf{r},x)\Big{]}$
$\displaystyle=\sum_{\mathbf{s}}{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)\Big{]}$
(51)

where the first equality is obtained by expanding $p(U,x)$ in terms of Pauli
paths (eqn.(25)). Hence the sXQUATH expression above becomes

sXQ $\displaystyle=\frac{2^{2n}}{2^{n}-1}\sum_{x\neq
0^{n}}\bigg{(}-\frac{2}{2^{n}}{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{r},x)\Big{]}+{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{r},x)^{2}\Big{]}+2\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)\Big{]}\bigg{)}\;.$
(52)

Now we treat each terms in the sum over $x$ above separately.

For the first term in the outer sum of eqn. (52), we have
${\mathbb{E}}_{U}[F(U,\mathbf{r},x)]=0$ because by expanding it in terms of
the Pauli paths as in eqn. (28) we get the term

$\displaystyle\frac{1}{2^{4}}{\mathbb{E}}_{V}\Big{[}\textup{Tr}\Big{(}V^{\otimes
2}ZI\otimes ZZ(V^{\dagger})^{\otimes 2}ZI\otimes
ZI\Big{)}\Big{]}=\frac{1}{2^{4}}G(ZI,ZZ;ZI,ZI)=0$ (53)

by eqn. (30). For the second term ${\mathbb{E}}_{U}[F(U,\mathbf{r},x)^{2}]$,
we use eqn. (32) with $\mathbf{r}=\mathbf{s}$ and evaluate the product of
Haar-random expectation values using (43), (41), and (42) to get

$\displaystyle\prod_{j=1}^{d_{U}}\prod_{i=1}^{(n+1)/2}{\mathbb{E}}_{V_{j,i}}\Big{[}\textup{Tr}\Big{(}V_{j,i}^{\otimes
4}(r_{j,i}\otimes\tilde{r}_{j,i}\otimes
s_{j,i}\otimes\tilde{s}_{j,i})(V_{j,i}^{\dagger})^{\otimes
4}(r_{j+1,i}\otimes\tilde{r}_{j+1,i}\otimes
s_{j+1,i}\otimes\tilde{s}_{j+1,i})\Big{)}\Big{]}$ (54)
$\displaystyle=G(ZZ/2,ZI/2,ZZ/2,ZI/2;ZI/2,ZI/2,ZI/2,ZI/2)$
$\displaystyle\quad\Big{(}G(ZI/2,ZI/2,ZI/2,ZI/2;ZI/2,ZI/2,ZI/2,ZI/2)\Big{)}^{d_{U}-1}$
$\displaystyle\quad\Big{(}G(II/2,II/2,II/2,II/2;II/2,II/2,II/2,II/2)\Big{)}^{(d_{U}-1)+\frac{n-1}{2}}$
$\displaystyle=\frac{95232}{2^{8}\Delta}\bigg{(}\frac{90048}{2^{8}\Delta}\bigg{)}^{d_{U}-1}$
$\displaystyle=(2^{8}\Delta)^{-d_{U}}\times 95232\times 90048^{d_{U}-1}\;.$

For shorthand let $\gamma=(2^{8}\Delta)^{-d_{U}}\times 95232\times
90048^{d_{U}-1}$, so by substituting this into eqn. (32) we get

$\displaystyle{\mathbb{E}}_{U}[F(U,\mathbf{r},x)^{2}]=\gamma\llangle
0x|\tilde{r}_{1}\rrangle^{2}\llangle\tilde{r}_{d_{U}+1}|R(\varphi_{1})|r_{d_{U}+1}\rrangle^{2}\llangle
r_{1}|0^{n+1}\rrangle^{2}$ (55)
$\displaystyle\quad=\frac{\gamma}{2^{4(n+1)}}\underbrace{\langle 0x|Z\otimes
I^{\otimes
n}|0x\rangle^{2}}_{=1}\,\underbrace{\textup{Tr}\big{(}R(\varphi_{1})ZR(\varphi_{1})^{\dagger}Z\big{)}^{2}}_{=2^{2}}\underbrace{\textup{Tr}(I^{\otimes
n})^{2}}_{2^{2n}}\,\underbrace{\langle 0^{n+1}|Z\otimes Z\otimes I^{\otimes
n-1}|0^{n+1}\rangle^{2}}_{=1}$ $\displaystyle\quad=\frac{\gamma}{2^{2(n+1)}}$

because $\langle y|I|y\rangle=1$ for $y\in\\{0,1\\}$ and $\langle
0|Z|0\rangle=1$ and because $R(\varphi_{1})$ and $Z$ commute. Since this is
true for all $x\neq 0^{n}$ then by pulling in the sum over $x\neq 0^{n}$ in
eqn. (52) inside the brackets we get the term

$\sum_{x\neq
0^{n}}{\mathbb{E}}_{U}[F(U,\mathbf{r},x)^{2}]=\frac{2^{n}-1}{2^{2(n+1)}}\gamma\;.$
(56)

Now we are left with the
$\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}[F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)]$
term in eqn. (52), where we need to evaluate this for every Pauli path
$\mathbf{s}$ such that $\mathbf{s}\neq\mathbf{r}$. Again we expand
${\mathbb{E}}_{U}[F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)]$ using eqn. (32) which
contains product of Haar-random expectations

$\displaystyle\gamma_{\mathbf{s}}$
$\displaystyle=\prod_{j=1}^{d_{U}}\prod_{i=1}^{(n+1)/2}{\mathbb{E}}_{V_{j,i}}\Big{[}\textup{Tr}\Big{(}V_{j,i}^{\otimes
4}(r_{j,i}\otimes\tilde{r}_{j,i}\otimes
s_{j,i}\otimes\tilde{s}_{j,i})(V_{j,i}^{\dagger})^{\otimes
4}(r_{j+1,i}\otimes\tilde{r}_{j+1,i}\otimes
s_{j+1,i}\otimes\tilde{s}_{j+1,i})\Big{)}\Big{]}$ (57)
$\displaystyle=G(ZZ/2,ZI/2,s_{1,1},\tilde{s}_{1,1};ZI/2,ZI/2,s_{2,1},\tilde{s}_{2,1})$
$\displaystyle\quad\bigg{(}\prod_{j=2}^{d_{U}}G(ZI/2,ZI/2,s_{j,1},\tilde{s}_{j,1};ZI/2,ZI/2,s_{j+1,1},\tilde{s}_{j+1,1})\bigg{)}$
$\displaystyle\quad\bigg{(}\prod_{j=1}^{d_{U}}\prod_{i=2}^{(n+1)/2}G(II/2,II/2,s_{j,i},\tilde{s}_{j,i};II/2,II/2,s_{j+1,i},\tilde{s}_{j+1,i})\bigg{)}\;.$

Note that $\gamma_{\mathbf{s}}$ is non-zero if and only if Pauli path
$\mathbf{s}$ is such that all instance of $G$ in it is non-zero, which can be
identified using (43), (41), and (42). Moreover, the values of $\llangle
s_{1,1}|00\rrangle$ and $\llangle 0x_{1}|\tilde{s}_{1,1}\rrangle$ also
determines which $\mathbf{s}$ gives a non-zero
${\mathbb{E}}_{U}[F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)]$. Their values for all
$\mathbf{s}$ such that $\gamma_{\mathbf{s}}\neq 0$ (see eqn.(43)) are

$\displaystyle\llangle s_{1,1}|00\rrangle=\begin{cases}0\quad&\textup{if
$s_{1,1}\in\\{PX/2,PY/2\\}$}\\\ \frac{1}{2}\quad&\textup{if
$s_{1,1}\in\\{ZI/2,ZZ/2,IZ/2,II/2\\}$}\end{cases}$ (58) $\displaystyle\llangle
0x_{1}|\tilde{s}_{1,1}\rrangle=\begin{cases}0\quad&\textup{if
$\tilde{s}_{1,1}\in\\{PX/2,PY/2\\}$}\\\ \frac{1}{2}\quad&\textup{if
$\tilde{s}_{1,1}\in\\{ZI/2,II/2\\}$}\\\ \frac{1}{2}\quad&\textup{if
$\tilde{s}_{1,1}\in\\{ZZ/2,IZ/2\\}$ and $x_{1}=0$}\\\
-\frac{1}{2}\quad&\textup{if $\tilde{s}_{1,1}\in\\{ZZ/2,IZ/2\\}$ and
$x_{1}=1$}\end{cases}\;,$

which implies that we only need to consider $\mathbf{s}$ (i.e. those that
gives nonzero $\gamma_{\mathbf{s}}$ and $\llangle s_{1,1}|00\rrangle$ and
$\llangle 0x_{1}|\tilde{s}_{1,1}\rrangle$) such that

$(s_{1,1},\tilde{s}_{1,1})\in\\{(ZI/2,ZZ/2),(ZZ/2,ZI/2),(IZ/2,II/2),(II/2,IZ/2)\\}\;.$
(59)

Now by doing similar calculation as in (55),

$\displaystyle{\mathbb{E}}_{U}[F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)]$ (60)
$\displaystyle=\gamma_{\mathbf{s}}\llangle 0x|\tilde{r}_{1}\rrangle\llangle
0x|\tilde{s}_{1}\rrangle\llangle\tilde{r}_{d_{U}+1}|R(\varphi_{1})|r_{d_{U}+1}\rrangle\llangle\tilde{s}_{d_{U}+1}|R(\varphi_{1})|s_{d_{U}+1}\rrangle\llangle
r_{1}|0^{n+1}\rrangle\llangle s_{1}|0^{n+1}\rrangle$
$\displaystyle=\frac{\gamma_{\mathbf{s}}}{2^{2n}}\llangle
0x_{1}|\tilde{s}_{1,1}\rrangle\,\llangle s_{1,1}|00\rrangle\;.$

Then by pulling the sum over $x\neq 0^{n}$ inside the brackets in eqn. (52),
we get

$\displaystyle\sum_{x\neq
0^{n}}\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}[F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)]$
$\displaystyle=\frac{1}{2^{2n}}\sum_{x\neq
0^{n}}\sum_{\mathbf{s}\neq\mathbf{r}}\gamma_{\mathbf{s}}\llangle
0x_{1}|\tilde{s}_{1,1}\rrangle\,\llangle s_{1,1}|00\rrangle$ (61)
$\displaystyle=\frac{1}{2^{2n}}\sum_{\mathbf{s}\in\mathcal{S}}\gamma_{\mathbf{s}}\llangle
s_{1,1}|00\rrangle\,\Big{(}(2^{n-1}-1)\llangle
00|\tilde{s}_{1,1}\rrangle+2^{n-1}\llangle 01|\tilde{s}_{1,1}\rrangle\Big{)}$

where $\mathcal{S}$ is the set of Pauli paths such that
$\mathbf{s}\neq\mathbf{r}$ and $\gamma_{\mathbf{s}}\neq 0$ and $\llangle
s_{1,1}|00\rrangle\neq 0$ and $\llangle 0x_{1}|\tilde{s}_{1,1}\rrangle\neq 0$.
Now consider a fixed
$s_{2},\dots,s_{d_{U}+1},\tilde{s}_{d_{U}+1},\dots,\tilde{s}_{2}\neq
r_{2},\dots,r_{d_{U}+1},\tilde{r}_{d_{U}+1},\dots,\tilde{r}_{2}$. By using
eqn. (43), let $\gamma_{\mathbf{s}}(Z^{3})$ be the product of Haar moments for
a Pauli path $\mathbf{s}$ such that
$(s_{1,1},\tilde{s}_{1,1})\in\\{(ZI/2,ZZ/2),(ZZ/2,ZI/2)\\}$ and
$\gamma_{\mathbf{s}}(Z^{1})$ the product of Haar moments for a Pauli path
$\mathbf{s}$ such that
$(s_{1,1},\tilde{s}_{1,1})\in\\{(IZ/2,II/2),(II/2,IZ/2)\\}$. For such Pauli
paths $s_{2},\dots,s_{d_{U}+1},\tilde{s}_{d_{U}+1},\dots,\tilde{s}_{2}$ we
have

$\displaystyle\sum_{s_{1,1},\tilde{s}_{1,1}}\gamma_{\mathbf{s}}\llangle
s_{1,1}|00\rrangle\,\Big{(}(2^{n-1}-1)\llangle
00|\tilde{s}_{1,1}\rrangle+2^{n-1}\llangle 01|\tilde{s}_{1,1}\rrangle\Big{)}$
(62)
$\displaystyle=\bigg{(}\sum_{s_{1,1},\tilde{s}_{1,1}}\frac{\gamma_{\mathbf{s}}(2^{n-1}-1)}{4}\bigg{)}+\bigg{(}\frac{\gamma_{\mathbf{s}(Z^{3})}}{2}\Big{(}\frac{2^{n-1}}{2}-\frac{2^{n-1}}{2}\Big{)}+\frac{\gamma_{\mathbf{s}(Z^{1})}}{2}\Big{(}\frac{2^{n-1}}{2}-\frac{2^{n-1}}{2}\Big{)}\bigg{)}$
$\displaystyle=\sum_{s_{1,1},\tilde{s}_{1,1}}\frac{\gamma_{\mathbf{s}}(2^{n-1}-1)}{4}\;,$

where the sum is over the pair $s_{1,1},\tilde{s}_{1,1}$ in (59). Note that
the first equality is due to $\llangle s_{1,1}|00\rrangle=\llangle
00|\tilde{s}_{1,1}\rrangle=\frac{1}{2}$. For
$s_{2},\dots,s_{d_{U}+1},\tilde{s}_{d_{U}+1},\dots,\tilde{s}_{2}=r_{2},\dots,r_{d_{U}+1},\tilde{r}_{d_{U}+1},\dots,\tilde{r}_{2}$,
similarly we get

$\displaystyle\sum_{s_{1,1},\tilde{s}_{1,1}}\gamma_{\mathbf{s}}\llangle
s_{1,1}|00\rrangle\,\Big{(}(2^{n-1}-1)\llangle
00|\tilde{s}_{1,1}\rrangle+2^{n-1}\llangle 01|\tilde{s}_{1,1}\rrangle\Big{)}$
(63)
$\displaystyle=\bigg{(}\sum_{s_{1,1},\tilde{s}_{1,1}}\frac{\gamma_{\mathbf{s}}(2^{n-1}-1)}{4}\bigg{)}+\bigg{(}\frac{\gamma_{\mathbf{s}(Z^{3})}}{2}\Big{(}-\frac{2^{n-1}}{2}\Big{)}+\frac{\gamma_{\mathbf{s}(Z^{1})}}{2}\Big{(}\frac{2^{n-1}}{2}-\frac{2^{n-1}}{2}\Big{)}\bigg{)}$
$\displaystyle=\frac{\gamma_{\mathbf{s}(Z^{3})}(2^{n-1}-1)}{2}+\frac{\gamma_{\mathbf{s}(Z^{1})}(2^{n-1}-1)}{2}-\frac{\gamma_{\mathbf{s}(Z^{3})}2^{n-1}}{4}$
$\displaystyle=\frac{\gamma_{\mathbf{s}(Z^{3})}(2^{n-1}-2)}{4}+\frac{\gamma_{\mathbf{s}(Z^{1})}(2^{n-1}-1)}{2}\;,$

where the sum in the first and second line are over the pair
$s_{1,1},\tilde{s}_{1,1}$ in (59) except for
$(s_{1,1},\tilde{s}_{1,1})=(ZZ/2,ZI/2)$ because
$(r_{1,1},\tilde{r}_{1,1})=(ZZ/2,ZI/2)$ and we require that
$\mathbf{s}\neq\mathbf{r}$. Hence by substituting eqn.(62) and eqn. (63) back
into eqn. (61) we obtain

$\displaystyle\sum_{x\neq
0^{n}}\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}[F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)]$
(64)
$\displaystyle=\frac{1}{2^{2n}}\bigg{(}\sum_{s_{1,1},\tilde{s}_{1,1}}\sum_{\mathbf{s}_{2:}\in\mathcal{S}_{2:}\backslash\\{\mathbf{r}_{2:}\\}}\frac{\gamma_{\mathbf{s}}(2^{n-1}-1)}{4}\bigg{)}+\frac{1}{2^{2n}}\bigg{(}\frac{\gamma_{\mathbf{s}(Z^{3})}(2^{n-1}-2)}{4}+\frac{\gamma_{\mathbf{s}(Z^{1})}(2^{n-1}-1)}{2}\bigg{)}$

where we denote
$\mathbf{s}_{2:}=s_{2},\dots,s_{d_{U}+1},\tilde{s}_{d_{U}+1},\dots,\tilde{s}_{2}$
and $\mathcal{S}_{2:}\backslash\\{\mathbf{r}_{2:}\\}$ is the set of
$\mathbf{s}_{2:}\neq
r_{2},\dots,r_{d_{U}+1},\tilde{r}_{d_{U}+1},\dots,\tilde{r}_{2}$. Also, here
the product of Haar moments $\gamma_{\mathbf{s}}(Z^{3})$ and
$\gamma_{\mathbf{s}}(Z^{1})$ are such that
$\mathbf{s}_{2:}=r_{2},\dots,r_{d_{U}+1},\tilde{r}_{d_{U}+1},\dots,\tilde{r}_{2}$.

We now analyze the value of the $\gamma_{\mathbf{s}}$’s. For Pauli path
$\mathbf{s}$ such that
$\mathbf{s}_{2:}=r_{2},\dots,r_{d_{U}+1},\tilde{r}_{d_{U}+1},\dots,\tilde{r}_{2}$
a calculation similar to eqn. (54) by using (43) gives us

$\displaystyle\gamma_{\mathbf{s}}(Z^{3})$
$\displaystyle=\bigg{(}\frac{90048}{2^{8}\Delta}\bigg{)}^{d_{U}-1}G(ZZ/2,ZI/2,IZ/2,ZZ/2;ZI/2,ZI/2,ZI/2,ZI/2)$
(65) $\displaystyle=(2^{8}\Delta)^{-d_{U}}\times 95232\times 90048^{d_{U}-1}$
and $\displaystyle\gamma_{\mathbf{s}}(Z^{1})$
$\displaystyle=\bigg{(}\frac{90048}{2^{8}\Delta}\bigg{)}^{d_{U}-1}G(ZZ/2,ZI/2,IZ/2,II/2;ZI/2,ZI/2,ZI/2,ZI/2)$
$\displaystyle=\bigg{(}\frac{90048}{2^{8}\Delta}\bigg{)}^{d_{U}-1}G(ZZ/2,ZI/2,II/2,IZ/2;ZI/2,ZI/2,ZI/2,ZI/2)$
$\displaystyle=(2^{8}\Delta)^{-d_{U}}\times 73664\times 90048^{d_{U}-1}\;.$

Hence, the second term in (64) is

$\displaystyle\frac{1}{2^{2n}}\bigg{(}\frac{\gamma_{\mathbf{s}(Z^{3})}(2^{n-1}-2)+\gamma_{\mathbf{s}(Z^{1})}(2^{n}-2)}{4}\bigg{)}$
$\displaystyle=\frac{1}{2^{2n}}\bigg{(}\frac{(2^{n-1}\times 242560-2\times
168896)90048^{d_{U}-1}}{4(2^{8}\Delta)^{d_{U}}}\bigg{)}\;,$ (66)

which is positive for all $n\geq 2$.

For Pauli paths $\mathbf{s}$ such that $\mathbf{s}_{2:}\neq
r_{2},\dots,r_{d_{U}+1},\tilde{r}_{d_{U}+1},\dots,\tilde{r}_{2}$, let us
denote

$\begin{gathered}g_{1}(s,\tilde{s},s^{\prime},\tilde{s}^{\prime})=G(ZZ/2,ZI/2,s,\tilde{s};ZI/2,ZI/2,s^{\prime},\tilde{s}^{\prime})\\\
g_{2}(s,\tilde{s},s^{\prime},\tilde{s}^{\prime})=G(ZI/2,ZI/2,s,\tilde{s};ZI/2,ZI/2,s^{\prime},\tilde{s}^{\prime})\\\
g_{3}(s,\tilde{s},s^{\prime},\tilde{s}^{\prime})=G(II/2,II/2,s,\tilde{s};II/2,II/2,s^{\prime},\tilde{s}^{\prime})\;,\end{gathered}$
(67)

so that we can write $\gamma_{\mathbf{s}}$ as

$\displaystyle\gamma_{\mathbf{s}}=g_{1}(s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1})\bigg{(}\prod_{j=2}^{d_{U}}g_{2}(s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1})\bigg{)}\bigg{(}\prod_{j=1}^{d_{U}}\prod_{i=2}^{(n+1)/2}g_{3}(s_{j,i},\tilde{s}_{j,i},s_{j+1,i},\tilde{s}_{j+1,i})\bigg{)}\;.$
(68)

For such Pauli path, in the product of Haar moments $\gamma_{\mathbf{s}}$ (see
eqn. (57)) there are:

  1. 1.

2 possible $s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1}$ such that
$g_{1}(s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1})=95232(2^{8}\Delta)^{-1}$

  2. 2.

2 possible $s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1}$ such that
$g_{1}(s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1})=73664(2^{8}\Delta)^{-1}$

  3. 3.

28 possible $s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1}$ such that
$g_{1}(s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1})=-6656(2^{8}\Delta)^{-1}$

  4. 4.

28 possible $s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1}$ such that
$g_{1}(s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1})=960(2^{8}\Delta)^{-1}$.

For each $j\in\\{2,\dots,d_{U}\\}$, there are:

  1. 1.

1 possible $s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1}$ such that
$g_{2}(s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1})=90048(2^{8}\Delta)^{-1}$

  2. 2.

$14\times 14=196$ possible
$s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1}$ such that
$g_{2}(s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1})=31680(2^{8}\Delta)^{-1}$

  3. 3.

28 possible $s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1}$ such that
$g_{2}(s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1})=18368(2^{8}\Delta)^{-1}$

  4. 4.

1 possible $s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1}$ such that
$g_{2}(s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1})=602048(2^{8}\Delta)^{-1}$.

For each $j\in\\{1,\dots,d_{U}\\}$ and $i\in\\{2,\dots,(n+1)/2\\}$ there are:

  1. 1.

1 possible $s_{j,i},\tilde{s}_{j,i},s_{j+1,i},\tilde{s}_{j+1,i}$ such that
$g_{3}(s_{j,i},\tilde{s}_{j,i},s_{j+1,i},\tilde{s}_{j+1,i})=1$

  2. 2.

$15\times 15=225$ possible
$s_{j,i},\tilde{s}_{j,i},s_{j+1,i},\tilde{s}_{j+1,i}$ such that
$g_{3}(s_{j,i},\tilde{s}_{j,i},s_{j+1,i},\tilde{s}_{j+1,i})=31680(2^{8}\Delta)^{-1}$.

Note that among all possible values of $g_{1},g_{2},g_{3}$ there is only a
single negative value, namely when $g_{1}$ takes the argument of
$\\{s,\tilde{s}\\}=\\{ZZ/2,ZI/2\\}$ and
$s^{\prime}=\tilde{s}^{\prime}\notin\\{ZI/2,II/2\\}$ in which it gives
$-6656(2^{8}\Delta)^{-1}$. Hence two products of $g_{2}$’s and $g_{3}$’s in
(68) are positive for any Pauli path $\mathbf{s}$. Now if we fix all Paulis in
$\mathbf{s}$ except for $s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1}$ then
let

$\displaystyle\xi_{\mathbf{s}}$
$\displaystyle=\sum_{s_{1,1},\tilde{s}_{1,1}}\sum_{s_{2,1},\tilde{s}_{2,1}}\frac{\gamma_{\mathbf{s}}(2^{n-1}-1)}{4}$
(69)
$\displaystyle=\frac{2^{n-1}-1}{4}\bigg{(}\prod_{j=2}^{d_{U}}g_{2}(s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1})\bigg{)}\bigg{(}\prod_{j=1}^{d_{U}}\prod_{i=2}^{(n+1)/2}g_{3}(s_{j,i},\tilde{s}_{j,i},s_{j+1,i},\tilde{s}_{j+1,i})\bigg{)}$
$\displaystyle\quad\times\Big{(}2\times 95232+2\times
73664+28\times(-6656)+28\times 960\Big{)}(2^{8}\Delta)^{-1}$
$\displaystyle=\frac{2^{n-1}-1}{4}\frac{178304}{2^{8}\Delta}\bigg{(}\prod_{j=2}^{d_{U}}g_{2}(s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1})\bigg{)}\bigg{(}\prod_{j=1}^{d_{U}}\prod_{i=2}^{(n+1)/2}g_{3}(s_{j,i},\tilde{s}_{j,i},s_{j+1,i},\tilde{s}_{j+1,i})\bigg{)}\;,$

which is positive. Therefore for any choice of Paulis that determines the
value of the $g_{2}$’s and $g_{3}$’s, namely
$\\{(s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1})\\}_{j=2}^{d_{U}}$
and
$\\{(s_{j,i},\tilde{s}_{j,i},s_{j+1,i},\tilde{s}_{j+1,i})\\}_{j=1,i=2}^{d_{U},(n+1)/2}$,
the first term of eqn. (64) are positive. Hence we can obtain a lower bound

$\displaystyle\frac{1}{2^{2n}}\bigg{(}\sum_{\mathbf{s}\backslash\\{s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1}\\}}\sum_{s_{1,1},\tilde{s}_{1,1}}\sum_{s_{2,1},\tilde{s}_{2,1}}\frac{\gamma_{\mathbf{s}}(2^{n-1}-1)}{4}\bigg{)}$
(70)
$\displaystyle=\frac{1}{2^{2n}}\bigg{(}\sum_{\mathbf{s}\backslash\\{s_{1,1},\tilde{s}_{1,1},s_{2,1},\tilde{s}_{2,1}\\}}\xi_{\mathbf{s}}\bigg{)}$
$\displaystyle\geq\frac{1}{2^{2n}}\frac{2^{n-1}-1}{4}\frac{178304}{2^{8}\Delta}\bigg{(}\frac{602048}{2^{8}\Delta}\bigg{)}^{d_{U}-1}$

by simply picking a single term in the sum on the second line where Pauli path
$\mathbf{s}$ is such that
$\\{(s_{j,1},\tilde{s}_{j,1},s_{j+1,1},\tilde{s}_{j+1,1})\\}_{j=2}^{d_{U}}$
and
$\\{(s_{j,i},\tilde{s}_{j,i},s_{j+1,i},\tilde{s}_{j+1,i})\\}_{j=1,i=2}^{d_{U},(n+1)/2}$
are all identities $II/2$. Note that this choice of $\mathbf{s}$ indeed
satisfies $\mathbf{s}\neq\mathbf{r}$.

Finally by substituting eqn. (66) and eqn. (70) back into (64) we get a lower
bound

$\displaystyle\sum_{x\neq
0^{n}}\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}[F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)]$
(71) $\displaystyle\geq\frac{(2^{n-1}-1)\times 178304\times
602048^{d_{U}-1}+(2^{n-1}\times 242560-2\times
168896)90048^{d_{U}-1}}{2^{2n+2}(2^{8}\Delta)^{d_{U}}}$

Putting eqn. (56) and eqn. (71) into sXQUATH value (52) gives us the final
lower bound

sXQ $\displaystyle=\frac{2^{2n}}{2^{n}-1}\sum_{x\neq
0^{n}}\bigg{(}-\frac{2}{2^{n}}{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{r},x)\Big{]}+{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{r},x)^{2}\Big{]}+2\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)\Big{]}\bigg{)}$
(72)
$\displaystyle\geq\frac{1}{2^{n}-1}\bigg{(}\frac{2^{n}-1}{2^{2}}\frac{95232\times
90048^{d_{U}-1}}{(2^{8}\Delta)^{d_{U}}}$
$\displaystyle\quad+\frac{(2^{n-1}-1)\times 178304\times
602048^{d_{U}-1}+(2^{n-1}\times 242560-2\times
168896)90048^{d_{U}-1}}{2^{2}(2^{8}\Delta)^{d_{U}}}\bigg{)}$
$\displaystyle\approx\frac{95232\times
90048^{d_{U}-1}}{2^{2}(2^{8}\Delta)^{d_{U}}}+\frac{178304\times
602048^{d_{U}-1}+242560\times 90048^{d_{U}-1}}{2^{3}(2^{8}\Delta)^{d_{U}}}$
$\displaystyle=c^{d_{U}}$

for some constant $c\in(0,1)$ independent of number of qubits $n$ and sub-
circuit $U$ depth $d_{U}$. By setting $d_{U}=o(n)$, this refutes sXQUATH for
single-block mQSVT circuit.

##  Appendix I Spoofing cross-entropy benchmarking using Pauli path simulation

Here we show Theorem 2 by using Pauli path algorithm to spoof sXES
benchmarking defined in eqn. (17), on average. This is done by using the Pauli
path algorithm in the proof of Theorem 1 (explained in detail in Supplementary
Material H). The average sXES score over random unitary $U$ is given by

$\displaystyle\mathrm{sXES}={\mathbb{E}}_{U}[\mathrm{sXES}(U)]={\mathbb{E}}_{U}\Big{[}\sum_{x\neq
0^{n}}p(U,x)\,q(U,x)\Big{]}\;.$ (73)

For convenience we restate the approximation $q(U,x)$ in Supplementary
Material H

$\displaystyle q(U,x)=\frac{1}{2^{n}}+F(U,\mathbf{r},x)\;,$ (74)

for Pauli path $\mathbf{r}=(Z\otimes I^{l}\otimes Z\otimes I^{\otimes
n-l-1},Z\otimes I^{\otimes n},\dots,Z\otimes I^{\otimes n})$. Details of this
Pauli path algorithm, i.e. which two-qubit unitary the input and output Paulis
correspond to, are in the paragraphs surrounding eqn.(44).

By using this Pauli path simulation, we can write the sXES score as

$\displaystyle\mathrm{sXES}$ $\displaystyle=\sum_{x\neq
0^{n}}{\mathbb{E}}_{U}\Big{[}p(U,x)\,\Big{(}\frac{1}{2^{n}}+F(U,\mathbf{r},x)\Big{)}\Big{]}$
(75) $\displaystyle=\sum_{x\neq
0^{n}}{\mathbb{E}}_{U}\Big{[}\frac{p(U,x)}{2^{n}}\Big{]}+{\mathbb{E}}_{U}\Big{[}p(U,x)\,F(U,\mathbf{r},x)\Big{]}$
$\displaystyle=\sum_{x\neq
0^{n}}{\mathbb{E}}_{U}\Big{[}\frac{p(U,x)}{2^{n}}\Big{]}+\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}\Big{[}F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)\Big{]}\;.$

Note that we can lower bound the second term using eqn. (71), restated below
for convenience

$\displaystyle\sum_{x\neq
0^{n}}\sum_{\mathbf{s}\neq\mathbf{r}}{\mathbb{E}}_{U}[F(U,\mathbf{s},x)\,F(U,\mathbf{r},x)]$
(76) $\displaystyle\geq\frac{(2^{n-1}-1)\times 178304\times
602048^{d_{U}-1}+(2^{n-1}\times 242560-2\times
168896)90048^{d_{U}-1}}{2^{2n+2}(2^{8}\Delta)^{d_{U}}}\;.$

Hence we can lower bound sXES score of this Pauli path simulation as

$\displaystyle\mathrm{sXES}$
$\displaystyle\geq\frac{1}{2^{n}}{\mathbb{E}}_{U}\Big{[}\sum_{x\neq
0^{n}}p(U,x)\Big{]}+\frac{(2^{n-1}-1)\times 178304\times
602048^{d_{U}-1}+(2^{n-1}\times 242560-2\times
168896)90048^{d_{U}-1}}{2^{2n+2}(2^{8}\Delta)^{d_{U}}}$ (77)
$\displaystyle\approx\frac{1}{2^{n}}\Big{(}{\mathbb{E}}_{U}\Big{[}\sum_{x\neq
0^{n}}p(U,x)\Big{]}+c^{d_{U}}\Big{)}$

for some constant $c\in(0,1)$ independent of $n$ and $d_{U}$.