# Entanglement of random hypergraph states

You Zhou<EMAIL_ADDRESS>Key Laboratory for Information Science of
Electromagnetic Waves (Ministry of Education), Fudan University, Shanghai
200433, China  Centre for Quantum Technologies, National University of
Singapore, 3 Science Drive 2, 117543 Singapore  Nanyang Quantum Hub, School of
Physical and Mathematical Sciences,Nanyang Technological University, Singapore
637371  Alioscia Hamma<EMAIL_ADDRESS>Physics Department, University
of Massachusetts Boston, 02125, USA  Dipartimento di Fisica Ettore Pancini,
Università degli Studi di Napoli Federico II, Via Cinthia, 80126 Napoli NA

###### Abstract

Random quantum states and operations are of fundamental and practical
interests. In this work, we investigate the entanglement properties of random
hypergraph states, which generalize the notion of graph states by applying
generalized controlled-phase gates on an initial reference product state. In
particular, we study the two ensembles generated by random Controlled-Z(CZ)
and Controlled-Controlled-Z(CCZ) gates, respectively. By applying tensor
network representation and combinational counting, we analytically show that
the average subsystem purity and entanglement entropy for the two ensembles
feature the same volume law, but greatly differ in typicality, namely the
purity fluctuation is small and universal for the CCZ ensemble while it is
large for the CZ ensemble. We discuss the implications of these results for
the onset of entanglement complexity and quantum chaos.

##  I Introduction

Entanglement [1] is the peculiar characteristic of quantum mechanics in
multipartite systems, not only enabling quantum information processing with an
advantage on its classical counterpart [2], but also finds fundamental
applications in other branches of physics, such as condensed matter [3] and
quantum gravity [4]. Quantum hypergrah states [5, 6, 7] are an archetypal
class of multipartite states generalizing the notion of graph states [8, 9] by
involving multi-qubit controlled-phase gates. Hypergraph state is of wide
interests in measurement-based quantum computing [10, 11, 12], quantum
advantage protocol [13], non-locality test [14, 15], quantum error correction
and topological phase of matter [16, 17, 11, 18].

In this work, we study the entanglement statistics of ensembles of hypergraph
states, specifically, ensembles generated by random CZ and CCZ gates
respectively. By adopting a tensor network representation, we reduce the
calculations to combinational problems. The main results of this paper are (i)
the average subsystem purity and entanglement entropy in the two ensembles are
essentially the same with Haar random states; on the other hand, (ii)
Fluctuations for the subsystem purity are very different: while the CCZ
ensemble features $O(d^{-2})$, Haar-like fluctuation, the CZ ensemble has
larger $O(d^{-1})$ fluctuations with $d$ the total Hilbert space dimension.
Consequently, for subsystem with half number of qubits, a volume law
$S_{2}\simeq N/2-1$ for the entanglement entropy is typical for the CCZ
ensemble with the variance of entanglement entropy exponentially small,
scaling $\exp(-N)$ with the qubit number $N$, while the variance of the CZ
ensemble is $O(1)$ and makes the expectation value not typical.

These results have a bearing on the different entanglement complexity of the
hypergraph states generated by CZ and CCZ gates, and can inspire further
studies on entanglement cooling algorithms [19, 20, 21], quantum
(pseudo-)randomness [22, 23, 24], quantum magic [25, 26], and quantum chaotic
dynamics [27, 28] in many-body physics. In particular, random hypergraph
states and generalized controlled-phase gates can provide toy models capturing
the essential physics for complex dynamics while being easier to simulate. In
addition, these techniques could be useful to study less structured quantum
ensembles that are not necessarily an (approximate) $t$-design [29, 30].

##  II Preliminaries

Figure 1: (a) A hypergraph with 4 vertices. There are three hyperedges, one of
them containing the three vertices $1,2,3$. (b) The preparation quantum
circuit in Eq. (1), which evolves from _right to left_ hereafter. Vertical
blue line denotes the $CZ_{e}$ gate, and the small circles on each qubit-line
indicate the connection. In a 5-qubit system, (c) shows a 2-uniform hypergraph
state, and (d) shows a 3-uniform one, respectively.

###  II.1 Quantum hypergraph state

First, let us recall the basic setup of hypergraph states [6, 7]. A hypergraph
$G=(V,E)$, is a pair consisting of the vertex set $V=\\{1,2\cdots,N\\}$, and
the edge set $E\subset V$. If a hyperedge $e\in E$ contains $1\leq k\leq N$
vertices, we say $e$ a $k$-edge. A hypergraph only containing $k$-edges is
said $k$-uniform. See Fig. 1 for an illustration. We attach a local Hilbert
space $\mathcal{H}_{i}$ at every vertex $i\in V$ and thus the total Hilbert
space is $\mathcal{H}=\otimes_{i\in V}\mathcal{H}_{i}$. We are concerned with
the case of qubits i.e., $\mathcal{H}_{i}\simeq\mathbb{C}^{2}$. The Hilbert
space associated to an edge $e$ is $\mathcal{H}_{e}:=\otimes_{i\in
e}\mathcal{H}_{i}$ and of course $\dim\mathcal{H}_{e}=2^{k}$ for a $k$-edge.
The total Hilbert space dimension is denoted as $d=2^{N}$.

To every hypergraph, we associate a (pure) quantum state in this way. First
define the reference state $\ket{\Psi_{0}}=\ket{+}^{\otimes N}$, with
$\ket{+}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$ the eigenstate of Pauli $X$
operator. Then, the hypergraph state is obtained from the reference state by
operating generalized controlled-Z gates according to the edges $e\in E$,

$\displaystyle\ket{G}=\left(\prod_{e\in E}CZ_{e}\right)\ket{\Psi_{0}}.$ (1)

Here the quantum gate $CZ_{e}=\otimes_{i\in e}\mathbb{I}_{i}-2\otimes_{i\in
e}\ket{1}_{i}\bra{1}$ acts non-trivially on $\mathcal{H}_{e}$, but trivially
on the qubits outside. See Fig. 1 (b) for the corresponding quantum circuit.
For a 1-edge $e=\\{i\\}$, $CZ_{e}$ is just a Pauli Z gate on the qubit $i$;
for a 2-edge, it becomes the normal Controlled-Z gate. Note that the sequence
to operate the $CZ_{e}$ gate does not matter as they commute with each other,
and thus the quantum hypergraph state $\ket{G}$ is uniquely determined by the
hypergraph $G$.

Previous works on the entanglement and correlation of hypergrah states mainly
deal with specific given states, see e.g. [14, 15], or results on entanglement
witnesses [31], local unitary transformations [32, 33, 34, 35], and efficient
verification [36, 37]. The structure of the states or the number of qubits in
the system are usually restricted, since the scaling of the problems makes it
quite challenging to extend. In this work, we instead consider the statistical
results of entanglement properties of random hypergraph state ensembles
(defined in the next section), and in the same time the behaviour under large
qubit number $N$ can be analysed. We also remark that Ref. [38] studies random
graph states, but follows a quite different definition.

###  II.2 Random state ensembles

In this section, we define the random hypergraph state ensembles $\mathcal{E}$
from the corresponding random hypergraph ensembles. In particular, we consider
random $2$-edge and random $3$-edge hypergraphs. A random $k$-uniform
hypergraph can be determined by the probability $p$ whether there is a
$k$-edge among any choice of $k$ sites. In the following, we focus on the case
$p=1/2$.

According to Eq. (1), the corresponding ensembles of hypergraph states are
generated by CZ gates and CCZ gates, as shown in Fig. 1 (c)-(d). Denote the
combination number $C^{k}_{N}:=\binom{N}{k}$, and formally the state ensemble
is defined as follows.

######  Definition 1.

The (k-uniform) random hypergraph state ensemble $\mathcal{E}$ on $N$-qubit
system is generated by

$\displaystyle\mathcal{E}=\left\\{\ket{\Psi}=U\ket{\Psi_{0}}\Big{|}U=U_{e_{C_{N}^{k}}}\cdots
U_{e_{2}}U_{e_{1}}\right\\}.$ (2)

Here each $e_{i}$ is a distinct $k$-edge of the $N$ vertices, with totally
$C_{N}^{k}$ such edges, $U_{e_{i}}$ acts on the Hilbert space
$\mathcal{H}_{e_{i}}$ by taking $\\{\mathbb{I}_{e_{i}},CZ_{e_{i}}\\}$ with 1/2
probability, and $\ket{\Psi_{0}}=\ket{+}^{\otimes N}$.

Since the $CZ_{e}$ gates commute, the order of the gate sequence in Eq. (2) is
irrelevant. Of course, there are $2^{C_{N}^{k}}$ elements in $\mathcal{E}$
with equal probability, that is, $|\mathcal{E}|=2^{C_{N}^{k}}$. In this work,
we focus on the $k=2$ and $k=3$ random hypergraph state ensembles, denoted by
$\mathcal{E}_{CZ}$ and $\mathcal{E}_{CZZ}$, respectively. Of course the $k=1$
case is trivial as this is just a single qubit gate, so that the corresponding
graph states are just product states. The first non-trivial gate is the $k=2$,
CZ gate. Note that CZ is a Clifford gate, but other $CZ_{e}$ for $k>2$ are not
[39]. By adding the Hadamard gate to $CZ_{e}$, the gate set becomes universal
for quantum computing [40]. And we conjecture that the results of CCZ hold for
other $CZ_{e}$ with some constant $k>3$.

###  II.3 Entanglement entropy and purity

Consider a bipartition of the $N$-qubit system into $\\{A,\bar{A}\\}$ with
$N_{A}$ and $N_{\bar{A}}$ qubits respectivley, and the total Hilbert space
$\mathcal{H}=\mathcal{H}_{A}\otimes\mathcal{H}_{\bar{A}}$. The bipartite
entanglement with respective to $\\{A,\bar{A}\\}$ of a pure quantum state
$\ket{\Psi}$ is quantified by the Rényi-$\alpha$ entanglement entropy defined
as

$\displaystyle
S_{\alpha}(\rho_{A})=\frac{1}{1-\alpha}\log_{2}[\mathrm{Tr}(\rho_{A}^{\alpha})],$
(3)

where $S_{\alpha}$ is the the Rényi-$\alpha$ entropy of the reduced density
matrix $\rho_{A}=\mathrm{Tr}_{\bar{A}}(\Psi)$, with
$\Psi=\ket{\Psi}\bra{\Psi}$. As $\alpha=1$, Eq. (3) gives the Von Neumann
entropy. The Rényi-2 entropy shows

$\displaystyle S_{2}(\rho_{A})=-\log_{2}(P_{A}),$ (4)

with $P_{A}=\mathrm{Tr}(\rho_{A}^{2})$ the purity functional. The Rényi-2
entropy is a lower bound of the Von Neumann entropy. This quantity is
particularly useful as the purity $P_{A}$ can be directly measured in
experiment [41, 42].

In the next sections, we compute the average subsystem purity and the variance
of the purity for the state $\Psi$ from the ensembles
$\mathcal{E}=\mathcal{E}_{CZ},\mathcal{E}_{CCZ}$, that is,

$\displaystyle\langle P_{A}\rangle_{\mathcal{E}}$
$\displaystyle:=\mathbb{E}_{\mathcal{E}}(P_{A}),$ (5)
$\displaystyle\delta^{2}_{\mathcal{E}}(P_{A})$
$\displaystyle:=\mathbb{E}_{\mathcal{E}}(P_{A}^{2})-[\mathbb{E}_{\mathcal{E}}(P_{A})]^{2}$

Hereafter we also use $\langle\cdot\rangle_{\mathcal{E}}$ to denote the
ensemble average.

##  III Average subsystem purity

In this section, we study the average purity of a subsystem $A$ for random
hypergraph states. By introducing a tensor network representation in Sec.
III.1 to facilitate the calculation, the problem is transformed to some
combinational counting, under different constraints induced by the CZ and CCZ
operations, respectively. And this methodology is also applied to the variance
of purity in Sec. IV.

The average purity of the state $\rho_{A}=\mathrm{Tr}_{\bar{A}}\Psi$ with
$\Psi\in\mathcal{E}$ can be expressed, by standard technique (e.g. [43]), as

$\displaystyle\mathbb{E}_{\Psi}(P_{A})$
$\displaystyle=\mathbb{E}_{\Psi}\mathrm{Tr}\left(T_{A}\otimes\mathbb{I}_{\bar{A}}^{\otimes
2}\ \Psi^{\otimes 2}\right)$ (6)
$\displaystyle=\mathbb{E}_{U\in\mathcal{E}}\mathrm{Tr}\left(T_{A}\otimes\mathbb{I}_{\bar{A}}^{\otimes
2}\ U^{\otimes 2}\Psi_{0}^{\otimes 2}U^{{\dagger}\otimes 2}\right)$
$\displaystyle=\mathrm{Tr}\left[T_{A}\otimes\mathbb{I}_{\bar{A}}^{\otimes 2}\
\mathbb{E}_{U\in\mathcal{E}}\left(U^{\otimes 2}\Psi_{0}^{\otimes
2}U^{{\dagger}\otimes 2}\right)\right]$
$\displaystyle=\mathrm{Tr}\left[T_{A}\otimes\mathbb{I}_{\bar{A}}^{\otimes 2}\
\Phi_{\mathcal{E}}^{2}\left(\Psi_{0}^{\otimes 2}\right)\right].$

Above, in the first line the purity is written as an observable on the two-
copy Hilbert space $\mathcal{H}^{\otimes 2}$, and $T_{A}$ is the swap operator
on $\mathcal{H}_{A}^{\otimes 2}$. The random state $\Psi$ is generated by
random unitary $U$ on the initial state $\Psi_{0}$, and we still denote the
unitary ensemble with $\mathcal{E}$ without ambiguity. In the third line of
Eq. (6), due to the linearity, the order of trace and ensemble average are
exchanged, and we denote the resulting 2-copy“twirling” channel as
$\Phi_{\mathcal{E}}^{2}$ in the final line. See Fig. 2 (a) for an
illustration.

To study the random hypergraph state, the initial state is taken as
$\ket{\Psi_{0}}=\ket{+}^{\otimes N}$, with the subsystem $A$ containing
$N_{A}\leq N/2\leq N_{\bar{A}}$ qubits without loss of generality. The
evolution $U$ is sampled from CZ or CCZ ensembles defined in Sec. II.2.
Actually, one only needs to consider the gate between $A$ and $\bar{A}$, since
the gate inside each subsystem commutes with $T_{A}$ and thus does not affect
the purity.

###  III.1 Tensor network representation

Here we introduce a tensor network representation to calculate the average
purity. To make the tensor diagram concise, we take the quantum state $\rho$
and observable $O$ as _vectors_ , and the quantum channel $\Phi$ as a
_matrix_. That is, in the form of $\langle\langle O|\Phi|\rho\rangle\rangle$.
In our case, $O=T_{A}\otimes\mathbb{I}_{\bar{A}}^{\otimes 2}$,
$\rho=\ket{+}\bra{+}^{\otimes 2N}$, and $\Phi$ is the twirling channel
$\Phi_{\mathcal{E}}^{2}$, as shown in the final line of Eq. (6). In
particular, one has

$\displaystyle\mathbb{E}_{\Psi}(P_{A})=\mathbb{E}_{U\in\mathcal{E}}\langle\langle
T_{A}|\ \otimes\langle\langle\mathbb{I}_{\bar{A}}^{2}|U\otimes U^{*}\otimes
U\otimes U^{*}\ \ket{\Psi_{0}}^{\otimes 4},$ (7)

which is illustrated in Fig. 2 (b). There are two different connections on the
left, which correspond to the vector form of the operators $\langle\langle
T_{A}|$ and $\langle\langle\mathbb{I}_{\bar{A}}^{2}|$ in Eq. (7),
respectively.

For the random hypergraph states here, the random unitary satisfies $U=U^{*}$,
and the initial state $\ket{\Psi_{0}}$ is real and product state. In Fig. 2
(c), we further rearrange the total Hilbert space $\mathcal{H}^{\otimes 2}$
into $(\mathcal{H}_{i}^{\otimes 2})^{\otimes N}$, i.e., put the two-copy of
the i-th qubit Hilbert space $\mathcal{H}_{i}$ together. On the right, every
qubit corresponds to 4 lines, each 2 for one-copy Hilbert space. In the
middle, we operate the random $CZ_{e}$ gate across $A$ and $\bar{A}$. Here we
show case of a CZ gate, which repeats 4 times connecting the corresponding
lines of the two-qubit in the tensor network. Note that the swap
$T_{A}=\otimes_{i\in A}T_{i}$, and of course the identity operator
$\mathbb{I}_{\bar{A}}^{\otimes 2}$ can be written in the product of each qubit
operators. As a result, on the left, there are two different connections for
each qubit determined by it belonging to $A$ or $\bar{A}$.

Figure 2: Tensor network of the purity formula and its vectorization. (a) The
purity formula of Eq. (6), with the red “cross” being the swap operator on
subsystem $A$. (b) Rearrangement of the tensors, with swap and identity
operators becoming two kinds of ‘vector’ on the left. (c) Take the input state
as $\ket{\Psi_{0}}=\ket{+}^{\otimes N}$ and further rearrange the tensor
network to put the two-copy of the i-th qubit Hilbert space $\mathcal{H}_{i}$
together. As a result, on the right, every qubit corresponds to 4 lines, each
2 for one-copy Hilbert space; in the middle, we operate the random $CZ_{e}$
gate across $A$ and $\bar{A}$. An example of CZ gate is shown, repeating 4
times connecting the corresponding lines of the two-qubit; on the left, the
original swap and identity in (b) are both decomposed to the qubit-level,
representing two different connections for qubit in $A$ and $\bar{A}$.

To calculate $\mathbb{E}_{\Psi}(P_{A})$, one needs to contract the tensor
network in Fig. 2 (c) for all possible random $U$ and then average them. Note
that in Fig. 2 (c), the input vector $(\ket{+}^{\otimes 4})^{\otimes N}$ on
the right can take all the possible $0/1$ bit values with a normalization
constant

$\displaystyle\mathcal{N}=(\frac{1}{\sqrt{2}})^{4N}=d^{-2}.$ (8)

The unitary in the middle is composed of $CZ_{e}$ gates, and only introduce
$\pm 1$ phase for any computational basis input. By averaging on these random
unitaries, some bit-strings may be cancelled out by taking $-1$ and $1$ for
different unitaries. As a result, to find the final average purity one only
needs to count the number of bit-strings which “survive” on the average effect
of all possible gate operations. The following proposition can simplify the
counting procedure by observing that the twirling channel in the middle can be
decomposed _locally_ , since the gate operations on distinct edges are
_independent_.

######  Proposition 1.

Consider a $t$-fold twirling channel
$\Phi_{\mathcal{E}}^{t}(\cdot):=\mathbb{E}_{U\in\mathcal{E}}U^{\otimes
t}(\cdot)U^{{\dagger}\otimes t}$, with random unitary $U=U_{e_{L}}\cdots
U_{e_{2}}U_{e_{1}}$, where each $U_{e_{i}}$ is sampled independently from the
local ensemble on the Hilbert space $\mathcal{H}_{e_{i}}$.
$\Phi_{\mathcal{E}}^{t}(\cdot)$ can be decomposed into the channel
multiplication of the corresponding local twirling channels

$\displaystyle\Phi_{\mathcal{E}}^{t}=\Phi_{\mathcal{E}_{e_{L}}}^{t}\circ\Phi_{\mathcal{E}_{e_{L-1}}}^{t}\cdots\circ\Phi_{\mathcal{E}_{e_{2}}}^{t}\circ\Phi_{\mathcal{E}_{e_{1}}}^{t}$
(9)

where $\mathcal{E}_{e_{i}}$ denotes the random unitary ensemble acting non-
trivially on $\mathcal{H}_{e_{i}}$.

###### Proof.

We prove it by using the matrix form of the twirling channel
$\tilde{\Phi}_{\mathcal{E}}^{t}=\mathbb{E}_{U\in\mathcal{E}}U^{\otimes
t}\otimes U^{*\otimes t}$, where the tilde denotes the matrix form, which is
also called the tensor product expander [44, 45]. In this way, the composition
of channel can be taken as the multiplication of the matrix,

$\displaystyle\tilde{\Phi}_{\mathcal{E}}^{t}$
$\displaystyle=\mathbb{E}_{U=U_{e_{L}}\cdots
U_{e_{2}}U_{e_{1}}}[U_{e_{L}}\cdots U_{e_{2}}U_{e_{1}}]^{\otimes
t}\otimes[U_{e_{L}}\cdots U_{e_{2}}U_{e_{1}}]^{*\otimes t}$ (10)
$\displaystyle=[\mathbb{E}_{U_{e_{L}}\in\mathcal{E}_{e_{L}}}U_{e_{L}}^{\otimes
t}\otimes U_{e_{L}}^{*\otimes
t}]\cdots[\mathbb{E}_{U_{e_{1}}\in\mathcal{E}_{e_{1}}}U_{e_{1}}^{\otimes
t}\otimes U_{e_{1}}^{*\otimes t}]$
$\displaystyle=\tilde{\Phi}_{\mathcal{E}_{e_{L}}^{t}}\cdots\tilde{\Phi}_{\mathcal{E}_{e_{2}}^{t}}\cdot\tilde{\Phi}_{\mathcal{E}_{e_{1}}^{t}},$

where the second line we use the independence of each unitary ensemble
$\mathcal{E}_{e_{i}}$, then we translate this back to the channel form and get
Eq. (9). ∎

Prop. 1 is general and suitable for any kind of random unitary ensemble. For
our random $CZ_{e}$ ensemble in Def. 1, each $e_{i}$ denotes a specific edge,
and $U_{e_{i}}\in\\{\mathbb{I}_{e_{i}},CZ_{e_{i}}\\}$ acting nontrivially on
$\mathcal{H}_{e_{i}}$ with 1/2 probability, which gives the local twirling
channel $\Phi_{\mathcal{E}_{e_{i}}}^{t}$. Note that the phase gates commutes
with each other, and thus the order of the decomposition in Eq. (9) does not
matter.

###  III.2 Average purity of CZ ensemble

Figure 3: (a) Tensor network for the two-qubit CZ operation. On the right,
there are all possible $0/1$ inputs of all black lines. As black lines
associated to the same red arc should take the same bit value, one only needs
to use the 2-bit of the red arcs to denote each qubit, and here we show case
for $\\{01,10\\}$. (b) We rotate (a) 90 degrees for clearness, and also omit
the nonessential black lines. The qubit $i$ and $j$ are labeled by the the
upper and lower two-red-arcs, with every arc can taking $0/1$ value. The
overall phase is determined by the phase accumulation of all four CZ gates.
For the $\\{01,10\\}$ case here, the overall phase is
$-1=(+1)*1*(-1)*(+1)*(+1)$. The corresponding phase matrix and the
corresponding diagram.

Equipped with the tensor network diagram, we are in the position to calculate
the average purity for CZ ensemble. To facilitate the counting procedure, we
should first figure out what happens locally, say the twirling channel
$\Phi^{2}_{\mathcal{E}_{e}}$ on a specific edge $e=\\{i,j\\}$.

First, for simplicity, let us consider a 2-qubit example, and then extend to
N-qubit later. Suppose the qubit $i$ is in $A$ and $j$ is in $\bar{A}$, as
shown in Fig. 3 (a). Remember that the input state $\ket{+}$ on the right
induces no constraint, i.e., every black line can take $0/1$ value by ignoring
the normalization $\mathcal{N}$ , thus every qubit can be denoted by 4
_classical_ bits. Moreover, since the red tensors on the left connect the ends
of the black lines, they induce constraints on the bit values. To be specific,
any two black lines should take the same bit value if they are connected to
the same red arc. Otherwise it will return zero in the tensor contraction, and
thus does not contribute to the summation, no matter what kind of gate
operations in the middle. In other words, the bit values of a qubit can be
reduced to that of the red arcs, and consequently one can use the red arcs on
the left to label the qubit and only needs to associate 2-bit to each qubit.
Fig. 3 (a) shows the case for $\\{01,10\\}$.

In Fig. 3 (b), for the simplicity of the following discussion, we rotate the
diagram 90 degrees and omit the nonessential black lines. The CZ gate on the
2-qubit can introduce phase, depending on the value of the classical bits of
the red arcs. To be specific, if there are both 1s of the red arcs on the two
ends of the CZ gate, it will give a $-1$ phase, otherwise the phase is 1, and
the final phase is determined by mutiplication of all phases from the four CZ
gates. For the $\\{01,10\\}$ case, the overall phase is $-1$ as shown in Fig.
3 (b). We list all possible cases as follows

$M_{p}=\bordermatrix{&00&01&10&11\cr 00&1&1&1&1\cr 01&1&-1&-1&1\cr
10&1&-1&-1&1\cr 11&1&1&1&1\cr},$ (11)

and denote it as the _phase_ matrix, where the row and column indexes are the
2-bit of the two qubits respectively. The phase matrix is symmetric between
the two qubits, also invariant under permutation of the 2-bit for the the row
or column, and these properties are also reflected in the diagram of Fig. 3
(b).

On the other hand, if there is no gate operation, the phase matrix is just the
trivial one

$J_{4}=\bordermatrix{&00&01&10&11\cr 00&1&1&1&1\cr 01&1&1&1&1\cr 10&1&1&1&1\cr
11&1&1&1&1\cr}.$ (12)

After taking the average for both cases, the final matrix is the summation of
them with $1/2$ probability as

$M_{s}=\bordermatrix{&00&01&10&11\cr 00&1&1&1&1\cr 01&1&0&0&1\cr 10&1&0&0&1\cr
11&1&1&1&1\cr},$ (13)

denoted as the _summation_ matrix.

$M_{s}$ in some sense can be regarded as a matrix representation of the local
twirling channel $\Phi^{2}_{\mathcal{E}_{e}}$, and we elaborate this point in
App. A. In the remaining of the paper, we will adopt this summation matrix
formalism to calculate the average purity and its variance.

The matrix $M_{s}$ in Eq. (13) indicates that only a few of bit configurations
survive under the effect of the local twirling channel
$\Phi^{2}_{\mathcal{E}_{e}}$. For instance, the configuration $\\{00,11\\}$
survives, but the configuration $\\{01,10\\}$ vanishes. To figure the average
purity in this minimal $N=2$ case, one only needs to count the number of $1$s
in Eq. (13), i.e, $12$, and normalizes it with $\mathcal{N}=1/16$ in Eq. (8)
to get $3/4$. This is consistent with the direct calculation: there is $1/2$
probability to prepare a product state with purity $1$ on $A$, and the other
$1/2$ probability to prepare the Bell state with purity $1/2$, which totally
returns the average $(1+1/2)/2=3/4$.

This counting argument can be extended to general N-qubit system by virtue of
Prop. 1. We still use 2-bit to denote one qubit and our task is to count the
total number of bit-strings which survive under all possible local twirling
channels $\Phi^{2}_{\mathcal{E}_{e}}$. Since there is
$\Phi^{2}_{\mathcal{E}_{e}}$ between any pair of qubits, we just need to move
the summation matrix $M_{s}$ in Eq. (13) on all 2-qubit between $A$ and
$\bar{A}$. For example, if the two-qubit say $i,j$ with $i\in A$ and
$j\in\bar{A}$, take the bit configuration such as $\\{01,10\\}$, no matter
what values of other qubits are, this kind of bit-string $\\{\cdots
01_{\\{i\\}},10_{\\{j\\}}\cdots\\}$ will vanish and not contribute to the
final result.

Note that the matrix elements just depend on the parity information, one can
simplify it further by using logical bit $\bar{0}=00,11$ and $\bar{1}=01,10$
to encode such that

$M_{s}=\bordermatrix{&\bar{0}&\bar{1}\cr\bar{0}&1&1\cr\bar{1}&1&0\cr}.$ (14)

and the phase matrix shows

$M_{p}=\bordermatrix{&\bar{0}&\bar{1}\cr\bar{0}&1&1\cr\bar{1}&1&-1\cr}.$ (15)

Now every qubit is labeled by _one_ classical bit, and we utilize $M_{s}$ to
constrain the bit value of any qubit-pair in $A$ and $\bar{A}$. From the
matrix $M_{s}$, one sees that $\bar{1}$ is not allowed in $A$ and $\bar{A}$
simultaneously. That is, all qubits in $A$ take $\bar{0}$ and those in
$\bar{A}$ are arbitrary or vice versa. Consequently, the total number of
surviving bit-string for the random CZ scenario is

$\displaystyle\\#_{CZ}=\left(2^{N_{A}}+2^{N_{\bar{A}}}-1\right)2^{N}.$ (16)

Here $-1$ accounts for deleting the double counting of the all $\bar{0}$ case;
the multiplication $2^{N}$ is due to the redundancy of the logical encoding.
The average purity is obtained by multiplying $\\#_{CZ}$ with the
normalization $\mathcal{N}$ in Eq. (8).

######  Theorem 1.

The average purity of the subsystem $A$ with $N_{A}$ qubits for the random
graph states from the CZ ensemble is

$\displaystyle\langle P_{A}\rangle_{CZ}=\frac{d_{A}+d_{\bar{A}}-1}{d}$ (17)

where $d_{A(\bar{A})}=2^{N_{A(\bar{A})}}$ is the Hilbert space dimension of
the subsystem $A(\bar{A})$. For the case of equal partition
$d_{A}=d_{\bar{A}}=\sqrt{d}$, one has $\langle
P_{A}\rangle_{CZ}=(2\sqrt{d}-1)/d\sim 2/\sqrt{d}$.

Figure 4: Phase matrix (3-index tensor) for the CCZ scenario. For (a) and (b),
qubit $i$ is in $A$, the other two qubits $j,k$ are in $\bar{A}$. (a) is the
phase tensor $M_{ijk}^{p}$ when operating the CCZ gate, and (b) is the trivial
all-ones tensor $J_{ijk}$ without gate operation. The summation tensor
$M_{ijk}^{s}$ is the average of both. (c) is the phase tensor
$\tilde{M}_{ijk}^{p}$ for the case of $i,j\in A,k\in\bar{A}$, which is
different from $M_{ijk}^{p}$ due to the shape of the red tensors. But it can
be deformed to $M_{kij}^{p}$ in (d) without changing the topology.

###  III.3 Average purity of CCZ ensemble

Now we move to the scenario of random CCZ hypergraph states. Similarly with
the CZ scenario in Sec. III.2, we still use two classical bits to denote one
qubit, and count the number of the surviving bit-strings.

First, we should figure out what happens locally, say the corresponding
summation matrix $M_{s}$ caused by the local twirling channel
$\Phi^{2}_{\mathcal{E}_{e}}$. The only difference compared with the CZ
scenario is that CCZ involves three qubits $i,j,k$, and thus the corresponding
phase matrix $M_{p}$ is actually a _three-index tensor_ $M_{ijk}^{p}$, and we
denote the trivial all-ones tensor without gate operation as $J_{ijk}$, as
shown in Fig. 4 (a) and (b). The summation tensor is their average

$\displaystyle M_{ijk}^{s}=\frac{1}{2}\left(M_{ijk}^{p}+J_{ijk}\right).$ (18)

Figure 5: Phase tensor $M_{ijk}^{p}$ in Fig. 4 (a) for different classical bit
values of qubit $i$. (a) For $\mathbf{i}=00$, the blue CCZ gate can not
introduce phase on the $j,k$ qubits, and thus the matrix between $j,k$ is
$J_{2}^{\otimes 2}$. (b) For $\mathbf{i}=11$, the CCZ gates reduce to CZ gates
on $j,k$. However, the nearby two CZ gates cancel with each other and lead
also to $J_{2}^{\otimes 2}$. (c) For $\mathbf{i}=01,10$, there is only one CZ
gate on a pair of red arcs, and the corresponding matrix form is
$H_{2}^{\otimes 2}$.

Suppose qubit $i\in A$, and the other two qubits $j,k\in\bar{A}$ for the case
in Fig. 4 (a), we can write down $M_{ijk}^{p}$ by fixing the bit value of $i$.
If qubit $i$ takes the logical $\bar{0}$, denoted by $\mathbf{i}=\bar{0}$ with
the blod font, the matrix between $j$ and $k$ is the trivial $4\times 4$ all-
ones matrix $J_{4}=J_{2}^{\otimes 2}$ in Fig. 5 (a) and (b). In this case, the
summation tensor is

$\displaystyle M_{ijk}^{s}$
$\displaystyle=\ket{\mathbf{i}}\bra{\mathbf{i}}\otimes\frac{1}{2}(J_{4}+J_{4})$
(19) $\displaystyle=\ket{\mathbf{i}}\bra{\mathbf{i}}\otimes J_{4}.$

with $\mathbf{i}=00,11$ and Dirac notation is adopted to write the tensor.

If qubit $\mathbf{i}=\bar{1}$, the matrix between $j,k$ is $H_{2}^{\otimes 2}$
in Fig. 4 (c), with $H_{2}$ being the $2\times 2$ Hadamard matrix _without_
normalization constant $1/\sqrt{2}$ hereafter. And the resulting summation
tensor is

$\displaystyle M^{s}_{ijk}$
$\displaystyle=\ket{\mathbf{i}}\bra{\mathbf{i}}\otimes 1/2(H_{2}^{\otimes
2}+J_{2}^{\otimes 2})$ (20)
$\displaystyle=\ket{\mathbf{i}}\bra{\mathbf{i}}\otimes\bordermatrix{&00&01&10&11\cr
00&1&1&1&1\cr 01&1&0&1&0\cr 10&1&1&0&0\cr 11&1&0&0&1\cr}.$
$\displaystyle:=\ket{\mathbf{i}}\bra{\mathbf{i}}\otimes M_{i}^{s}$

for $\mathbf{i}=01,10$, and we denote the matrix between $j,k$ with a fixed
$\mathbf{i}$ as $M_{i}^{s}$.

For simplicity of discussion, in the following we first consider a sub-
ensemble with random CCZ gates defined as follows. For every three-qubit $i\in
A,j,k\in\bar{A}$, we operate a CCZ on them or not with probability $1/2$, and
the whole ensemble is composed of these local ones, similar as in Def. 1. This
ensemble is different from the original random CCZ ensemble, where $CCZ_{ijk}$
with $i,j\in A,k\in\bar{A}$ is also allowed, and thus we call it _half_ CCZ
ensemble. See Fig. 6 for an illustration.

Figure 6: An illustration for the _half_ CCZ ensemble. In an $N=6$-qubit
system, the subsystem $A$ and $\bar{A}$ both contain $N_{A}=N_{\bar{A}}=3$
qubits. For every three-qubit $i\in A,j,k\in\bar{A}$, we could operate a CCZ
on them or not with $1/2$ probability. In this way, there are
$N_{A}*C_{N_{\bar{A}}}^{2}$ possible gate patterns with equal probability. In
(a) and (b) we show two examples for the gate pattern.

Similar as the CZ scenario, we will count the number of survival bit-strings
of this half ensemble to calculate the average purity, with constraints from
Eq. (19) and (20). By Eq. (19), it is not hard to see that as
$\mathbf{i}=\bar{0}$, actually there is no constraint on $j,k$; by Eq. (20),
as $\mathbf{i}=\bar{1}$, some values of $j,k$ would vanish, shown as the zero
elements in the matrix $M_{i}^{s}$.

First, if $\forall i\in A,\mathbf{i}=\bar{0}$, $j\in\bar{A}$ can take any
value, totally $1*4^{N_{\bar{A}}}*2^{N_{A}}$, where $2^{N_{A}}$ is the logical
encoding abundance. Second, if there exists $\mathbf{i}=\bar{1}\in A$, there
are three possibilities for $j\in\bar{A}$.

  1. 1.

$j$ only takes $00$ or $11$, totally $2^{N_{\bar{A}}}$.

  2. 2.

there exists one $\mathbf{j}=01$ or $10$, and the remaining $k\in\bar{A}$ can
just be $00$, totally $2C_{N_{\bar{A}}}^{1}=2{N_{\bar{A}}}$.

  3. 3.

there exists one $\mathbf{j}=01$ and one $\mathbf{k}=10$, and the remaining
qubits can just be $00$, totally
$2C_{N_{\bar{A}}}^{2}=N_{\bar{A}}({N_{\bar{A}}}-1)$.

As a result, the average purity of this half ensemble is obtained by summing
the number of survival bit-strings in all the above cases and multiplying the
normalization in Eq. (8).

$\displaystyle\langle
P_{A}\rangle_{CCZ,h}=2^{N_{A}}\frac{4^{N_{\bar{A}}}+(2^{N_{A}}-1)[2^{N_{\bar{A}}}+N_{\bar{A}}({N_{\bar{A}}}+1)]}{4^{N}}$
(21)
$\displaystyle=\frac{d_{A}+d_{\bar{A}}-1}{d}+\frac{d_{A}(d_{A}-1)N_{\bar{A}}({N_{\bar{A}}}+1)}{d^{2}}$

where the front $2^{N_{A}}$ is for the logical encoding abundance of the qubit
in $A$. In the case of equal partition $N_{A}=N_{\bar{A}}=N/2$, it shows
$\langle P_{A}\rangle_{CCZ,h}\sim 2/\sqrt{d}+O(N^{2}/d)$.

Finally, we look into the original full CCZ ensemble. Like before, we should
additionally figure out the phase tensor for the case $i,j\in A$, and
$k\in\bar{A}$. By the symmetry, the new tensor is almost the same to the
original one. One has the relation of the phase tensor
$\tilde{M}_{ijk}^{p}=M_{kij}^{p}$ by deforming the tensor in Fig. 4 (c) to the
one in (d), so does the summation tensor. As a result, the additional gate
will induce more constraints on the bit-string, which leads to the _decrease_
of the average purity.

Actually, only the last two cases 2 and 3 listed before change. When there is
$k\in\bar{A}$ taking $01$ or $10$, that is $\mathbf{k}=\bar{1}$, we can use
the summation tensor $\tilde{M}_{ijk}^{s}=M_{kij}^{s}$ in Eq. (20) to
constraint the bit value of qubits back in $A$. Since the case of $\forall
i\in A,\mathbf{i}=\bar{0}$ has already be counted, one needs to figure out the
case that $\exists i\in A,\mathbf{i}=\bar{1}$. Following the same counting
procedure in cases 2 and 3, one can find that there are $N_{A}(N_{A}+1)$
choices for $A$. By summing the numbers of all these possibilities, one has
the result of average purity as follows.

######  Theorem 2.

The average purity of the subsystem $A$ with $N_{A}$ qubits for the random
hypergraph states from the CCZ ensemble is

$\displaystyle\langle
P_{A}\rangle_{CCZ}=\frac{d_{A}+d_{\bar{A}}-1}{d}+\frac{N_{A}(N_{A}+1)N_{\bar{A}}({N_{\bar{A}}}+1)}{d^{2}}$
(22)

where $d_{A(\bar{A})}=2^{N_{A(\bar{A})}}$ is the Hilbert space dimension of
the subsystem $A(\bar{A})$. For the case of equal partition
$d_{A}=d_{\bar{A}}=\sqrt{d}$, one has $\langle
P_{A}\rangle_{CCZ}=2/\sqrt{d}-1/d+O(N^{4}/d^{2})$.

At the end of this section, we remark that the average purity results of CZ
and CCZ ensembles obtained here are almost equal to that of Haar random states
[46, 47], i.e.,

$\displaystyle\langle
P_{A}\rangle_{\mathrm{Haar}}=\frac{d_{A}+d_{\bar{A}}}{d+1},$ (23)

and any state ensemble satisfies projective 2-design, such as the orbit of
Clifford group [22, 48]. Actually, the CZ and CCZ ensemble are _not_
projective 2-design, even approximately [49, 50].

##  IV Fluctuations of the purity

In Sec. III, one sees that the average subsystem purities of random CZ and CCZ
ensembles share the same leading term. In this section, we find that the
variances of the purity of the two ensembles are quite different.

$\displaystyle\delta^{2}(P_{A})=\mathbb{E}_{\Psi}(P_{A}^{2})-[\mathbb{E}_{\Psi}(P_{A})]^{2},$

The essential quantity one needs to figure out is the first term
$\mathbb{E}_{\Psi}(P_{A}^{2})$. Similar as Eq. (6) for the average purity, it
can be written on the 4-copy Hilbert space $\mathcal{H}^{\otimes 4}$ as

$\displaystyle\mathbb{E}_{\Psi}(P_{A}^{2})$
$\displaystyle=\mathbb{E}_{\Psi}\left[\mathrm{Tr}\left(T_{A}\otimes\mathbb{I}_{\bar{A}}^{\otimes
2}\ \Psi^{\otimes 2}\right)\right]^{2}$ (24)
$\displaystyle=\mathbb{E}_{U\in\mathcal{E}}\ \
\mathrm{Tr}\left[T^{(1,2)}_{A}\otimes
T^{(3,4)}_{A}\otimes\mathbb{I}_{\bar{A}}^{\otimes 4}\ \ U^{\otimes
4}\Psi_{0}^{\otimes 4}U^{{\dagger}\otimes 4}\right]$
$\displaystyle=\mathrm{Tr}\left[T^{(1,2)}_{A}\otimes
T^{(3,4)}_{A}\otimes\mathbb{I}_{\bar{A}}^{\otimes 4}\ \
\Phi_{\mathcal{E}}^{4}\left(\Psi_{0}^{\otimes 2}\right)\right].$

Here we can still vectorize Eq. (24) in the form of $\langle\langle
O|\tilde{\Phi}|\rho\rangle\rangle$ as in Eq. (7). $O=T^{(1,2)}_{A}\otimes
T^{(3,4)}_{A}\otimes\mathbb{I}^{\otimes 4}_{\bar{A}}$,
$\rho=\ket{+}\bra{+}^{\otimes 4N}$, and $\Phi$ is the 4-copy twirling channel
$\Phi_{\mathcal{E}}^{4}$, whose matrix form shows

$\displaystyle\tilde{\Phi}_{\mathcal{E}}^{4}=(U\otimes U^{*})^{\otimes
4}=U^{\otimes 8}$ (25)

with the fact that $U=U^{*}$ for phase gates. One can draw the corresponding
diagram by _doubling_ Fig. 2 (b).

Similar as the average purity in Fig. 2 (c), we still apply the tensor network
representation to calculate the expectation value here. We arrange the total
Hilbert space $\mathcal{H}^{\otimes 4}$ as $(\mathcal{H}_{i}^{\otimes
4})^{\otimes N}$, i.e., put the two-copy of the i-th qubit Hilbert space
$\mathcal{H}_{i}$ together in Fig. 7 (a). On the right, every qubit
corresponds to 8 lines, each 2 for one-copy Hilbert space. In the middle, we
operate the random $CZ_{e}$ gate across $A$ and $\bar{A}$. Here we show case
of a CZ gate, which repeats 8 times by Eq. (25), connecting the corresponding
lines of the two-qubit in the tensor network. On the left, by decomposing the
swap $T^{(1,2)}_{A}\otimes T^{(3,4)}_{A}$ and the identity
$\mathbb{I}^{\otimes 4}_{\bar{A}}$ to the qubit level, there are two different
connections for each qubit determined by it belonging to $A$ or $\bar{A}$.

To calculate $\mathbb{E}_{\Psi}(P_{A}^{2})$, one needs to contract the tensor
network in Fig. 7 (a) under the averge effect of the random $U$. Note that the
input vector $(\ket{+}^{\otimes 8})^{\otimes N}$ on the right of Fig. 7 (a)
can take all the possible $0/1$ bit values with a normalization constant

$\displaystyle\mathcal{N}_{v}=(\frac{1}{\sqrt{2}})^{8N}=d^{-4}.$ (26)

Similar as the average purity scenario, one needs to count the number of bit-
strings which survive under the twirling channel $\Phi_{\mathcal{E}}^{4}$,
which can also be decomposed locally by Prop. 1. In fact, like Fig. 3 (a), one
can associate 4 classical bit to one qubit due to the connections on the left
in Fig. 7 (a), and we still apply the phase/summation matrix (tensor) to
describe the local twirling channel $\Phi_{\mathcal{E}_{e}}^{4}$ on a edge
$e$.

Figure 7: Tensor network for the purity variance formula and the phase
tensors. (a) We rearrange Eq. (24) in the current tensor network form. On the
right, every qubit corresponds to 8 lines, each 2 for one-copy Hilbert space.
Every line can take one bit $0/1$ value. In the middle, we can operate CZ or
CCZ across $A$ and $\bar{A}$ in this double Hibert space. Here we show
explicitly the CZ between the last qubit in $A$ and the first qubit in
$\bar{A}$. On the left, there are two kinds of boundary operators correspond
to swap and identity on the qubit Hilbert space $\mathcal{H}_{i}^{\otimes 4}$,
depending on whether the qubit-i is in $A$ or $\bar{A}$. (b) The phase matrix
for the CZ gate, which is the 2-copy tensor product of the one in Fig. 3 (b)
for the average purity scenario. (c) The phase tensor for the CCZ gate with
qubit-i in A and j,k in $\bar{A}$, which is the tensor product of the one in
Fig. 4 (a). (d) The effective matrix on $j,k$ depends on the value of i. For
example, if i takes $\bar{01}$, the matrix on j,k is $J_{4}\otimes H_{4}$
shown in Eq. (33).

###  IV.1 Variance of purity for CZ ensemble

Similar as the average purity scenario in Sec. III.2, we should first figure
out what happens locally, say the summation matrix for the twirling channel
$\Phi_{\mathcal{E}_{e}}^{4}$. Considering $e=\\{i,j\\}$ with $i\in
A,j\in\bar{A}$, each qubit is labeled by 4-bit shown in Fig. 7 (b), where one
can directly see that the phase matrix is just the tensor product of the one
in Fig. 3 (b). By applying the logical encoding as in Eq. (15), each qubit can
be labeled by 2-bit, and the phase matrix here shows

$M_{p}^{\prime}=M_{p}^{\otimes
2}=\bordermatrix{&\bar{00}&\bar{01}&\bar{10}&\bar{11}\cr\bar{00}&1&1&1&1\cr\bar{01}&1&-1&1&-1\cr\bar{10}&1&1&-1&-1\cr\bar{11}&1&-1&-1&1\cr}.$
(27)

The summation matrix is obtained by average $M_{p}^{\prime}$ with the all-ones
matrix

$M_{s}^{\prime}=\bordermatrix{&\bar{00}&\bar{01}&\bar{10}&\bar{11}\cr\bar{00}&1&1&1&1\cr\bar{01}&1&0&1&0\cr\bar{10}&1&1&0&0\cr\bar{11}&1&0&0&1\cr}$
(28)

$M_{s}^{\prime}$ shows the constraint on the classical bit configurations of
the qubits in $A$ and $\bar{A}$. Like Sec. III.2, we list all the surviving
possibilities on the logical encoding level as follows.

  1. 1.

$A$ only contains $\bar{00}$, and there is no constraint on the bit value of
qubits in $\bar{A}$, and vice versa, totally $4^{N_{A}}+4^{N_{\bar{A}}}-1$.

  2. 2.

only $\bar{00}$ and $\bar{11}$ appear in both $A$ and $\bar{A}$, totally
$(2^{N_{A}}-1)(2^{N_{\bar{A}}}-1)$.

  3. 3.

$A$ contains $\bar{01}$ and $\bar{00}$, and $\bar{A}$ contains $\bar{10}$ and
$\bar{00}$, and vice versa, totally $2(2^{N_{A}}-1)(2^{N_{\bar{A}}}-1)$.

As a result, by summing the number of the possible bit-strings and normalizing
the constant in Eq. (26), one has

$\displaystyle\langle P_{A}^{2}\rangle_{CZ}$
$\displaystyle=\frac{4^{N}[4^{N_{A}}+4^{N_{\bar{A}}}-1+3(2^{N_{A}}-1)(2^{N_{\bar{A}}}-1)]}{4^{2N}}$
(29)
$\displaystyle=\frac{d_{A}^{2}+d_{\bar{A}}^{2}-1+3(d_{A}-1)(d_{\bar{A}}-1)}{d^{2}}.$

Here $4^{N}$ multiplication is due to the logical encoding redundancy. For
example, $\bar{00}$ encoding for a qubit can correspond to 4 possibilities. As
a result, by combing the average purity result in Eq. (17), the variance shows
as follows.

######  Theorem 3.

For a subsystem $A$ with $N_{A}$ qubits, the variance of the purity $P_{A}$
defined in Eq. (5) for the random graph states from the CZ ensemble is

$\displaystyle\delta^{2}_{CZ}(P_{A})$
$\displaystyle=\frac{(d_{A}-1)(d_{\bar{A}}-1)}{d^{2}}$ (30)

where $d_{A(\bar{A})}=2^{N_{A(\bar{A})}}$ is the Hilbert space dimension of
the subsystem $A(\bar{A})$. For the case of equal partition
$d_{A}=d_{\bar{A}}=\sqrt{d}$, one has
$\delta^{2}_{CZ}(P_{A})=d^{-1}-2d^{-\frac{3}{2}}+d^{-2}$.

We remark that the variance of the subsystem purity of CZ ensemble is similar
to that of random stabilizer states [51], which scales as $d^{-1}$ for the
equal partition.

To get the above varaince, one subtracts $[\mathbb{E}_{\Psi}(P_{A})]^{2}$ from
$\mathbb{E}_{\Psi}(P_{A}^{2})$ in Eq. (29). Actually one is only left with the
bit-strings in case 2, and the bit-strings in case 1 and 3 also survive in the
formula of $[\mathbb{E}_{\Psi}(P_{A})]^{2}$. The reason is as follows. For
qubit $i$, it can be denoted by two logical bits
$\mathbf{i_{1}}\mathbf{i_{2}}$, and the constraint from $M_{p}^{\prime}$ in
Eq. (27) on any qubit-pair i and j reads

$\displaystyle\bra{\mathbf{i_{1}}}M_{p}\ket{\mathbf{j_{1}}}*\bra{\mathbf{i_{2}}}M_{p}\ket{\mathbf{j_{2}}}=1.$
(31)

On the other hand, the constraint of $[\mathbb{E}_{\Psi}(P_{A})]^{2}$ for the
two logical bits are independent, say
$\bra{\mathbf{i_{1}}}M_{p}\ket{\mathbf{j_{1}}}=1$ _and_
$\bra{\mathbf{i_{2}}}M_{p}\ket{\mathbf{j_{2}}}=1$. As a result, the difference
is the case where there exist two qubit $i,j$ such that the two terms both
take $-1$, which is just the case 2. This phenomena is general and also
applicable to the CCZ scenario, and we illustrate it in detail in App. B.

###  IV.2 Variance of purity for CCZ ensemble

Similar as the average purity scenario in Sec. III.3, we first figure out the
local phase and summation tensors. Considering three qubits $i\in A$ and
$j,k\in\bar{A}$, as shown in Fig. 7 (c), each qubit is labeled by 4-bit. It is
clear that the phase tensor is the tensor-product of the one in the average
purity scenario in Fig. 4 (a),

$\displaystyle{M^{\prime}}_{ijk}^{p}=M_{i_{1}j_{1}k_{1}}^{p}\otimes
M_{i_{2}j_{2}k_{2}}^{p}$ (32)

with $i=\\{i_{1}i_{2}\\}$ and $i_{1},i_{2}$ both taking 2-bit values, same for
$k$ and $j$.

By using the logical encoding as in Sec. III.3, $i_{1}$ and $i_{2}$ of qubit-i
can be both labeled by 1 logical bit of $\bar{0},\bar{1}$. Depending on the
status of $i$, the matrix between $j$ and $k$ shows,

$\displaystyle\mathbf{i}=\bar{00},\ J_{4}\otimes J_{4}=J_{16},$ (33)
$\displaystyle\mathbf{i}=\bar{01},\ J_{4}\otimes H_{4},$
$\displaystyle\mathbf{i}=\bar{10},\ H_{4}\otimes J_{4},$
$\displaystyle\mathbf{i}=\bar{11},\ H_{4}\otimes H_{4}=H_{16},$

where $J_{4}$ denotes the trivial all-ones $4\times 4$ matrix, and
$H_{4}=H_{2}^{\otimes 2}$. See Fig. 7 (d) for the illustration of the second
case $\mathbf{i}=\bar{01}$.

The summation tensor is obtained by averaging ${M^{\prime}}_{ijk}^{p}$ with
the trivial all-ones tensor $J_{ijk}$. For a fixed $\mathbf{i}$, say
$\mathbf{i}=\bar{01}$, the matrix between $j,k$ shows

$\displaystyle{M^{\prime}}_{i}^{s}=\frac{1}{2}(J_{4}\otimes
H_{4}+J_{16})=J_{4}\otimes\frac{1}{2}(H_{4}+J_{4})=J_{4}\otimes M^{s}_{i}$
(34)

where the explicit form of $M^{s}_{i}$ is given in Eq. (20). Similarly,
$M_{i}^{\prime s}$ for different $\mathbf{i}$ is obtained by averaging every
matrix in Eq. (33) with $J_{16}$, and they show respectively

$\displaystyle\mathbf{i}=\bar{00},\ {M^{\prime}}_{i}^{s}=J_{16},$ (35)
$\displaystyle\mathbf{i}=\bar{01},\ {M^{\prime}}_{i}^{s}=J_{4}\otimes
M^{s}_{i},$ (36) $\displaystyle\mathbf{i}=\bar{10},\
{M^{\prime}}_{i}^{s}=M^{s}_{i}\otimes J_{4},$ (37)
$\displaystyle\mathbf{i}=\bar{11},\
{M^{\prime}}_{i}^{s}=\frac{1}{2}(H_{16}+J_{16}).$ (38)

In the following, as in the average purity scenario in Sec. III.3, we first
count the survival bit-string for the half ensemble of CCZ gates, say any
$CCZ_{\\{ijk\\}}$ gate with $i\in A,j,k\in\bar{A}$, with the help of the
summation tensor in Eq. (35) to (38), and extend to the full ensemble later.
There are several possible cases listed as follows.

  1. 1.

$A$ only contains $\bar{00}$, $\bar{A}$ can be arbitrary by Eq. (35), totally
$16^{N_{\bar{A}}}$.

  2. 2.

$A$ only contains $\bar{00}$ and $\bar{01}$. Due to Eq. (36), the first two-
bit of qubit in $\bar{A}$ can be arbitrary, and the last two should be
restricted by $M^{s}_{i}$ in Eq. (20). Totally

$\displaystyle(2^{N_{A}}-1)4^{N_{\bar{A}}}\left[2^{N_{\bar{A}}}+N_{\bar{A}}(N_{\bar{A}}+1)\right].$
(39)

Here $(2^{N_{A}}-1)$ counts the possibility for $A$. $4^{N_{\bar{A}}}$ counts
the possibility for the first two-bit of the qubit in $\bar{A}$.
$[2^{N_{\bar{A}}}+N_{\bar{A}}(N_{\bar{A}}+1)]$ accounts for the possibility
for the last-two bit of qubits in $\bar{A}$, which follows similarly by
summing cases 1 to 3 in Sec. III.3.
Same result holds for $A$ only containing $\bar{00}$ and $\bar{10}$.

  3. 3.

$A$ contains at least two types from $\\{\bar{01},\bar{10},\bar{11}\\}$. For
the qubit in $\bar{A}$, both the first two and last two-bit are restricted.
For example, suppose $A$ has $\bar{01}$ and $\bar{11}$, the constraint follows
Eq. (36) and (38). Consider two qubits $j,k\in\bar{A}$, the constraint on the
classical 4-bit values is actually

$\displaystyle\bra{\mathbf{j_{1}}}H_{4}\ket{\mathbf{k_{1}}}=1$ (40)
$\displaystyle\bra{\mathbf{j_{2}}}H_{4}\ket{\mathbf{k_{2}}}=1$

with $\mathbf{j_{1}},\mathbf{j_{2}}$ denoting the first and last-two bits of
qubit j, similar for k. Note that the constraints are _independent_ on
$\mathbf{j_{1}}$ and $\mathbf{j_{2}}$. Totally

$\left[4^{N_{A}}-3(2^{N_{A}}-1)-1\right]\left[2^{N_{\bar{A}}}+N_{\bar{A}}(N_{\bar{A}}+1)\right]^{2}$
(41)

where the first braket counts the possibility for $A$, and the second for
$\bar{A}$ follows similar argument as in case 39. We count the possibility for
the first and lat 2-bit independently and thus there is a square.

  4. 4.

$A$ contains $\bar{00}$ and $\bar{11}$. For the qubit in $\bar{A}$, both the
first two and last two-bit are restricted. Now the bit values of qubits
$j,k\in\bar{A}$ is constrained _jointly_ by Eq. (38). That is,

$\displaystyle\bra{\mathbf{j_{1}}}H_{4}\ket{\mathbf{k_{1}}}*\bra{\mathbf{j_{2}}}H_{4}\ket{\mathbf{k_{2}}}=1$
(42)

compared with Eq. (40) in case 41. We count this case explicitly as follows in
Lemma 1.

Denote the 4-bit of the two qubit $j,k$ as $\\{a_{t}\\}$ and $\\{b_{t}\\}$
with $t=1,2,3,4$. The constraint in Eq. (42) is actually

$\displaystyle\prod_{t}\bra{a_{t}}H_{2}\ket{b_{t}}=\prod_{t}(-1)^{a_{t}b_{t}}=(-1)^{\sum_{t}a_{t}b_{t}}=1$
(43)

or equivalently the binary vector $\vec{a}$ and $\vec{b}$ are orthogonal on
the binary filed. If we denote the number of bit configurations satisfy this
condition as $\\#_{4}$, one has the following result of it, with the proof in
App. C.

######  Lemma 1.

Suppose there are $m$ distinct positions, one assigns 4-bit vector
$\vec{v}_{i}\in\mathbb{F}_{2}^{4}$ to each of them $1\leq i\leq m$, with the
constraint

$\vec{v}_{i}\cdot\vec{v}_{j}=0\ \mathrm{Mod}(2),\forall i\neq j.$

The number of all possible assignments is

$\displaystyle\\#_{4}=3*4^{m}+\Theta(m^{2})2^{m}+\Theta(m^{4})$ (44)

for large $m$.

As a result, by summing all the possibilities and normalizing the constant in
Eq. (26), one has

$\displaystyle\langle P_{A}^{2}\rangle_{CCZ,h}$
$\displaystyle=4^{N_{A}}\frac{16^{N_{\bar{A}}}+2(2^{N_{A}}-1)4^{N_{\bar{A}}}\left[2^{N_{\bar{A}}}+N_{\bar{A}}(N_{\bar{A}}+1)\right]+\left[4^{N_{A}}-3(2^{N_{A}}-1)-1\right]\left[2^{N_{\bar{A}}}+N_{\bar{A}}(N_{\bar{A}}+1)\right]^{2}+(2^{N_{A}}-1)\\#_{4}}{4^{2N}}$
(45)
$\displaystyle=\frac{\left\\{d(d_{A}+d_{\bar{A}}-1)+d_{A}(d_{A}-1)N_{\bar{A}}({N_{\bar{A}}}+1)\right\\}^{2}+d_{A}^{2}(d_{A}-1)\left\\{\\#_{4}-\left[d_{\bar{A}}+N_{\bar{A}}(N_{\bar{A}}+1)\right]^{2}\right\\}}{d^{4}}$

with $4^{N_{A}}$ multiplication due to the logical encoding redundancy for
qubit in $A$. As a result, by combing the average purity result in Eq. (21),
the variance of the half CCZ ensemble shows as follows.

######  Theorem 4.

For a subsystem $A$ with $N_{A}$ qubits, the variance of the purity $P_{A}$
defined in Eq. (5) for the random hypergraph states from the half CCZ ensemble
is

$\displaystyle\delta^{2}_{CCZ,h}(P_{A})$
$\displaystyle=\frac{d_{A}^{2}(d_{A}-1)\left\\{\\#_{4}-\left[d_{\bar{A}}+N_{\bar{A}}(N_{\bar{A}}+1)\right]^{2}\right\\}}{d^{4}}$
(46) $\displaystyle\leq\frac{9d_{A}}{d^{2}}\leq 9d^{-\frac{3}{2}},$

where $\\#_{4}$ is in Lemma 1 by taking $m=N_{\bar{A}}$, and
$d_{A(\bar{A})}=2^{N_{A(\bar{A})}}$ is the Hilbert space dimension of the
subsystem $A(\bar{A})$.

Similar as the discussion at the end of Sec. IV.2, from Eq. (46), it is not
hard to see that only the case 42 contributes to the final variance. Actually
the bit-strings in cases 1 to 41 have already been counted for
$[\mathbb{E}_{\Psi}(P_{A})]^{2}$ of Eq. (21) in Sec. III.3. In particular, the
$\left[d_{\bar{A}}+N_{\bar{A}}(N_{\bar{A}}+1)\right]^{2}$ in Eq. (46)
indicates that one should further substrate the solution of Eq. (42) with
$\bra{\mathbf{j_{1}}}H_{4}\ket{\mathbf{k_{1}}}=\bra{\mathbf{j_{2}}}H_{4}\ket{\mathbf{k_{2}}}=1$
for all $j,k$ pairs.

Before moving to the full CCZ ensemle, we would like to remark that as one
extends the random CCZ gates from the half ensemble to the full ensemble, the
average value should decrease

$\displaystyle\langle P_{A}^{2}\rangle_{CCZ}\leq\langle
P_{A}^{2}\rangle_{CCZ,h},$ (47)

since the full ensemble will induce more constraints on the bit configuration
and less of them can survive. As a result, by inserting the average purity in
Eq. (22), one has the result for the full ensemble, with the proof left in
App. D.

######  Corollary 1.

For a subsystem $A$ with $N_{A}$ qubits, the variance of the purity $P_{A}$
defined in Eq. (5) for the random hypergraph states from the CCZ ensemble is
upper bounded by

$\displaystyle\delta^{2}_{CCZ}(P_{A})<\langle P_{A}^{2}\rangle_{CCZ,h}-\langle
P_{A}\rangle_{CCZ}^{2}<3N^{2}d^{-\frac{3}{2}}$ (48)

for sufficient large $N$ and $d=2^{N}$ is the total Hilbert space dimension.

Furthermore, one can enhance the bound by more delicate counting as in the
average purity scenario in Sec. III.3, and show that the variance of the full
ensemble scales as $d^{-2}$, compared to $d^{-1.5}$ in Corollary 1.

######  Theorem 5.

For a subsystem $A$ with $N_{A}$ qubits, the variance of the purity $P_{A}$
defined in Eq. (5) for the random hypergraph states from the CCZ ensemble is

$\displaystyle\delta^{2}_{CCZ}(P_{A})=4d^{-2}-2(d_{A}+d_{\bar{A}})d^{-3}+O(N^{4})d^{-3}$
(49)

where $d=2^{N}$ is the total Hilbert space dimension.

The proof is left in App. E. Note that the variance of the subsystem purity of
CCZ ensemble is similar to that of Haar random states [52, 51], which scales
as $d^{-2}$ for the equal partition.

At the end of this subsection, we give some remark on the generalization of
our method beyond the uniform ensemble of the $CZ_{e}$ gate in Def. 1. First,
suppose the hypergraph state ensemble is not uniform, say the probability
$p\neq 1/2$, one can still apply the phase/summation matrix formalism, and now
$M_{s}$ say in Eq. (13) become $M_{s}=pM_{p}+(1-p)J$, which could make the
calculation more involved. But we conjecture that any constant deviation of
$p$ from $1/2$ will not essentially change the previous results on the purity
and its variance. Generally, the $M_{s}$ matrix could be a summation or
integral like

$\displaystyle M_{s}=\sum_{i}p_{i}M_{p}^{(i)}$ (50)

where $M_{p}^{(i)}$ is the phase matrix for some phase gate with applying
probability $p_{i}$. In our original uniform ensemble, the gates are
$\\{\mathbb{I}_{e},CZ_{e}\\}$, both with $1/2$ probability. Moreover, our
formalism could also be suitable for diagonal gates, since they keep the
transformation on the computational basis.

##  V Implications for the entanglement entropy

In this section, we utilize the results of the average subsystem purity and
its variance obtained in Sec. III and IV, to show some statistical behaviour
of the entanglement entropy.

Recall that the Von Neumann entropy can be bounded by the Rényi-2 entropy

$\displaystyle\mathbb{E}_{\Psi}S_{1}(\rho_{A})$
$\displaystyle\geq\mathbb{E}_{\Psi}S_{2}(\rho_{A})$ (51)
$\displaystyle=\mathbb{E}_{\Psi}-\log_{2}(P_{A})$
$\displaystyle\geq-\log_{2}(\mathbb{E}_{\Psi}P_{A}),$

where the last line is due to the convexity. Consequently, by Theorem 1 and 2,
one has the following result.

######  Corollary 2.

For a subsystem $A$ with $N_{A}$ qubits, the average Rényi-2 entanglement
entropy of the random hypergraph states from both CZ and CCZ ensembles is
lower bounded by

$\displaystyle\langle
S_{2}(\rho_{A})\rangle\geq-\log_{2}\left(\frac{d_{A}+d_{\bar{A}}}{d}\right)$
(52)

where $d_{A(\bar{A})}=2^{N_{A(\bar{A})}}$ is the Hilbert space dimension of
the subsystem $A(\bar{A})$, and so does the average Von Neumann entropy
$\langle S_{1}(\rho_{A})\rangle$ by Eq. (51).

Some remarks are as follows. In the regime $N_{\bar{A}}-N_{A}\gg 1$, it is
clear that the average entanglement entropy for both ensembles equals the
qubit number in the subsystem $A$, $\langle
S_{2}(\rho_{A})\rangle\sim-\log(d_{A}^{-1})=N_{A}$, which is the largest
possible value. In the regime $N_{A}=N_{\bar{A}}=N/2$, the lower bound of
average entropy reads $-\log(2d^{-1/2})=N/2-1$, which shows a constant
departure to the maximal possible value. This subtlety is also observed for
random stabilizer states [53], and Haar random states [54].

Moreover, we can apply the variance of the purity function $P_{A}$ to show the
typical behaviour. By Chebyshev inequality,

$\displaystyle\mathrm{Pr}\\{|P_{A}-\langle
P_{A}\rangle|>\varepsilon\\}\leq\frac{\delta^{2}(P_{A})}{\varepsilon^{2}}.$
(53)

and one can further obtain the following result on entanglement entropy.

######  Proposition 2.

For a subsystem $A$ with $N_{A}$ qubits, the probability of the entanglement
entropy deviation is upper bounded by

$\displaystyle\mathrm{Pr}\left\\{S_{2}(\rho_{A})\leq-\log_{2}\left(\frac{d_{A}+d_{\bar{A}}}{d}\right)-1.5\varepsilon
d_{A}\right\\}\leq\frac{\delta^{2}(P_{A})}{\varepsilon^{2}},$ (54)

where $d_{A(\bar{A})}=2^{N_{A(\bar{A})}}$ is the Hilbert space dimension of
the subsystem $A(\bar{A})$, and $\delta^{2}(P_{A})$ is the variance of the
subsystem purity $P_{A}$ of CZ or CCZ ensembles.

By Theorem 3 and Theorem 5, the variances
$\delta^{2}_{CZ}(P_{A})=\Theta(d^{-1})$ and
$\delta^{2}_{CCZ}(P_{A})=\Theta(d^{-2})$, no matter the relative size between
$N_{A}$ and $N_{\bar{A}}$. In the regime $d_{A}\ll d_{\bar{A}}$, one can
choose $\delta(P_{A})\ll\varepsilon\ll d_{A}^{-1}$ for both ensembles such
that the amount of the deviation, i.e., $1.5\varepsilon d_{A}$, from the
maximal entropy is negligible, and also the probability of this deviation
i.e., $\delta^{2}(P_{A})/\varepsilon^{2}$, is exponentially small with
respective to the qubit number $N$. As a result, one can further show
exponentially small variance of the entanglement entropy. We leave the proof
of Prop. 2 and the detailed discussion in App. F.1.

In the regime $d_{A}\simeq d_{\bar{A}}$ i.e., the subsystem size is comparable
$N_{\bar{A}}-N_{A}=O(\log(N))$, $d_{A}\sim d^{-\frac{1}{2}}$ now. The previous
argument can still apply for the CCZ ensemble, for example, by choosing
$d^{-1}\ll\varepsilon\sim d^{-\frac{3}{4}}\ll d^{-\frac{1}{2}}$ to make the
deviation and the corresponding probability both exponentially small. We
summarize the result for the equal partition for conciseness as follows.

######  Theorem 6.

Given a system of $N$-qubit with $N$ sufficient large, and the equal subsystem
size $N_{A}=N_{\bar{A}}$, for the random hypergraph states from the CCZ
ensemble, the probability of the entanglement entropy deviation is upper
bounded by

$\displaystyle\mathrm{Pr}\left\\{\left|S_{2}(\rho_{A})-\left(\frac{N}{2}-1\right)\right|\geq
1.6\varepsilon d^{\frac{1}{2}}\right\\}\leq\frac{4d^{-2}}{\varepsilon^{2}},$
(55)

where $d=2^{N}$ is the total Hilbert space dimension and
$d^{-1}\ll\varepsilon\ll d^{-\frac{1}{2}}$. Consequently, by taking
$\varepsilon\sim d^{-\frac{3}{4}}$, the variance of the entanglement entropy
with respective to the CCZ ensemble is bounded by

$\displaystyle\mathrm{Var}_{CCZ}[S_{2}(\rho_{A})]<1.6Nd^{-\frac{1}{2}}.$ (56)

The proof of Theorem 6 is left in App. F.2. It is not hard to see that such
exponentially small variance of entanglement entropy also holds for the half
CCZ ensemble, as the standard variance of purity is about
$\delta_{CCZ,h}(P_{A})\sim d^{-3/4}\ll d^{-1/2}$ in Theorem 4. We remark that
similar concentration of measure bound on entanglement entropy of Haar random
states is also shown in Ref. [54].

However, it is not applicable to the CZ ensemble now, since
$\delta_{CZ}(P_{A})=\Theta(d^{-1/2})$ and $d_{A}\sim d^{1/2}$, i.e., the
standard variance is comparable to the expectation value of purity $\langle
P_{A}\rangle\sim d^{-1/2}$ by Theorem 1. There is no room to choose a
appropriate $\varepsilon$ such that the deviation and the corresponding
probability in Eq. (54) both keep exponentially small. Especially in the equal
partition case, one thus expects a _constant_ variance of the entanglement
entropy, which is proved in the following Theorem.

######  Theorem 7.

Given a system of $N$-qubit with the equal subsystem size $N_{A}=N_{\bar{A}}$,
for the random graph states generated by random CZ gates, the variance of the
entanglement entropy

$\displaystyle\mathrm{Var}_{CZ}[S_{2}(\rho_{A})]>0.128,$ (57)

for sufficient large $N$.

The proof is based on the statistical result of the rank distribution for the
random binary matrix [55], and we leave it in App. F.3.

##  VI concluding remarks

In this work, we study the entanglement properties of random hypergraph states
generated by CZ and CCZ gates, respectively. We find that, though the average
subsystem purity and entanglement both feature the same volume law,
fluctuations of entanglement in the CZ ensemble are large, while the CCZ
ensemble shows typical values of entanglement with vanishing fluctuations.
These results show that, in spite of CCZ gates not being universal, they
feature universal entanglement behavior [51].

In perspective, there are several directions to explore starting from the
results presented here. First, one could study general hypergraph states with
$k>3$ edges using the phase matrix method here. The extension to more general
diagonal gates [5, 50, 56], qudit cases [57, 58] and mixed states [47, 59] are
also possible. Second, in this work we focus on the bipartite entanglement,
and it is interesting to study the tripartite and even complex entanglement
structure [60, 61] and entanglement distillation yield [47] of the random
hypergraph state, which would supply useful tools to quantum networks. Third,
the main difference between CCZ and CZ gates is that CCZ gates are non-
Clifford, and as such they can produce ‘magic’. The relationship between
fluctuations of the purity and magic has been shown in [51, 62]. On the other
hand, non-Clifford gates are involved in the onset of entanglement complexity
and emergent irreversibility in unitary evolution [19]. In this context, it
would be interesting to show the transition to quantum chaos behavior by
doping a CZ circuit with CCZ gates [63, 64, 51]. Moreover, it would thus be
very important to show that the fluctuations of the purity are directly
responsible for the onset of entanglement complexity and the impossibility of
undoing entanglement by Metropolis-like algorithms [19, 20]. For the same
reason, it would be interesting to study the behavior of (higher order) out-
of-time-order correlation functions [65, 17] under CZ and CCZ circuits, with
and without doping. Finally, it would be intriguing to see whether our
techniques here can be useful to study many-qubit magic states [66, 62].

##  VII acknowledgements

We thank Mile Gu, Xun Gao, Arthur Jaffe and Zhengwei Liu for the useful
discussions. Y.Z. is supported by the start-up funding of Fudan Univ., the
Quantum Engineering Program QEP-SF3, National Research Foundation of Singapore
under its NRF-ANR joint program (NRF2017-NRF-ANR004 VanQuTe), the Singapore
Ministry of Education Tier 1 grant RG162/19, FQXi-RFP-IPW-1903 from the
foundational Questions Institute and Fetzer Franklin Fund, a donor advised
fund of Silicon Valley Community Foundation. A.H. acknowledges support from
NSF award number 2014000. Any opinions, findings and conclusions or
recommendations expressed in this material are those of the author(s) and do
not reflect the views of the National Research Foundation, Singapore.

## References

  * Horodecki  _et al._ [2009] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Quantum entanglement, Rev. Mod. Phys. 81, 865 (2009).
  * Nielsen and Chuang [2011] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ , 10th ed. (Cambridge University Press, New York, NY, USA, 2011).
  * Amico  _et al._ [2008] L. Amico, R. Fazio, A. Osterloh, and V. Vedral, Entanglement in many-body systems, Rev. Mod. Phys. 80, 517 (2008).
  * Qi [2018] X.-L. Qi, Does gravity come from quantum information?, Nature Physics 14, 984 (2018).
  * Kruszynska and Kraus [2009] C. Kruszynska and B. Kraus, Local entanglability and multipartite entanglement, Phys. Rev. A 79, 052304 (2009).
  * Rossi  _et al._ [2013] M. Rossi, M. Huber, D. BruB, and C. Macchiavello, Quantum hypergraph states, New Journal of Physics 15, 113022 (2013).
  * Qu  _et al._ [2013] R. Qu, J. Wang, Z.-s. Li, and Y.-r. Bao, Encoding hypergraphs into quantum states, Phys. Rev. A 87, 022311 (2013).
  * Briegel and Raussendorf [2001] H. J. Briegel and R. Raussendorf, Persistent entanglement in arrays of interacting particles, Phys. Rev. Lett. 86, 910 (2001).
  * Hein  _et al._ [2006] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, and H. J. Briegel, Entanglement in Graph States and its Applications, arXiv e-prints , quant-ph/0602096 (2006), arXiv:quant-ph/0602096 [quant-ph] .
  * Miller and Miyake [2016] J. Miller and A. Miyake, Hierarchy of universal entanglement in 2d measurement-based quantum computation, npj Quantum Information 2, 1 (2016).
  * Miller and Miyake [2018] J. Miller and A. Miyake, Latent computational complexity of symmetry-protected topological order with fractional symmetry, Phys. Rev. Lett. 120, 170503 (2018).
  * Takeuchi  _et al._ [2019] Y. Takeuchi, T. Morimae, and M. Hayashi, Quantum computational universality of hypergraph states with pauli-x and z basis measurements, Scientific reports 9, 1 (2019).
  * Bremner  _et al._ [2016] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations, Phys. Rev. Lett. 117, 080501 (2016).
  * Gühne  _et al._ [2014] O. Gühne, M. Cuquet, F. E. Steinhoff, T. Moroder, M. Rossi, D. Bruß, B. Kraus, and C. Macchiavello, Entanglement and nonclassical properties of hypergraph states, Journal of Physics A: Mathematical and Theoretical 47, 335303 (2014).
  * Gachechiladze  _et al._ [2016] M. Gachechiladze, C. Budroni, and O. Gühne, Extreme violation of local realism in quantum hypergraph states, Phys. Rev. Lett. 116, 070401 (2016).
  * Levin and Gu [2012] M. Levin and Z.-C. Gu, Braiding statistics approach to symmetry-protected topological phases, Phys. Rev. B 86, 115109 (2012).
  * Yoshida [2016] B. Yoshida, Topological phases with generalized global symmetries, Phys. Rev. B 93, 155131 (2016).
  * Hamma  _et al._ [2005] A. Hamma, R. Ionicioiu, and P. Zanardi, Bipartite entanglement and entropic boundary law in lattice spin systems, Phys. Rev. A 71, 022315 (2005).
  * Chamon  _et al._ [2014] C. Chamon, A. Hamma, and E. R. Mucciolo, Emergent irreversibility and entanglement spectrum statistics, Phys. Rev. Lett. 112, 240501 (2014).
  * Shaffer  _et al._ [2014] D. Shaffer, C. Chamon, A. Hamma, and E. R. Mucciolo, Irreversibility and entanglement spectrum statistics in quantum circuits, Journal of Statistical Mechanics: Theory and Experiment 2014, P12007 (2014).
  * Yang  _et al._ [2017] Z.-C. Yang, A. Hamma, S. M. Giampaolo, E. R. Mucciolo, and C. Chamon, Entanglement complexity in quantum many-body dynamics, thermalization, and localization, Phys. Rev. B 96, 020408 (2017).
  * DiVincenzo  _et al._ [2002] D. P. DiVincenzo, D. W. Leung, and B. M. Terhal, Quantum data hiding, IEEE Transactions on Information Theory 48, 580 (2002).
  * Dankert  _et al._ [2009] C. Dankert, R. Cleve, J. Emerson, and E. Livine, Exact and approximate unitary 2-designs and their application to fidelity estimation, Physical Review A 80, 012304 (2009).
  * Collins and Nechita [2016] B. Collins and I. Nechita, Random matrix techniques in quantum information theory, Journal of Mathematical Physics 57, 015215 (2016).
  * Veitch  _et al._ [2012] V. Veitch, C. Ferrie, D. Gross, and J. Emerson, Negative quasi-probability as a resource for quantum computation, New Journal of Physics 14, 113011 (2012).
  * Veitch  _et al._ [2014] V. Veitch, S. H. Mousavian, D. Gottesman, and J. Emerson, The resource theory of stabilizer quantum computation, New Journal of Physics 16, 013009 (2014).
  * Hayden and Preskill [2007] P. Hayden and J. Preskill, Black holes as mirrors: quantum information in random subsystems, Journal of high energy physics 2007, 120 (2007).
  * Roberts and Yoshida [2017] D. A. Roberts and B. Yoshida, Chaos and complexity by design, Journal of High Energy Physics 2017, 1 (2017).
  * Ambainis and Emerson [2007] A. Ambainis and J. Emerson, Quantum t-designs: t-wise independence in the quantum world, in  _Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07)_ (IEEE, 2007) pp. 129–140.
  * Gross  _et al._ [2007] D. Gross, K. Audenaert, and J. Eisert, Evenly distributed unitaries: On the structure of unitary designs, Journal of mathematical physics 48, 052104 (2007).
  * Ghio  _et al._ [2017] M. Ghio, D. Malpetti, M. Rossi, D. Bruß, and C. Macchiavello, Multipartite entanglement detection for hypergraph states, Journal of Physics A: Mathematical and Theoretical 51, 045302 (2017).
  * Chen and Wang [2014] X.-y. Chen and L. Wang, Locally inequivalent four-qubit hypergraph states, Journal of Physics A: Mathematical and Theoretical 47, 415304 (2014).
  * Gachechiladze  _et al._ [2017] M. Gachechiladze, N. Tsimakuridze, and O. Gühne, Graphical description of unitary transformations on hypergraph states, Journal of Physics A: Mathematical and Theoretical 50, 19LT01 (2017).
  * Tsimakuridze and Gühne [2017] N. Tsimakuridze and O. Gühne, Graph states and local unitary transformations beyond local clifford operations, Journal of Physics A: Mathematical and Theoretical 50, 195302 (2017).
  * Lyons  _et al._ [2015] D. W. Lyons, D. J. Upchurch, S. N. Walck, and C. D. Yetter, Local unitary symmetries of hypergraph states, Journal of Physics A: Mathematical and Theoretical 48, 095301 (2015).
  * Morimae  _et al._ [2017] T. Morimae, Y. Takeuchi, and M. Hayashi, Verification of hypergraph states, Physical Review A 96, 062321 (2017).
  * Zhu and Hayashi [2019] H. Zhu and M. Hayashi, Efficient verification of hypergraph states, Physical Review Applied 12, 054047 (2019).
  * Collins  _et al._ [2010] B. Collins, I. Nechita, and K. Życzkowski, Random graph states, maximal flow and fuss–catalan distributions, Journal of Physics A: Mathematical and Theoretical 43, 275303 (2010).
  * Gottesman [1998] D. Gottesman, The heisenberg representation of quantum computers, arXiv preprint quant-ph/9807006 (1998).
  * Shi [2002] Y. Shi, Both toffoli and controlled-not need little help to do universal quantum computation, arXiv preprint quant-ph/0205115 (2002).
  * Islam  _et al._ [2015] R. Islam, R. Ma, P. M. Preiss, M. Eric Tai, A. Lukin, M. Rispoli, and M. Greiner, Measuring entanglement entropy in a quantum many-body system, Nature 528, 77 (2015).
  * Brydges  _et al._ [2019] T. Brydges, A. Elben, P. Jurcevic, B. Vermersch, C. Maier, B. P. Lanyon, P. Zoller, R. Blatt, and C. F. Roos, Probing rényi entanglement entropy via randomized measurements, Science 364, 260 (2019), https://science.sciencemag.org/content/364/6437/260.full.pdf .
  * Hamma  _et al._ [2012a] A. Hamma, S. Santra, and P. Zanardi, Quantum entanglement in random physical states, Phys. Rev. Lett. 109, 040502 (2012a).
  * Low [2010] R. A. Low, Pseudo-randomness and learning in quantum computation, arXiv preprint arXiv:1006.5227 (2010).
  * Tóth and García-Ripoll [2007] G. Tóth and J. J. García-Ripoll, Efficient algorithm for multiqudit twirling for ensemble quantum computation, Phys. Rev. A 75, 042311 (2007).
  * Zyczkowski and Sommers [2001] K. Zyczkowski and H.-J. Sommers, Induced measures in the space of mixed quantum states, Journal of Physics A: Mathematical and General 34, 7111 (2001).
  * Smith and Leung [2006] G. Smith and D. Leung, Typical entanglement of stabilizer states, Phys. Rev. A 74, 062314 (2006).
  * Zhu  _et al._ [2016] H. Zhu, R. Kueng, M. Grassl, and D. Gross, The clifford group fails gracefully to be a unitary 4-design, arXiv preprint arXiv:1609.08172 (2016).
  * Nakata  _et al._ [2014] Y. Nakata, M. Koashi, and M. Murao, Generating a statet-design by diagonal quantum circuits, New Journal of Physics 16, 053043 (2014).
  * Nakata and Murao [2014] Y. Nakata and M. Murao, Diagonal quantum circuits: Their computational power and applications, The European Physical Journal Plus 129, 152 (2014).
  * Leone  _et al._ [2021a] L. Leone, S. F. E. Oliviero, Y. Zhou, and A. Hamma, Quantum Chaos is Quantum, Quantum 5, 453 (2021a).
  * Hamma  _et al._ [2012b] A. Hamma, S. Santra, and P. Zanardi, Ensembles of physical states and random quantum circuits on graphs, Phys. Rev. A 86, 052324 (2012b).
  * Dahlsten and Plenio [2005] O. Dahlsten and M. B. Plenio, Exact entanglement probability distribution of bi-partite randomised stabilizer states, arXiv preprint quant-ph/0511119 (2005).
  * Hayden  _et al._ [2006] P. Hayden, D. W. Leung, and A. Winter, Aspects of generic entanglement, Communications in mathematical physics 265, 95 (2006).
  * Kolchin [1998] V. F. Kolchin,  _Random Graphs_, Encyclopedia of Mathematics and its Applications (Cambridge University Press, 1998).
  * Iaconis [2021] J. Iaconis, Quantum state complexity in computationally tractable quantum circuits, PRX Quantum 2, 010329 (2021).
  * Steinhoff  _et al._ [2017] F. E. Steinhoff, C. Ritz, N. Miklin, and O. Gühne, Qudit hypergraph states, Physical Review A 95, 052340 (2017).
  * Xiong  _et al._ [2018] F.-L. Xiong, Y.-Z. Zhen, W.-F. Cao, K. Chen, and Z.-B. Chen, Qudit hypergraph states and their properties, Physical Review A 97, 012323 (2018).
  * Wu  _et al._ [2014] J.-Y. Wu, M. Rossi, H. Kampermann, S. Severini, L. C. Kwek, C. Macchiavello, and D. Bruß, Randomized graph states and their entanglement properties, Physical Review A 89, 052335 (2014).
  * Guhne  _et al._ [2005] O. Guhne, G. Toth, and H. J. Briegel, Multipartite entanglement in spin chains, New Journal of Physics 7, 229 (2005).
  * Zhou  _et al._ [2019] Y. Zhou, Q. Zhao, X. Yuan, and X. Ma, Detecting multipartite entanglement structure with minimal resources, npj Quantum Information 5, 1 (2019).
  * Leone  _et al._ [2021b] L. Leone, S. F. Oliviero, and A. Hamma, R$\backslash$’enyi entropy of magic (2021b), arXiv:2106.12587 [quant-ph] .
  * Zhou  _et al._ [2020] S. Zhou, Z. Yang, A. Hamma, and C. Chamon, Single t gate in a clifford circuit drives transition to universal entanglement spectrum statistics, SciPost Physics 9, 087 (2020).
  * Haferkamp  _et al._ [2020] J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, and I. Roth, Quantum homeopathy works: Efficient unitary designs with a system-size independent number of non-clifford gates, arXiv preprint arXiv:2002.09524 (2020).
  * Shenker and Stanford [2014] S. H. Shenker and D. Stanford, Multiple shocks, Journal of High Energy Physics 2014, 10.1007/jhep12(2014)046 (2014).
  * Liu and Winter [2020] Z.-W. Liu and A. Winter, Many-body quantum magic (2020), arXiv:2010.13817 [quant-ph] .
  * Hein  _et al._ [2004] M. Hein, J. Eisert, and H. J. Briegel, Multiparty entanglement in graph states, Phys. Rev. A 69, 062311 (2004).

##  Appendix A The relation between $M_{s}$ and $\Phi_{\mathcal{E}_{e}}^{k}$

In main text, we use the summation matrix (tensor) $M_{s}$ to account for the
effect of the local twirling channel $\Phi_{\mathcal{E}_{e}}^{k}$, with $k=2$
and $4$ for the average purity and the variance respectively. Here we clarify
the relation between $M_{s}$ and $\Phi_{\mathcal{E}_{e}}^{k}$ in detail by
considering the example for $k=2$ and the random CZ gate. The argument applies
to other cases.

Recall in Fig. 2 (c) in main text, the formula of average purity has been
vectorized. The input state is $\ket{+}^{\otimes 2N}$ which can exhaust all
the computational basis input. The matrix representation of the twirling
channel $\tilde{\Phi}_{\mathcal{E}}^{2}$ is diagonal in the computational
basis. And it can be decomposed to local twirling channels
$\tilde{\Phi}_{\mathcal{E}_{e}}^{2}$, with $e$ for a specific edge
$e=\\{i,j\\}$, by Prop. 1. The tensor diagram is shown in Fig. 8, which is the
average of the two possibilities $CZ_{e}$ and $\mathbb{I}_{e}$. Every line can
take take $0/1$, and thus $\tilde{\Phi}_{\mathcal{E}_{e}}^{2}$ is $8\times 8$
diagonal matrix. To get $\tilde{\Phi}_{\mathcal{E}_{e}}^{2}$, one just needs
to figure out $8$ diagonal elements there.

Figure 8: Tensor network for the matrix form of the local twirling channel
$\tilde{\Phi}_{\mathcal{E}_{e}}^{2}$

Actually, for the average purity we consider, one needs not to figure out all
of them. The vectorized swap and identity operators on the left in Fig. 2 (c)
further restrict the possible computational basis input. As illustrated in
Fig. 3 (a), the 4 bits on the line of $i$ and $i^{\prime}$ which correspond to
qubit-$i$ will be reduced to 2 bits, similar to the qubit-$j$.

By further taking $i,i^{\prime}$ as the row index, and $j,j^{\prime}$ as the
column index, we reach the phase matrix in Fig. 3 (b) and also the summation
matrix $M_{s}$ in Eq. (13).

##  Appendix B The difference between $\mathbb{E}_{\Psi}(P_{A}^{2})$ and
$[\mathbb{E}_{\Psi}(P_{A})]^{2}$ in the view of phase matrix

Figure 9: Tensor network for $[\mathbb{E}_{\Psi}(P_{A})]^{2}$ and the phase
matrix.

The difference of $\mathbb{E}_{\Psi}(P_{A}^{2})$ and
$[\mathbb{E}_{\Psi}(P_{A})]^{2}$ is the variance in Eq. (5). Here we
illustrate the difference with phase matrix formalism in detail, which can
simplify the counting procedure of the surviving bit-strings when calculating
the variance.

By doubling Eq. (6), let us write down $[\mathbb{E}_{\Psi}(P_{A})]^{2}$
explicitly on 4-copy Hilbert space $\mathcal{H}^{\otimes 4}$ as

$\displaystyle\left[\mathbb{E}_{\Psi}(P_{A})\right]^{2}$
$\displaystyle=\mathrm{Tr}\left[T_{A}\otimes\mathbb{I}_{\bar{A}}^{\otimes 2}\
\Phi_{\mathcal{E}}^{2}\left(\Psi_{0}^{\otimes 2}\right)\right]^{2}$ (58)
$\displaystyle=\mathrm{Tr}\left[T^{(1,2)}_{A}\otimes
T^{(3,4)}_{A}\otimes\mathbb{I}_{\bar{A}}^{\otimes
4}\quad\Phi_{\mathcal{E}}^{2}\otimes\Phi_{\mathcal{E}}^{2}\left(\Psi_{0}^{\otimes
4}\right)\right].$

Compared with $\mathbb{E}_{\Psi}(P_{A}^{2})$ in Eq. (24), the input state
$\Psi_{0}^{\otimes 4}$ and the swap/identity operators are the same, and the
only difference is the twirling channel in the middle. In particular, one is
$\Phi_{\mathcal{E}}^{2}\otimes\Phi_{\mathcal{E}}^{2}$, where the first 2-copy
and the last 2-copy are independently twirled and the other is
$\Phi_{\mathcal{E}}^{4}$, with 4-copy twirled together. Similar as the proof
for Prop. 1, $\Phi_{\mathcal{E}}^{2}\otimes\Phi_{\mathcal{E}}^{2}$ can also be
decomposed to the local twirling channel on a specific edge
$\Phi_{\mathcal{E}_{e}}^{2}\otimes\Phi_{\mathcal{E}_{e}}^{2}$.

In the following, we use CZ ensemble to illustrate the difference of these two
twirling channels, in term of the phase matrix. The result on CCZ ensemble
follows similarly. Similar as Fig. 7 (a) of $\mathbb{E}_{\Psi}(P_{A}^{2})$, we
can draw the tensor network diagram of
$\left[\mathbb{E}_{\Psi}(P_{A})\right]^{2}$ of Eq. (58) in Fig. 9 (a). On the
right, every qubit corresponds to 8 lines, each 2 for one-copy Hilbert space.
Every line can take can take one bit $0/1$ value with a normalization constant
in Eq. (26). On the left, there are two different connections for each qubit
by decomposing the swap $T^{(1,2)}_{A}\otimes T^{(3,4)}_{A}$ and the identity
$\mathbb{I}^{\otimes 4}_{\bar{A}}$ to the qubit level. The difference is in
the middle, where we operate the random $CZ_{e}$ gate across $A$ and
$\bar{A}$, and we show case of the gates between $i$ and $j$. Note that two
different colors (blue and green) are used to denote the independence of the
CZ gates on the first 2-copy and the last 2-copy.

In Fig. 9 (b), we rotate the diagram to compare it with the previous phase
matrix in Fig. 7 (b), where the CZ gate repeats 8 times. Similar as the
discussion Sec. IV.1, every qubit-i is denoted by 4-bit and further by 2-bit
$i_{1}i_{2}$ with logical encoding. Now the constraints between any qubit pair
$i,j$ across $A,\bar{A}$ becomes

$\displaystyle\bra{\mathbf{i_{1}}}\bra{\mathbf{i_{2}}}M_{s}\otimes
M_{s}\ket{\mathbf{j_{1}}}\ket{\mathbf{j_{2}}}$ (59) $\displaystyle=$
$\displaystyle\bra{\mathbf{i_{1}}}\bra{\mathbf{i_{2}}}\frac{M_{p}+J_{2}}{2}\otimes\frac{M_{p}+J_{2}}{2}\ket{\mathbf{j_{1}}}\ket{\mathbf{j_{2}}}$

with $M_{s}$ and $M_{p}$ defined in Eq. (14) and (15). That is,

$\displaystyle\bra{\mathbf{i_{1}}}M_{p}\ket{\mathbf{j_{1}}}=1,\
\bra{\mathbf{i_{2}}}M_{p}\ket{\mathbf{j_{2}}}=1.$ (60)

On the other hand, the phase matrix of Eq. (27) in Fig. 7 (b) induces
constraint as

$\displaystyle\bra{\mathbf{i_{1}}}\bra{\mathbf{i_{2}}}\frac{M_{p}^{\otimes
2}+J_{4}}{2}\ket{\mathbf{j_{1}}}\ket{\mathbf{j_{2}}},$ (61)

i.e.,

$\displaystyle\bra{\mathbf{i_{1}}}M_{p}\ket{\mathbf{j_{1}}}*\bra{\mathbf{i_{2}}}M_{p}\ket{\mathbf{j_{2}}}=1$
(62)

Compared with Eq. (60), this constraint is loose. That is, any bit-string
configuration satisfies Eq. (60) also survives here, which leads to
$\delta^{2}=\mathbb{E}_{\Psi}(P_{A}^{2})-\left[\mathbb{E}_{\Psi}(P_{A})\right]^{2}\geq
0$, a non-negative variance. As a result, to calculate $\delta^{2}$, one only
needs to count the net number of bit-strings which satisfy Eq. (62), but not
Eq. (60). That is, for a bit-string configuration, there exists qubit-pair
$i,j$, such that $\bra{\mathbf{i_{1}}}M_{p}\ket{\mathbf{j_{1}}}=-1$ and
$\bra{\mathbf{i_{2}}}M_{p}\ket{\mathbf{j_{2}}}=-1$.

##  Appendix C Proof of Lemma 1

###### Proof.

To satisfy the inner product on the binary field, generally one can not assign
the same binary vector $\vec{v}$ with an odd hamming weight (the number of
$1$s), denoted by $w_{2}(\vec{v})=1$, to more than one position, since the
inner product $\vec{v}\cdot\vec{v}=1$ in this case.

First, we give explicit assignments, with $\vec{v}$ only owning a even Hamming
weight $w_{2}(\vec{v})=0$. There are totally eight ones, and they can be
divided into three sets, each with four elements, i.e.,

$\displaystyle\\{0000,0011,1100,1111\\},\\{0000,0101,1010,1111\\},$ (63)
$\displaystyle\\{0000,0110,1001,1111\\}.$

It is easy to check that the inner product between the elements (also with
itself) inside each set is $0$. As a result, one can randomly assign bit-
string from any of three sets to the $m$ positions which satisfies the inner
product constraint. This gives $3*4^{m}-2*2^{m}$, where $2^{m}$ accounts for
the redundant counting of the case by only assigning bit-string from the set
$\\{0000,1111\\}$.

Furthermore, we consider adding $\vec{v}$ with $w_{2}(\vec{v})=1$ to the
previous assignments. For a given $\vec{v}$, as mentioned before, it can only
appear in the $m$ position once. At the same time, the subsequent assignment
of $\vec{v}^{\prime}$ with $w_{2}(\vec{v}^{\prime})=0$ is restricted. In
particular, besides $\vec{v}^{\prime}=0000$, one can only choose one element
in each set in Eq. (63), due to the inner product constraint. For example,
suppose $\vec{v}=1000$, we can only choose $\vec{v}_{1}^{\prime}=0011$,
$\vec{v}_{2}^{\prime}=0101$ and $\vec{v}_{3}^{\prime}=0110$ besides $0000$.
Note that one can not choose any two of them
$\vec{v}_{1}^{\prime},\vec{v}_{2}^{\prime},\vec{v}_{3}^{\prime}$ in the same
time since the inner product between them is 1. Consequently, the number of
all possible assignments containing exact one element $\vec{v}$ with
$w_{2}(\vec{v})=1$ is

$C_{8}^{1}A_{m}^{1}*3*2^{m-1}=12m2^{m}$

where $C_{8}^{1}A_{m}^{1}$ represents choosing one $\vec{v}$ from total 8 odd-
weight bit-strings and putting it in one of the $m$ positions; $3*2^{m-1}$
represents assigning bit-string to other $m-1$ positions from
$\\{0000,\vec{v}_{i}^{\prime}\\}$ for $i=1,2,3$.

We can continue this process by considering more than one odd-weight bit-
string in the $m$ positions. In fact, this process can at most goes to four
odd-weight bit-strings. To be specific, suppose one choose four distinct odd-
weight strings, $\vec{v}_{1},\vec{v}_{2},\vec{v}_{3},\vec{v}_{4}$, which are
orthogonal to each other, they already form a complete basis of
$\mathbb{F}_{2}^{4}$. Consequently, there is no bit-string $v_{5}$ besides the
trivial $0000$ such that the inner products of $v_{5}$ with $v_{i},1\leq i\leq
4$ are all zero. For this case of four odd-weight strings, one can only assign
$0000$ to other $m-4$ position. Totally $56A_{m}^{4}$.

Similar argument also holds for the case of three odd-weight strings, for
example, $\vec{v}_{1}=1000,\vec{v}_{2}=0100,\vec{v}_{3}=0010$. One can not
find a even-weight string $\vec{v}^{\prime}$ orthogonal to all of them.
Totally $8A_{m}^{3}$. For the case of two odd-weight strings, it depends on
the specific choose. For example, if one select
$\vec{v}_{1}=1000,\vec{v}_{2}=0111$, there are 3 legal even-weight strings
besides $0000$, same as the one odd-weight string case; if
$\vec{v}_{1}=1000,\vec{v}_{2}=0100$, there is only one nontrivial string
$\vec{v}^{\prime}=0011$. As a result, totally
$(C_{4}^{1}*3+C_{4}^{2}*2)A_{m}^{2}2^{m-2}$.

In summary, the number of all possible assignments is obtained by summing
these numbers of all possible assignments

$\displaystyle\\#_{4}$
$\displaystyle=3*4^{m}-2*2^{m}+12m2^{m}+24A_{m}^{2}2^{m-2}+8A_{m}^{3}+56A_{m}^{4}$
(64)
$\displaystyle=3*4^{m}+(6m^{2}+6m-2)2^{m}+4A_{m}^{2}+8A_{m}^{3}+56A_{m}^{4}$
$\displaystyle=3*4^{m}+\Theta(m^{2})2^{m}+\Theta(m^{4})$

and finish the proof.

∎

##  Appendix D Proof of Corollary 1 for $N_{A}$ qubits in subsystem $A$.

Here we prove Corollary 1 for the general qubit number in $A$. As mentioned in
main text, the variance of the purity for the full CCZ ensemble can be upper
bounded by

$\displaystyle\delta^{2}_{CCZ}$ $\displaystyle<\langle
P_{A}^{2}\rangle_{CCZ,h}-\langle P_{A}\rangle_{CCZ}^{2}$ (65)
$\displaystyle=\langle P_{A}^{2}\rangle_{CCZ,h}-\langle
P_{A}\rangle_{CCZ,h}^{2}+\langle P_{A}\rangle_{CCZ,h}^{2}-\langle
P_{A}\rangle_{CCZ}^{2}$ $\displaystyle=\delta^{2}_{CCZ,h}+\langle
P_{A}\rangle_{CCZ,h}^{2}-\langle P_{A}\rangle_{CCZ}^{2}$

By inserting the results in Eq. (21), (22) and (46), one has

$\displaystyle\delta^{2}_{CCZ}$
$\displaystyle<\frac{9d_{A}}{d^{2}}+3\frac{d_{A}+d_{\bar{A}}-1}{d}*\frac{d_{A}(d_{A}-1)N_{\bar{A}}({N_{\bar{A}}}+1)}{d^{2}}$
(66)
$\displaystyle<\frac{9d_{A}}{d^{2}}+\frac{6d_{\bar{A}}}{d}*\frac{d_{A}^{2}N_{\bar{A}}({N_{\bar{A}}}+1)}{d^{2}}$
$\displaystyle=\frac{d_{A}}{d^{2}}[9+6N_{\bar{A}}({N_{\bar{A}}}+1)]<3N^{2}d^{-1.5}.$

by using the fact that $N_{A}\leq N_{\bar{A}}$ and $d_{A}\leq d_{\bar{A}}$.

##  Appendix E Proof of Th. 5

Here we prove a tighter result for the variance of the purity of the full CCZ
ensemble by counting the total surviving bit-strings. Similar as the average
purity scenario in Sec. III.3, the further introduction of the random gates
$CCZ_{ijk}$ with $i,j\in A,k\in\bar{A}$ will induce more constraints on the
bit configuration back from $\bar{A}$ to $A$. In particular, similar as Eq.
(32) in Fig. 7 (c), the phase tensor follows directly by the tensor product of
the one in Fig. 4 (c),
$\tilde{M}_{ijk}^{p}=\tilde{M}_{i_{1}j_{1}k_{1}}^{p}\otimes\tilde{M}_{i_{2}j_{2}k_{2}}^{p}$,
and it equals $M_{kij}^{p}$ by Fig. 4 (d).

In the following, we follows the cases 1 to 42 of the half CCZ ensemble in
Sec. IV.2, and use the phase tensor to apply additional constraints from
$\bar{A}$ to $A$. Remembering in the discussion on the half CCZ ensemble in
Sec. IV.2, only the case 42 can contain bit-strings surviving in the formula
of $\mathbb{E}_{\Psi}(P_{A}^{2})$ but not in the one of
$[\mathbb{E}_{\Psi}(P_{A})]^{2}$, which account for the final variance (see
also the illustration in App. B). For completeness, here we list all the
possible bit-stings, but finally we will only count the one that contributes
to the net variance.

  1. 1.

$A$ only contains $\bar{00}$, $\bar{A}$ can be arbitrary, and vice versa.
Totally $(4^{N_{A}}+4^{N_{\bar{A}}}-1)4^{N}$ with $4^{N}$ for the logical
encoding.

  2. 2.

$A$ only contains $\bar{00}$ and $\bar{01}$. The first two-bit of qubit in
$\bar{A}$ can be arbitrary, and the last two should be restricted. We consider
several possibilities for the last two-bit.

     * a.

If they all take $\bar{0}$, it will not induce any constraint backwards on
$A$, thus $(2^{N_{A}}-1)*(2^{N_{\bar{A}}}-1)4^{N}$.

     * b.

For the case there is one $01(10)$ or two of $01,10$, it means logical
$\bar{1}$ on the last 2-bit. As a result, it further induces constraint on the
last 2-bit of the qubits in $A$, i.e., the logical $\bar{01}$ there. Similar
as case 39 in Sec. IV.2, one has totally
$2^{N_{A}}N_{A}(N_{A}+1)*4^{N_{\bar{A}}}N_{\bar{A}}(N_{\bar{A}}+1)$.

Same result holds for $A$ only containing $\bar{00}$ and $\bar{10}$ by
symmetry.

  3. 3.

$A$ contains at least two types from $\\{\bar{01},\bar{10},\bar{11}\\}$. For
the qubit in $\bar{A}$, both the first two and last two-bit are constrained
independently. Previously there are totally
$4^{N_{A}}\left[4^{N_{A}}-3(2^{N_{A}}-1)-1\right]\left[2^{N_{\bar{A}}}+N_{\bar{A}}(N_{\bar{A}}+1)\right]^{2}$
bit-strings. The first term is for possibilities of $A$, and the second one is
for $\bar{A}$. Since now different bit configurations induce different
constraints backwards on $A$, we discuss the terms in
$\left[2^{N_{\bar{A}}}+N_{\bar{A}}(N_{\bar{A}}+1)\right]^{2}$ separately.

     * a.

$2^{N_{\bar{A}}}*2^{N_{\bar{A}}}$. This term corresponds to that all bit-
strings take $\bar{00}$ in $\bar{A}$, which has already been counted in case
1.

     * a.

$2*2^{N_{\bar{A}}}N_{\bar{A}}(N_{\bar{A}}+1)$. This term corresponds to the
first 2-bits of all qubits in $\bar{A}$ take $\bar{0}$, and the last 2-bits
take one $01(10)$ or two of $01,10$, or vice versa. For the first case, there
is logical $\bar{1}$ on the last 2-bit and thus it induces constraint on the
logical $\bar{01}$ and $\bar{11}$ in $A$. The number of the possibilities in
$A$ reduces from $4^{N_{A}}\left[4^{N_{A}}-3(2^{N_{A}}-1)-1\right]$ to
$[4(2^{N_{A}-1}-1)C_{N_{A}}^{1}+4(2^{N_{A}-2}-1)C_{N_{A}}^{2}+4(2^{N_{A}-2})C_{N_{A}}^{2}]*2^{N_{A}}\sim\Theta(N_{A}^{2})4^{N_{A}}$.

     * c.

$N_{\bar{A}}^{2}({N_{\bar{A}}}+1)^{2}$. This term corresponds to the case that
both the first 2-bits and the last 2-bits of the qubits in $\bar{A}$ can take
logical $\bar{1}$. There are a few of different induced constraints on $A$
based on the specific bit configurations, and we will figure out the updated
number of surviving bit-strings, denoted by $n_{3c}$, later.

  4. 4.

$A$ only contains $\bar{00}$ and $\bar{11}$. For the qubit in $\bar{A}$, both
the first and the last two-bit are restricted jointly. The summation tensor is
given in Eq. (38), and previously there are
$4^{N_{A}}(2^{N_{A}}-1)*\\#_{4}(m=N_{\bar{A}})$ surviving bit-strings with
$\\#4$ in Eq. (44) by taking $m=N_{\bar{A}}$. Different choices of bit-strings
from $\\#4$, which is detailed in App. C, will induce different constraints
backwards on $A$. We denote the updated number of surviving bit-strings as
$n_{4}$ and figure out it later.

To calculate the variance, one should in principle get
$\mathbb{E}_{\Psi}(P_{A}^{2})$ by summing all the numbers of the above
possibilities in cases 1 to 4, and normalizing it with the constant in Eq.
(26). As discussed before, there are actually only a few bit-strings
contributing to the final variance, since many of them in the above cases also
survive in the formula of $[\mathbb{E}_{\Psi}(P_{A})]^{2}$. In particular, it
is not hard to check that only the above case c. (c) and case 4 can contain
this kind of ‘genuine’ bit-strings. As a result, one has the upper bound on
the variance

$\displaystyle\delta^{2}_{CCZ}<(n_{3c}+n_{4})d^{-4}.$ (67)

Let us first figure out $n_{4}$ in case 4, by checking all the possible bit-
strings in $\bar{A}$, described by $\\#4$ shown explicitly in App. C. First,
we are interested in the leading order in $\\#_{4}$, that is, the
configuration from the three even-hamming-weight sets shown in Eq. (63). Note
that the first set corresponds to all $\bar{00}$ case, which has been already
counted in case 1. The last two sets both correspond to $\bar{00},\bar{11}$,
and thus induce constraint backwards on $A$, which is described by the
summation tensor in Eq. (38), or more explicitly by Eq. (42) with $j,k\in A$
now. Just as the previous constraint from $A$ to $\bar{A}$, the number of
legal bit configuration in $A$ is $2*4^{N_{A}}-2^{N_{A}}$, where we can only
choose the last two sets in Eq. (63) now for $A$. Second, for the bit
configuration with a few odd-hamming-weight bit-strings, there is $\bar{01}$
or $\bar{10}$ appearing in $\bar{A}$. For example, if there is $\bar{10}$ in
$\bar{A}$, the first 2-bit on the logical $\bar{00}$ and $\bar{11}$ in $A$
will be restricted, and there are $2^{N_{A}}N_{A}(N_{A}+1)$ possibilities, and
this number can further decrease to $\Theta(N_{A}^{2})$ if there is also
constraint on the last 2-bit. As a result, the number is case 4 is bounded by

$\displaystyle n_{4}<$
$\displaystyle(2*4^{N_{A}}-2^{N_{A}})(2*4^{N_{\bar{A}}}-2^{N_{\bar{A}}})+2^{N_{A}}N_{A}(N_{A}+1)*\Theta(N_{\bar{A}}^{2})2^{N_{\bar{A}}}$
(68) $\displaystyle=$ $\displaystyle
4d^{2}-2(d_{A}+d_{\bar{A}})d+\Theta(N_{A}^{2}N_{\bar{A}}^{2})d.$

Similarly, one can consider the bit-strings in case c. (c). For previous total
$N_{\bar{A}}^{2}({N_{\bar{A}}}+1)^{2}$ bit configurations,
$2N_{\bar{A}}({N_{\bar{A}}}+1)$ of them correspond to $\bar{A}$ only
containing $\bar{00},\bar{11}$. In this case, by following case 4, the number
of possibilities on $A$ is upper bounded by the odd-hamming weight cases in
$\\#4(m=N_{A})$, since the precondition is that $A$ has two types from
$\\{\bar{01},\bar{10},\bar{11}\\}$. For the other cases, $\bar{A}$ contains
two types from $\\{\bar{01},\bar{10},\bar{11}\\}$. One can directly follows
case c. (c), and the possibilities in $A$ is thus bounded by
$N_{A}^{2}({N_{A}}+1)^{2}$. As a result, one has

$\displaystyle n_{3c}$
$\displaystyle=\Theta(N_{A}^{2})2^{N_{A}}\Theta(N_{\bar{A}}^{2})+\Theta(N_{A}^{4})\Theta(N_{\bar{A}}^{4})$
(69) $\displaystyle=\Theta(N_{A}^{2}N_{\bar{A}}^{2})d_{A}.$

Inserting Eq. (68) and (69) into Eq. (67), one has

$\displaystyle\delta^{2}_{CCZ}<4d^{-2}-2(d_{A}+d_{\bar{A}})d^{-3}+\Theta(N_{A}^{2}N_{\bar{A}}^{2})d^{-3}.$
(70)

In addition, by observing that the configurations in the first term of Eq.
(68), that is,
$(2*4^{N_{A}}-2^{N_{A}})(2*4^{N_{\bar{A}}}-2^{N_{\bar{A}}})+2^{N_{A}}N_{A}(N_{A}+1)$
are all genuine ones. Consequently, one also has

$\displaystyle\delta^{2}_{CCZ}>4d^{-2}-2(d_{A}+d_{\bar{A}})d^{-3}.$ (71)

and we finish the proof. We remark that the more exact value of the variance
is

$\displaystyle\delta^{2}_{CCZ}=4d^{-2}-2(d_{A}+d_{\bar{A}})d^{-3}+\Theta(N_{A}^{2}N_{\bar{A}}^{2})(d_{A}+d_{\bar{A}})d^{-4}.$
(72)

by counting the genuine configurations in $n_{3c}$ and $n_{4}$ more carefully.
Since it shares the leading and sub-leading terms with Eq. (49), we do not
elaborate it here.

##  Appendix F On the fluctuation of the entanglement entropy

###  F.1 Proof of Prop. 2 and discussion on the variance

Here we first prove the deviation probability of Prop. 2 in main text, and
discuss the implication on the variance of the entanglement entropy. Hereafter
for simplicity the $\log$ function is base 2 without clarification.

###### Proof.

The probability of the entanglement entropy deviation can be bounded by
Chebyshev inequality,

$\displaystyle\mathrm{Pr}\\{-\log(P_{A})\leq-\log(\langle
P_{A}\rangle+\varepsilon)\\}=\mathrm{Pr}\\{P_{A}-\langle
P_{A}\rangle\geq\varepsilon\\}\leq\mathrm{Pr}\\{|P_{A}-\langle
P_{A}|\rangle\geq\varepsilon\\}\leq\frac{\delta^{2}(P_{A})}{\varepsilon^{2}}.$
(73)

The average purity $\langle P_{A}\rangle\leq\frac{d_{A}+d_{\bar{A}}}{d}$ for
both ensembles by Theorem 1 and 2, and one has

$\displaystyle-\log(\langle
P_{A}\rangle+\varepsilon)\geq-\log\left(\frac{d_{A}+d_{\bar{A}}}{d}+\varepsilon\right)$
$\displaystyle=-\log\left(\frac{d_{A}+d_{\bar{A}}}{d}\right)-\log\left(1+\frac{\varepsilon
d}{d_{A}+d_{\bar{A}}}\right)$ (74)
$\displaystyle\geq-\log\left(\frac{d_{A}+d_{\bar{A}}}{d}\right)-\frac{\log(e)\varepsilon
d}{d_{A}+d_{\bar{A}}}\geq-\log\left(\frac{d_{A}+d_{\bar{A}}}{d}\right)-1.5\varepsilon
d_{A}.$

where in the last-but-one inequality we use $\log_{2}(1+x)\leq\log_{2}(e)x$.
Substituting $-\log(\langle P_{A}\rangle+\varepsilon)$ in Eq. (73) with the
lower bound in Eq. (74), we finish the proof. ∎

As mentioned in main text, we can use the deviation probability in Prop. 2 to
bound the variance of the entanglement entropy. Denote
$\Delta=\frac{d_{A}+d_{\bar{A}}}{d}$, one bounds the variance by the
expectation for the square of the difference to the maximal possible entropy
$\log(d_{A})=N_{A}$.

$\displaystyle\mathrm{Var}[S_{2}(\rho_{A})]=$
$\displaystyle\mathbb{E}_{\Psi}\left[S_{2}(\rho_{A})-\langle
S_{2}(\rho_{A})\rangle\right]^{2}$ (75) $\displaystyle\leq$
$\displaystyle\mathbb{E}_{\Psi}\left[\log(d_{A})-S_{2}(\rho_{A})\right]^{2}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\\{\Psi|S_{2}(\rho_{A})\leq-\log(\Delta)-\log(e)\varepsilon
d_{A}\\}}\left[\log(d_{A})-S_{2}(\rho_{A})\right]^{2}+\mathbb{E}_{\\{\Psi|S_{2}(\rho_{A})>-\log(\Delta)-\log(e)\varepsilon
d_{A}\\}}\left[\log(d_{A})-S_{2}(\rho_{A})\right]^{2}$ $\displaystyle\leq$
$\displaystyle N_{A}^{2}\
\mathrm{Pr}\left\\{S_{2}(\rho_{A})\leq-\log(\Delta)-\log(e)\varepsilon
d_{A}\right\\}+\left[\log(d_{A})+\log(\Delta)+\log(e)\varepsilon
d_{A}\right]^{2}$ $\displaystyle\leq$ $\displaystyle
N^{2}\frac{\delta^{2}(P_{A})}{\varepsilon^{2}}+\log^{2}(e)(d_{A}/d_{\bar{A}}+\varepsilon
d_{A})^{2}.$

In the last-but-one line, for the first term we note that
$\left[\log(d_{A})-S_{2}(\rho_{A})\right]^{2}\leq N_{A}^{2}$, and later use
Prop. 2 to bound the probability for the small entropy cases; for the second
term corresponding to the cases with entropy near $\log(d_{A})$, we directly
take the maximal deviation and the probability can be bounded trivially by
$1$.

In the regime $d_{A}\ll d_{\bar{A}}$, one can choose an appropriate
$\delta(P_{A})\ll\varepsilon\ll d_{A}^{-1}$ to control the variance
exponentially small for both ensembles. To balance the two terms in Eq. (75),
one can choose $\varepsilon=\sqrt{\delta(P_{A})d_{A}^{-1}}$. In this way, the
entropy variance is in the order.

$\displaystyle\mathrm{Var}[S_{2}(\rho_{A})]\sim\delta(P_{A})d_{A}$ (76)

by omitting the insignificant coefficient of $N$. Remembering that the purity
variances $\delta^{2}_{CZ}(P_{A})=\Theta(d^{-1})$ and
$\delta^{2}_{CCZ}(P_{A})=\Theta(d^{-2})$ by Theorem 3 and Theorem 5,
consequently the entropy variances for both ensembles can be quite small in
the regime $d_{A}\ll d_{\bar{A}}$. It is not hard to see that this is also
true for $S_{1}(\rho_{A})$.

###  F.2 Proof of Theorem 6

Furthermore, in the regime that $d_{A}\sim d_{\bar{A}}\sim d^{1/2}$, the
argument in Sec. F.1 can still apply for the CCZ ensemble. We prove Theorem 6
as follows.

###### Proof.

Similar as Eq. (73), we can bound the probability for entropy deviation by
Chebyshev inequality. Different from Eq. (73), we now consider deviation on
both sides.

$\displaystyle\mathrm{Pr}\\{-\log(P_{A})\geq-\log(\langle
P_{A}\rangle-\varepsilon)\\}\bigcup\mathrm{Pr}\\{-\log(P_{A})\leq-\log(\langle
P_{A}\rangle+\varepsilon)\\}\leq\frac{\delta^{2}}{\varepsilon^{2}}.$ (77)

By Theorem 2 for the case of $d_{A}=d_{\bar{A}}=d^{1/2}$,

$\displaystyle-\log(\langle
P_{A}\rangle-\varepsilon)<-\log\left(2d^{-1/2}-d^{-1}-\varepsilon\right)$
$\displaystyle=-\log\left(2d^{-1/2}\right)-\log\left[1-\frac{1}{2}(d^{-1}+\varepsilon)d^{1/2}\right]$
(78) $\displaystyle<(N/2-1)+\frac{1.1}{2}\log(e)(d^{-1}+\varepsilon)d^{1/2}$
$\displaystyle<(N/2-1)+0.8(d^{-1}+\varepsilon)d^{1/2}$

In the last-but-one line, we use the relation
$-\log_{2}(1-x)=\log_{2}(e)(x+x^{2}/2+x^{3}/3\cdots)<1.1\log_{2}(e)x<0.8x$ for
sufficient small $x=\frac{1}{2}(d^{-1}+\varepsilon)d^{1/2}$ here. By Eq. (74),
one also has $-\log(\langle
P_{A}\rangle+\varepsilon)\geq(N/2-1)-1.5\varepsilon d^{1/2}$. Since we take
$d^{-1}\ll\varepsilon\ll d^{-\frac{1}{2}}$, one has
$0.8(d^{-1}+\varepsilon)d^{1/2}<1.6\varepsilon d^{1/2}$. By inserting these
bounds in Eq. (77) and note that $\delta^{2}_{CCZ}(P_{A})<4d^{-2}$ in Theorem
5, one has

$\displaystyle\mathrm{Pr}\left\\{\left|S_{2}(\rho_{A})-\left(\frac{N}{2}-1\right)\right|\geq
1.6\varepsilon d^{1/2}\right\\}\leq\frac{4d^{-2}}{\varepsilon^{2}}.$ (79)

The variance of the entanglement entropy can be proved in the same way as in
Eq. (75), but consider the difference from $N/2-1$ here.

$\displaystyle\mathrm{Var}[S_{2}(\rho_{A})]=$
$\displaystyle\mathbb{E}_{\Psi}\left[S_{2}(\rho_{A})-\langle
S_{2}(\rho_{A})\rangle\right]^{2}$ (80) $\displaystyle\leq$
$\displaystyle\mathbb{E}_{\Psi}\left[S_{2}(\rho_{A})-(N/2-1)\right]^{2}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\\{\Psi|\left|S_{2}(\rho_{A})-(N/2-1)\right|\geq
1.6\varepsilon
d^{1/2}\\}}\left[S_{2}(\rho_{A})-(N/2-1)\right]^{2}+\mathbb{E}_{\\{\Psi|\left|S_{2}(\rho_{A})-\left(\frac{N}{2}-1\right)\right|<1.6\varepsilon
d^{1/2}\\}}\left[(N/2-1)-S_{2}(\rho_{A})\right]^{2}$ $\displaystyle\leq$
$\displaystyle(N/2)^{2}\
\mathrm{Pr}\left\\{\left|S_{2}(\rho_{A})-\left(\frac{N}{2}-1\right)\right|\geq
1.6\varepsilon d^{1/2}\right\\}+(1.6\varepsilon d^{1/2})^{2}$
$\displaystyle\leq$ $\displaystyle
N^{2}\frac{d^{-2}}{\varepsilon^{2}}+1.6^{2}\varepsilon^{2}d.$

By taking $\varepsilon=\sqrt{N/1.6}d^{-\frac{3}{4}}$ one has
$\mathrm{Var}[S_{2}(\rho_{A})]\leq 1.6Nd^{-\frac{1}{2}}$. ∎

###  F.3 Proof of Theorem 7

For the CZ ensemble, as mentioned in main text, since the variance of the
purity $\delta_{CZ}(P_{A})=\Theta(d^{-1/2})$ is comparable to the expectation
value of the purity $\langle P_{A}\rangle\sim d^{-1/2}$ in the regime
$d_{A}\sim d_{\bar{A}}$, one expects a constant variance of entanglement
entropy, and we prove Theorem 7 here.

Compared to studying the the variance $\mathrm{Var}[S_{2}(\rho_{A})]$ with
$\delta_{CZ}(P_{A})$ in the previous subsections, here we directly evaluate
$S(\rho_{A})$ and then $\mathrm{Var}[S_{2}(\rho_{A})]$ by the property of the
graph state.

Firstly, we briefly review the formula of the entanglement entropy of graph
state [67]. Any simple graph $G$ can be uniquely determined by its adjacency
matrix denoted as $\Gamma$, with $\Gamma_{i,j}=1$ iff $(i,j)\in E$. Suppose
the vertex set $V=\\{N\\}$ is partitioned into two complementary subsets $A$
and $\bar{A}$, the adjacency matrix $\Gamma$ can be arranged in the following
form,

$\Gamma_{G}=\left(\begin{array}[]{cc}\Gamma_{A}&\Gamma_{A\bar{A}}\\\
\Gamma_{A\bar{A}}^{T}&\Gamma_{\bar{A}}\\\ \end{array}\right),$ (81)

where $\Gamma_{A}$, $\Gamma_{\bar{A}}$ describe the connections inside each
subsystem, and the off-diagonal $N_{A}\times N_{\bar{A}}$ submatrix
$\Gamma_{A\bar{A}}$ is for the ones between them.

Given a graph state $\ket{G}$ with its associated graph $G$, the reduced
density matrix of a subsystem $A$ is
$\rho_{A}=\mathrm{Tr}_{\bar{A}}(\ket{G}\bra{G})$, where the partial trace is
on $\bar{A}$. The explicit formula of the entanglement entropy is

$S_{2}(\rho_{A})=\mathrm{rank}(\Gamma_{A\bar{A}})$ (82)

where the $\mathrm{rank}$ is on the binary field $\mathbb{F}_{2}$. Note that
Renyi-$\alpha$ entropy $S_{\alpha}(\rho_{A})$ of any order is also suitable
here, since the spectrum of $\rho_{A}$ is flat for graph states [67].

The random graph state generated by random CZ gates just corresponds to
randomly assigning $0/1$ with equal probability in the adjacency matrix
$\Gamma$. If only considering the entanglement entropy, one only needs to
study the statistical property of $\mathrm{rank}(\Gamma_{A\bar{A}})$ for
random $\Gamma_{A\bar{A}}$. The following Lemma considering the rank
distribution of the random binary matrix [55].

######  Lemma 2.

_(Th. 3.2.1[55])_ For the random $n\times n$ binary matrix $\Gamma$, with each
element $\Gamma_{ij}$ distributes independently, and equally taking value
$0/1$, the probability for the rank of $\Gamma$ on the binary field shows

$\displaystyle
Q_{s}:=\mathrm{Pr}\\{\mathrm{rank}(\Gamma)=n-s\\}=2^{-s^{2}}\prod_{i\geq
s+1}^{\infty}(1-2^{-i})\prod_{1\leq i\leq s}(1-2^{-i})^{-1}$ (83)

as $n\rightarrow\infty$. In particular, $Q_{1}=2Q_{0}$,
$Q_{2}=\frac{4}{9}Q_{0}$, and numerically $Q_{0}\approx 0.288\cdots$.

Based on these preknowledges, we can prove Theorem 7 by considering the square
matrix $\Gamma_{A\bar{A}}$ with $N_{A}=N_{\bar{A}}=N/2$ with
$N\rightarrow\infty$.

###### Proof.

From Corollary 2, one knows that $\langle
S_{2}(\rho_{A})\rangle\geq-\log\left(\frac{2\sqrt{d}}{d}\right)=N/2-1$. By
using Lemma 2, one has

$\displaystyle\mathrm{Var}[S_{2}(\rho_{A})]$
$\displaystyle=\sum_{s=0}^{N/2}Q_{s}[(N/2-s)-\langle
S_{2}(\rho_{A})\rangle]^{2}$ (84) $\displaystyle>Q_{2}[(N/2-2)-\langle
S_{2}(\rho_{A})\rangle]^{2}$
$\displaystyle>Q_{2}[(N/2-2)-(N/2-1)]^{2}=\frac{4}{9}Q_{0}\approx 0.128.$

∎