# Quantum Chaos is Quantum

Lorenzo Leone<EMAIL_ADDRESS>Physics Department, University of
Massachusetts Boston, 02125, USA  Salvatore F.E. Oliviero  Physics Department,
University of Massachusetts Boston, 02125, USA  You Zhou  School of Physical
and Mathematical Sciences, Nanyang Technological University, 637371, Singapore
Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA
Alioscia Hamma  Physics Department, University of Massachusetts Boston, 02125,
USA

###### Abstract

It is well known that a quantum circuit on $N$ qubits composed of Clifford
gates with the addition of $k$ non Clifford gates can be simulated on a
classical computer by an algorithm scaling as
$\operatorname{poly}(N)\mathrm{exp}\left({k}\right)$[1]. We show that, for a
quantum circuit to simulate quantum chaotic behavior, it is both necessary and
sufficient that $k=\Theta(N)$. This result implies the impossibility of
simulating quantum chaos on a classical computer.

## Introduction

Quantum chaos is a certain type of complex quantum behavior that results in
the exponential decay of out-of-time-order correlation functions (OTOC)[2, 3,
4] efficient operator spreading[5, 6], small fluctuations of the purity[7] and
information scrambling[8, 9]. All these quantities can be unified in a single
framework[10] which shows that, in order to simulate quantum chaos, one needs
at least a unitary $4$-design, that is, a set of unitary operators that
reproduces up to the four moments of the Haar distribution over the unitary
group $\mathcal{U}(d)$ in an $d$-dimensional Hilbert space. Here, we define
quantum chaos for a quantum evolution in terms of attaining the Haar value for
general multi-point OTOC, that is, the value that would be reached by a random
unitary operator in $\mathcal{U}(d)$. We consider a subgroup of the unitary
group - the Clifford group - which only reproduces up to the four-point
OTOC[3] and thus it is not sufficient to simulate quantum chaotic evolutions.
In [11], it was shown numerically that a Clifford circuit on a
$d=2^{N}$-dimensional system of $N$ qubits doped by a single $T$ gate can
bring a typical product state in an entangled state with the same entanglement
spectrum statistics resulting from the random matrix theory for
$\mathcal{U}(d)$. This result opens the question of whether it would be
possible to simulate quantum chaos with classical resources. In a seminal
paper[12], the authors show that an $\epsilon$-approximate $t$-design can be
obtained by doping a Clifford circuit with
$k=O(t^{4}\log^{2}t\log\epsilon^{-1})$ non Clifford gates. In particular, one
can $\epsilon$-simulate the quantum channel that realizes a $4$-design by
classical resources. This result is striking: by injecting a vanishing density
$\sigma=k/N$ of non Clifford gates in a Clifford quantum circuit - as the
authors say, homeopathically \- one can obtain any $\epsilon$-approximate
$t$-design. Does this mean that one can simulate quantum chaos classically?
The answer is no, because - as we will show - to simulate quantum chaos, the
error $\epsilon$ must be exponentially small in $N$,
$\epsilon=O(d^{-\alpha})$, where $\alpha$ only depends on the Haar average
over the full unitary group. A corollary of the result in[12] is that a
sufficient condition to simulate quantum chaos requires $O(N)$ non Clifford
resources.

In this paper, we show that $\Theta(N)$ non Clifford resources are both
necessary and sufficient to simulate quantum chaos. To this end, we explicitly
compute the $8$-point OTOC and the fluctuations of the purity in a subsystem
and show that a doped Clifford circuit will attain the Haar values for these
quantities if and only if $\Theta(N)$ non Clifford resources are used. In
other words, one needs more than a homeopathic dose of non Clifford gates to
simulate quantum chaos. Can a classical computer simulate quantum chaos? In
order to simulate a Clifford circuit with a $\Theta(N)$ non-Clifford
resources, an exponential number of classical resources are needed [1].
Complexity-theoretic arguments [13, 14] imply that one cannot simulate
efficiently on a classical computer a quantum Clifford circuit doped with
$\Theta(N)$ non-Clifford gates, and therefore, since this is necessary to
simulate quantum chaos, the latter cannot be efficiently simulated on a
classical computer: quantum chaos is quantum.

##  1 Doped Random Quantum Clifford Circuits

Consider doped random quantum Clifford circuits $U^{(k)}$ on a system
$\mathcal{H}=\mathbb{C}^{2\otimes N}$ of $N$ qubits of dimension $d=2^{N}$.
The architecture of the circuit is the following: we have layers of random
Clifford unitary operators on the full $\mathcal{H}$ interspersed by a single
qubit gate $K_{i}$ applied randomly on any qubit $i$, see Fig.1. As we shall
see in Sec. C.2, the positioning $i$ of the gates $K$ does not play any role.
We denote by $k$ the number of gates $K$ in the circuit, also called the
number of layers of the circuit, $\psi$ a pure input state for the circuit,
and $\psi_{U}=U\psi U^{\dagger}$ its output. We call the quantity $\sigma=k/N$
the doping of the circuit $U^{(k)}$.

Figure 1: Left: Scheme of the $4$-Doped Clifford circuit. Right: Detail of
$K_{C_{4}}$, a unitary single-qubit non Clifford gate $K$ evolved adjointly by
a Clifford circuit $C_{4}$. Note that the set formed by these circuits is
equivalent to the set of doped Clifford circuits, i.e circuits composed by
Clifford unitaries $C_{i}$ interspersed with single-qubit non Clifford gates
$K_{i}$.

We denote by $x$ a set of unitary operators, e.g.
$x=\mathcal{U}(d),\mathcal{C}(d)$ the unitary and Clifford group,
respectively, on $\mathcal{H}$. For $k=0$, the circuit is just a Clifford
circuit, $U^{(0)}\in\mathcal{C}(d)$. The Haar average on these sets will be
denoted by $\langle\cdot\rangle_{U\in x}$. We define the $(x,t)$-fold channel
as

$\displaystyle\Phi_{x}^{(t)}(\mathcal{O}):=\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in
x}$ (1)

where $\mathcal{O}\in\mathcal{B}(\mathcal{H}^{\otimes t})$ and
$\mathcal{O}_{U}\equiv U^{\otimes t}\mathcal{O}U^{{\dagger}\otimes t}$.
Averaging over $\mathcal{C}(d)$ for a circuit $U^{(k)}$ with $k$ layers
involves averaging over $k$ independent Clifford groups; in the following we
define this set of circuits as $\mathcal{C}_{k}$. The
$(\mathcal{C}_{k},4)$-fold channel is

$\Phi^{(4)}_{\mathcal{C}_{k}}(\mathcal{O})=\left\langle\mathcal{O}_{U}\right\rangle_{U\in\mathcal{C}_{k}}\equiv\left\langle
C_{k}^{\otimes 4}K_{i_{k}}^{\otimes 4}\dots C_{1}^{\otimes
4}K_{i_{1}}^{\otimes 4}C_{0}^{\otimes 4}\mathcal{O}C_{0}^{{\dagger}\otimes
4}K_{i_{1}}^{{\dagger}\otimes 4}C_{1}^{\otimes 4}\dots
K_{i_{k}}^{{\dagger}\otimes 4}C_{k}^{{\dagger}\otimes
4}\right\rangle_{C_{1}\ldots C_{k}\in\mathcal{C}(d)}$ (2)

Notice that the above average over $\mathcal{C}(d)$ is the same thing -
because of the left/right invariance of group averages - than the average over
circuits of the type sketched in Fig.1.

Quantum chaos can be defined as an appropriate form of the butterfly
effect[15]: an exponential (in $N$) decay of the OTOCs defined as

$\text{OTOC}_{8}(U):=d^{-1}{\operatorname{tr}}\left(AB_{U}CD_{U}A^{\dagger}D^{\dagger}_{U}C^{\dagger}B^{\dagger}_{U}\right)$
(3)

so that the OTOCs adhere to the value of the OTOCs obtained by Haar-random $U$
on the unitary group scaling with $d^{-4}$, while other ensembles, like the
Clifford group, feature a scaling of $d^{-2}$[3]. It is immediate to see that,
in order to distinguish the two types of scaling, one needs an
$\epsilon=O(d^{-4})$. As $2t$-OTOCs are probes of $t$-designs, an $8$-point
OTOC is a probe of a $4$-design, and therefore a quantum chaotic channel needs
to have a frame potential exponentially close to that of the Haar measure on
$\mathcal{U}(d)$.

A related measure of chaos[10] is given by the fluctuations of the purity of
the reduced density matrix to a subsystem

$\displaystyle\Delta_{x}\operatorname{Pur}(\psi_{U})_{A}:=\left\langle(\operatorname{Pur}(\psi_{U})_{A}-\langle\operatorname{Pur}(\psi_{U})_{A}\rangle_{U\in
x})^{2}\right\rangle_{U\in x}$ (4)

This quantity is related to the emergent irreversibility in closed quantum
systems[16] and to both $4$-designs and OTOCs. In Sec. 4, we show that the
purity fluctuations are exponentially small for every doping (including no
doping, $k=0$) of the random Clifford circuits and thus also to distinguish
the fluctuations of the purity one needs an exponentially small error
$\epsilon$. We ask the question: what is the necessary and sufficient number
$k$ of non Clifford gates $K$ for $U\in\mathcal{C}_{k}$ to simulate quantum
chaos?

The main goal of this paper is to show that, for $\mathcal{C}_{k}$ to
reproduce the Haar-unitary values of the probes Eqs. (3) and (4), $\Theta(N)$
non Clifford resources are both necessary and sufficient. We will prove it in
the next sections by explicitly computing these two quantities. Here, we want
to make some more general considerations. Given a probe to quantum chaos
defined as
$\mathcal{P}_{t}(U):={\operatorname{tr}}(T^{(t)}\mathcal{O}_{1}U^{\otimes
t}\mathcal{O}_{2}U^{{\dagger}\otimes t})$, see[10, 7], we can establish the
following

######  Proposition 1.

Let $\mathcal{P}_{t}(U)$ a probe of quantum chaos of order $t$. If the number
$k$ of non Clifford gates in the doped Clifford circuit $U\in\mathcal{C}_{k}$
is $k=O((\alpha+t)Nt^{4}\log^{2}(t))$, then:

$\delta_{\mathcal{P}}^{(k)}\equiv\left|\left\langle{\mathcal{P}(U)}\right\rangle_{U\in\mathcal{C}_{k}}-\left\langle{\mathcal{P}(U)}\right\rangle_{U\in\mathcal{U}(d)}\right|\leq
O(d^{-\alpha})$ (5)

where $\alpha$ is given by the following relation
$\left\langle{\mathcal{P}(U)}\right\rangle_{U\in\mathcal{U}(d)}=O(d^{-\alpha})$.

###### Proof.

The proof is straightforward from the result in [12]. In [10], we proved that
the generic probe $\mathcal{P}_{t}(U)$ to quantum chaos can be written as
$\mathcal{P}_{t}(U)={\operatorname{tr}}(T^{(t)}\mathcal{O}_{1}U^{\otimes
t}\mathcal{O}_{2}U^{{\dagger}\otimes t})$ where
$\mathcal{O}_{1},\mathcal{O}_{2},T^{(t)}\in\mathcal{B}(\mathcal{H}^{\otimes
t})$, including the $2t$-point OTOC which characterize $t$-designs[3]. Then,
the following inequality holds:

$\delta_{\mathcal{P}}^{(k)}\leq\|T^{(t)}\mathcal{O}_{1}\|_{\infty}\|\mathcal{O}_{2}\|_{1}\|\Phi^{(t)}_{\mathcal{C},k}(\cdot)-\Phi^{(t)}_{\mathcal{U}(d)}(\cdot)\|_{\diamond}\leq
d^{t}\|T^{(t)}\mathcal{O}_{1}\|_{\infty}\|\mathcal{O}_{2}\|_{\infty}\|\Phi^{(t)}_{\mathcal{C},k}(\cdot)-\Phi^{(t)}_{\mathcal{U}(d)}(\cdot)\|_{\diamond}$
(6)

where we bounded
$\|\mathcal{O}_{2}\|_{1}\leq\|\mathcal{O}_{2}\|_{\infty}\|{\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}^{\otimes t}\|_{1}=d^{t}\|\mathcal{O}_{2}\|_{\infty}$. Thus if
$k=O((\alpha+t)Nt^{4}\log^{2}(t))$ then
$\delta^{(k)}_{\mathcal{P}}=O(d^{-\alpha})$.∎

As we will show in the following sections, the error $O(d^{-\alpha})$ is
required to have OTOCs and fluctuations of the purity attain the unitary-Haar
values. It follows that injecting $O(N)$ non Clifford resources into a
Clifford circuit is sufficient to obtain quantum chaos.

As we stated above, the necessary (together with the sufficient) condition
will follow from direct calculations. It is important at this point to make
some remarks about the value of $t$. One wonders if it is enough to consider
$8$-OTOCs to reveal quantum chaos, or if sometimes it should be necessary to
use higher order OTOCs. From the point of view of the above proposition, it is
clear that $O(N)$ non Clifford resources are sufficient to obtain any OTOC
with an exponentially good $O(d^{-\alpha})$ approximation. Once one has proved
the necessary condition for $t=4$, it will also hold for any $t>4$ design, as
an approximate $t$-design is necessarily a $t^{\prime}$ approximate design,
for all $t^{\prime}<t$. In other words, polynomials of degree four are all
that takes to reveal quantum chaos. To see this, notice that the $4m-$OTOCs
defined as

$\text{OTOC}_{4m}(U):=d^{-1}{\operatorname{tr}}[(A_{1}B_{1}^{U}A_{2}B_{2}^{U}\cdots
A_{m}B_{m}^{U})A_{1}^{{\dagger}}(A_{1}B_{1}^{U}A_{2}B_{2}^{U}\cdots
A_{m}B_{m}^{U})]$ (7)

reduces, for $A_{3},\dots,A_{m},B_{3},\dots B_{m}={\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}$,
to the $8-$OTOC in Eq. (3); therefore $k=\Omega(N)$ are necessary to obtain
any $4m-$OTOC with an exponentially good approximation.

##  2 Main Theorem

From the technical point of view, the main result of this paper is the exact
calculation of the fourth moment of the output of a $k$-doped random Clifford
circuit for a generic operator $\mathcal{O}\in\mathcal{B}(\mathcal{H}^{\otimes
4})$:

######  Theorem 1.

Let $\mathcal{O}\in\mathcal{B}(\mathcal{H}^{\otimes 4})$ be a bounded
operator, $U\in\mathcal{C}_{k}$ a $k$-doped Clifford circuit; then the
$(\mathcal{C}_{k},4)$-fold channel for the $k$-doped Clifford circuit reads

$\Phi^{(4)}_{\mathcal{C}_{k}}(\mathcal{O})=\sum_{\pi,\sigma\in\mathcal{S}_{4}}\left[\left({(\Xi^{k})_{\pi\sigma}Q+\Gamma_{\pi\sigma}^{(k)}}\right)c_{\pi}(\mathcal{O})+\delta_{\pi\sigma}b_{\pi}(\mathcal{O})\right]T_{\sigma}$
(8)

where

$Q=\frac{1}{d^{2}}\sum_{P\in\mathcal{P}(2^{N})}P^{\otimes
4};\qquad\;Q^{\perp}={\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}^{\otimes 4}-Q$ (9)

and $\mathcal{P}(2^{N})$ is the Pauli group on $N$ qubits; $T_{\pi}$ are
permutation operators corresponding to $\pi\in\mathcal{S}_{4}$, then $\Xi^{k}$
is the $k$-matrix power of the matrix $\Xi$, whose components read

$\Xi_{\sigma\pi}\equiv\sum_{\tau\in\mathcal{S}_{4}}\left[W^{+}_{\pi\tau}{\operatorname{tr}}\left(T_{\sigma}K^{\otimes
4}QK^{{\dagger}\otimes
4}QT_{\tau})-W^{-}_{\pi\tau}{\operatorname{tr}}(T_{\sigma}K^{\otimes
4}QK^{{\dagger}\otimes 4}Q^{\perp}T_{\tau}\right)\right]$ (10)

with

$\displaystyle\Gamma^{(k)}_{\pi\sigma}$ $\displaystyle\equiv$
$\displaystyle\sum_{\tau\in\mathcal{S}_{4}}\Lambda_{\pi\tau}\sum_{i=0}^{k-1}(\Xi^{i})_{\tau\sigma}$
(11) $\displaystyle\Lambda_{\pi\tau}$ $\displaystyle\equiv$
$\displaystyle\sum_{\sigma\in\mathcal{S}_{4}}W^{-}_{\pi\sigma}{\operatorname{tr}}(T_{\tau}K^{\otimes
4}QK^{{\dagger}\otimes 4}Q^{\perp}T_{\sigma})$ (12)

and the information about the operator $\mathcal{O}$ is all contained in the
coefficients

$\displaystyle c_{\pi}(\mathcal{O})$ $\displaystyle\equiv$
$\displaystyle\sum_{\sigma\in\mathcal{S}_{4}}[W^{+}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}QT_{\sigma})-W^{-}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}Q^{\perp}T_{\sigma})]$
(13) $\displaystyle b_{\pi}(\mathcal{O})$ $\displaystyle\equiv$
$\displaystyle\sum_{\sigma\in\mathcal{S}_{4}}W^{-}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}Q^{\perp}T_{\sigma})$
(14)

where $W^{\pm}_{\pi\sigma}$ are the generalized Weingarten functions for the
Clifford group, introduced and discussed in App. A.1.

The proof of the theorem can be found in App. B.1.

For many purposes, it is important to know to what
$\Phi^{(4)}_{\mathcal{C}_{k}}(\cdot)$ converges in the limit of infinite
layers. Without substantial loss of generality, we consider the case of the
non Clifford resources given by phase gates $P_{\theta}$ with
$\theta\neq\pi/2$. We can thus establish the application:

######  Application 1.

For
$K=P_{\theta}\equiv\left|{0}\right\rangle\left\langle{0}\right|+e^{i\theta}\left|{1}\right\rangle\left\langle{1}\right|$,
where $\\{\left|{0}\right\rangle,\left|{1}\right\rangle\\}$ is the single
qubit computational basis, and for any $\theta\neq\pm\pi/2$ the
$(\mathcal{C}_{k},4)$-fold channel equals the $(\mathcal{U}(d),4)$-fold
channel in the limit $k\rightarrow\infty$ is

$\lim_{k\rightarrow\infty}\Phi^{(4)}_{\mathcal{C}_{k}}(\mathcal{O})=\Phi^{(4)}_{\mathcal{U}(d)}(\mathcal{O})$
(15)

The proof can be found in App. B.2. Note that the above result can be also
seen as a consequence of the results in [17].

In the next sections, we apply these theorems to calculating the $8$-point
OTOCs and fluctuations of subsystem purity to find how these quantities
approach the Haar-average on $\mathcal{U}(d)$ with $k$.

##  3 The $8$-point OTOC

Consider four non-identity and non-overlapping Pauli operators
$A,B,C,D\in\mathcal{P}(d)$. Then consider the unitary evolution of
$A_{U}=UAU^{{\dagger}}$ in the Heisenberg picture and define an $8$-point Out
of Time Order Correlator (OTOC) as[3], defined in Eq.(3)

$\text{OTOC}_{8}(U):=d^{-1}{\operatorname{tr}}(AB_{U}CD_{U}AD_{U}CB_{U})$ (16)

We are interested in taking the twirling of the $8$-point OTOC for a $k$-doped
Clifford circuit, in order to find a necessary and sufficient condition for
the exponential decay of the OTOC. Thanks to Theorem 1 we obtain

######  Application 2.

Let $K\equiv T$ the single qubit $T$-gate, then the average of the $8$-point
OTOC over the $k$-doped Clifford circuit reads

$\displaystyle\left\langle{\text{OTOC}_{8}(U)}\right\rangle_{U\in\mathcal{C}_{k}}$
$\displaystyle=$
$\displaystyle\frac{5d^{2}}{(d^{2}-1)(d^{2}-4)(d^{2}-9)}-(f^{-})^{k}\frac{d(d^{2}+4d+6)}{6(d^{2}-1)(d+2)(d+3)}$
(17) $\displaystyle+$
$\displaystyle(f^{+})^{k}\frac{d(d^{2}-4d+6)}{6(d^{2}-1)(d-2)(d-3)}+\left({\frac{f^{+}+f^{-}}{2}}\right)^{k}\frac{4d^{2}}{3(d^{2}-1)(d^{2}-4)}$

where $f^{\pm}\equiv f^{\pm}_{\pi/4}=\frac{3d^{2}\pm
3d-4}{4(d^{2}-1)}=\frac{3}{4}+\Theta(d^{-1})$, where $f^{\pm}_{\theta}$ are
defined in Eq.(84).

###### Proof.

Starting from Eq.(16) we can write the $8$-point OTOC for $U$ as

$\text{OTOC}_{8}(U)=d^{-1}{\operatorname{tr}}(T_{(1432)}(A\otimes C\otimes
A\otimes C)U^{\otimes 4}(B\otimes D\otimes D\otimes B)U^{{\dagger}\otimes 4})$
(18)

Taking the average over the $k$-doped Clifford $U\in\mathcal{C}_{k}$ we have

$\left\langle{\text{OTOC}_{8}(U)}\right\rangle_{U\in\mathcal{C}_{k}}=d^{-1}{\operatorname{tr}}\left(T_{(1432)}\left(A\otimes
C\otimes A\otimes C\right)\left\langle{\left(B\otimes D\otimes D\otimes
B\right)_{U}}\right\rangle_{U\in\mathcal{C}_{k}}\right)$ (19)

from the latter equation, the calculation is a straightforward, but tedious
application of Theorem 1. ∎

The following corollary explicitly shows the difference in the scaling of the
$8$-point OTOC for a pure Clifford circuit and a universal circuit. As we
shall see there is a marked difference in these scalings. As a direct
consequence of Theorem 1 and Application 1, we obtain the following

######  Corollary 1.

Taking the average for $U\in\mathcal{U}(d)$ and $C\in\mathcal{C}(d)$ of the
$8$-point OTOC, one gets

$\displaystyle\left\langle{\text{OTOC}_{8}(U)}\right\rangle_{U\in\mathcal{U}(d)}$
$\displaystyle=$
$\displaystyle\frac{5d^{2}}{(d^{2}-1)(d^{2}-4)(d^{2}-9)}=\frac{5}{d^{4}}+\Theta(d^{-6})$
(20)
$\displaystyle\left\langle{\text{OTOC}_{8}(C)}\right\rangle_{C\in\mathcal{C}(d)}$
$\displaystyle=$
$\displaystyle\frac{d^{2}}{d^{4}-5d^{2}+4}=\frac{1}{d^{2}}+\Theta(d^{4})$ (21)

###### Proof.

The proof of Eq.(20) can be obtained from Eq.(17) in the limit
$k\rightarrow\infty$, in virtue of Theorem 1, while Eq.(21) can be obtained
from Eq.(17) setting $k=0$.∎

With the following statement, we give the necessary and sufficient condition
for the number of non Clifford gates needed to precisely simulate the behavior
of the $8$-point OTOC, and thus to simulate quantum chaos.

######  Corollary 2.

Iff $k=\Theta(\log d)$, then

$\delta_{\text{OTOC}}^{(k)}\equiv\left|\left\langle{\text{OTOC}_{8}(U)}\right\rangle_{U\in\mathcal{C}_{k}}-\left\langle{\text{OTOC}_{8}({U})}\right\rangle_{U\in\mathcal{U}(d)}\right|=\Theta(d^{-4})$
(22)

###### Proof.

Taking the difference in absolute value between Eq.(17) and (20) we get

$\displaystyle\delta_{\text{OTOC}}^{(k)}$ $\displaystyle=$
$\displaystyle-(f^{-})^{k}\frac{d(d^{2}+4d+6)}{6(d^{2}-1)(d+2)(d+3)}+(f^{+})^{k}\frac{d(d^{2}-4d+6)}{6(d^{2}-1)(d-2)(d-3)}$
(23) $\displaystyle+$
$\displaystyle\left({\frac{f^{+}+f^{-}}{2}}\right)^{k}\frac{4d^{2}}{3(d^{2}-1)(d^{2}-4)}$

Taking the asymptotic limit for $d\rightarrow\infty$ up to $\Theta(d^{-4})$

$\delta_{\text{OTOC}}^{(k)}=\frac{1}{d^{2}}\left|\frac{k-3}{3}\right|\left({\frac{3}{4}}\right)^{k}+\Theta(d^{-4})$
(24)

from here it’s easy to see that one has the following condition

$\left(\frac{3}{4}\right)^{k}k=\Theta(d^{-2})\iff k=\Theta(\log d)$ (25)

which leads to the desired result. ∎

##  4 Purity and its Fluctuations

In this section, we compute the fluctuations of a subsystem purity Eq.(4) for
the output of the $k$-doped Clifford circuit $U\in\mathcal{C}_{k}$. To this
end, we first apply Theorem 1 to calculate the average of the fourth tensor
power of a pure state $\psi$, namely
$\Phi^{(4)}_{\mathcal{C}_{k}}(\psi^{\otimes 4})$.

######  Application 3.

The $(\mathcal{C}_{k},4)$-fold channel of a pure state $\psi^{\otimes
4}\in\mathcal{B}(\mathcal{H}^{\otimes 4})$ reads

$\displaystyle\Phi^{(4)}_{\mathcal{C}_{k}}(\psi^{\otimes
4})=a_{k}Q\Pi_{\text{sym}}^{(4)}+b_{k}\Pi_{\text{sym}}^{(4)}$ (26)

where $\Pi_{\text{sym}}^{(4)}$ is the projector onto the completely symmetric
subspace of the permutation group $\mathcal{S}_{4}$ and
$D_{\text{sym}}={\operatorname{tr}}(\Pi_{\text{sym}}^{(4)})$. The coefficients
$a_{k},b_{k}$ are given by

$\displaystyle a_{k}$ $\displaystyle\equiv$
$\displaystyle\left(\frac{{\operatorname{tr}}(\psi^{\otimes
4}Q)}{D^{+}}-\frac{{\operatorname{tr}}(\psi^{\otimes
4}Q^{\perp})}{D^{-}}\right)\left(\frac{c_{Q}}{D^{+}}-\frac{c_{QQ^{\perp}}}{D^{-}}\right)^{k}$
$\displaystyle b_{k}$ $\displaystyle\equiv$
$\displaystyle\frac{{\operatorname{tr}}(\psi^{\otimes
4}Q^{\perp})}{D^{-}}+\frac{c_{QQ^{\perp}}}{D^{-}}\sum_{i=0}^{k-1}a_{i}$ (27)

with

$c_{Q}\equiv{\operatorname{tr}}(K^{\otimes 4}QK^{{\dagger}\otimes
4}Q\Pi_{\text{sym}}^{(4)}),\quad
c_{QQ^{\perp}}\equiv{\operatorname{tr}}(K^{\otimes 4}QK^{{\dagger}\otimes
4}Q^{\perp}\Pi_{\text{sym}}^{(4)})$ (28)

The proof can be found in App. B.3. The evaluation of Eq.(26) becomes
particularly simple if the gate $K$ is a $P_{\theta}$-gate:

######  Application 4.

If the single qubit gate $K$ is the $P_{\theta}$-gate, the coefficients
$c_{Q},c_{QQ^{\perp}}$ read:

$\displaystyle c_{Q}$ $\displaystyle=$
$\displaystyle\frac{(d+2)(4+7d+(4+d)\cos(4\theta))}{48}$ (29) $\displaystyle
c_{QQ^{\perp}}$ $\displaystyle=$
$\displaystyle\frac{(d+2)(d+4)}{24}\sin^{2}(2\theta)$ (30)

Then for any $k$ we can write the coefficients $a_{k},b_{k}$ as

$\displaystyle a_{k}$ $\displaystyle=$
$\displaystyle\frac{24}{(d^{2}-1)(d+2)(d+4)}\left(\frac{d(d+3)}{4}{\operatorname{tr}}(\psi^{\otimes
4}Q)-1\right)(f_{\theta}^{-})^{k}$ $\displaystyle b_{k}$ $\displaystyle=$
$\displaystyle\frac{1}{D_{\text{sym}}}+\frac{24}{(d^{2}-1)(d+2)(d+4)}\left(\frac{4}{d(d+3)}-{\operatorname{tr}}(\psi^{\otimes
4}Q)\right)(f_{\theta}^{-})^{k}$ (31)

where $(f_{\theta}^{-})$ is defined in Eq.(84); note that $(f_{\theta}^{-})<1$
unless $\theta=\pm\pi/2$, i.e unless $P_{\theta}=S$ the $S$-gate
$\in\mathcal{C}(d)$.

See App. B.4 for the proof.

######  Corollary 3.

For any $\theta\neq\pm\pi/2$

$\lim_{k\rightarrow\infty}\Phi^{(4)}_{\mathcal{C},k}(\psi^{\otimes
4})=\Phi^{(4)}_{\mathcal{U}(d)}(\psi^{\otimes 4})$ (32)

###### Proof.

The proof follows directly from Application 1; here we give an alternative
version: setting $f_{\theta}<1$ in Eq.(31) and taking the limit
$k\rightarrow\infty$ one gets

$\displaystyle\lim_{k\rightarrow\infty}a_{k}$ $\displaystyle=$ $\displaystyle
0$ (33) $\displaystyle\lim_{k\rightarrow\infty}b_{k}$ $\displaystyle=$
$\displaystyle D_{\text{sym}}^{-1}$ (34)

Now, since the fourth tensor power of $\psi_{U}$ averages to - see Eq.(65) in
App. A.3.1 for a proof -

$\Phi^{(4)}_{\mathcal{U}(d)}(\psi^{\otimes
4})=\frac{\Pi_{\text{sym}}^{(4)}}{D_{\text{sym}}}$ (35)

then by Application 3 the proof is complete. ∎

In what follows, we calculate the purity and its fluctuations in a bipartite
Hilbert space for the output state of a $k$-doped Clifford circuit, calculated
above in Eq.(26). Consider then a bipartition of the $N$-qubit system
$\mathcal{H}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ with
$\mathcal{H}_{A(B)}=\mathbb{C}^{2\otimes N_{A(B)}}$, $N_{A}+N_{B}=N$ and
$d_{A(B)}=2^{N_{A(B)}}$. The purity of a marginal state
$\psi_{A}={\operatorname{tr}}_{B}\psi\in\mathcal{B}(\mathcal{H}_{A})$ is given
by

$\operatorname{Pur}(\psi_{A}):={\operatorname{tr}}(\psi_{A}^{2})$ (36)

The averages over Unitary and Clifford group for the purity of the output
$\psi$ of a random quantum circuits are the same, namely

$\left\langle{\operatorname{Pur}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{U}(d)}=\left\langle{\operatorname{Pur}(\psi_{C})_{A}}\right\rangle_{C\in\mathcal{C}(d)}=\frac{d_{A}+d_{B}}{d_{A}d_{B}+1}$
(37)

This is a consequence of $\mathcal{C}(d)$ being a $3$-design[18, 19] (in fact,
being a $2$-design is sufficient), see App. A.3.1 for a proof. Notice that the
average purity does not depend on the input state.

The fluctuations of the purity for the set $x$ are defined as

$\displaystyle\Delta_{x}\operatorname{Pur}(\psi_{U})_{A}:=\langle(\operatorname{Pur}(\psi_{U})_{A}-\langle\operatorname{Pur}(\psi_{U})_{A}\rangle_{U\in
x})^{2}\rangle_{U\in x}$ (38)

Since the fluctuations involve the fourth moment of the Haar measure, the
fluctuations for $\mathcal{U}(d),\mathcal{C}(d)$ are expected to be different.
We have indeed, for $d_{A}=d_{B}=\sqrt{d}$

$\displaystyle\Delta_{\mathcal{U}(d)}\operatorname{Pur}(\psi_{U})_{A}$
$\displaystyle=$
$\displaystyle\frac{2(d-1)^{2}}{(d+1)^{2}(d+2)(d+3)}=\Theta(d^{-2})$ (39)
$\displaystyle\Delta_{\mathcal{C}(d)}\operatorname{Pur}(\psi_{C})_{A}$
$\displaystyle=$
$\displaystyle\frac{(d-1)[d(d+1){\operatorname{tr}}(Q\psi^{\otimes
4})-2]}{(d+1)^{2}(d+2)}=\begin{cases}\Theta(d^{-1}),\quad\psi=\left|{0}\right\rangle\left\langle{0}\right|^{\otimes
N}\\\
\Theta(d^{1-\log_{2}5}),\quad\psi=\otimes_{i}\psi_{i},\;\psi_{i}\;\text{random}\end{cases}$
(40)

This result is a consequence of Application 3 and Corollary 3. Notice that
while the fluctuations of the purity for the unitary group again do not depend
on the initial state, those for the Clifford group do. For $\psi$ being any
other stabilizer state different from
$\left|{0}\right\rangle\left\langle{0}\right|^{\otimes N}$, the formula would
not change thanks to the left/right invariance of the Haar measure over
groups. Notably, starting from completely factorized states, there is a marked
difference whether the initial state $\psi$ is a stabilizer state or a random
product state.

######  Lemma 1.

The fluctuations of the purity in the $k$-doped Clifford circuit, for
$d_{A}=d_{B}=\sqrt{d}$ and
$\psi=\left|{0}\right\rangle\left\langle{0}\right|^{\otimes N}$, are

$\Delta_{\mathcal{C}_{k}}\operatorname{Pur}(\psi_{U})_{A}=\frac{(d-1)^{2}}{(d+1)^{2}(d+2)(d+3)}(2+(d+1)(f_{\theta}^{-})^{k})$
(41)

where $f_{\theta}^{-}$ is defined in Eq.(84).

The proof can be found in App. B.5.

######  Remark 1.

For the undoped, $k=0$, pure Clifford circuit, one finds

$\left\langle{\operatorname{Pur}^{2}(\psi_{C})_{A}}\right\rangle_{C\in\mathcal{C}(d)}=\frac{5d+1}{(d+1)(d+2)}$
(42)

Notice that, in the large $d$ limit,

$\displaystyle\left\langle{\operatorname{Pur}^{2}(\psi_{C})_{A}}\right\rangle_{C\in\mathcal{C}(d)}$
$\displaystyle=$ $\displaystyle\frac{5}{d}+\Theta(d^{-2})$ (43)
$\displaystyle\left\langle{\operatorname{Pur}^{2}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{U}(d)}$
$\displaystyle=$ $\displaystyle\frac{4}{d}+\Theta(d^{-2})$ (44)

and thus have the same order. However, the next corollary shows that - because
of an exact cancellation - the fluctuations are very different in scaling with
$d$.

######  Corollary 4.

The fluctuations of the purity, for $d_{A}=d_{B}=\sqrt{d}$ and
$\psi=\left|{0}\right\rangle\left\langle{0}\right|^{\otimes N}$ for the
Clifford circuit are

$\displaystyle\Delta_{\mathcal{C}(d)}\operatorname{Pur}(\psi_{C})_{A}$
$\displaystyle=$
$\displaystyle\frac{(d-1)^{2}}{(d+1)^{2}(d+2)}=\Theta(d^{-1})$ (45)
$\displaystyle\Delta_{\mathcal{U}(d)}\operatorname{Pur}(\psi_{U})_{A}$
$\displaystyle=$
$\displaystyle\frac{2(d-1)^{2}}{(d+1)^{2}(d+2)(d+3)}=\Theta(d^{-2})$ (46)

###### Proof.

Eq.(45) follows immediately from Lemma 1 by setting $k=0$, while Eq.(46) can
be found in [20]. ∎

######  Corollary 5.

For any $\theta\neq\pm\pi/2$, for $d_{A}=d_{B}=\sqrt{d}$ and
$\psi=\left|{0}\right\rangle\left\langle{0}\right|^{\otimes N}$, iff
$k=\Theta(\log d)$

$\delta_{\operatorname{Pur}}^{(k)}\equiv|\Delta_{\mathcal{C}_{k}}\operatorname{Pur}(\psi_{U})_{A}-\Delta_{\mathcal{U}(d)}\operatorname{Pur}(\psi_{U})_{A}|=\Theta(d^{-2})$
(47)

###### Proof.

From Eq.(41) one has

$\delta_{\operatorname{Pur}}^{(k)}=\frac{(d-1)^{2}}{(d+1)(d+2)(d+3)}(f_{\theta}^{-})^{k}$
(48)

for $k=0$ this difference is $\Theta(d^{-1})$, then in order to get
$O(d^{-2})$ one needs to have

$f_{\theta}^{k}=\Theta(d^{-1})\iff k=\Theta(\log d)$ (49)

moreover, note that the rate of convergence is dictated by $f_{\theta}$, which
reaches its minimum value for $\theta=\pi/4$, that is the $T$-gate, cfr.
Eq.(84).∎

######  Lemma 2.

The fluctuations of the purity for a $k$-doped Clifford circuit, for
$d_{A}=d_{B}=\sqrt{d}$ and $\psi$ be a random product state read

$\Delta_{\mathcal{C}_{k}}\operatorname{Pur}(\psi_{U})_{A}=\frac{2(d-1)^{2}}{(d+1)^{2}(d+2)(d+3)}+\frac{(d-1)(d^{(2-\log_{2}5)}(d-3)-4)(f^{-}_{\theta})^{k}}{(d+1)(d+2)(d+3)}$
(50)

###### Proof.

The proof is straightforward and is left to the interested reader: by plugging
(158) into Eqs. (27) and (26) and using Eq.(120) the calculation follows
easily.∎

######  Corollary 6.

The fluctuations of the purity for a non-doped Clifford circuit, for
$d_{A}=d_{B}=\sqrt{d}$ and $\psi$ a random product state, are

$\Delta_{\mathcal{C}(d)}\operatorname{Pur}(\psi_{U})_{A}=\frac{(d-1)[d(d+1)d^{1-\log_{2}5}-2]}{(d+1)^{2}(d+2)}$
(51)

###### Proof.

This result is obtained from Lemma 2 setting $k=0$.∎

######  Remark 2.

The hypothesis $d_{A}=d_{B}=\sqrt{d}$ only simplifies the displayed formulas
and the related considerations but does not change the general behavior. For
instance, in the case $d_{B}\gg d_{A}\gg 1$ one has - after a lengthy
calculation,

$\Delta_{\mathcal{C}_{k}}\operatorname{Pur}(\psi_{U})_{A}=\frac{2(d^{2}-d_{A}^{2})(d^{2}_{A}-1)}{(d+1)^{2}(d+2)(d+3)d^{2}_{A}}+\frac{(d^{2}-d_{A}^{2})(d_{A}^{2}-1)f^{k}_{\theta}(d(d+3){\operatorname{tr}}\left({Q\psi^{\otimes
4}}\right)-4)}{(d-1)(d+1)(d+2)(d+3)d^{2}_{A}}$ (52)

## Conclusions and Outlook

In this paper, we showed that in a random Clifford circuit with $N$ qubits,
$\Theta(N)$ non Clifford gates are both necessary and sufficient to simulate
quantum chaos. As a consequence, quantum chaos cannot be efficiently simulated
on a classical computer, as the cost for simulating such circuits is
exponential in the non Clifford resources.

In perspective, there are several open questions. One could generalize many of
these results by proving that an $\epsilon$-approximate $2t$-OTOC
characterizes an $\epsilon$-approximate $t$-design. Although the scaling is
fixed to be $\Theta(N)$, the actual number of non Clifford resources is
undetermined and it would be of practical importance in obtaining approximate
$t$-designs with a noisy, intermediate-scale quantum computer. One could thus
study the optimal arrangement of non Clifford resources. A related question is
the onset of irreversibility in a closed quantum system in the sense of
entanglement complexity[16] is driven by the doping of a Clifford circuit.
Similarly, it would be interesting to show how the entanglement spectrum
statistics converges with the doping[11].

## Acknowledgments

We acknowledge support from NSF award number 2014000. The authors thank
Claudio Chamon for important and enlightening discussions and comments.

## References

  * [1] S. Bravyi and D. Gosset,  _Improved classical simulation of quantum circuits dominated by Clifford gates_ ,  Physical Review Letters 116, 250501 (2016),  doi:10.1103/PhysRevLett.116.250501.
  * [2] A. Kitaev,  _Hidden correlations in the Hawking radiation and thermal noise_ ,  In _Talk given at the Fundamental Physics Prize Symposium_ , vol. 10 (2014).
  * [3] D. A. Roberts and B. Yoshida,  _Chaos and complexity by design_ ,  Journal of High Energy Physics 2017(4), 121 (2017),  doi:10.1007/JHEP04(2017)121.
  * [4] A. W. Harrow, L. Kong _et al._ ,  _A separation of out-of-time-ordered correlation and entanglement_ ,  arXiv (2020),  [quant-ph/1906.02219].
  * [5] A. Nahum, S. Vijay and J. Haah,  _Operator spreading in random unitary circuits_ ,  Physical Review X 8, 021014 (2018),  doi:10.1103/PhysRevX.8.021014.
  * [6] V. Khemani, A. Vishwanath and D. A. Huse,  _Operator spreading and the emergence of dissipative hydrodynamics under unitary evolution with conservation laws_ ,  Physical Review X 8, 031057 (2018),  doi:10.1103/PhysRevX.8.031057.
  * [7] S. F. E. Oliviero, L. Leone _et al._ ,  _Random Matrix Theory of the Isospectral twirling_ ,  SciPost Phys. 10, 76 (2021),  doi:10.21468/SciPostPhys.10.3.076.
  * [8] D. Ding, P. Hayden and M. Walter,  _Conditional mutual information of bipartite unitaries and scrambling_ ,  Journal of High Energy Physics 2016(12), 145 (2016),  doi:10.1007/JHEP12(2016)145.
  * [9] P. Hosur, X. Qi _et al._ ,  _Chaos in quantum channels_ ,  Journal of High Energy Physics 2016(2), 4 (2016),  doi:10.1007/JHEP02(2016)004.
  * [10] L. Leone, S. F. Oliviero and A. Hamma,  _Isospectral twirling and quantum chaos_ ,  arXiv (2020),  [quant-ph/2011.06011].
  * [11] S. Zhou, Z. Yang _et al._ ,  _Single T gate in a Clifford circuit drives transition to universal entanglement spectrum statistics_ ,  SciPost Phys. 9, 87 (2020),  doi:10.21468/SciPostPhys.9.6.087.
  * [12] J. Haferkamp, F. Montealegre-Mora _et al._ ,  _Quantum homeopathy works: Efficient unitary designs with a system-size independent number of non-Clifford gates_ ,  arXiv (2020),  [quant-ph/2002.09524].
  * [13] M. J. Bremner, R. Jozsa and D. J. Shepherd,  _Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy_ ,  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467(2126), 459 (2011),  doi:10.1098/rspa.2010.0301.
  * [14] A. W. Harrow and A. Montanaro,  _Quantum computational supremacy_ ,  Nature 549(7671), 203 (2017),  doi:10.1038/nature23458.
  * [15] D. A. Roberts and B. Swingle,  _Lieb-Robinson bound and the butterfly effect in quantum field theories_ ,  Physical Review Letters 117, 091602 (2016),  doi:10.1103/PhysRevLett.117.091602.
  * [16] C. Chamon, A. Hamma and E. R. Mucciolo,  _Emergent irreversibility and entanglement spectrum statistics_ ,  Physical Review Letters 112, 240501 (2014),  doi:10.1103/PhysRevLett.112.240501.
  * [17] A. W. Harrow and R. A. Low,  _Random quantum circuits are approximate 2-designs_ ,  Communications in Mathematical Physics 291(1), 257 (2009),  doi:10.1007/s00220-009-0873-6.
  * [18] Z. Webb,  _The Clifford group forms a unitary 3-design_ ,  arXiv (2016),  [quant-ph/1510.02769].
  * [19] H. Zhu,  _Multiqubit Clifford groups are unitary 3-designs_ ,  Physical Review A 96, 062336 (2017),  doi:10.1103/PhysRevA.96.062336.
  * [20] A. Hamma, S. Santra and P. Zanardi,  _Ensembles of physical states and random quantum circuits on graphs_ ,  Physical Review A 86, 052324 (2012),  doi:10.1103/PhysRevA.86.052324.
  * [21] B. Collins and P. Śniady,  _Integration with respect to the Haar measure on unitary, orthogonal and symplectic group_ ,  Communications in Mathematical Physics 264(3), 773 (2006),  doi:10.1007/s00220-006-1554-3.
  * [22] B. Collins,  _Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability_ ,  International Mathematics Research Notices 2003(17), 953 (2003),  doi:10.1155/S107379280320917X.
  * [23] I. Roth, R. Kueng _et al._ ,  _Recovering quantum gates from few average gate fidelities_ ,  Physical Review Letters 121, 170502 (2018),  doi:10.1103/PhysRevLett.121.170502.
  * [24] H. Zhu, R. Kueng _et al._ ,  _The Clifford group fails gracefully to be a unitary 4-design_ ,  arXiv (2016),  [quant-ph/1609.08172].

##  Appendix A Haar averages: Unitary vs Clifford group

In this section, we are going to display the explicit formula to average over
the full unitary group and the full Clifford group without going into the
group theoretic details. See [21, 22] for the Haar integration and [23, 24]
for the Clifford integration formula.

###  A.1 Clifford group average

Starting from the result about the $4$-th moment of the Haar average over the
Clifford group in[23] we are going to prove a useful lemma.

######  Lemma 3.

Let $\mathcal{O}\in\mathcal{B}(\mathcal{H}^{\otimes 4})$, the integration
formula for the Clifford group reads

$\left\langle{\mathcal{O}_{C}}\right\rangle_{C\in\mathcal{C}(d)}=\int_{\mathcal{C}(d)}{\operatorname{d}}CC^{{\dagger}\otimes
4}\mathcal{O}C^{\otimes
4}=\sum_{\pi,\sigma\in\mathcal{S}_{4}}W^{+}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}QT_{\pi})QT_{\sigma}+W^{-}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}Q^{\perp}T_{\pi})Q^{\perp}T_{\sigma}$
(53)

where $Q=\frac{1}{d^{2}}\sum_{P\in\mathcal{P}(d)}P^{\otimes 4}$ and
$Q^{\perp}={\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}^{\otimes 4}-Q$, while
$W^{\pm}_{\pi\sigma}$ are the generalized Weingarten functions, defined as

$W^{\pm}_{\pi\sigma}=\sum_{\begin{subarray}{c}\lambda\vdash 4\\\
D^{\pm}_{\lambda}\neq
0\end{subarray}}\frac{d_{\lambda}^{2}}{(4!)^{2}}\frac{\chi^{\lambda}(\pi\sigma)}{D^{\pm}_{\lambda}}$
(54)

here $\lambda$ labels the irreducible representations of the symmetric group
$\mathcal{S}_{4}$, $\chi^{\lambda}(\pi\sigma)$ are the characters of
$\mathcal{S}_{4}$, $d_{\lambda}$ is the dimension of the irreducible
representation $\lambda$, $D_{\lambda}^{+}={\operatorname{tr}}(QP_{\lambda})$
and $D_{\lambda}^{-}={\operatorname{tr}}(Q^{\perp}P_{\lambda})$ where
$P_{\lambda}$ are the projectors onto the irreducible representations of
$\mathcal{S}_{4}$ and finally $T_{\sigma}$ are permutation operators
corresponding to the permutation $\sigma\in\mathcal{S}_{4}$.

###### Proof.

The projectors onto the irreducible representations of $\mathcal{S}_{4}$ read

$\Pi_{\lambda}^{(4)}=\frac{d_{\lambda}}{4!}\sum_{\tau\in\mathcal{S}_{4}}\chi^{\lambda}(\tau)T_{\tau}$
(55)

Starting from the integration formula $(32)$ in [23] we have

$\displaystyle\left\langle{\mathcal{O}_{C}}\right\rangle_{C\in\mathcal{C}(d)}$
$\displaystyle=\frac{1}{(4!)^{2}}\sum_{\lambda\vdash 4,l(\lambda)\leq
d}d_{\lambda}^{2}\sum_{\sigma\in\mathcal{S}_{4}}\left({\frac{1}{D_{\lambda}^{+}}{\operatorname{tr}}(\mathcal{O}QT_{\sigma})Q+\frac{1}{D_{\lambda}^{-}}{\operatorname{tr}}(\mathcal{O}Q^{\perp}T_{\sigma})Q^{\perp}}\right)T_{\sigma}^{-1}\chi^{\lambda}(\tau)T_{\tau}$
(56) $\displaystyle=\frac{1}{(4!)^{2}}\sum_{\lambda\vdash 4,l(\lambda)\leq
d}d_{\lambda}^{2}\sum_{\tau\sigma\in\mathcal{S}_{4}}\left({\frac{1}{D_{\lambda}^{+}}{\operatorname{tr}}(\mathcal{O}QT_{\sigma})Q+\frac{1}{D_{\lambda}^{-}}{\operatorname{tr}}(\mathcal{O}Q^{\perp}T_{\sigma})Q^{\perp}}\right)\chi^{\lambda}(\tau)T_{\sigma^{-1}\tau}$
$\displaystyle=\frac{1}{(4!)^{2}}\sum_{\lambda\vdash 4,l(\lambda)\leq
d}d_{\lambda}^{2}\sum_{\pi,\sigma\in\mathcal{S}_{4}}\left({\frac{1}{D_{\lambda}^{+}}{\operatorname{tr}}(\mathcal{O}QT_{\sigma})Q+\frac{1}{D_{\lambda}^{-}}{\operatorname{tr}}(\mathcal{O}Q^{\perp}T_{\sigma})Q^{\perp}}\right)\chi^{\lambda}(\sigma\pi)T_{\pi}$

At this point, we just define

$W^{\pm}_{\pi\sigma}=\sum_{\begin{subarray}{c}\lambda\vdash 4\\\
D^{\pm}_{\lambda}\neq
0\end{subarray}}\frac{d_{\lambda}^{2}}{(4!)^{2}}\frac{\chi^{\lambda}(\pi\sigma)}{D^{\pm}_{\lambda}}$
(57)

and the derivation is complete. ∎

An important property that will be used throughout the paper is the following:

$[Q,T_{\pi}]=0,\quad\forall\,\pi\in\mathcal{S}_{4}$ (58)

another important property is that $Q$ is a projector, namely $Q^{2}=Q$.
Another useful result, related to the generalized Weingarten functions is

$\sum_{\pi,\sigma\in\mathcal{S}_{4}}W^{\pm}_{\pi\sigma\in\mathcal{S}_{4}}T_{\pi}=\frac{\Pi_{\text{sym}}^{(4)}}{D^{\pm}}$
(59)

the proof comes from Eq. $\eqref{generalizedWeingarten}$ and from
$\Pi_{\text{sym}}^{(4)}=(4!)^{-1}\sum_{\pi\in\mathcal{S}_{4}}T_{\pi}$.

###  A.2 Unitary group average

Let $\mathcal{O}\in\mathcal{B}(\mathcal{H}^{\otimes t})$ be a bounded operator
on $t$-copies of $\mathcal{H}$, then the Haar average reads[22, 21]

$\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{U}(d)}=\int_{\mathcal{U}(d)}{\operatorname{d}}UU^{{\dagger}\otimes
t}\mathcal{O}U^{\otimes
t}=\sum_{\pi,\sigma\in\mathcal{S}_{t}}W_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}T_{\sigma})T_{\pi}$
(60)

where $T_{\pi}$ is the permutation operator corresponding to the permutation
$\pi\in S_{t}$, the $t$-dimensional symmetric group and $W_{\pi\sigma}$ are
the Weingarten functions defined as

$W_{\pi\sigma}=\sum_{\lambda\vdash
t}\frac{d_{\lambda}^{2}}{(t!)^{2}}\frac{\chi^{\lambda}(\pi\sigma)}{D_{\lambda}}$
(61)

where $D_{\lambda}={\operatorname{tr}}(\Pi^{(4)}_{\lambda})$.

###  A.3 A couple of Haar averages over $\mathcal{U}(d)$

####  A.3.1 The average purity

Let us calculate the average purity for the output state $\psi_{U}$, for
$U\in\mathcal{U}(d)$ or $U\in\mathcal{C}(d)$; indeed the result of the average
for the two groups is the same because the Clifford group forms a unitary
$3$-design and being a $t$-design means being a $\tilde{t}$-design for any
$\tilde{t}\leq t$. Then, the average purity

$\left\langle{\operatorname{Pur}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{U}(d)}=\int_{\mathcal{U}(d)}{\operatorname{d}}U{\operatorname{tr}}(T_{(12)}^{(A)}U^{\otimes
2}\psi^{\otimes 2}U^{{\dagger}\otimes
2})=\sum_{\pi,\sigma\in\mathcal{S}_{2}}W_{g}(\pi\sigma){\operatorname{tr}}(\psi^{\otimes
2}T_{\sigma}){\operatorname{tr}}(T_{(12)}^{(A)}T_{\pi})$ (62)

Since $T_{\sigma}\psi^{\otimes 2}=\psi^{\otimes 2}$ as long as $\psi$ is a
pure state, we have

$\left\langle{\operatorname{Pur}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{U}(d)}=\sum_{\pi,\sigma\in\mathcal{S}_{2}}W_{g}(\pi\sigma){\operatorname{tr}}(T_{(12)}^{(A)}T_{\pi})=\frac{1}{D_{\text{sym}}}{\operatorname{tr}}(T_{(12)}^{(A)}\Pi_{\text{sym}}^{(2)})$
(63)

where
$\Pi_{\text{sym}}^{(2)}\equiv\frac{1}{2}\sum_{\sigma\in\mathcal{S}_{2}}T_{\sigma}$
and $D_{\text{sym}}={\operatorname{tr}}(\Pi_{\text{sym}}^{(2)})=d(d+1)/2$.
Then, since $T_{\sigma}=T_{\sigma}^{(A)}\otimes T_{\sigma}^{(B)}$, see Sec.
C.2 for a more rigorous treatment, we have

$\displaystyle\left\langle{\operatorname{Pur}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{U}(d)}$
$\displaystyle=$
$\displaystyle\frac{1}{d(d+1)}\left({\operatorname{tr}}(T_{(12)}^{(A)}T_{(12)}^{(A)}){\operatorname{tr}}(T_{(12)}^{(B)})+{\operatorname{tr}}(T_{(12)}^{(A)}{\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}^{(A)\otimes 2}){\operatorname{tr}}({\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}^{(B)\otimes 2})\right)$ (64) $\displaystyle=$
$\displaystyle\frac{2}{d(d+1)}(d_{A}^{2}d_{B}+d_{A}d_{B}^{2})=\frac{d_{A}+d_{B}}{d_{A}d_{B}+1}$

where we have used $d=d_{A}d_{B}$.

####  A.3.2 The average state $\left\langle{\psi_{U}^{\otimes
4}}\right\rangle_{U\in\mathcal{U}(d)}$

Let $\psi_{U}$ be the output state of a quantum circuit $U$. Let us average
the fourth tensor power of this output state for $U\in\mathcal{U}(d)$. Using
formula (60) we have

$\left\langle{\psi_{U}^{\otimes
4}}\right\rangle_{U\in\mathcal{U}(d)}=\sum_{\pi,\sigma\in\mathcal{S}_{4}}W_{\pi\sigma}{\operatorname{tr}}(T_{\sigma}\psi^{\otimes
4})T_{\pi}=\sum_{\pi,\sigma\in\mathcal{S}_{4}}W_{\pi\sigma}T_{\pi}=\frac{\Pi_{\text{sym}}^{(4)}}{D_{\text{sym}}}$
(65)

where we used the fact that $T_{\sigma}\psi^{\otimes 4}=\psi^{\otimes 4}$ for
any permutation operator $T_{\sigma}$ and that
$\sum_{\pi,\sigma\in\mathcal{S}_{4}}W_{\pi\sigma}T_{\pi}=\Pi^{(4)}_{\text{sym}}/D_{\text{sym}}$,
where $D_{\text{sym}}={\operatorname{tr}}(\Pi^{(4)}_{\text{sym}})$.

##  Appendix B Proofs

###  B.1 Proof of Theorem 1

Let $\mathcal{O}\in\mathcal{B}(\mathcal{H}^{\otimes 4})$ and let the
$\Phi^{(4)}_{\mathcal{C}_{k}}(\mathcal{O})$ be its output through the
$(\mathcal{C}_{k},4)$-fold channel. Then

$\Phi^{(4)}_{\mathcal{C}_{k}}(\mathcal{O}):=\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{k}}\equiv\langle
C_{k}^{\otimes 4}K_{i_{k}}^{\otimes 4}\dots C_{1}^{\otimes
4}K_{i_{1}}^{\otimes 4}C_{0}^{\otimes 4}\mathcal{O}C_{0}^{{\dagger}\otimes
4}K_{i_{1}}^{{\dagger}\otimes 4}C_{1}^{\otimes 4}\dots
K_{i_{k}}^{{\dagger}\otimes 4}C_{k}^{{\dagger}\otimes 4}\rangle_{C_{1}\ldots
C_{k}\in\mathcal{C}(d)}$ (66)

then since the averages over $C_{i}$ for $i=1,\dots,k$ are independent from
each other, we can also write

$\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{k}}=\left\langle{\mathcal{C}_{k}^{\otimes
4}K_{i_{k}}^{\otimes 4}\dots K_{i_{2}}^{\otimes 4}\left\langle{C_{1}^{\otimes
4}K_{i_{1}}^{\otimes 4}\left\langle{\mathcal{C}_{0}^{\otimes
4}\mathcal{O}\mathcal{C}_{0}^{{\dagger}\otimes
4}}\right\rangle_{C_{0}\in\mathcal{C}(d)}K_{i_{1}}^{{\dagger}\otimes
4}C_{1}^{{\dagger}\otimes
4}}\right\rangle_{C_{1}\in\mathcal{C}(d)}K_{i_{2}}^{{\dagger}\otimes 4}\dots
K_{i_{k}}^{{\dagger}\otimes 4}\mathcal{C}^{\otimes
4}_{k}}\right\rangle_{C_{k}\in\mathcal{C}(d)}$ (67)

The first Clifford average before inserting any single qubit $K$-gate reads

$\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{0}}=\sum_{\pi,\sigma\in\mathcal{S}_{4}}[W^{+}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}QT_{\sigma})-W^{-}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}Q^{\perp}T_{\sigma})]QT_{\pi}+\sum_{\pi,\sigma\in\mathcal{S}_{4}}W^{-}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}Q^{\perp}T_{\sigma})T_{\pi}$
(68)

where we have used Eq.(53). We can recast it as

$\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{0}}=\sum_{\pi\in\mathcal{S}_{4}}(c_{\pi}(\mathcal{O})Q+b_{\pi}(\mathcal{O}))T_{\pi}$
(69)

where

$\displaystyle c_{\pi}(\mathcal{O})$ $\displaystyle=$
$\displaystyle\sum_{\sigma\in\mathcal{S}_{4}}[W^{+}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}QT_{\sigma})-W^{-}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}Q^{\perp}T_{\sigma})]$
(70) $\displaystyle b_{\pi}(\mathcal{O})$ $\displaystyle=$
$\displaystyle\sum_{\sigma\in\mathcal{S}_{4}}W^{-}_{\pi\sigma}{\operatorname{tr}}(\mathcal{O}Q^{\perp}T_{\sigma})$
(71)

Now we need to apply the first $K_{i_{1}}$-gate on the $i$-th qubit; noting
that $[T_{\pi},K_{i_{1}}^{\otimes 4}]=0$ for all $\pi\in\mathcal{S}_{4}$, we
have

$\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{0}}\rightarrow
K^{{\dagger}\otimes
4}_{i_{1}}\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{0}}K_{i_{1}}^{\otimes
4}=\sum_{\pi\in\mathcal{S}_{4}}(c_{\pi}(\mathcal{O})K_{i_{1}}^{\otimes
4}QK_{i_{1}}^{{\dagger}\otimes 4}+b_{\pi}(\mathcal{O}))T_{\pi}$ (72)

and then average over another Clifford layer, knowing that the Clifford
operator only acts non trivially only on the operator $K_{i_{1}}^{\otimes
4}QK_{i_{1}}^{{\dagger}\otimes 4}T_{\pi}$ because $[C^{\otimes
4},T_{\sigma}]=0,\,\forall\sigma$

$\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{1}}=\left\langle{C_{1}^{\otimes
4}K_{i_{1}}^{\otimes
4}\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{0}}K_{i_{1}}^{{\dagger}\otimes
4}C_{1}^{{\dagger}\otimes
4}}\right\rangle_{C_{1}\in\mathcal{C}(d)}=\sum_{\pi\in\mathcal{S}_{4}}c_{\pi}(\mathcal{O})\left\langle{C_{1}^{{\dagger}\otimes
4}K_{i_{1}}^{\otimes 4}QK_{i_{1}}^{{\dagger}\otimes
4}T_{\pi}C_{1}^{{\dagger}\otimes
4}}\right\rangle_{C_{1}\in\mathcal{C}(d)}+b_{\pi}(\mathcal{O})T_{\pi}$ (73)

Then, from Eq.(53)

$\left\langle{C_{1}^{{\dagger}\otimes 4}K_{i_{1}}^{\otimes
4}QK_{i_{1}}^{{\dagger}\otimes 4}T_{\pi}C_{1}^{{\dagger}\otimes
4}}\right\rangle_{C_{1}\in\mathcal{C}(d)}=\sum_{\sigma\in\mathcal{S}_{4}}(\Xi_{\pi\sigma}Q+\Lambda_{\pi\sigma})T_{\sigma}$
(74)

where $\Xi_{\pi\sigma}$ and $\Lambda_{\pi\sigma}$ read

$\displaystyle\Xi_{\sigma\pi}$ $\displaystyle\equiv$
$\displaystyle\sum_{\tau\in\mathcal{S}_{4}}[W^{+}_{\pi\tau}{\operatorname{tr}}(T_{\sigma}K^{\otimes
4}QK^{{\dagger}\otimes
4}QT_{\tau})-W^{-}_{\pi\tau}{\operatorname{tr}}(T_{\sigma}K^{\otimes
4}QK^{{\dagger}\otimes 4}Q^{\perp}T_{\tau})]$ (75)
$\displaystyle\Lambda_{\sigma\pi}$ $\displaystyle\equiv$
$\displaystyle\sum_{\tau\in\mathcal{S}_{4}}W^{-}_{\pi\tau}{\operatorname{tr}}(T_{\sigma}K^{\otimes
4}QK^{{\dagger}\otimes 4}Q^{\perp}T_{\tau})$ (76)

we have defined the matrix $\Xi$ omitting the subscript $K_{i_{1}}$ because,
as shown in Lemma 6, it does not play any role. Thus, we have
$\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{1}}=\sum_{\pi,\sigma\in\mathcal{S}_{4}}(\Xi_{\sigma\pi}Q+\Lambda_{\sigma\pi})c_{\pi}(\mathcal{O})T_{\sigma}+b_{\pi}(\mathcal{O})T_{\pi}$;
at the next iteration

$\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{2}}=\sum_{\pi,\sigma\tau\in\mathcal{S}_{4}}(\Xi_{\tau\sigma}Q+\Lambda_{\tau\sigma})\Xi_{\sigma\pi}c_{\pi}(\mathcal{O})T_{\tau}+\sum_{\pi,\sigma\in\mathcal{S}_{4}}[\Lambda_{\sigma\pi}c_{\pi}(\mathcal{O})+\delta_{\pi\sigma}b_{\pi}(\mathcal{O})]T_{\sigma}$
(77)

we can recast it as

$\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{2}}=\sum_{\pi,\sigma\in\mathcal{S}_{4}}\left[\left({(\Xi^{2})_{\pi\sigma}Q+\Lambda_{\pi\sigma}+\sum_{\tau\in\mathcal{S}_{4}}\Lambda_{\pi\tau}\Xi_{\tau\sigma}}\right)c_{\pi}(\mathcal{O})+\delta_{\pi\sigma}b_{\pi}(\mathcal{O})\right]T_{\sigma}$
(78)

The latter relationship can be easily generalized to $k$ layers as

$\left\langle{\mathcal{O}_{U}}\right\rangle_{U\in\mathcal{C}_{k}}=\sum_{\pi,\sigma\in\mathcal{S}_{4}}\left[\left({(\Xi^{k})_{\pi\sigma}Q+\Gamma_{\pi\sigma}^{(k)}}\right)c_{\pi}(\mathcal{O})+\delta_{\pi\sigma}b_{\pi}(\mathcal{O})\right]T_{\sigma}$
(79)

where we have defined
$\Gamma^{(k)}_{\pi\sigma}\equiv\sum_{\tau\in\mathcal{S}_{4}}\Lambda_{\pi\tau}\sum_{i=0}^{k-1}(\Xi^{i})_{\tau\sigma}$.
This concludes the proof. ∎

###  B.2 Proof of Application 1

From theorem 1, the $(\mathcal{C}_{k},4)$-fold channel reads

$\Phi^{(4)}_{\mathcal{C}_{k}}(\mathcal{O})=\sum_{\pi,\sigma\in\mathcal{S}_{4}}\left[\left({(\Xi^{k})_{\pi\sigma}Q+\Gamma_{\pi\sigma}^{(k)}}\right)c_{\pi}(\mathcal{O})+\delta_{\pi\sigma}b_{\pi}(\mathcal{O})\right]T_{\sigma}$
(80)

First of all let us write this equation in matrix form for the coefficients;
define $\mathbf{T}$ a vector with components the permutation operators
$T_{\sigma}$, $\mathbf{c}$ the vector with components $c_{\pi}(\mathcal{O})$
and similarly for $\mathbf{b}$, then Eq.(80) becomes

$\Phi^{(4)}_{\mathcal{C}_{k}}(\mathcal{O})=(\Xi^{k}\cdot\mathbf{c},\mathbf{T})Q+(\Gamma^{(k)}\cdot\mathbf{c}+\mathbf{b},\mathbf{T})$
(81)

where the $\cdot$ stands for the row by column product and $(\cdot,\cdot)$ for
the usual scalar product between lists. Recall that for the Unitary group the
$(\mathcal{U}(d),4)$-fold channel reads

$\Phi^{(4)}_{\mathcal{U}(d)}(\mathcal{O})=(W\cdot\mathbf{t},\mathbf{T})$ (82)

where $W$ is the matrix with components the Unitary group Weingarten
functions, cfr Eq.(61). In the following we prove that the first piece in
Eq.(81) vanishes in the limit $k\rightarrow\infty$, while the second returns
the matrix $W$.

######  Lemma 4.

For
$K=P_{\theta}\equiv\left|{0}\right\rangle\left\langle{0}\right|+e^{i\theta}\left|{1}\right\rangle\left\langle{1}\right|$,
the matrix $\Xi$, defined in Eq.(10) has the following properties

  * •

$\Xi$ is symmetric;

  * •

$\Xi$ has rank 6;

  * •

the eigenvalues read

$\displaystyle\lambda^{(\pm)}$ $\displaystyle=$ $\displaystyle
f^{\pm}_{\theta},\quad\mu(\lambda^{\pm})=1$ $\displaystyle\lambda^{av}$
$\displaystyle=$
$\displaystyle\frac{f^{+}_{\theta}+f^{-}_{\theta}}{2},\quad\mu(\lambda^{av})=4$
(83)

where $\mu(\lambda)$ stands for the algebraic multiplicity of the eigenvalue
$\lambda$ and

$\displaystyle f^{\pm}_{\theta}$ $\displaystyle=$
$\displaystyle\frac{7d^{2}\pm 3d+d(d\mp
3)\cos(4\theta)-8}{8(d^{2}-1)}<1,\quad\forall\,\theta\neq\pm\frac{\pi}{2}$
(84) $\displaystyle f_{\theta}^{\pm}$ $\displaystyle=$ $\displaystyle
1,\quad\theta=\pm\frac{\pi}{2}$

  * •

the maximum eigenvalue is $f^{+}_{\theta}$.

The proof comes from direct calculation of the $24\times 24$ matrix $\Xi$ with
$K=P_{\theta}$. ∎

Since all the eigenvalues of $\Xi$ are less than $1$,

$\lim_{k\rightarrow\infty}(\Xi^{k})_{\pi\sigma}=0,\quad\text{for all
$\pi,\sigma$}$ (85)

and

$\sum_{i=0}^{\infty}\Xi^{i}=(1-\Xi)^{-1}$ (86)

thus $\Gamma^{(\infty)}=\Lambda(1-\Xi)^{-1}$. Defining the vector $\mathbf{q}$
having components ${\operatorname{tr}}(\mathcal{O}QT_{\sigma})$ and the vector
$\mathbf{t}$ having components ${\operatorname{tr}}(\mathcal{O}T_{\sigma})$,
from Eq.(13) and Eq.(14) we note that

$\displaystyle\mathbf{c}$ $\displaystyle=$
$\displaystyle(W^{+}+W^{-})\cdot\mathbf{q}-W^{-}\cdot\mathbf{t}$
$\displaystyle\mathbf{b}$ $\displaystyle=$ $\displaystyle
W^{-}\cdot\mathbf{t}-W^{-}\cdot\mathbf{q}$ (87)

where $W^{\pm}$ are the matrices with components the generalized Weingarten
functions for the Clifford group, cfr. (54). Therefore taking the limit
$k\rightarrow\infty$ in Eq.(81)

$\lim_{k\rightarrow\infty}\Phi^{(4)}_{\mathcal{C},k}(\mathcal{O})=\left([\Lambda(1-\Xi)^{-1}(W^{+}+W^{-})-W^{-}]\cdot\mathbf{q},\mathbf{T}\right)+\left({[W^{-}-\Lambda(1-\Xi)^{-1}W^{-}]\cdot\mathbf{t},\mathbf{T}}\right)$
(88)

It is straightforward to check that

$W^{-}-\Lambda(1-\Xi)^{-1}W^{-}=W$ (89)

Then, the vector $\mathbf{q}$ is in kernel of the matrix
$\zeta=\Lambda(1-\Xi)^{-1}(W^{+}+W^{-})-W^{-}$, namely
$\operatorname{ker}(\zeta)$; indeed

$\operatorname{ker}(\zeta)=\mathrm{span}\left({{\mathbf{e}^{(\alpha)}\,|\,\alpha=1,\dots,6}}\right)$
(90)

where the non null components of these six vectors read

$\displaystyle e_{(e)}^{(1)}$ $\displaystyle=$ $\displaystyle
e_{(12)(34)}^{(1)}=e_{(13)(24)}^{(1)}=e_{(14)(23)}^{(1)}$ $\displaystyle
e_{(13)}^{(2)}$ $\displaystyle=$ $\displaystyle
e_{(24)}^{(2)}=e_{(1432)}^{(2)}=e_{(1234)}^{(2)}$ $\displaystyle
e_{(14)}^{(3)}$ $\displaystyle=$ $\displaystyle
e_{(23)}^{(3)}=e_{(1342)}^{(3)}=e_{(1243)}^{(3)}$ $\displaystyle
e_{(12)}^{(4)}$ $\displaystyle=$ $\displaystyle
e_{(34)}^{(4)}=e_{(1324)}^{(4)}=e_{(1423)}^{(4)}$ $\displaystyle
e_{(132)}^{(5)}$ $\displaystyle=$ $\displaystyle
e_{(124)}^{(5)}=e_{(143)}^{(5)}=e_{(234)}^{(5)}$ $\displaystyle
e_{(123)}^{(6)}$ $\displaystyle=$ $\displaystyle
e_{(142)}^{(6)}=e_{(134)}^{(6)}=e_{(243)}^{(6)}$ (91)

because of Lemma 5 it is clear that $\mathbf{q}\in\operatorname{ker}(\zeta)$,
which proves the theorem. ∎

###  B.3 Proof of Application 3

We will make use of Theorem 1

$\Phi^{(4)}_{\mathcal{C}_{k}}(\psi^{\otimes
4})=\sum_{\pi,\sigma\in\mathcal{S}_{4}}\left[\left({(\Xi^{k})_{\pi\sigma}Q+\Gamma_{\pi\sigma}^{(k)}}\right)c_{\pi}(\psi^{\otimes
4})+\delta_{\pi\sigma}b_{\pi}(\psi^{\otimes 4})\right]T_{\sigma}$ (92)

Let us first compute the term
$\sum_{\pi,\sigma\in\mathcal{S}_{4}}c_{\sigma}(\psi^{\otimes
4})(\Xi^{k})_{\pi\sigma}QT_{\pi}$; note that $[T_{\pi},Q]=0$. This is a fact
that will be repeatedly exploited in this proof. First we prove that
$c_{\sigma}=c$ independent from the specific permutation $\sigma$; from
Eq.(13) we have

$\displaystyle c_{\sigma}(\psi^{\otimes 4})$ $\displaystyle=$
$\displaystyle\sum_{\pi\in\mathcal{S}_{4}}[W^{+}_{\pi\sigma}{\operatorname{tr}}(\psi^{\otimes
4}QT_{\pi})-W^{-}_{\pi\sigma}{\operatorname{tr}}(\psi^{\otimes
4}Q^{\perp}T_{\pi})]=\sum_{\pi\in\mathcal{S}_{4}}W^{+}_{\pi\sigma}{\operatorname{tr}}(Q\psi^{\otimes
4})-W^{-}_{\pi\sigma}{\operatorname{tr}}(Q^{\perp}\psi^{\otimes 4})$ (93)
$\displaystyle=$
$\displaystyle\frac{1}{4!D^{+}}{\operatorname{tr}}(Q\psi^{\otimes
4})-\frac{1}{4!D^{-}}{\operatorname{tr}}(Q^{\perp}\psi^{\otimes 4})\equiv c$

where we used $T_{\pi}\psi^{\otimes 4}=\psi^{\otimes 4}$ for all $\pi$ and
$\sum_{\pi\in\mathcal{S}_{4}}W^{\pm}_{\pi\sigma}=(4!D^{\pm})^{-1}$. Then the
sum can be written as

$\displaystyle\sum_{\pi,\sigma\in\mathcal{S}_{4}}c_{\pi}(\psi^{\otimes
4})(\Xi^{k})_{\pi\sigma}QT_{\sigma}$ $\displaystyle=$ $\displaystyle
c\sum_{\pi,\sigma\in\mathcal{S}_{4}}(\Xi^{k})_{\pi\sigma}QT_{\sigma}=c\sum_{\pi,\sigma,\tau\in\mathcal{S}_{4}}\Xi_{\pi\tau}(\Xi^{k-1})_{\tau\sigma}QT_{\sigma}$
(94) $\displaystyle=$ $\displaystyle
c\sum_{\sigma,\tau\in\mathcal{S}_{4}}\left(\sum_{\pi}\Xi_{\pi\tau}\right)(\Xi^{k-1})_{\tau\sigma}T_{\sigma}Q$

let us prove that $\sum_{\pi\in\mathcal{S}_{4}}\Xi_{\pi\tau}$ does not depend
on $\tau$; from Eq.(10) it is easy to see that

$\sum_{\pi\in\mathcal{S}_{4}}\Xi_{\pi\tau}=\frac{1}{D^{+}}{\operatorname{tr}}(\Pi_{\text{sym}}^{(4)}K^{\otimes
4}QK^{{\dagger}\otimes
4}Q)-\frac{1}{D^{-}}{\operatorname{tr}}(\Pi_{\text{sym}}^{(4)}K^{\otimes
4}QK^{{\dagger}\otimes
4}Q^{\perp})=\frac{c_{Q}}{D^{+}}-\frac{c_{QQ^{\perp}}}{D^{-}}$ (95)

where we have used
$\sum_{\pi\in\mathcal{S}_{4}}W^{\pm}_{\pi\sigma}=(4!D^{\pm})^{-1}$ and
$\Pi_{\text{sym}}^{(4)}T_{\tau}=\Pi_{\text{sym}}^{(4)}$ for any
$\tau\in\mathcal{S}_{4}$. The coefficients $c_{Q}$ and $c_{QQ^{\perp}}$ are to
be computed in a straightforward way; for the case $K=P_{\theta}$ they are
explicitly calculated in App. B.4. Since
$\sum_{\pi\in\mathcal{S}_{4}}\Xi_{\pi\tau}$ does not depend on $\tau$, the
decomposition introduced in the last equality of Eq. $\eqref{xidec}$ can be
reiterated $k$ times to obtain

$\displaystyle\sum_{\pi,\sigma\in\mathcal{S}_{4}}c_{\pi}(\psi^{\otimes
4})(\Xi^{k})_{\pi\sigma}QT_{\sigma}$ $\displaystyle=$ $\displaystyle
c\left({\frac{c_{Q}}{D^{+}}-\frac{c_{QQ^{\perp}}}{D^{-}}}\right)^{k}\sum_{\sigma\in\mathcal{S}_{4}}T_{\sigma}Q$
(96) $\displaystyle=$
$\displaystyle\left({\frac{{\operatorname{tr}}(Q\psi^{\otimes
4})}{D^{+}}-\frac{{\operatorname{tr}}(\psi^{\otimes
4}Q^{\perp})}{D^{-}}}\right)\left({\frac{c_{Q}}{D^{+}}-\frac{c_{QQ^{\perp}}}{D^{-}}}\right)^{k}\Pi_{\text{sym}}^{(4)}Q$

Now we compute the term
$\sum_{\pi,\sigma\in\mathcal{S}_{4}}\Gamma^{(k)}_{\pi\sigma}c_{\pi}(\psi^{\otimes
4})T_{\sigma}$ where $\Gamma^{(k)}_{\pi\sigma}$ is defined in Theorem 1; since
$c_{\pi}(\psi^{\otimes 4})$ is independent from the permutation $\pi$ we can
write

$\sum_{\pi,\sigma\in\mathcal{S}_{4}}\Gamma^{(k)}_{\pi\sigma}c_{\pi}(\psi^{\otimes
4})T_{\sigma}=c\sum_{\pi,\sigma\in\mathcal{S}_{4}}\Gamma^{(k)}_{\pi\sigma}T_{\sigma}=c\sum_{\pi,\sigma,\tau\in\mathcal{S}_{4}}\Lambda_{\pi\tau}\left(\sum_{i=0}^{k-1}(\Xi^{i})_{\tau\sigma}\right)T_{\sigma}$
(97)

It is easy to see
$\sum_{\pi\in\mathcal{S}_{4}}\Lambda_{\pi\tau}=c_{QQ^{\perp}}/D^{-}$ does not
depend on $\tau$; from this fact, we can use the same technique used above to
compute
$\sum_{\tau\in\mathcal{S}_{4}}\left(\sum_{i=0}^{k-1}(\Xi^{i})_{\tau\sigma}\right)$
and finally obtain

$\sum_{\pi,\sigma\in\mathcal{S}_{4}}\Gamma^{(k)}_{\pi\sigma}c_{\pi}(\psi^{\otimes
4})T_{\sigma}=\frac{{\operatorname{tr}}(\psi^{\otimes
4}Q^{\perp})}{D^{-}}+\frac{c_{QQ^{\perp}}}{D^{-}}\left(\frac{{\operatorname{tr}}(Q\psi^{\otimes
4})}{D^{+}}-\frac{{\operatorname{tr}}(Q^{\perp}\psi^{\otimes
4})}{D^{-}}\right)\sum_{i=0}^{k-1}\left(\frac{c_{Q}}{D^{+}}-\frac{c_{QQ^{\perp}}}{D^{-}}\right)^{i}\Pi_{\text{sym}}^{(4)}$
(98)

The last term we need to evaluate is $\sum_{\pi}b_{\pi}(\psi^{\otimes
4})T_{\pi}$; as before, let us prove that $b_{\pi}(\psi^{\otimes 4})$ does not
depend on $\pi$

$b_{\pi}(\psi^{\otimes
4})=\sum_{\sigma\in\mathcal{S}_{4}}W_{\pi\sigma}^{-}{\operatorname{tr}}\left({\psi^{\otimes
4}Q^{\perp}T_{\sigma}}\right)=\sum_{\sigma\in\mathcal{S}_{4}}W_{\pi\sigma}^{-}{\operatorname{tr}}\left({\psi^{\otimes
4}Q^{\perp}}\right)=\frac{1}{4!D^{-}}{\operatorname{tr}}({Q^{\perp}\psi^{\otimes
4}})$ (99)

then

$\sum_{\pi\in\mathcal{S}_{4}}b_{\pi}(\psi^{\otimes
4})T_{\pi}=\frac{1}{D^{-}}{\operatorname{tr}}(Q^{\perp}\psi^{\otimes
4})\frac{1}{4!}\sum_{\pi\in\mathcal{S}_{4}}T_{\pi}=\frac{1}{D^{-}}{\operatorname{tr}}(Q^{\perp}\psi^{\otimes
4})\Pi_{\text{sym}}^{(4)}$ (100)

Putting together Eqs. (96), (98) and (100) we obtain the final result in
Eq.(26). ∎

###  B.4 Proof of Application 4

In this section we evaluate $c_{Q}={\operatorname{tr}}(K_{i_{j}}^{\otimes
4}QK_{i_{j}}^{{\dagger}\otimes 4}Q\Pi_{\text{sym}}^{(4)})$ for
$K=P_{\theta}\equiv\left|{0}\right\rangle\left\langle{0}\right|+e^{i\theta}\left|{1}\right\rangle\left\langle{1}\right|$.
As pointed out in Lemma 6, the position of the operator $K_{i_{j}}$ does not
affect the calculations, so in the following we analyze the case in which the
operator $K_{i}$ acts on the first qubit $i_{1}$. The term $c_{Q}$ can be
rewritten as

${\operatorname{tr}}(K_{i_{1}}^{\otimes 4}QK_{i_{1}}^{{\dagger}\otimes
4}Q\Pi_{\text{sym}}^{(4)})={\operatorname{tr}}(R^{-1}RK^{\otimes
4}_{i_{1}}R^{-1}RQR^{-1}RK_{i_{1}}^{{\dagger}\otimes
4}R^{-1}RQR^{-1}R\Pi_{\text{sym}}^{(4)})$ (101)

where $R\in\mathcal{S}_{4N}$ is a permutation operator whose action on a
tensor product basis element is

$R\left|{i_{1}\ldots i_{N}}\right\rangle^{\otimes
4}\equiv\left|{i_{1}}\right\rangle^{\otimes 4}\left|{i_{2}\ldots
i_{N}}\right\rangle^{\otimes 4}$ (102)

The adjoint action of the permutation $R$ allows us to rewrite the operator
$Q$ as

$RQR^{-1}=\frac{1}{4}(Q_{I}+Q_{X}+Q_{Y}+Q_{Z})$ (103)

where $X,Y,Z,I$ are single qubit Pauli matrices and for example $Q_{X}$ reads

$Q_{X}=\frac{1}{(d/2)^{2}}\sum_{P\in\mathcal{P}(d/2)}X^{\otimes 4}\otimes
P^{\otimes 4}=X^{\otimes 4}\otimes Q_{d/2}$ (104)

and $Q_{d/2}=(d/2)^{-2}\sum_{P\in\mathcal{P}(d/2)}P^{\otimes 4}$. Similarly
the adjoint action of $R$ on $K^{\otimes 4}$

$RK^{\otimes 4}_{i_{1}}R^{-1}=K^{\otimes 4}\otimes({\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}_{2}\otimes\dots\otimes{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}_{N})^{\otimes 4}$
(105)

acting on the first qubit element of each copy of $\mathcal{H}$ it acts on the
first four elements of $RQR^{-1}$. It is simple to see that the adjoint action
of $R$ on the symmetric projector $\Pi_{\text{sym}}^{(4)}$ give us again the
symmetric projector on the new permuted space and we denote it with
$\tilde{\Pi}_{\text{sym}}^{(4)}$. The term $c_{Q}$ can be rewritten as

$\displaystyle{\operatorname{tr}}(K_{i_{1}}^{\otimes
4}QK_{i_{1}}^{{\dagger}\otimes 4}Q\tilde{\Pi}_{\text{sym}}^{(4)})$
$\displaystyle=$ $\displaystyle\frac{1}{16}{\operatorname{tr}}(RK^{\otimes
4}_{i_{1}}R^{-1}(Q_{I}+Q_{X}+Q_{Y}+Q_{Z})RK^{{\dagger}\otimes
4}_{i_{1}}R^{-1}(Q_{I}+Q_{X}+Q_{Y}+Q_{Z})\tilde{\Pi}_{\text{sym}}^{(4)})$
(106) $\displaystyle=$
$\displaystyle\frac{1}{16}{\operatorname{tr}}[(Q_{I}+Q_{Z})(Q_{I}+Q_{X}+Q_{Y}+Q_{Z})\tilde{\Pi}_{\text{sym}}^{(4)}]$
$\displaystyle+$ $\displaystyle{\operatorname{tr}}[K_{i_{1}}^{\otimes
4}(Q_{X}+Q_{Y})K_{i_{1}}^{{\dagger}\otimes
4}(Q_{I}+Q_{X}+Q_{Y}+Q_{Z})\tilde{\Pi}_{\text{sym}}^{(4)}]$

where we used the fact that $[K,I]=[K,Z]=0$; then the first term of
Eq.$\eqref{kacqdec}$ reads

${\operatorname{tr}}[(Q_{I}+Q_{Z})(Q_{I}+Q_{X}+Q_{Y}+Q_{Z})\tilde{\Pi}_{\text{sym}}^{(4)}]=8{\operatorname{tr}}(Q\tilde{\Pi}_{\text{sym}}^{(4)})=8D^{+}.$
(107)

We focus now on the second term of Eq.$\eqref{kacqdec}$

$\displaystyle{\operatorname{tr}}[K_{i_{1}}^{\otimes
4}(Q_{X}+Q_{Y})K_{i_{1}}^{{\dagger}\otimes
4}(Q_{I}+Q_{X}+Q_{Y}+Q_{Z})\tilde{\Pi}_{\text{sym}}^{(4)}]$ $\displaystyle=$
$\displaystyle{\operatorname{tr}}[(Q_{KXK^{{\dagger}}}+Q_{KYK^{{\dagger}}})(Q_{I}+Q_{X}+Q_{Y}+Q_{Z})\tilde{\Pi}_{\text{sym}}^{(4)}]$
(108) $\displaystyle=$ $\displaystyle
2{\operatorname{tr}}[(Q_{KXK^{{\dagger}}}+Q_{KXK^{{\dagger}}X}+Q_{KXK^{{\dagger}}Y}+Q_{KYK^{{\dagger}}})\tilde{\Pi}_{\text{sym}}^{(4)}]$
$\displaystyle=$ $\displaystyle
2{\operatorname{tr}}(\tilde{Q}\tilde{\Pi}_{\text{sym}}^{(4)})=\frac{1}{12}\sum_{\sigma\in\mathcal{S}_{4}}{\operatorname{tr}}(\tilde{Q}\tilde{T}_{\sigma})$

where denoted $\tilde{T}_{\sigma}=RT_{\sigma}R^{-1}$ and defined

$\tilde{Q}\equiv(Q_{KXK^{{\dagger}}}+Q_{KXK^{{\dagger}}X}+Q_{KXK^{{\dagger}}Y}+Q_{KYK^{{\dagger}}})$
(109)

and

$\displaystyle Q_{KXK^{{\dagger}}X}$ $\displaystyle=$
$\displaystyle(KXK^{{\dagger}}X)^{\otimes 4}\otimes Q_{d/2},$ (110)
$\displaystyle Q_{KXK^{{\dagger}}Y}$ $\displaystyle=$
$\displaystyle(KXK^{{\dagger}}Y)^{\otimes 4}\otimes Q_{d/2},$ $\displaystyle
Q_{KXK^{{\dagger}}}$ $\displaystyle=$ $\displaystyle(KXK^{{\dagger}})^{\otimes
4}\otimes Q_{d/2}$ $\displaystyle Q_{KYK^{{\dagger}}}$ $\displaystyle=$
$\displaystyle(KYK^{{\dagger}})^{\otimes 4}\otimes Q_{d/2}$

Therefore

$c_{Q}={\operatorname{tr}}(K^{\otimes 4}QK^{{\dagger}\otimes
4}Q\Pi_{\text{sym}}^{(4)})=\frac{D^{+}}{2}+\frac{\sum_{\sigma\in\mathcal{S}_{4}}{\operatorname{tr}}(\tilde{Q}\tilde{T}_{\sigma})}{192}$
(111)

In a similar fashion to what we have done in Sec. C.2 it is possible to see
that $\tilde{T}_{\sigma}=T_{\sigma}^{(2)}\otimes T_{\sigma}^{(d/2)}$ where
$T_{\sigma}^{(2)}\in\mathcal{B}((\mathbb{C}^{2})^{\otimes 4})$ and
$T_{\sigma}^{(d/2)}\in\mathcal{B}((\mathbb{C}^{2\otimes(N-1)})^{\otimes 4})$;
thus, the following equality holds

$\displaystyle{\operatorname{tr}}[(Q_{KXK^{{\dagger}}}+Q_{KXK^{{\dagger}}X}+Q_{KXK^{{\dagger}}Y}+Q_{KYK^{{\dagger}}})\tilde{\Pi}_{\text{sym}}^{(4)}]=$
(112)
$\displaystyle\frac{1}{12}\sum_{\sigma\in\mathcal{S}_{4}}{\operatorname{tr}}[T_{\sigma}^{(2)}((KXK^{{\dagger}})^{\otimes
4}+(KYK^{{\dagger}})^{\otimes 4}-(KXK^{{\dagger}}X)^{\otimes
4}-(KXYK^{{\dagger}}Y)^{\otimes
4})]{\operatorname{tr}}(Q_{d/2}T_{\sigma}^{(d/2)})$

It is easy to see that

$\displaystyle(KXK^{{\dagger}})^{\otimes 4}=\begin{pmatrix}0&e^{-i\theta}\\\
e^{i\theta}&0\end{pmatrix}^{\otimes 4},$
$\displaystyle\quad(KYK^{{\dagger}})^{\otimes
4}=\begin{pmatrix}0&-ie^{-i\theta}\\\ ie^{i\theta}&0\end{pmatrix}^{\otimes
4},$ (113) $\displaystyle(KXK^{{\dagger}}X)^{\otimes
4}=\begin{pmatrix}e^{-i\theta}&0\\\ 0&e^{i\theta}\end{pmatrix}^{\otimes 4},$
$\displaystyle\quad(KXK^{{\dagger}}Y)^{\otimes
4}=\begin{pmatrix}ie^{-i\theta}&0\\\ 0&-ie^{i\theta}\end{pmatrix}^{\otimes
4},$

With all the previous consideration we are now ready to compute the
coefficients

$\displaystyle 1\times{\operatorname{tr}}(\tilde{Q})$ $\displaystyle=$
$\displaystyle
16(\cos^{4}\theta+\sin^{4}\theta){\operatorname{tr}}(Q_{d/2})=4(\cos^{4}\theta+\sin^{4}\theta)d^{2}$
$\displaystyle 6\times{\operatorname{tr}}(T_{(ij)}\tilde{Q})$ $\displaystyle=$
$\displaystyle
8\cos^{2}(2\theta){\operatorname{tr}}(T_{(ij)}Q_{d/2})=4d\cos^{2}(2\theta)$
$\displaystyle 8\times{\operatorname{tr}}(T_{(ijk)}\tilde{Q})$
$\displaystyle=$ $\displaystyle 4\cos(4\theta)$ (114) $\displaystyle
6\times{\operatorname{tr}}(T_{ijkl}\tilde{Q})$ $\displaystyle=$ $\displaystyle
8\cos^{2}(2\theta){\operatorname{tr}}(T_{(ijkl)}Q_{d/2})=4d\cos^{2}(2\theta)$
$\displaystyle 3\times{\operatorname{tr}}(T_{(ij)(kl)}\tilde{Q})$
$\displaystyle=$ $\displaystyle
4(3+\cos(4\theta)){\operatorname{tr}}(T_{(ij)(kl)}Q_{d/2})=d^{2}(3+\cos(4\theta))$

Thus
$\frac{1}{12}\sum_{\sigma\in\mathcal{S}_{4}}{\operatorname{tr}}(\tilde{Q}\tilde{T}_{\sigma})=\frac{4(d+2)(3d+(d+4)\cos(4\theta))}{12}$
and

$\displaystyle c_{Q}$ $\displaystyle=$
$\displaystyle{\operatorname{tr}}(K_{i_{1}}^{\otimes
4}QK_{i_{1}}^{{\dagger}\otimes
4}Q\Pi_{\text{sym}}^{(4)})=\frac{d^{2}+3d+2}{12}+\frac{(d+2)(3d+(d+4)\cos(4\theta))}{48}$
$\displaystyle=$ $\displaystyle\frac{(d+2)((d+4)\cos(4\theta)+7d+4)}{48}$
$\displaystyle c_{QQ^{\perp}}$ $\displaystyle=$
$\displaystyle{\operatorname{tr}}(K_{i_{1}}^{\otimes
4}QK_{i_{1}}^{{\dagger}\otimes
4}Q^{\perp}\Pi_{\text{sym}}^{(4)})={\operatorname{tr}}(Q\tilde{\Pi}_{\text{sym}}^{(4)})-c_{Q}=\frac{(d+4)(d+2)}{24}\sin^{2}(2\theta)$
(116)

Therefore

$\displaystyle a_{k}$ $\displaystyle=$
$\displaystyle\frac{24(f_{\theta}^{-})^{k}}{(d^{2}-1)(d+2)(d+4)}\left(\frac{d(d+3)}{4}{\operatorname{tr}}(\psi^{\otimes
4}Q)-1\right)$ (117) $\displaystyle b_{k}$ $\displaystyle=$
$\displaystyle\frac{1}{D_{\text{sym}}}+\frac{24}{(d^{2}-1)(d+2)(d+4)}(f_{\theta}^{-})^{k}\left(\frac{4}{d(d+3)}-{\operatorname{tr}}(\psi^{\otimes
4}Q)\right)$ (118)

where $f_{\theta}^{-}$ is, cfr. (84)

$f_{\theta}^{-}\equiv\frac{7d^{2}-3d+d(d+3)\cos(4\theta)-8}{8(d^{2}-1)}=\frac{7+\cos(4\theta)}{8}+\Theta(d^{-1})$
(119)

It is possible to calculate the extreme points of $f_{\theta}$. the maximum is
$f_{\theta}=1$ for $\theta=\pi/2$, while the minimum is
$f_{\theta}\approx\frac{3}{4}$ for $\theta=\pi/4$.

###  B.5 Proof of Lemma 1

The average square purity for the $k$-doped Clifford circuit can be written
as[20]

$\left\langle{\operatorname{Pur}^{2}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{C}_{k}}={\operatorname{tr}}\left(T^{(A)}_{(12)(34)}\left\langle{\psi^{\otimes
4}_{U}}\right\rangle_{U\in\mathcal{C}_{k}}\right)$ (120)

Then, substituting Eq.(26)

$\left\langle{\operatorname{Pur}^{2}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{C}_{k}}=a_{k}{\operatorname{tr}}(Q\Pi_{\text{sym}}^{(4)}T_{(12)(34)}^{(A)})+b_{k}{\operatorname{tr}}(\Pi_{\text{sym}}^{(4)}T_{(12)(34)}^{(A)})$
(121)

where $a_{k}$ and $b_{k}$ are defined in Eq.(27). Recalling that
$Q=Q_{A}\otimes Q_{B}$ up to a rearrangement of the tensor product (cfr. App.
C.2), then $T_{\sigma}=T^{(A)}_{\sigma}\otimes T_{\sigma}^{(B)}$ and
$\Pi_{\text{sym}}^{(4)}=1/24\sum_{\sigma\in\mathcal{S}_{4}}T_{\sigma}$, we
write

$\displaystyle{\operatorname{tr}}(Q\Pi_{\text{sym}}^{(4)}T_{(12)(34)}^{(A)})$
$\displaystyle=$
$\displaystyle\frac{1}{24}\sum_{\sigma\in\mathcal{S}_{4}}{\operatorname{tr}}(Q_{A}T_{\sigma}^{(A)}T_{(12)(34)}^{(A)}){\operatorname{tr}}(Q_{B}T_{\sigma}^{(B)})$
(122)
$\displaystyle{\operatorname{tr}}(\Pi_{\text{sym}}^{(4)}T_{(12)(34)}^{(A)})$
$\displaystyle=$
$\displaystyle\frac{1}{24}\sum_{\sigma\in\mathcal{S}_{4}}{\operatorname{tr}}(T_{\sigma}^{(A)}T_{(12)(34)}^{(A)}){\operatorname{tr}}(T_{\sigma}^{(B)})$
(123)

after some long but trivial algebra one gets, for the case
$d_{A}=d_{B}=\sqrt{d}$ and
$\psi=\left|{0}\right\rangle\left\langle{0}\right|^{\otimes N}$

$\displaystyle\left\langle{\operatorname{Pur}^{2}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{C}_{k}}$
$\displaystyle=$
$\displaystyle\frac{2(2d^{2}+9d+1)+(d^{2}-2d+1)(f^{-}_{\theta})^{k}}{(d+1)(d+2)(d+3)}$
(124)
$\displaystyle\left\langle{\operatorname{Pur}^{2}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{U}(d)}$
$\displaystyle=$ $\displaystyle\frac{4d^{2}+18d+2}{(d+1)(d+2)(d+3)}$ (125)

and thus, by computing
$\left\langle{\operatorname{Pur}^{2}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{C}_{k}}-\left\langle{\operatorname{Pur}(\psi_{U})_{A}}\right\rangle_{U\in\mathcal{U}(d)}^{2}$
one finds Eq.(41). ∎

##  Appendix C Other Proofs

###  C.1 Notes on Pauli operators

The Pauli operators on $\mathbb{C}^{2\otimes N}$ are formed by all Pauli
strings

$P=p_{1}\otimes p_{2}\otimes\cdots\otimes p_{N}$ (126)

where $p_{i}\in\\{I,X,Y,Z\\}$ are usual Pauli matrices on $\mathbb{C}^{2}$.
They are unitary and hermitian operators. Moreover, the Pauli group forms a
$1$-design, i.e the $(\mathcal{P}(d),1)$-fold channel of the Pauli group
equals the $(\mathcal{U}(d),1)$-fold channel

$\Phi^{(1)}_{\mathcal{P}(d)}(\mathcal{O})\equiv\frac{1}{d^{2}}\sum_{P\in\mathcal{P}(d)}P\mathcal{O}P=\frac{{\operatorname{tr}}(\mathcal{O})}{d}$
(127)

Since Pauli operators commute or anticommute, we define for
$P_{1},P_{2}\in\mathcal{P}(2^{N})$

$P_{2}P_{1}P_{2}=K(P_{1},P_{2})P_{1}\quad
K(P_{1},P_{2}):=\frac{1}{d}{\operatorname{tr}}(P_{2}^{{\dagger}}P_{1}P_{2}P_{1})$
(128)

where $K(P_{1},P_{2})$ is either $1$ or $-1$; a useful rule for combining them

$K(P_{1},P_{2})K(P_{1},P_{3})=\frac{1}{d}K(P_{1},P_{2}P_{3})=\frac{1}{d^{2}}{\operatorname{tr}}((P_{2}P_{3})^{{\dagger}}P_{1}P_{2}P_{3}P_{1})$
(129)

where $P_{1},P_{2},P_{3}\in\mathcal{P}(2^{N})$. The above facts are sufficient
to prove the following lemma

######  Lemma 5.

Let $\mathcal{O}\in\mathcal{B}(\mathcal{H}^{\otimes 4})$ and let
$Q=d^{-2}\sum_{P\in\mathcal{P}(2^{N})}P^{\otimes 4}$, then the following
relations hold

$\displaystyle{\operatorname{tr}}(\mathcal{O}Q)$ $\displaystyle=$
$\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{(12)(34)})={\operatorname{tr}}(\mathcal{O}QT_{(13)(24)})={\operatorname{tr}}(\mathcal{O}QT_{(14)(23)})$
(130) $\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{(24)})$
$\displaystyle=$
$\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{(1432)})={\operatorname{tr}}(\mathcal{O}QT_{(13)})={\operatorname{tr}}(\mathcal{O}QT_{(1234)})$
(131) $\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{14})$ $\displaystyle=$
$\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{(23)})={\operatorname{tr}}(\mathcal{O}QT_{(1342)})={\operatorname{tr}}(\mathcal{O}QT_{(1243)})$
(132) $\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{(12)})$
$\displaystyle=$
$\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{(34)})={\operatorname{tr}}(\mathcal{O}QT_{(1324)})={\operatorname{tr}}(QT_{(1423)})$
(133) $\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{(132)})$
$\displaystyle=$
$\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{(234)})={\operatorname{tr}}(\mathcal{O}QT_{(124)})={\operatorname{tr}}(\mathcal{O}QT_{(143)})$
(134) $\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{(123)})$
$\displaystyle=$
$\displaystyle{\operatorname{tr}}(\mathcal{O}QT_{(142)})={\operatorname{tr}}(\mathcal{O}QT_{(243)})={\operatorname{tr}}(\mathcal{O}QT_{(134)})$
(135)

###### Proof.

In order to prove the above relationship we need the expansion of
$\mathcal{O}$ in Pauli operators

$\mathcal{O}=\sum_{\begin{subarray}{c}P_{1},P_{2}\in\mathcal{P}(2^{N})\\\
P_{3},P_{4}\in\mathcal{P}(2^{N})\end{subarray}}={\operatorname{tr}}(\mathcal{O}P_{1}\otimes
P_{2}\otimes P_{3}\otimes P_{4})P_{1}\otimes P_{2}\otimes P_{3}\otimes P_{4}$
(136)

At this point we can prove the above relations for $\mathcal{O}\equiv
P_{1}\otimes P_{2}\otimes P_{3}\otimes P_{4}$ without loss of generality. We
won’t perform all the calculations, rather just some instructive examples. Let
us prove Eq.(130)

${\operatorname{tr}}[(P_{1}\otimes P_{2}\otimes P_{3}\otimes
P_{4})Q]=\frac{1}{d^{2}}\sum_{P\in\mathcal{P}(2^{N})}{\operatorname{tr}}(P_{1}P){\operatorname{tr}}(P_{2}P){\operatorname{tr}}(P_{3}P){\operatorname{tr}}(P_{4}P)=d^{2}\sum_{P\in\mathcal{P}(2^{N})}\delta_{PP_{1}}\delta_{PP_{2}}\delta_{PP_{3}}\delta_{PP_{4}}=d^{2}\delta_{P_{1}P_{2}P_{3}P_{4}}$
(137)

the second one

$\displaystyle{\operatorname{tr}}[(P_{1}\otimes P_{2}\otimes P_{3}\otimes
P_{4})QT_{(12)(34)}]$ $\displaystyle=$ $\displaystyle
d^{-2}\sum_{P\in\mathcal{P}(2^{N})}{\operatorname{tr}}(P_{1}PP_{2}P){\operatorname{tr}}(P_{3}PP_{4}P)$
$\displaystyle=$
$\displaystyle\frac{1}{d^{2}}\sum_{P\in\mathcal{P}(2^{N})}d^{2}\delta_{P_{1}P_{2}}\delta_{P_{3}P_{4}}K(P,P_{4})K(P,P_{2})$
$\displaystyle=$
$\displaystyle\delta_{P_{1}P_{2}}\delta_{P_{3}P_{4}}\sum_{P\in\mathcal{P}(2^{N})}\frac{1}{d}{\operatorname{tr}}((P_{2}P_{4})^{\dagger}P(P_{3}P_{4})P)=\delta_{P_{1}P_{2}}\delta_{P_{2}P_{4}}{\operatorname{tr}}(P_{2}P_{4})^{2}$
$\displaystyle=$ $\displaystyle d^{2}\delta_{P_{1}P_{2}P_{3}P_{4}}$

the same procedure follows for $T_{(13)(24)}$ and $T_{(14)(23)}$. Let us prove
Eq.(133)

$\displaystyle{\operatorname{tr}}[(P_{1}\otimes P_{2}\otimes P_{3}\otimes
P_{4})QT_{(12)}]$ $\displaystyle=$
$\displaystyle\frac{1}{d^{2}}\sum_{P\in\mathcal{P}(2^{N})}{\operatorname{tr}}(P_{1}PP_{2}P){\operatorname{tr}}(P_{3}P){\operatorname{tr}}(P_{4}P)=\delta_{P_{3}P_{4}}{\operatorname{tr}}(P_{1}P_{3}P_{2}P_{3})$
(139) $\displaystyle=$ $\displaystyle
dK(P_{2},P_{3})\delta_{P_{3}P_{4}}\delta_{P_{1}P_{2}}$

the $4$-cycle

$\displaystyle{\operatorname{tr}}[(P_{1}\otimes P_{2}\otimes P_{3}\otimes
P_{4})QT_{(1423)}]$ $\displaystyle=$
$\displaystyle\frac{1}{d^{2}}\sum_{P\in\mathcal{P}(2^{N})}{\operatorname{tr}}(P_{1}PP_{3}PP_{2}PP_{4}P)=\frac{1}{d^{2}}\sum_{P\in\mathcal{P}(2^{N})}K(P,P_{4})K(P,P_{3}){\operatorname{tr}}(P_{1}P_{3}P_{2}P_{4})$
(140) $\displaystyle=$
$\displaystyle\frac{1}{d^{3}}\sum_{P\in\mathcal{P}(2^{N})}K(P,P_{4}P_{3}){\operatorname{tr}}(P_{1}P_{3}P_{2}P_{4})=d\delta_{P_{3}P_{4}}\delta_{P_{1}P_{2}}{\operatorname{tr}}(P_{1}P_{3}P_{2}P_{4})$
$\displaystyle=$ $\displaystyle
dK(P_{2},P_{3})\delta_{P_{1}P_{2}}\delta_{P_{3}P_{4}}$

the same calculations follow for $T_{(34)}$ and $T_{(1324)}$. ∎

###  C.2 $Q$ decomposition and traces

It is interesting to prove a useful property of the operator $Q$, that we
recall is defined as

$Q=\frac{1}{d^{2}}\sum_{P\in\mathcal{P}(2^{N})}P^{\otimes
4}=\frac{1}{d^{2}}\sum_{\sigma_{i_{1}},\ldots,\sigma_{i_{N}}}(\sigma_{i_{1}}\otimes\cdots\otimes\sigma_{i_{N}})^{\otimes
4}$ (141)

where $\sigma_{i_{j}}\in\mathcal{P}(2)$. It is possible to introduce a
permutation $S\in\mathcal{S}_{4N}$, whose action on a tensor product state is
defined as

$S(\left|{i_{1}\ldots i_{N}}\right\rangle^{\otimes
4})=\left|{i_{1}}\right\rangle^{\otimes
4}\cdots\left|{i_{N}}\right\rangle^{\otimes 4}$ (142)

The adjoint action of a permutation $S$ on $Q$ reads

$\displaystyle SQS^{-1}$ $\displaystyle=$
$\displaystyle\frac{1}{d^{2}}\sum_{\sigma_{i_{1}},\ldots,\sigma_{i_{N}}}S(\sigma_{i_{1}}\otimes\cdots\otimes\sigma_{i_{N}})^{\otimes
4}S^{-1}$ (143) $\displaystyle=$
$\displaystyle\left(\frac{1}{4}\right)^{N}\sum_{\sigma_{i_{1}},\ldots,\sigma_{i_{N}}}\sigma_{i_{1}}^{\otimes
4}\otimes\cdots\otimes\sigma_{i_{N}}^{\otimes 4}=Q_{2}^{\otimes N}$ (144)

where $Q_{2}=\sum_{\sigma\in\mathcal{P}(2)}\sigma^{\otimes 4}$. Then, let us
show the adjoint action of $S$ on a permutation operator between the
$4$-copies of $\mathcal{H}$. Let
$T_{\sigma}\in\mathcal{B}(\mathcal{H}^{\otimes 4})$ a permutation operator
between $4$ copies of $\mathcal{H}\equiv\mathbb{C}^{2\otimes N}$ corresponding
to $\sigma\in\mathcal{S}_{4}$; written in terms of bras and kets it reads

$T_{\sigma}=\sum_{\begin{subarray}{c}i_{1}\ldots i_{N}\\\ j_{1}\ldots
j_{N}\end{subarray}}\sum_{\begin{subarray}{c}k_{1}\ldots k_{N}\\\ l_{1}\ldots
l_{N}\end{subarray}}\left|{\sigma(i_{1})\ldots\sigma(i_{N})\sigma(j_{1})\ldots\sigma(j_{N})\sigma(k_{1})\ldots\sigma(k_{N})\sigma(l_{1})\ldots\sigma(l_{N})}\right\rangle\left\langle{i_{1}\dots
i_{N}j_{1}\dots j_{N}k_{1}\dots k_{N}l_{1}\dots l_{N}}\right|$ (145)

The adjoint action of $S$ reads

$ST_{\sigma}S^{-1}=\sum_{\begin{subarray}{c}i_{1}\ldots i_{N}\\\ j_{1}\ldots
j_{N}\end{subarray}}\sum_{\begin{subarray}{c}k_{1}\ldots k_{N}\\\ l_{1}\ldots
l_{N}\end{subarray}}\left|{\sigma(i_{1})\sigma(j_{1})\sigma(k_{1})\sigma(l_{1})}\right\rangle\left\langle{i_{1}j_{1}k_{1}l_{1}}\right|\otimes\cdots\otimes\left|{\sigma(i_{N})\sigma(j_{N})\sigma(k_{N})\sigma(l_{N})}\right\rangle\left\langle{i_{N}j_{N}k_{N}l_{N}}\right|$
(146)

It is clear that we can write

$ST_{\sigma}S^{-1}=T_{\sigma}^{(2)\otimes N}$ (147)

where we are denoting
$T_{\sigma}^{(2)}=\sum_{i,j,k,l}\left|{\sigma(i)\sigma(j)\sigma(k)\sigma(l)}\right\rangle\left\langle{ijkl}\right|\in\mathcal{B}(\mathbb{C}^{2})$
which is a permutation operator between $4$ copies of a single qubit Hilbert
space $\mathbb{C}^{2}$.

######  Lemma 6.

Let $K_{i}$ and $K_{j}$ two identical single qubit gates with support on a
different qubit, $i$ and $j$ respectively. Let $T_{\sigma}$ be a permutation
operator between the $4$-copies of $\mathcal{H}$; the following equality holds

${\operatorname{tr}}(T_{\sigma}QK_{i}^{\otimes 4}QK_{i}^{{\dagger}\otimes
4})={\operatorname{tr}}(T_{\sigma}QK_{j}^{\otimes 4}QK_{j}^{{\dagger}\otimes
4})$ (148)

###### Proof.

First of all

$K_{i}^{\otimes 4}=({\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}_{1}\otimes\dots\otimes{\mathchoice{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}_{i-1}\otimes K\otimes{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm
1\mskip-5.0mul}}_{i+1}\otimes\dots\otimes{\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}_{N})^{\otimes 4}$
(149)

Acting adjointly with the permutation operator $S\in\mathcal{S}_{4N}$, defined
in Eq.(142) on $K_{i}^{\otimes 4}$ we have

$SK_{i}^{\otimes 4}S^{-1}=({\mathchoice{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.0mul}{\rm 1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}_{1}^{\otimes
4}\otimes\dots\otimes{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}_{i-1}^{\otimes 4}\otimes K^{\otimes
4}\otimes{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}_{i+1}^{\otimes
4}\otimes\dots\otimes{\mathchoice{\rm 1\mskip-4.0mul}{\rm 1\mskip-4.0mul}{\rm
1\mskip-4.5mul}{\rm 1\mskip-5.0mul}}_{N}^{\otimes 4})$ (150)

Then from the above equality and from Eq.(144) and Eq.(147) we have

$\displaystyle{\operatorname{tr}}(T_{\sigma}QK_{i}^{\otimes
4}QK_{i}^{{\dagger}\otimes 4})$ $\displaystyle=$
$\displaystyle{\operatorname{tr}}(T_{\sigma}^{(2)\otimes N}Q_{2}^{\otimes
N}(SK_{i}^{\otimes 4}S^{-1})Q_{2}^{\otimes N}(SK_{i}^{{\dagger}\otimes
4}S^{-1}))$ $\displaystyle=$
$\displaystyle{\operatorname{tr}}(T_{\sigma}^{(2)}Q_{2}KQ_{2}K^{{\dagger}}){\operatorname{tr}}(T_{\sigma}^{(2)\otimes(N-1)}Q_{2}^{\otimes(N-1)})$

where we used the fact that $(Q_{2}^{\otimes N-1})^{2}=Q_{2}^{\otimes N-1}$.
From the above relation it’s clear that the position of the qubit on which $K$
applies does not play any particular role. ∎

######  Application 5.

Let $\psi=\otimes_{i}\psi_{i}$ a completely factorized random product state on
$\mathbb{C}^{2\otimes N}$. Then

${\operatorname{tr}}(\psi^{\otimes 4}Q)=d^{-1-(\log_{2}5-2)}$ (152)

###### Proof.

Let us calculate ${\operatorname{tr}}(Q\psi^{\otimes 4})$ in the case
$\psi=\left|{0}\right\rangle\left\langle{0}\right|^{\otimes N}$. As proven in
Sec. C.2

$SQS^{-1}=(Q_{2})^{\otimes N}$ (153)

where $S$ is a permutation operator defined in Eq.(142). Here $Q_{2}$ reads

$Q_{2}=\frac{1}{4}(I+X+Y+Z)$ (154)

therefore

${\operatorname{tr}}(Q\psi^{\otimes 4})=\langle
0|Q_{2}|0\rangle^{N}=\frac{1}{2^{N}}=d^{-1}$ (155)

Now let us average ${\operatorname{tr}}(\psi^{\otimes 4}Q)$ with the local-
qubit Haar average. Let $\psi_{loc}^{\otimes 4}$ be

$\psi_{loc}^{\otimes
4}=\int\prod_{i=1}^{N}{\operatorname{d}}U_{i}\left(\bigotimes_{i=1}^{N}U_{i}\psi_{i}U_{i}^{{\dagger}}\right)^{\otimes
4}$ (156)

where $\operatorname{supp}(U_{i})=\mathbb{C}^{2}$ for any $i$. Using the Haar
average formulas displayed in Sec. A the adjoint action of $S$ on
$\psi_{loc}^{\otimes 4}$, defined in Eq.(142), reads

$S\psi_{loc}^{\otimes
4}S^{-1}=\left(\frac{\Pi_{\text{sym}}^{(4)}}{D_{\text{sym}}}\right)^{\otimes
N}$ (157)

where $\text{supp}(\Pi_{\text{sym}}^{(4)})=\mathbb{C}^{2}$ and
$D_{\text{sym}}^{(4)}=(2\cdot 3\cdot 4\cdot 5)/24$. Therefore
${\operatorname{tr}}(\psi_{loc}^{\otimes 4}Q)$ is

${\operatorname{tr}}(\psi^{\otimes
4}Q)={\operatorname{tr}}\left(\left(\frac{\Pi_{\text{sym}}^{(4)}}{D_{\text{sym}}}\right)^{\otimes
N}Q_{2}^{\otimes
N}\right)=5^{-N}({\operatorname{tr}}(\Pi_{\text{sym}}^{(4)}Q_{2}))^{N}=\left(\frac{2}{5}\right)^{N}=d^{-1-(\log_{2}5-2)}$
(158)

∎