\bra{x_j}\bra{x_j}\mathsf{N}(\gamma_j)\ket{x_j}\ket{x_j} \leq \max\{\bra{x_j}\bra{x_j}\mathsf{N}(I_4)\ket{x_j}\ket{x_j},\bra{x_j}\bra{x_j}\mathsf{N}(S)\ket{x_j}\ket{x_j}\} \eqqcolon e_j
\end{equation}

for each $j$.

\begin{equation}
\mathbb{E}_{\mathcal{B}}[p_{x}^2] \leq \left[\sum_{\gamma_1,\gamma_2,\ldots, \gamma_n \in \{I_4,S\}}\left(\sum_{\substack{\gamma \in \{I_4,S\}^{n\times (s+1)} \\ \gamma^{s+1} = \gamma_1\gamma_2\cdots \gamma_n}} \mathrm{wt}_{\mathrm{B}'}(\gamma)\right)\right]\left(e_1e_2\cdots e_n\right).
\end{equation}

Using Eq. (<ref>),

\begin{equation}
\mathbb{E}_{\mathcal{B}}[p_{x}^2] \leq \mathbb{E}_{\mathcal{B}'}[p_{x}^2]\left(e_1e_2\cdots e_n\right).
\end{equation}

By Lemma <ref>, since $\mathbb{E}_{\mathcal{B}'}[p_{x}^2] \leq \mathbb{E}_{\tilde{\mathcal{B}}'}[p_{x}^2]$,

\begin{equation}
\label{eq:second_moment_relation1}
\mathbb{E}_{\mathcal{B}}[p_{x}^2] \leq \mathbb{E}_{\tilde{\mathcal{B}}'}[p_{x}^2]\left(e_1e_2\cdots e_n\right).
\end{equation}

Now, by the construction of $\tilde{\mathcal{B}}'$ and Proposition <ref>,

\begin{equation}
\begin{aligned}
\mathbb{E}_{\tilde{\mathcal{B}}'}[p_{x}^2]
&= \left(\frac{3}{10} - \left[\dfrac{-2a+b}{10(a+2b)} + (1-a-2b)^{d-1} \left(-\dfrac{1}{30} - \dfrac{-2a+b}{10(a+2b)}\right)\right]\right)^n.
\end{aligned}
\end{equation}

Here, we used the fact that $\bra{0}\bra{0}(2I + S)\ket{0}\ket{0} = \bra{1}\bra{1}(2I + S)\ket{1}\ket{1} = 3$ and $\bra{0}\bra{0}(I_4 - 2S)\ket{0}\ket{0} = \bra{1}\bra{1}(I_4 - 2S)\ket{1}\ket{1} = -1$.
By definition of $a$ and $b$,

\begin{align}
\label{eq:c}
c &\coloneqq 1 - (1-p)^2(1-q)\left(1 - \frac{q}{3}\right), \\
\label{eq:r}
r &\coloneqq \Bigg\{
\begin{array}{ll}
q, & \mathcal{N} =
\mathcal{N}^{(\textup{amp})}_q \circ \mathcal{N}^{(\textup{dep})}_p, \\
q(1-p), & \mathcal{N} = \mathcal{N}^{(\textup{dep})}_p \circ \mathcal{N}^{(\textup{amp})}_q,
\end{array}
\end{align}

we have

\begin{equation}
\mathbb{E}_{\tilde{\mathcal{B}}'}[p_{x}^2] = \left(\left(\frac{1}{4} + \frac{r^2}{12c}\right) +
(1 - c)^{d-1} \left(\dfrac{1}{12} - \dfrac{r^2}{12c}\right) \right)^n.
\end{equation}

By taking

\begin{align}
\mu &= \frac{1}{4} + \frac{r^2}{12c}, \\
\nu &= \dfrac{1}{12} - \dfrac{r^2}{12c},
\end{align}

\begin{equation}
\mathbb{E}_{\tilde{\mathcal{B}}'}[p_{x}^2] = \left(\mu +
(1 - c)^{d-1} \nu \right)^n.
\end{equation}

Here, we will check $\mu,\nu \geq 0$.
It trivially follows that $\mu \geq 0$ from the definition.
Next, we evaluate $\nu$.
Since $r \leq q$ by definition,

\begin{align}
\nu
&= \dfrac{1}{12} - \dfrac{r^2}{12c}\\
&\geq \dfrac{1}{12} - \dfrac{q^2}{12c} \\
&= \dfrac{c - q^2}{12c}.
\end{align}

By substituting <ref> and <ref>,

\begin{align}
\dfrac{c - q^2}{12c}
&= \dfrac{1 - (1-p)^2(1-q)\left(1 - \frac{q}{3}\right) - q^2}{12c}.
\end{align}

Since $(1-p)^2 \leq 1$,

\begin{align}
\dfrac{1 - (1-p)^2(1-q)\left(1 - \frac{q}{3}\right) - q^2}{12c}
&\geq \dfrac{1 - (1-q)\left(1 - \frac{q}{3}\right) - q^2}{12c} \\
&= \dfrac{\frac{4q}{3}(1-q)}{12c} \\
&= \dfrac{q(1-q)}{9c}.
\end{align}

Since $q\geq 0$ and $1-p \geq 0$, we have

\begin{align}
\nu \geq 0.
\end{align}

Since $1 + x \leq \mathrm{e}^{x}$ for all $x\in\mathbb{R}$,

\begin{equation}
\label{eq:second_moment_rekation2}\mathbb{E}_{\tilde{\mathcal{B}}'}[p_{x}^2] \leq \mu^n \exp\left[n\dfrac{\nu}{\mu} \mathrm{e}^{-c(d-1)}\right].
\end{equation}

Using Eqs. (<ref>) and (<ref>),

\begin{equation}
\label{eq:second_moment_rekation3}
\mathbb{E}_{\mathcal{B}}[p_{x}^2] \leq  \mu^n \exp\left[n\dfrac{\nu}{\mu} \mathrm{e}^{-c(d-1)}\right]\left(e_1e_2\cdots e_n\right).
\end{equation}

Now, we evaluate $e_j$.

\begin{equation}
e_j \coloneqq \max\left\{\bra{x_j}\bra{x_j}\mathsf{N}(I_4)\ket{x_j}\ket{x_j},\bra{x_j}\bra{x_j}\mathsf{N}(S)\ket{x_j}\ket{x_j}\right\}  = \Bigg\{
\begin{array}{cc}
(1+r)^2, & x_j = 0, \\
(1-r)^2, & x_j = 1.
\end{array}
\end{equation}

That is, if $w_x \geq \tfrac{n}{2}$,

\begin{equation}
\label{eq:second_moment_rekation4}
e_1e_2\cdots e_n = (1+r)^{2(n-w_x)}(1-r)^{2w_x} \leq (1+r)^{n}(1-r)^{n} = (1-r^2)^{n} = \eta^n.
\end{equation}

Combining Eqs. (<ref>) and (<ref>),

\begin{equation}
\mathbb{E}_{\mathcal{B}}[p_{x}^2] \leq  \mu^n\eta^n \exp\left[n\dfrac{\nu}{\mu} \mathrm{e}^{-c(d-1)}\right],
\end{equation}

which completes the proof.

§ PROOF OF LEMMA <REF>

Any circuit $\mathcal{C}$ in $\mathcal{B}'$ can be written in the following form.

\begin{align*}
\begin{tikzcd}[transparent,row sep=0.7em]
& \gate[2]{U_2}& \gate[1]{\mathcal{N}} & \gate[1]{U_1} &\gate[1]{\mathcal{N}} & \gate[2]{U_2} & \qw\\
& \qw & \gate[1]{\mathcal{N}} &  \gate[2]{U_2} &\gate[1]{\mathcal{N}} &  \qw &\qw\\
& \gate[2]{U_2} & \gate[1]{\mathcal{N}} & \qw &\gate[1]{\mathcal{N}} & \gate[2]{U_2} & \qw\\
&\qw & \gate[1]{\mathcal{N}} & \gate[2]{U_2} & \gate[1]{\mathcal{N}} & \qw & \qw\\
& \gate[1]{U_1} & \gate[1]{\mathcal{N}} &  \qw & \gate[1]{\mathcal{N}} & \gate[1]{U_1}& \qw
\end{tikzcd}
\end{align*}

Let $s$ be the number of 2-qubit Haar random gate in given $\mathcal{C}\in \mathcal{B}'$.
Let us introduce a numbering of the 2-qubit Haar random gates in $\mathcal{C}$: $U_2^{(k)}$ refers to the $k^{\text{th}}$ 2-qubit Haar random gate, where the counting starts from the top gate at the last layer.
Rewiring the circuit $\mathcal{C}$, we have

\begin{align}
\label{eq:circuit_0}
\begin{tikzcd}[transparent,row sep=0.7em]
& \gate[2]{U_2^{(s-1)}}& \gate[1]{U_1} & \gate[1]{\mathcal{N}}  & \gate[1]{U_1} & \qw & \gate[1]{U_1}& \gate[1]{\mathcal{N}}  & \gate[1]{U_1}& \gate[2]{U_2^{(1)}} & \qw \\
& \qw & \gate[1]{U_1}& \gate[1]{\mathcal{N}}  & \gate[1]{U_1}& \gate[2]{U_2^{(3)}} & \gate[1]{U_1}& \gate[1]{\mathcal{N}}  & \gate[1]{U_1}&\qw& \qw \\
& \gate[2]{U_2^{(s)}} & \gate[1]{U_1} & \gate[1]{\mathcal{N}}  & \gate[1]{U_1}& \qw & \gate[1]{U_1}& \gate[1]{\mathcal{N}}  & \gate[1]{U_1}& \gate[2]{U_2^{(2)}}& \qw \\
&\qw & \gate[1]{U_1} & \gate[1]{\mathcal{N}}  & \gate[1]{U_1}&\gate[2]{U_2^{(4)}} & \gate[1]{U_1}& \gate[1]{\mathcal{N}}  & \gate[1]{U_1}&\qw& \qw \\
& \qw & \gate[1]{U_1} & \gate[1]{\mathcal{N}}  & \gate[1]{U_1}& \qw & \gate[1]{U_1}& \gate[1]{\mathcal{N}}  & \gate[1]{U_1}& \qw  &\qw
\end{tikzcd}
\end{align}

Construct a sequence of circuits $\{\mathcal{C}_j: j=0,1,2,\ldots,s\}$ in the following recursive way.

* $\mathcal{C}_0 = \mathcal{C} \in \mathcal{B}'$.

* For $j = 1,2,\ldots,s$, $\mathcal{C}_j$ is a circuit obtained by replacing the leading 2-qubit Haar random gate in $\mathcal{C}_{j-1}$, i.e., $U_2^{(j)}$, by two parallel independent single-qubit Haar random gates.

By construction, $\mathcal{C}_{s}$ consists only of single-qubit Haar random gates and noise channels, and $\mathcal{C}_{s} \in \tilde{\mathcal{B}}'$.
Let $x \in \{0,1\}^n$ be any $n$-bit string.
Here, we aim to show

\begin{equation}
\underset{\mathcal{C}_0 \sim \mathcal{B}'}{\mathbb{E}}[p_x^2] \leq \underset{\mathcal{C}_s \sim \tilde{\mathcal{B}}'}{\mathbb{E}}[p_x^2],
\end{equation}

and to this end, it suffices to show

\begin{equation}
\underset{\mathcal{C}_j}{\mathbb{E}}[p_x^2] \leq \underset{\mathcal{C}_{j+1}}{\mathbb{E}}[p_x^2]
\end{equation}

for all $j = 0,1,2,\ldots, s-1$.
For this purpose, fix $j$, and let us look at $\mathcal{C}_j$ and $\mathcal{C}_{j+1}$.
We will show

\begin{equation}
\underset{\mathcal{C}_j}{\mathbb{E}}[p_x^2] \leq \underset{\mathcal{C}_{j+1}}{\mathbb{E}}[p_x^2]
\end{equation}

for this $j$.
Suppose that $U_2^{(j)}$ acts on the $k^{\text{th}}$ and $l^{\text{th}}$ qubits.
Recall the characterization shown in Eq. (<ref>).
Then, by absorbing the action of the single-qubit Haar random gates and noise channels acting on qubits other than $k^{\text{th}}$ or $l^{\text{th}}$ one to the preceding gates, we may write

\begin{equation}
\mathcal{C}_j =
\begin{tikzcd}[transparent,row sep=0.7em]
& \gate[5]{\tilde{\mathcal{C}}_j}\slice{} & \qw & \qw &\qw\\
& \qw & \qw & \qw &\qw\\
& \qw& \gate[2]{U_2^{(j+1)}} & \gate[1]{\tilde{\mathcal{U}}_{U_1,\mathcal{N}}^{(m)}}&\qw \\
&\qw & \qw & \gate[1]{\tilde{\mathcal{U}}_{U_1,\mathcal{N}}^{(m)}} &\qw\\
& \qw & \qw & \qw &\qw
\end{tikzcd}
\end{equation}

\begin{equation}
\mathcal{C}_{j+1} =
\begin{tikzcd}[transparent,row sep=0.7em]
& \gate[5]{\tilde{\mathcal{C}}_j}\slice{} & \qw & \qw &\qw\\
& \qw & \qw & \qw &\qw\\
& \qw& \gate[1]{U_1} & \gate[1]{\tilde{\mathcal{U}}_{U_1,\mathcal{N}}^{(m)}}&\qw \\
&\qw & \gate[1]{U_1} & \gate[1]{\tilde{\mathcal{U}}_{U_1,\mathcal{N}}^{(m)}} &\qw\\
& \qw & \qw & \qw &\qw
\end{tikzcd}
\end{equation}

\begin{equation}
\tilde{\mathcal{U}}_{U_1,\mathcal{N}}^{(m)} \coloneqq \underbrace{(\mathcal{U}_1 \circ \mathcal{N}\circ \mathcal{U}_1) \circ \cdots \circ (\mathcal{U}_1 \circ \mathcal{N}\circ \mathcal{U}_1) }_{m~\mathrm{times}}
\end{equation}

with some non-negative integer $m$.
Here, we consider $\{I_4,S\}^n$ bitstring representation.
Suppose that we have $\gamma \in \{I_4,S\}^n$ just before the red dashed line.
Suppose that $\gamma$ will change as

\begin{align}
&\gamma \xrightarrow{\mathcal{C}_j:\mathrm{After\,\,red\,\,line}} \sum_{\gamma' \in \{I_4,S\}^n} c^{(\gamma')}_j \gamma' \\
&\gamma \xrightarrow{\mathcal{C}_{j+1}:\mathrm{After\,\,red\,\,line}} \sum_{\gamma' \in \{I_4,S\}^n} c^{(\gamma')}_{j+1} \gamma'.
\end{align}

\begin{align}
a^{(\gamma)}_j &\coloneqq \sum_{\gamma' \in \{I_4,S\}^n} c^{(\gamma')}_j \\
a^{(\gamma)}_{j+1} &\coloneqq \sum_{\gamma' \in \{I_4,S\}^n} c^{(\gamma')}_{j+1}.
\end{align}

It suffices to show that

\begin{equation}
a^{(\gamma)}_j \leq a^{(\gamma)}_{j+1}
\end{equation}

for all $\gamma$. Observe that after the red line, the gates only act on the $k^{\text{th}}$ and the $l^{\text{th}}$ qubits.
So, let us focus on these two qubits.

* If $\gamma_{k,l} = II,SS$, since

\begin{align}
&II \xrightarrow{U_2^{(j+1)}} II\\
&II \xrightarrow{U_1\otimes U_1} II
\end{align}

\begin{align}
&SS \xrightarrow{U_2^{(j+1)}} SS\\
&SS \xrightarrow{U_1\otimes U_1} SS,
\end{align}

we have

\begin{equation}
a^{(\gamma)}_j =  a^{(\gamma)}_{j+1}
\end{equation}

in this case.

* If $\gamma_{k,l} = IS,SI$, without loss of generality, we may assume $\gamma_{k,l} = IS$. The proof for $\gamma_{k,l} = SI$ similarly follows.
We have

\begin{align}
&IS \xrightarrow{U_2^{(j+1)}} \dfrac{2}{5}\left(II + SS\right)\\
&IS \xrightarrow{U_1\otimes U_1} IS.
\end{align}

By Lemma <ref> (shown below this section),

\begin{align}
&IS \xrightarrow{\mathcal{C}_j:\mathrm{After\,\,red\,\,line}} \frac{2}{5}\left((x_m I_4 + y_m S)(x_m I_4 + y_m S) + (z_m I_4 + w_m S)(z_m I_4 + w_m S)\right) \\
&IS \xrightarrow{\mathcal{C}_{j+1}:\mathrm{After\,\,red\,\,line}} (x_m I_4 + y_m S)(z_m I_4 + w_m S),
\end{align}

\begin{align}
x_m &= 1 - \dfrac{1 - (1-a-2b)^m}{1 + \tfrac{2b}{a}},\\
y_m &= \dfrac{1 - (1-a-2b)^m}{\tfrac{1}{2} + \tfrac{b}{a}}, \\
z_m &= \dfrac{1}{2} - \dfrac{\tfrac{1}{2} + \tfrac{b}{a}(1-a-2b)^m}{1 + \tfrac{2b}{a}}, \\
w_m &=  \dfrac{\tfrac{1}{2} + \tfrac{b}{a}(1-a-2b)^m}{\tfrac{1}{2} + \tfrac{b}{a}}.
\end{align}

\begin{align}
a^{(\gamma)}_j &= \dfrac{2}{5}\left(u_m^2 + v_m^2\right), \\
a^{(\gamma)}_{j+1} &= u_mv_m,
\end{align}

\begin{align}
u_m &= x_m + y_m = 1 + \dfrac{1 - (1-a-2b)^m}{1 + \tfrac{2b}{a}}, \\
v_m &= z_m + w_m = \dfrac{1}{2} + \dfrac{\tfrac{1}{2} + \tfrac{b}{a}(1-a-2b)^m}{1 + \tfrac{2b}{a}}.
\end{align}

\begin{equation}
\begin{aligned}
&a^{(\gamma)}_j \leq a^{(\gamma)}_{j+1} \\
&\Leftrightarrow \dfrac{2}{5}\left(u_m^2 + v_m^2\right) \leq u_mv_m \\
&\Leftrightarrow 0 \leq (2v_m - u_m)(2u_m - v_m).
\end{aligned}
\end{equation}

Here, if $0\leq 1 - a -2b$,

\begin{equation}
2v_m - u_m = \dfrac{\left(\tfrac{b}{a} + 2\right)(1-a-2b)^m}{1 + \tfrac{2b}{a}} \geq 0,
\end{equation}

and if $0\leq 1 - a -2b \leq 1$,

\begin{equation}
2u_m - v_m = \left(2 + \dfrac{2 - 2(1-a-2b)^m}{1 + \tfrac{2b}{a}}\right) - \left(\dfrac{1}{2} + \dfrac{\tfrac{1}{2} + \tfrac{b}{a}(1-a-2b)^m}{1 + \tfrac{2b}{a}}\right) \geq 2 - 1 = 1 \geq 0.
\end{equation}

Hence, if $0\leq 1 - a -2b \leq 1$, $a^{(\gamma)}_j \leq a^{(\gamma)}_{j+1}$, which completes the proof.

In the proof, we used the following lemma.

Let $\mathcal{N}$ be a single qubit noise channel, and let $\mathsf{N} = \mathcal{N} \otimes \mathcal{N}$ be two copies of $\mathcal{N}$ acting on two qubits.
Define a two-qubit operator

\begin{equation}
\tilde{M}_{U_1, \mathsf{N}} = M_{U_1} \circ \mathsf{N} \circ M_{U_1}
\end{equation}

\begin{equation}
M_{U_1}[\rho] = \underset{U_1 \sim \mathcal{U}_{\textup{Haar}}}{\mathbb{E}}\bigg[U_1^{\otimes 2} \rho U_1^{\dagger \otimes 2} \bigg].
\end{equation}

Suppose that

\begin{align}
\label{eq:noise1_appendix}
\tilde{M}_{U_1, \mathsf{N}}(I_4) &= (1 - a)I_4 + 2a S, \\
\label{eq:noise2_appendix}
\tilde{M}_{U_1, \mathsf{N}}(S) &= bI_4 + (1 - 2b) S
\end{align}

with $a > 0$ and $b > 0$,
where $I_4$ is the 2-qubit identity operator and $S$ is the 2-qubit SWAP gate.

\begin{align}
\underbrace{\tilde{M}_{U_1, \mathsf{N}} \circ \tilde{M}_{U_1, \mathsf{N}} \circ \cdots \circ \tilde{M}_{U_1, \mathsf{N}}}_{m~\text{times}} \left(I_4\right) &= \left(1 - \dfrac{1 - (1-a-2b)^m}{1 + \tfrac{2b}{a}}\right)I_4 + \left(\dfrac{1 - (1-a-2b)^m}{\tfrac{1}{2} + \tfrac{b}{a}}\right)S, \\
\underbrace{\tilde{M}_{U_1, \mathsf{N}} \circ \tilde{M}_{U_1, \mathsf{N}} \circ \cdots \circ \tilde{M}_{U_1, \mathsf{N}}}_{m~\text{times}} \left(S\right) &= \left(\dfrac{1}{2} - \dfrac{\tfrac{1}{2} + \tfrac{b}{a}(1-a-2b)^m}{1 + \tfrac{2b}{a}}\right)I_4 + \left(\dfrac{\tfrac{1}{2} + \tfrac{b}{a}(1-a-2b)^m}{\tfrac{1}{2} + \tfrac{b}{a}}\right)S.
\end{align}

Let us write

\begin{align}
\underbrace{\tilde{M}_{U_1, \mathsf{N}} \circ \tilde{M}_{U_1, \mathsf{N}} \circ \cdots \circ \tilde{M}_{U_1, \mathsf{N}}}_{m~\text{times}} \left(I_4\right) &= x_m I_4 + y_m S.
\end{align}

Using Eqs. (<ref>) and (<ref>),

\begin{align}
x_{m+1} &= (1-a)x_m + by_m, \\
y_{m+1} &= 2a x_m + (1-2b)y_m.
\end{align}

This is equivalent to

\begin{align}
x_{m+1} + \dfrac{1}{2} y_{m+1} &= x_{m} + \dfrac{1}{2} y_{m}, \\
x_{m+1} - \dfrac{b}{a} y_{m+1} &= (1-a-2b) \left(x_{m} - \dfrac{b}{a} y_{m}\right).
\end{align}

Therefore, we have

\begin{align}
x_{m} + \dfrac{1}{2} y_{m} &= x_{0} + \dfrac{1}{2} y_{0} = 1, \\
x_{m} - \dfrac{b}{a} y_{m} &= (1-a-2b)^m \left(x_{0} - \dfrac{b}{a} y_{0}\right) = (1-a-2b)^m.
\end{align}

\begin{align}
x_m &= 1 - \dfrac{1 - (1-a-2b)^m}{1 + \tfrac{2b}{a}},\\
y_m &= \dfrac{1 - (1-a-2b)^m}{\tfrac{1}{2} + \tfrac{b}{a}}.
\end{align}

With a very similar argument, letting us write

\begin{align}
\underbrace{\tilde{M}_{U_1, \mathsf{N}} \circ \tilde{M}_{U_1, \mathsf{N}} \circ \cdots \circ \tilde{M}_{U_1, \mathsf{N}}}_{m~\text{times}} \left(S\right) &= z_m I_4 + w_m S,
\end{align}

we have

\begin{align}
z_m &= \dfrac{1}{2} - \dfrac{\tfrac{1}{2} + \tfrac{b}{a}(1-a-2b)^m}{1 + \tfrac{2b}{a}}, \\
w_m &=  \dfrac{\tfrac{1}{2} + \tfrac{b}{a}(1-a-2b)^m}{\tfrac{1}{2} + \tfrac{b}{a}}.
\end{align}

§ EFFECT OF NOISELESS SINGLE QUBIT GATES IN THE LAST LAYER

Let us consider a layer of single-qubit gates that immediately follows the last layer of noise. This is equivalent to arbitrarily locally rotating the measurement basis. Moreover, assume that these gates are noiseless.
A single qubit gate $U$ is parametrized as

\begin{equation}
U(\theta, \phi) =
\begin{pmatrix}
&\cos(\theta) \cdot e^{i \phi} && \sin(\theta) \\
&-\sin(\theta) && \cos(\theta) \cdot e^{-i \phi}& \\
\end{pmatrix}.
\end{equation}

Let $U_i(\theta_i, \phi_i)$ be the unitary applied to the $i^{\text{th}}$ qubit in the last layer.

Let $\mathcal{B}$ be an ensemble of amplitude-damped random quantum circuits, with noise strength $q$. Additionally, before measurement, for every $i \in [n]$, let $U_i(\theta_i, \phi_i)$—a single qubit, noiseless gate—be applied to qubit $i$. Then,

\begin{equation}
\underset{\mathcal{B}}{\mathbb{E}}[p_{i, b}] = \frac{1}{2} + \frac{(-1)^{b} \cdot q\cos2\theta_i}{2},
\end{equation}

where $p_{i, b}$ is marginal probabilities of getting $b \in \{0, 1\}$, in the $i^{\text{th}}$ qubit.

As per earlier convention, let $\mathcal{N}$ be the single-qubit noise channel, and let $K_0$ and $K_1$ be the corresponding Kraus operators.
Let $\mathcal{C} \in \mathcal{B}$ be a noisy random circuit.
Let $\tilde{\mathcal{C}}$ be the quantum circuit without the last layer; that is,

\begin{equation}
\mathcal{C} = \mathcal{N}^{\otimes n} \circ \tilde{\mathcal{C}}.
\end{equation}

For $i \in [n]$, define $\rho_i$ as follows:

\begin{equation}
\begin{aligned}
\rho_i = \underset{\mathcal{B}}{\mathbb{E}}[\Tr_{1, \ldots, i-1, i+1, \ldots n}(\tilde{\mathcal{C}}(\ketbra{0^n}{0^n}))],
\end{aligned}
\end{equation}

where $I_2$ is the single-qubit identity matrix.
In other words, $\rho_i$ is the expected reduced density matrix on just the $i^{\text{th}}$ qubit.
By definition, we have

\begin{equation}
\rho_i = \frac{I_2}{2}.
\end{equation}

In the last noiseless layer, since the parameters are implicit, we will drop the subscripts and refer to the $i^{\text{th}}$ single qubit gate as just $U_i$.
Then, by the definition of the adjoint map,

\begin{align}
\underset{\mathcal{B}}{\mathbb{E}}[p_{i, 0}] &=  \underset{\mathcal{B}}{\mathbb{E}}[ \Tr(\ket{0}\bra{0} U_i \mathcal{N}(\rho_i) U_i^{\dagger}) ] \\
&=  \underset{\mathcal{B}}{\mathbb{E}}[\Tr( U_i^{\dagger} \ket{0}\bra{0} U_i \mathcal{N}(\rho_i)) ]  \\
&= \underset{\mathcal{B}}{\mathbb{E}}[\Tr( U_i^{\dagger} \ket{0}\bra{0} U_i \mathcal{N}(\rho_i)) ] \\
\label{lasteq}
& =  \underset{\mathcal{B}}{\mathbb{E}}[\Tr( K_0^{\dagger}U_i^{\dagger} \ket{0}\bra{0} U_i K_0 ~\rho_i) ] + \underset{\mathcal{B}}{\mathbb{E}}[\Tr( K_1^{\dagger}U_i^{\dagger} \ket{0}\bra{0} U_i K_1 ~\rho_i) ],
\end{align}

where we have repeatedly used the cyclic property of trace.
In <ref>, we used the Kraus operators $K_0$ and $K_1$ of the amplitude damping noise channel.
Since $\rho_i = \tfrac{I_2}{2}$, <ref> is equal to

\begin{align}
\frac{1}{2} \left(\Tr( K_0^{\dagger}U_i^{\dagger} \ket{0}\bra{0} U_i K_0)  + \Tr( K_1^{\dagger}U_i^{\dagger} \ket{0}\bra{0} U_i K_1)\right).
\end{align}

By explicitly computing each term, we have

\begin{align}
\underset{\mathcal{B}}{\mathbb{E}}[p_{i, 0}] = \frac{1}{2}\left((\cos^2\theta_i + (1-q)\sin^2\theta_i) + q\cos^2\theta_i\right)
= \frac{1 + q(\cos^2\theta_i - \sin^2\theta_i)}{2}
= \frac{1}{2} + \frac{q\cos2\theta_i}{2}.
\end{align}

Let us define the "bias" $\beta_i$, of qubit $i$ as

\begin{equation}
\beta_i = q\cos2\theta_i.
\end{equation}

Note that $\beta_i \in [-q, q]$. Hence,

\begin{equation}
\underset{\mathcal{B}}{\mathbb{E}}[p_{i, b}] = \frac{1}{2} + \frac{\beta_i}{2},~~~~~\underset{\mathcal{B}}{\mathbb{E}}[p_{i, b}] = \frac{1}{2} - \frac{\beta_i}{2}.
\end{equation}

One way to interpret <ref> is to observe that there is an “effective” amplitude damping channel acting on each qubit, but each such channel has a "tunable" noise strength, which can now also be negative.

A negative noise strength means that the outcome $0$ is suppressed and the outcome $1$ is assigned higher weight. However, which strings are suppressed, and by how much depend on the "bias" of each qubit. By changing the single qubit gates, we can control the bias.

§ OUTPUT DISTRIBUTION WITH A LAST LAYER OF NOISELESS GATES

Let $\mathcal{B}$ be an ensemble of amplitude-damped random quantum circuits, with noise strength $q$. Additionally, before measurement, for every $i \in [n]$, let $U_i(\theta_i, \phi_i)$—a single qubit, noiseless gate—be applied to qubit $i$.

\begin{equation}
4 - \sqrt{15} < |\cos 2\theta_i|
\end{equation}

for all $i \in [n]$,
then there exists a string $x \in \{0,1\}^n$ such that for any $q > 0$ and $d= \Omega(\log n)$,

\begin{equation}
\underset{n \rightarrow \infty}{\lim} \underset{\mathcal{B}}{\Pr}\left[p_x < \frac{\alpha}{2^n} \right] = 1,
\end{equation}

for any $\alpha \in (0, 1]$.

Following the same argument as in the proof of Theorem <ref> in Appendix <ref>, for sufficiently large depth and sufficiently large $n$, we have

\begin{equation}
\underset{\mathcal{B}}{\mathbb{E}}[p_x^2] \leq \left(\left(\frac{1}{4-q}\right)^n (e_1e_2\cdots e_n)\right)\times \mathcal{O}(1)
\end{equation}

\begin{equation}
\begin{aligned}
&= \max\left\{\bra{x_j}\bra{x_j}(\mathcal{U}_j\otimes \mathcal{U}_j)\mathsf{N}(I_4)(\mathcal{U}_j\otimes \mathcal{U}_j)^\dagger\ket{x_j}\ket{x_j},\bra{x_j}\bra{x_j}(\mathcal{U}_j\otimes \mathcal{U}_j)\mathsf{N}(S)(\mathcal{U}_j\otimes \mathcal{U}_j)^\dagger\ket{x_j}\ket{x_j}\right\} \\
\begin{array}{cc}
(1 + q\cos 2\theta_j)^2 & x_j = 0 \\
(1 - q\cos 2\theta_j)^2 & x_j = 1
\end{array}
\end{aligned}
\end{equation}

for $j = 1,2,\dots,n$.
Choose $x$ so that

\begin{equation}
e_j =  (1 - q |\cos 2\theta_j|)^2.
\end{equation}

In this case,

\begin{equation}
\underset{\mathcal{B}}{\mathbb{E}}[p_x^2] \leq  \left(\frac{(1 - q |\cos 2\theta|)^2}{4-q}\right)^n \times \mathcal{O}(1),
\end{equation}

\begin{equation}
\theta \coloneqq \argmin_{\theta_j : j\in[n]}  |\cos2\theta_j|.
\end{equation}

To see the concentration, it suffices to check if

\begin{align}
4\frac{(1 - q |\cos 2\theta|)^2}{4-q} < 1,
\end{align}

which is equivalent to

\begin{equation}
q\left(4|\cos 2\theta|^2q -(8|\cos 2\theta| - 1) \right) < 0.
\end{equation}

When $q = 0$, this inequality cannot be satisfied, so $q > 0$.
Under this condition, we have

\begin{equation}
4|\cos 2\theta|^2q -(8|\cos 2\theta| - 1) < 0.
\end{equation}

\begin{equation}
4 - \sqrt{15} < |\cos 2\theta|,
\end{equation}

all $q > 0$ satisfy this condition, which completes the proof.

§ A NOTE ON THE EASINESS OF SAMPLING RESULTS

In this section, we will sketch the easiness results of <cit.> and why anticoncentration is believed to be an important criterion for the current analysis techniques to go through. This is just a sketch, so we will not be too formal with the definitions and proofs.

Without loss of generality, let $\mathcal{C}$ be a unitary quantum circuit circuit. By $p_x(\mathcal{C})$, for $x \in \{0, 1\}^n$, let us denote the probability of getting string $x$ in the output distribution of $\mathcal{C} |0^n \rangle$. Using techniques from <cit.>, we can rewrite $p_x(\mathcal{C})$ in terms of Pauli paths as

\begin{equation}
p_x(\mathcal{C}) = \sum_{s} f(\mathcal{C}, x, s),
\end{equation}

where $f(\mathcal{C}, x, s)$ are as defined in <cit.> — they are path weights for each Pauli path — and $s$ is the number of non–identity Pauli terms for each Pauli path. Similarly, let

\begin{equation}
\tilde{p}_x(\mathcal{C}) = \sum_{s} \tilde{f}(\tilde{\mathcal{C}}, x, s)
\end{equation}

be the output probability, written as Pauli paths, for the noisy version of $\mathcal{C}$, denoted by $\tilde{\mathcal{C}}$.
Now, to sample from the output distribution of $\tilde{\mathcal{C}} |0^n \rangle$, we consider a new distribution $\tilde{\tilde{q}}$ given by

\begin{equation}
\tilde{\tilde{q}}_x(\tilde{\mathcal{C}}) = \underset{s, |s| \leq l}{\sum} \tilde{f}(\tilde{\mathcal{C}}, x, s),
\end{equation}

where $l$ is some threshold that we choose. Consider an ensemble $\mathcal{B}$ of such noisy circuits. Now, let us calculate the total variation distance between $\tilde{p}$ and $\tilde{\tilde{q}}$.

\begin{align}
\underset{\mathcal{B}}{\mathbb{E}}\big[|\tilde{p}-\tilde{\tilde{q}}|_1^{2}\big] &\leq 2^n \cdot \underset{\mathcal{B}}{\mathbb{E}} \left[ \sum_{x \in \{0, 1\}^n} \big(\tilde{p}_x(\mathcal{C}) - \tilde{\tilde{q}}_x(\tilde{\mathcal{C}})\big)^2  \right] \\
&\leq 2^n \cdot \underset{\mathcal{B}}{\mathbb{E}}\left[ \sum_{x \in \{0, 1\}^n} \sum_{s, |s| > l} \tilde{f}(\tilde{\mathcal{C}}, x, s)^2 \right],
\end{align}

where the first line follows from the Cauchy-Schwarz inequality, and the second line follows from definitions. Note that for any choice of the cutoff $l$,

\begin{align}
\label{firsteq2}
& 2^n \cdot \underset{\mathcal{B}}{\mathbb{E}}\left[ \sum_{x \in \{0, 1\}^n} \sum_{s, |s| > l} \tilde{f}(\tilde{\mathcal{C}}, x, s)^2 \right] \\
& \leq 2^n \cdot \underset{\mathcal{B}}{\mathbb{E}}\left[  \sum_{x \in \{0, 1\}^n}  \sum_{s} \tilde{f}(\tilde{\mathcal{C}}, x, s)^2 \right] \\
& \leq 2^n \cdot  \underset{\mathcal{B}}{\mathbb{E}}\left[\sum_{x \in \{0, 1\}^n} \tilde{p}_x^2\right],
\end{align}

where the last line follows from orthogonality of Pauli paths in a random circuit.

§.§ Special case of the depolarizing channel

For the special case of the depolarizing channel,

\begin{equation}
\label{Depolarizing}
\tilde{f}(\tilde{\mathcal{C}}, x, s) = (1 - q)^{|s|} f({\mathcal{C}}, x, s).
\end{equation}

So, for a choice of cutoff $l$, using similar steps as in the previous section, <ref> can be upper bounded with the quantity

\begin{equation}
(1 - q)^{2 l} \cdot 2^{n} \cdot  \sum_{x \in \{0, 1\}^n} p_x^{2}.
\end{equation}

It is known that for sufficiently deep circuits <cit.>, the scaled noiseless collision probability,

\begin{equation}
2^{n} \cdot \underset{\mathcal{B}}{\mathbb{E}}\left[\sum_{x \in \{0, 1\}^n} p_x^{2}\right]
\end{equation}

is $\mathcal{O}(1)$. So, by appropriately choosing $l$, one can make the total variation distance an inverse polynomial or less.

Note that <ref> is true for the special case of the depolarizing channel, but is not true in general. So, this analysis, where it suffices to look at the convergence of the noiseless collision probability because that can, essentially, be "factored out" of the actual expression and dealt with separately, does not work in general.

Note that one could also have directly upper bounded the noisy collision probability

\begin{equation}
\label{cp_remark}
2^n \cdot  \sum_{x \in \{0, 1\}^n} \tilde{p}_x^2,
\end{equation}

for the depolarizing channel. Indeed, this is done in <cit.>. However, in <cit.>, the bound is $\mathcal{O}(1)$, and not as tight as the analysis in <ref>. This is necessary for inverse polynomial closeness in total variation distance, but is not sufficient. So, we still need the techniques from <ref> to prove our bound.

In general, since noisy ensembles do not satisfy the form in <ref>, directly bounding the noisy collision probability is the best that we can hope for, which may not always give us tight bounds.

§.§ Lack of anticoncentration implies failure of proof technique

When the noisy ensemble $\mathcal{B}$ is anticoncentrated, with respect to <ref>, then it means that

\begin{equation}
2^n \cdot  \underset{\mathcal{B}}{\mathbb{E}}\left[\sum_{x \in \{0, 1\}^n} \tilde{p}_x^2 \right] = \mathcal{O}(1),
\end{equation}

which implies,

\begin{equation}
\label{tvd}
\underset{\mathcal{B}}{\mathbb{E}}\big[|\tilde{p}-\tilde{\tilde{q}}|_1^{2}\big] \leq 2^n \cdot \underset{\mathcal{B}}{\mathbb{E}}\left[ \sum_{x \in \{0, 1\}^n} \sum_{s, |s| > l} \tilde{f}(\tilde{\mathcal{C}}, x, s)^2 \right] \leq 2^n \cdot  \underset{\mathcal{B}}{\mathbb{E}}\left[\sum_{x \in \{0, 1\}^n} \tilde{p}_x^2 \right] = \mathcal{O}(1).
\end{equation}

This alone does not guarantee that the classical sampler, from <ref>, samples from a distribution that is inverse polynomially close, in total variation distance, to the actual distribution. However, the satisfaction of <ref> is a necessary condition for present proof techniques to go through, in the following sense: if an ensemble were to exhibit lack of anticoncentration, according to <ref>, then the quantity

\begin{equation}
2^n \cdot  \underset{\mathcal{B}}{\mathbb{E}}\left[\sum_{x \in \{0, 1\}^n} \tilde{p}_x^2 \right]
\end{equation}

diverges with $n$, and the chain of inequalities in <ref> does not hold, no matter where we choose the cutoff $l$. This does not mean that there couldn't be better analysis techniques which do not need anticoncentration: however, to the best of our knowledge, no such technique is known.

§ EASINESS OF COMPUTING EXPECTATION VALUES

In this section, we will, very broadly, sketch the argument of <cit.> about computing the expectation value of certain observables, for random quantum circuits with the depolarizing noise. The ideas are extremely similar to that of <ref>, but the argument does not require anticoncentration. To start with, note that for the depolarizing channel,

\begin{equation}
\label{impeq}
\tilde{f}(\tilde{\mathcal{C}}, x, s) = (1 - q)^{|s|} f({\mathcal{C}}, x, s),
\end{equation}

where $f$ is a Pauli path of the noiseless circuit $\mathcal{C}$, $\tilde{f}$ is a Pauli path of the noisy circuit $\tilde{C}$, $x \in \{0, 1\}^n$, and $s \in \{0, 1\}^{2n}$ is the number of non–identity Pauli terms in the path. In <cit.>, it is shown how the expectation value of any observable can be written as

\begin{equation}
\sum_{s} \tilde{f}(\tilde{\mathcal{C}}, x, s).
\end{equation}

Now, using <ref>, any path such that $s = \omega(\log n)$ is at least inverse–superpolynomially suppressed, and only polynomially many paths — those for which $s = \mathcal{O}(\log n)$ — have at least $\frac{1}{\text{poly}(n)}$ weight. Then, just by classically estimating those paths, we get an estimate of the expectation value that is $\approx \frac{1}{\text{poly}(n)}$ close to the original expectation value. Note that each Pauli path can be estimated in classical polynomial time. Note that this technique does not need anticoncentration.

Note that <ref> is a special property of the depolarizing channel: it is not evident whether the strategy described works for other noise channels.

§ ANTICONCENTRATION AND CLOSENESS TO THE UNIFORM DISTRIBUTION

In this section, we show the relation between anticoncentration, according to <ref>, and closeness to the uniform distribution. Let $\mathcal{B}$ be an ensemble of noisy random quantum circuits, and let $\mathcal{C}$ be the random variable corresponding to each circuit. Let

\begin{equation}
\rho = \mathcal{C}(\ket{0^n}\bra{0^n}).
\end{equation}

For $x \in \{0, 1\}^n$, let

\begin{equation}
\underset{\mathcal{B}}{\mathbb{E}}\left[p_x\right] = \underset{\mathcal{B}}{\mathbb{E}}\left[\Tr(|x\rangle \langle x| ~\rho)\right].
\end{equation}

Now, note that

\begin{align}
\underset{\mathcal{B}}{\mathbb{E}}\left[\sum_{x \in \{0, 1\}^n} \bigg| p_x - \frac{1}{2^n} \bigg|^2 \right]
&= \underset{\mathcal{B}}{\mathbb{E}}\left[\sum_{x \in \{0, 1\}^n} p_x^2 \right] - 2 \cdot \frac{1}{2^n} + \frac{1}{2^n}
\\&= \underset{\mathcal{B}}{\mathbb{E}}\left[\sum_{x \in \{0, 1\}^n} p_x^2 \right] - \frac{1}{2^n}.
\end{align}

Hence, if

\begin{equation}~\label{eq:flatness_condition}
\underset{\mathcal{B}}{\mathbb{E}}\left[\sum_{x \in \{0, 1\}^n} \bigg| p_x - \frac{1}{2^n} \bigg|^2 \right] = \mathcal{O}(2^{-n}),
\end{equation}

\begin{equation}~\label{eq:anticoncentration_condition}
\underset{\mathcal{B}}{\mathbb{E}}\left[\sum_{x \in \{0, 1\}^n} p_x^2 \right] = \mathcal{O}(2^{-n}),
\end{equation}

which means <ref> is satisfied. The vice versa also holds.

Let $\Delta_n$ be the $n$-qubit completely dephasing channel with respect to the computational basis; that is, for any $n$-qubit state $\sigma$,

\begin{equation}
\Delta_n(\sigma) \coloneqq \sum_{x\in\{0,1\}^n} \bra{x}\sigma\ket{x} \ketbra{x}{x}.
\end{equation}

Now, let us assume the following equation holds:

\begin{equation}~\label{eq:1norm_condition_original2}
\underset{\mathcal{B}}{\mathbb{E}} \left\|\rho -  \frac{I_{2^n}}{2^n}\right\|_1^2 = \mathcal{O}(2^{-n}).
\end{equation}

Then, from monotonicity of trace distance, we get that

\begin{equation}~\label{eq:1norm_condition2}
\underset{\mathcal{B}}{\mathbb{E}} \left\|\Delta_n(\rho) -  \frac{I_{2^n}}{2^n}\right\|_1^2 = \mathcal{O}(2^{-n}).
\end{equation}

We used the fact that $\Delta_n(I_{2^n}) = I_{2^n}$. Then, since the 2-norm is smaller than the trace norm, from <ref> we get

\begin{equation}~\label{eq:2norm_condition}
\underset{\mathcal{B}}{\mathbb{E}} \left\|\Delta_n(\rho) -  \frac{I_{2^n}}{2^n}\right\|_2^2 = \mathcal{O}(2^{-n}).
\end{equation}

Hence, combining this observation with the calculations in <ref>, <ref> implies <ref>.