A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS

KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

Abstract. We study the entanglement entropy of a random tensor network (RTN) using
tools from free probability theory. Random tensor networks are simple toy models that help the
understanding of the entanglement behavior of a boundary region in the ADS/CFT context.
One can think of random tensor networks are specific probabilistic models for tensors having
some particular geometry dictated by a graph (or network) structure. We first introduce our
model of RTN, obtained by contracting maximally entangled states (corresponding to the edges
of the graph) on the tensor product of Gaussian tensors (corresponding to the vertices of the
graph). We study the entanglement spectrum of the resulting random spectrum along a given
bipartition of the local Hilbert spaces. We provide the limiting eigenvalue distribution of the
reduced density operator of the RTN state, in the limit of large local dimension. The limit
arXiv:2407.02559v1 [quant-ph] 2 Jul 2024

value is described via a maximum flow optimization problem in a new graph corresponding
to the geometry of the RTN and the given bipartition. In the case of series-parallel graphs,
we provide an explicit formula for the limiting eigenvalue distribution using classical and free
multiplicative convolutions. We discuss the physical implications of our results, allowing us to
go beyond the semiclassical regime without any cut assumption, specifically in terms of finite
corrections to the average entanglement entropy of the RTN.

Contents
1. Introduction 2
2. Main results 3
3. Random tensor networks 7
3.1. Random tensor network 8
3.2. Entanglement 10
4. Moment computation 11
5. Asymptotic behaviour of moments 13
6. Moment for ordered series-parallel network 19
6.1. Series-Parallel graph 19
6.2. Moment as graph dependent measure 20
7. Examples of series-parallel networks 25
7.1. Single vertex network 25
7.2. Series network 26
7.3. 2D lattice 27
8. Results for normalized tensor network states 28
8.1. Concentration 28
8.2. Entanglement entropy 29
9. Conclusion 31
References 32
Appendix A. Basics of the combinatorial approach to free probability theory 35

Date: July 4, 2024.

1
2 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

1. Introduction
The ADS/CFT correspondence consists in describing a quantum theory (more precisely a con-
formal field theory) as lying on the boundary of an anti de Sitter space-time geometry [Mal99].
Many particular features of this correspondence remains mysterious, in particular the link with
quantum information theory with entanglement. It was shown in [RT06], that for a fixed time
slice, the entanglement behaviour of a given region of the boundary quantum theory is propor-
tional to the minimal hypersurface bulk area homologous to the region of interest known as the
Ryu-Takayanagi entanglement entropy. The Ryu-Tkayanagi formula shows in the context of
ADS/CFT a crucial link between the entanglement behaviour of an intrinsic quantum theory
and its link with the bulk gravitational field. This results open a new point on the understand-
ing quantum gravity in the ADS/CFT framework from the perspective of entanglement and
quantum information theory. We refer to [CCW22] and the reference therein for a complete
introduction.
The difficulty of computing the entanglement properties of boundary quantum theories has led to
the development of attractable simple models particularly the tensor network and random tensor
network frameworks. Initially, the tensor network framework started as “good” models approx-
imating ground states in condensed matter physics. In the context of condensed matter physics,
tensor networks represent ground states of a class of gapped Hamiltonian [CPGSV21]. More-
over, tensor networks have paved the way to understanding different physical properties such as
the classification of topological phases of matter. We simply refer to [CPGSV21] for an extensive
review of all the different applications. Recently other extensions of tensor networks to ran-
dom tensor networks for studying random matrix product states or projected entangled pairs of
states were introduced in [CGGPG13, GGJN18, LPG22]. However, the random tensor network
(or simply RTN) was initiated in [HNQ+ 16] as toy models reproducing the key properties of the
entanglement behaviour in the ADS/CFT context [DQW21, KFNR22, PSSY22, QSY22, QY18,
QYY17, YHQ16]. Moreover the random tensor network framework appears in different active
areas from condensed matter physics in the random quantum circuits and measurement frame-
work [LC21, LPWV20, LVFL21, MVS21, MWW20, NRSR21, VPYL19, YLFC22, YYQ18].
In general, a random tensor network (or simply RTN) will consist of defining random quantum
states from a given fixed graph structure, as we shall describe in the following lines. The
main problem consists of computing the average entanglement as D → ∞, where D plays the
dimension of the Hilbert space of the model, behaviour of the state associated with a given fixed
subregion of the graph. From Different results have been established allowing the understanding
of the entanglement entropy of the RTN models as toy models mimicking the entanglement
behaviour in quantum gravity. Different work has been explored in the literature where the
entanglement entropy as D → ∞ scales as the number of minimal cuts needed to separate the
region of interest from the rest of the graph times log D [HNQ+ 16, CLP+ 22]. Moreover one
should mention that several directions have been explored to go beyond the toy model picture
of the (random) tensor network [AKC22, BPSW19].
In this work, we will focus on a general random tensor network from a maximal flow approach.
The use of the maximal flow approach was already explored in [KFNR22] to compute the
entanglement negativity and in [FH17] to derive the Ryu-Takayanagi entanglement entropy
in the continuum setting. As was described in the previous paragraph the model consists of
defining a random quantum state from a given fixed graph structure. In our model, we shall
consider a graph with edges (bulk edges) and half edges (boundary edges). The use of bulk and
boundary edges will become clear from the definition of the model. We shall associate to each
half edge a finite dimensional Hilbert space CD and for each edge a Hilbert space (CD )⊗2 . The
edges Hilbert space will generate a local Hilbert space associated to each vertex of the graph. In
order to define an RTN, one should associate to each components of the graph quantum state
generated as random. For that, we will generate for each vertex a random Gaussian state and
we shall associate to each of the edges maximally entangled state. A random tensor network is
defined by projecting all the maximally entangled states associated with the graph on the total
random states generated in each vertex. The obtained random tensor network lies in the full
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 3

boundary Hilbert space. The main goal of this work is to consider a sub-boundary region A of
the graph and evaluate the entanglement behaviour of the associated residual state as D → ∞.
The first computation is to estimate the moment computation of the state associated to the
region A as D → ∞. With the help of the maximal flow, that we will develop in this work in
full details, we are able to estimate the moments without any cuts assumption and shows that
converges to the moment of a graph-dependent measure. We will show if the obtained partial
order is series-parallel, and with the use of free probability theory, we are able to explicitly
construct the measure associated to the graph without any cut assumption. Moreover, we will
show the existence of higher order correction terms of the entanglement entropy given with
graph-dependent measure which can be explicitly given if the partial-order is series-parallel.
We will show in different example how one can compute explicitly the measures associated to
the initial graph in the case if the obtained partial order is series-parallel. The link between
quantum information theory, free probability and random tensor network was already explored
in [CLP+ 24] with the use of a general link state representing the effect of bulk matter field
in the ADS/CFT context which allows to go beyond the semiclassical regime with correction
terms of the entanglement structure. Moreover, the obtained results in [CLP+ 24] assumes the
existence of two disjoint minimal cuts separating the region A from the rest. In this work, we
only work with maximally entangled states in the bulk edge of the model. Without any cut
assumption, we do obtain higher order correction terms which we may interpret as intrinsic
fluctuations. In the context of ADS/CFT those are intrinsic to the quantum spacetime nature
of bulk gravitational field without any bulk matter field.
This work is organised as follows. In Section 2, we will give a summary of our work by presenting
all the main results. In Section 3 we will introduce our random tensor network framework. In
Section 4, we will give the moment computation of a given state ρA associated to a given
suboudary region of the graph A. In Section 5, with the help of the maximal flow approach, we
will compute the asymptotic scaling of the moments and show the convergence to a measure
given by a graph-dependent measure. In Section 6, we will introduce the notion of series-parallel
partial order with the help of free probability we will show explicitly how one can construct
a graph-dependent measure with free product convolution and classical measure product. In
Section 7, we will give various examples of random tensor networks and show explicitly the
associated obtained measure in the case of an obtained partial order is series-parallel. In Section
8, we will give the main technical results, with the help of concentration inequalities we will
show the obtained higher-order entanglement correction terms, without any cut assumption,
are graph-dependent moreover the graph dependent measure can be explicitly constructed if
the partial order is series-parallel.

2. Main results
In this section, we will introduce the main definitions and main results obtained in this work.
This work will consist of computing the entanglement entropy of a given random tensor net-
work. We shall consider the most general framework of random tensor networks and study
the entanglement structure of the random tensor, concerning a fixed bipartition of the total
Hilbert space. By addressing the problem using a network flow approach, we can compute the
leading term, plus higher order correction terms of the entanglement entropy which are graph
dependent. The higher order correction terms plays a crucial role in different areas, particularly
in the context of ADS/CFT [LM13, HNQ+ 16, BPSW19, CLP+ 24] as we shall comment after
we give the main results. One can informally summarize the key results of this work as follows:
4 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

In the limit of large local Hilbert space dimension D, the average Rényi entanglement
entropy of a RTN G, across a given bipartition (A|B), has:
• a dominating term of the form maxflow(GA|B ) · log D
• a finite correction term which is graph dependent.
In the case where GA|B is a series-parallel graph, we can compute the distribution of the
entanglement spectrum (and hence the finite entropy correction) as an iterative classical
and free convolution of Marc̆henko-Pastur distributions.

A random tensor network has a corresponding random quantum state |ψG ⟩ that encodes the
structure of a graph G. For that, we shall introduce the graph G and some terminology. We
refer to Section 3 for more technical details and definitions of the model. Let G = (V, E)
be a connected undirected finite graph with (full) edges and half edges; the former encode
the internal entanglement structure of the quantum state |ψG ⟩, while the latter represents the
physical systems (Hilbert spaces) on which |ψG ⟩ lives. We shall denote by Eb and E∂ the
set of edges (bulk edges) and half edges (boundary edges) respectively. Formally the set of
edges and half edges are respectively given by Eb := {ex,y | ex,y = (x, y) : x, y ∈ V } and
E∂ := {ex = (x, ·) : x ∈ V } where E := Eb ⊔ E∂ . Then, the corresponding random tensor |ψG ⟩
is defined as
DO O E
⊗|E∂ |
|ψG ⟩ := Ωe gx ∈ CD ,
e∈Eb x∈V

where |gx ⟩ are random Gaussian states defined in the local Hilbert space of each vertex x.
Moreover, for each (full) edge e ∈ Eb , we associate a maximally entangled state |Ωe ⟩ ∈ CD ⊗
CD that is used to contract the internal degrees of freedom of the tensor network. For a
representation of a random tensor network see Figure 1, which we will treat in great detail for
an illustration of our different main results of this work. We refer to Definition 3.1 for more
details.
As was mentioned earlier, this work aims to evaluate the entanglement entropy of the random
quantum state |ψG ⟩, along a bi-partition A|B of the boundary edges E∂ = A ⊔ B. We shall do
so in the limit of large local Hilbert space dimension D → ∞. To evaluate the entanglement
entropy of the pure state |ψG ⟩, we shall compute its asymptotic entanglement spectrum along the
bi-partition A|B, that is the limiting spectrum of the density matrix ρA = TrB |ψG ⟩⟨ψG |. From
this spectral information, we can deduce the average Rényi entanglement and von Neumann
entropies for the approximate normalised state ρ̃A respectively given by:
(
1
limD→∞ E Sn (ρ̃A ) with Sn (ρ) := 1−n log (Tr ρn ) ,
ρ̃A := D−|E∂ | ρA →
limD→∞ E S(ρ̃A ) with S(ρ) := − Tr(ρ log ρ).

Above, the expectation is taken with respect to the Gaussian distribution of the independent
random tensors |gx ⟩ present at each vertex of the graph. It will be clear from Section 8 the use
of approximate normalised state instead of a “true” normalised state ρ̃A := ρA / Tr ρA .
We first compute exactly the moments of the random matrix ρA and then we analyze the main
contributing terms at large dimensions by relating the problem to a maximum flow question in
a related graph. By the use of the maximal flow and tools from free probability theory, we will
able to derive the leading and the fluctuating terms of the Rényi entropy and then deduce the
behaviour of the von Neumann entanglement entropy.

Moment computation We shall first consider the normalised state ρ̃A := ρA / Tr ρA and
compute the moments. For the first step, we use the graphical Wick formula from [CN11] to
find
X (n)
E [Tr(ρnA )] = Dn|E∂ |−HG (α) , ∀ n ∈ N (1)
|V |
α=(αx )∈Sn
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 5

(n)
where HG (α) can be understood as the Hamiltonian of a classical “spin system”, where each
spin variable takes a value from the permutation group Sn :
(n)
X X X
HG (α) := |γx−1 αx | + | id−1
x αx | + |αx−1 αy |.
(x,·)∈A (x,·)∈B (x,y)∈Eb

Above, we associate to the region B, the identity permutation idx ∈ Sp (corresponding to taking
the partial trace over B), and to the region A the full-cycle permutation γx = (n n − 1 · · · 2 1)
(corresponding to the trace of the n-th power of ρA ). We refer to Proposition 4.1 in Section 4
for a more precise statement and proof. One should also mention that the contribution of the
normalisation term of ρ̃A will be given by:
X (n)
E [(Tr ρA )n ] = Dn|E∂ |−hG (α) , ∀ n ∈ N
|V |
α=(αx )∈Sn

where
(n)
X X
hG (α) := | id−1
x αx | + |αx−1 αy |.
(x,·)∈E∂ (x,y)∈Eb
(n) (n)
Remark above that hG (α) is simply HG (α) with A = ∅. See Proposition 4.2 for more details.
Note that in the particular case n = 2, the authors of [HNQ+ 16] gave an exact mapping to the
partition function of a classical Ising model. Notice the frustrated boundary conditions of the
Hamiltonian above: vertices connected to the region A prefer the configuration αx = γx , while
vertices connected to the region B prefer the low energy state αx = idx .
Maximal flow. The (max)-flow approach will consist of identifying the leading terms from
the moment formula above as D → ∞. For that, we introduce a network GA|B , derived from
the original graph G, by connecting all the half-edges in A to an extra vertex γ (sink) and all
the half-edges in B to id (source). In GA|B , the vertices are valued in the permutation group Sn
and all the half edges are connected either to the source id or to the sink γ. The flow approach
will consist by looking at the different paths starting from the source id to the sink γ. The
different paths in the flow approach will induce an ordering structure more precisely a poset
structure in the network GA|B . Intuitively the maximal flow will consist of searching of the
maximal number of such paths such that if on take them off the source and the sink will be not
anymore connected. More precisely, by Menger’s theorem, the maximum flow in this graph is
equal to the number of edge-disjoint augmenting paths that start from the source id and end in
the sink γ. Figure 7 represents the different paths achieving the maximal flow in the network
GA|B from the original graph G as represented in Figure 1. This procedure allows us to find a
(n)
lower bound to the Hamiltonian HGA|B (α) that can be attained by some choice of the variables
αx .
Theorem A. For all n ≥ 1, we have
(n)
min HGA|B (α) = (n − 1) maxflow(GA|B ),
|V |
α∈Sn

(n)
where HGA|B (α) is the extended Hamiltonian in the network GA|B . Once one takes out all
the augmenting paths achieving the maximum flow in GA|B , one is left with a clustered graph
GcA|B that is obtained by clustering all the remaining connected components (see Figure 8).
Importantly, it follows from the maximality of the flow that in this clustered graph, the cluster-
vertices [id] and [γ] are disjoint. We refer to Proposition 5.12 for more details and the proof of
the result above.
As a direct consequence of the result above, one can deduce the moment convergence as D → ∞,
we refer to Theorem 5.14 for more details of the following result.
Theorem B. In the limit D → ∞, we have, for all n ≥ 1,
1 h  n  i
lim E F (G ) Tr DF (GA|B )−|E∂ | ρA = mn
D→∞ D A|B
6 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

where mn are the moments of a probability measure µGA|B and F (GA|B ) = maxflow(GA|B ).
Moreover one can show the normalisation term converges to 1 as shown in Corollary 5.18.
The previous maximum flow computation gives the first order in the formula for the average
entanglement entropy of random tensor network states:
E [Sn (ρ̃A )] ≈ maxflow(GA|B ) · log D ∀ n ≥ 1.
Free probability theory and entanglement Our main contribution in this work is to show
that one can find the second order (or the finite corrections) of the Rényi and von Neumann
entanglement entropy by carefully analyzing the set of augmenting paths achieving the maxi-
mum flow in the graph GA|B . Once the different paths achieve the maximal flow in the graph
GA|B , after the clustering operation we obtain an partial order GoA|B where the vertices are
the different permutation clusters formed from the clustered graph GcA|B . See Figure 9 of the
obtained partial order from the original graph G in Figure 1. Our results are general, and they
become explicit in the setting of the partial order GoA|B is series-parallel. With the help of free
probability theory, we are able in this setting to deduce the second-order correction terms of
each of the Rényi and von Neumann entropy.
Definition 2.1. A graph G is called series-parallel if it can be constructed recursively using the
following two operations:
F
• Series concatenation: G = H1 S H2 is obtained by identifying the sink of H1 with the
source of H2 . F
• Parallel concatenation: G = H1 P H2 obtained by identifying the sources and the sinks
of H1 and H2 .
Definition 2.2. To a series-parallel graph G we associate a probability measure µG , defined
recursively as follows.
• To the trivial graph Gtriv = ({s, t}, {{s, t}}), we associate the Dirac mass at 1: µGtriv :=
δ1 .
• Series concatenation: µG FS H := µG ⊠ MP ⊠ µH .1
• Parallel concatenation: µG FP H := µG × µH .

Theorem C. In the limit D → ∞, the average Rényi entanglement entropy ∀ n ≥ 1 and von
Neumann entropy of an approximate normalised state ρ̃A := D−|E∂ | ρA behaves respectively as
Z
1
E [Sn (ρ̃A )] = maxflow(GA|B ) · log D − log tn dµGA|B (t) + o(1)
n−1
Z
o
E [S(ρ̃A )] = maxflow(GA|B ) · log D − t log t dµGA|B + o(1).

We refer to Corollary 8.7 for more details and the proof of the above statements. In particular
if the obtained partial order GoA|B is series-parallel the measure µGA|B = µGoA|B can be explicitly
constructed, we refer to Theorem 6.4 for more details. The use of the approximate normalised
state instead of “the” normalised state ρ̃A := ρA / Tr ρA will be justified from the concentration
result of Tr ρA in Subsection 8.1.
It was previously argued in [HNQ+ 16, BPSW19] if one wants to encode the quantum fluctuations
one needs to use instead of a maximally entangled state a general “link state” |φe ⟩ defined by:
D
X p
e ∈ Eb → |φe ⟩ := λe,i |ix , iy ⟩ .
i=1
It was recently shown in [CLP+ 24]that the non-flat spectra of the link state under the existence
assumption of two non-disjoint cuts that one obtains the quantum fluctuations beyond the
semiclassical regime in ADS/CFT. The use of a generic link state in the context of ADS/CFT
represents the bulk matter field contribution. In this work with the maximal flow approach, we
1dMP := √
1
2π
4t−1 − 1 dt is the Marc̆henko-Pastur distribution and ⊠ is the free convolution product. We
refer to Appendix A for more details.
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 7

were able to show the existence of quantum fluctuations without any minimal cut assumption
and with maximally entangled state as link state. The obtained higher order correction terms in
our context can be interpreted as the “intrinsic” quantum fluctuations of spacetime geometry
without any bulk matter field in the bulk represented by a general link state.
For example, in the case of the graph represented in Figure 1, the resulting partial order GoA|B
is series-parallel (see Figure 9) where:
G G
GoA|B = G1 S G2 S G3 with µGoA|B = µG1 ⊠ MP ⊠ µG2 ⊠ MP ⊠ µG3 = µG1 ⊠ MP⊠2 ,

as represented in Figure 10 the graph G2 and G3 are trivial hence µG2 = µG3 = δ1 . The graph
G1 can be factored as a parallel composition of two other graphs as represented in Figure 11:
G
G1 = G5 P G4 with µG1 = µG4 × µG5 .

The graph G4 as represented in Figure 12 factorises as:

 G G
G4 = G6 P G7 S G8 with µG4 = (µG6 × µG7 ) ⊠ MP ⊠ µG8 = (MP × MP) ⊠ MP

where we have used the fact that G6 and G7 are series compositions of two trivial graphs, so
µG6 = µG7 = MP, while µG8 = δ1 .
Moreover the graph G5 as represented in Figure 13 factorises as:
G G G G
G5 = G9 S G10 S G11 P G12 S G13

with the associated measure

µG5 = µG9 ⊠ MP ⊠ µG10 ⊠ MP ⊠ (µG11 × µG12 ) ⊠ MP ⊠ µG13 = MP⊠3 ⊠ MP⊠2 × MP ,

where we have used iteratively the series composition for G11 and G12 with their respective
measure given by µG11 = MP⊠2 and µG12 = MP. In the case of random tensor network
represented in Figure 1 the partial order is series-parallel with the associated measure:
G G
GoA|B = G1 S G2 S G3 ,

with
MP⊠3 ⊠ (MP⊠2 × MP) × [(MP × MP) ⊠ MP] ⊠ MP⊠2 ,
 
µGoA|B =
which is obtained by combining all the results stated above. If one considers the minimal cuts
associated with the network GA|B (see Figure 7) as represented in Figure 14 where we have
considered four ways2 achieving the minimal cuts crossing common edges, therefore intersects.

3. Random tensor networks

In this section, from a given graph with edges (bulk edges) and half edges (boundary edges),
we will introduce random tensor network model. For that for each edge and half edge of the
graph, we will associate a Hilbert space. The edge Hilbert space will induce a local Hilbert
space for each vertex in the graph. We will associate to each of the vertices a random Gaussian
state, and to each edge a maximally entangled state. The random tensor network is defined by
projecting all the maximally entangled state associated to all edges of the graph over the vertex
states given by the tensor product of all the random Gaussian vectors. This section aims to
introduce the main definitions of the model and recall the different entanglement notions.
In Subsection 3.1, we shall introduce our random tensor network model. In Subsection 3.2, we
recall the different entanglement notions and their properties.

2We have only represented four cuts for simplicity. Remark in Figure 14 we have more than four minimal cuts
which may share a common edge.
8 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

3.1. Random tensor network. In the following, we shall give the construction of the random
tensor network model. Let G = (V, E) be a bulk connected undirected finite graph with edges
and half edges. We shall denote by Eb and E∂ the set of edges and half edges respectively.
Formally the set of edges and half edges are defined as follows

Eb := {ex,y | ex,y = (x, y) : x, y ∈ V },

E∂ := {ex = (x, ·) : x ∈ V },
E := Eb ⊔ E∂ .

For later discussion, the set of edges Eb and half edges E∂ we shall call them the set of bulk
and boundary edges. The bulk connectivity assumes that all the vertices in the bulk region
of the graph are connected; this is the same notion as the “connected network” property from
[Has17, Definition 2]. We denote by |Eb |, |E∂ | and |E| = |Eb | + |E∂ | the cardinality of the bulk,
boundary and the total edge set.
For each half-edge on a given vertex in the graph, we shall associate a Hilbert space CD , and
for each bulk edge connecting two vertices, we associate CD ⊗ CD for finite D known as the
bond dimension. We will define a random Gaussian to each vertex of the graph state that lies
in the local Hilbert space associated to each vertex. Moreover, on each edge of the graph, we
associate a maximally entangled state. The random tensor network is a random quantum state
constructed by projecting the total tensor product of the random Gaussian state for each vertex
over all the maximally entangled state formed in bulk edges (see Definition 3.1).
Formally, for each part of the graph G we shall associate to each part of the graph Hilbert
spaces where:
• For each half-edge defined on a vertex x, we associate a finite-dimensional Hilbert space
He x :

ex ∈ E∂ → Hex := CD
O
E∂ → H∂ := Hex ,
ex ∈E∂

• For each edges ex,y ∈ Eb we shall associate Hilbert space Hex,y :

ex,y ∈ Eb → Hex,y := CD ⊗ CD ,

where Hex,y denote the Hilbert space connecting the two vertices x and y.
• For each vertex x ∈ V , we define the local vertex Hilbert space Hx where:
O
x ∈ V → Hx := He
E∋e→x
O O O
V → HV := Hx = He ,
x∈V x∈V E∋e→x

where the Hilbert space Hx represents the local Hilbert space associated with a vertex
x defined as all the edges of Hilbert space that contribute locally.
Having defined the general Hilbert space structure associated with a generic graph G, in the
following, we shall define quantum states in the graph G which will allow us to introduce the
random tensor network model. By construction let for each:
• Vertex x a random quantum state |gx ⟩ ∈ Hx sampled from an i.i.d Gaussian distribution:

x ∈ V → |gx ⟩ ∈ Hx
O
V → |gx ⟩ ∈ HV
x∈V
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 9

• Bulk edge ex,y a maximally entangled state |Ωe ⟩ given by:

ex,y ∈ Eb → Hex,y
D
1 X
ex,y → |Ωe ⟩ := √ |ix , iy ⟩ ,
D i=1
where we have used the notation |ix ⟩ and |iy ⟩ for the state associated to the vertex x
sharing an edge with y.
Definition 3.1. A random tensor network |ψG ⟩ is defined as a projection of the vertex state
over all the maximally entangled states |Ωe ⟩ for each ex,y in Eb where:
DO O E
⊗|E∂ |
|ψG ⟩ := Ωe gx ∈ CD . (2)
e∈Eb x∈V

One should mention that the following example will be used in all other parts of this work as
an illustration of the different results obtained in each section.

3 4

1 2 6 13
14
15 5 12

7 9 10 11
17
16
8
Figure 1. A tensor network depicting a tensor from (CD )⊗10 obtained by con-
tracting 17 tensors. The 10 Hilbert space factors are partitioned into two subsets
B ⊔ A.

Example 3.2. As an illustration of a random tensor, see Figure 1, where the boundary region
of G are all the half edges E∂ := {e1 , e15 , e7 , e8 , e9 , e10 , e11 , e14 }. We shall mention that in Figure
1, the region A are the half edges in the vertices {9, 10, 11, 14},i.e A := {e9 , e10 , e11 , e14 }. The
complementary region B := E∂ \ A are half edges associated to the vertices {1, 15, 7, 8}, where
B := {e1 , e15 , e7 , e8 }.
We shall also mention that our construction of the random tensor network, the edges, and the
half edges generate the vertex Hilbert space Hx . Other types of random tensor network models
were already explored in the literature see [HNQ+ 16, DQW21, CLP+ 22] and the reference
therein. In the models mentioned previously, at first, they define the bulk and boundary vertices
while in our work the focus is on the edges and the half edges which generates the local Hilbert
space for each vertex, and the bulk states are given by a maximally entangled state. The first
initial work in the random tensor network was in [HNQ+ 16] where the aim was to compute
the entanglement entropy of subregion of the random tensor network which is proportional as
the bond dimension tends to infinity to the minimal cuts of the graph reproducing the famous
Ryu-Takayanagi entanglement entropy [RT06] in a discrete version.
In a recent work [CLP+ 22], the authors associate a state with a general “link” state connecting
two bulk vertices, therefore generalizing the previous models where they allowed the existence
of two non-crossing minimal cuts. This result allows the authors to compute higher-order
correction terms of the entanglement entropy. The main goal of this work, with the maximal
10 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

flow approach without any minimal cut assumption, we will be able to derive the higher order
correction terms with a maximally entangled state connecting the bulk vertices.

3.2. Entanglement. In the following, we shall recall different entanglement notions used in
quantum information theory in particular von Neumann entropy and Rényi entropy.
The von Neumann entropie for a given normalised quantum state ρ defined as
S(ρ) := − Tr (ρ log ρ) . (3)
In general, in physical systems with an exponential number of degrees of freedom it is in general
difficult to compute it. There exists a generalisation where we do not need to diagonalise the
density matrix ρ. This definition is due to Renyi which is known as the Renyi entropy defined
as:
1
Sn (ρ) := log (Tr ρn ) , (4)
1−n
where it is well known that as n → 1 the Renyi entropy converges to von Neumann entropy.
The definitions given above are for normalised quantum states, if the state is not normalised
one should normalise it first and then compute the entropy.

Now, we mention a bit about a subtlety regarding the upper bound on the rank of the reduced
density matrix induced by the minimal cut. A minimal cut consists of finding the minimal
number of edges in a graph that need to be removed to fully separate to a given fixed region
of the graph. Although it is trivial to see that the rank of the reduced density matrix ρA is
upper bounded by the local dimension D raised to the number of edges in the set A, that is,
rank(ρA ) ≤ D|A| . However, there exists a subtlety. The rank of the reduced density matrix is, in
fact, upper bounded by the minimum number of connecting edges or the bottleneck (min-cut)
and not the number of edges:
rank(ρA ) ≤ DFA , (5)
where, FA is the min-cut or the number of edges in the “bottleneck”.

Now, we demonstrate this more clearly using an example. Consider a state |ψG ⟩, which we can
use to construct ρA as shown below. Now, consider the internal structure of |ψG ⟩, where we

Figure 2. Constructing ρA from |ψG ⟩ by tracing out the edges corresponding

to the set B.

divide the graph into two subgraphs denoted by L and R, connected by the “bottleneck” which
is the set of all edges which when removed would disconnect the boundary sets A and B. Now,

Figure 3

it is clear that rank(ρA ) ≤ DFA , where, in this case FA = 2, and consequently,

S(ρA ) ≤ FA log D. (6)
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 11

Having established the natural intuition for the role of the min-cut (FA ) in upper-bounding
the entropy, we now move on to establish our (maximal) flow approach for the random tensor
network in the following sections.

4. Moment computation
From a given random tensor network, we want to understand the behaviour of entanglement
of a given subregion of the tensor network with the rest. For that we shall adress at first the
moment computation of quantum state ρ̃A for a given subregion A ⊆ E∂ . This first computation
will allows us in the following sections to analyse the Renyi and the von Neumann entropy.

Let A ⊆ E∂ be a sub-boundary region of N the graph G. We shall N denote by B := E∂ \ A the

complementary region of A. Let HA := H
ex ∈A ex and H B := ex ∈B Hex respectively the
Hilbert space associated to the boundary regions A and B.
In this work, we will be interested in computing the average entanglement entropy at large bond
dimension: (
ρA limD→∞ E Sn (ρ̃A )
ρ̃A := → (7)
Tr ρA limD→∞ E S(ρ̃A ),
where ρ̃A is the normalised quantum state obtained by tracing out the region B, i.e ρA =
TrB |ψG ⟩⟨ψG | where the partial trace over the Hilbert space HB . In the expression above, the
average is over all the random Gaussian states.
The first computation that we shall adress here is the moment computation as described in the
following proposition. This will allow us later, as analysed in detail in the following sections,
to compute the average entanglement entropy (Rényi and von Neumann entropy) as D → ∞.
The result above has been previously obtained in a very similar setting by Hastings [Has17,
Theorem 3, Eind ensemble].
Proposition 4.1. For any A ⊆ E∂ , we have
X (n)
E [Tr(ρnA )] = Dn|E|−n|Eb |−HG (α)
, ∀n∈N (8)
|V |
α=(αx )∈Sn
(n)
where HG (α) can be understood as the Hamiltonian of a classical “spin system”, where each
spin variable takes a value from the permutation group Sn :
(n)
X X X
HG (α) := |γx−1 αx | + | id−1
x αx | + |αx−1 αy |. (9)
(x,·)∈A (x,·)∈B (x,y)∈Eb

Before giving the proof of the proposition above, we shall recall some properties of the permu-
tation group Sn and fix some notations. We denote by γx the total cycle in the permutation
group Sn evaluated in (x, ·) ∈ A
∀(x, ·) ∈ A, γx = (n . . . 1).
We recall that one can define a notion of distance in Sn known as the Cayley distance given by
Sn × Sn → R+
d : (αi , αj ) → d(αi , αj ) := n − #(αi−1 αj ),
where #(α) stands for the number of cycles in α. The distance d(αi , αj ) gives the minimum
number of transpositions to turn αi to αj . In general the distance in Sn satifies the triangle
inequality where:
d(αi , αj ) ≤ d(αi , σ) + d(σ, αj ).
In particular, we say that σ is a geodesic between αi and αj in Sn if d(αi , αj ) = d(αi , σ)+d(σ, αj ).
We shall adopt the following notation for the distance instead of d(·, ·) where
(αi , αj ) ∈ Sn × Sn , d(αi , αj ) = |αi−1 αj |.
12 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

Proof. To prove the result announced in the proposition, one should remark first that we can
write the trace on the left-hand side of equation (8) with the well known replica trick as:
 
Tr(ρnA ) = Tr |ψG ⟩⟨ψG |⊗n UγA ⊗ idB ,

The trace in the left-hand is on HA that one rewrite as a full trace one n copy of the full Hilbert
space, bulk and boundary Hilbert space, N in the right-hand side of the equation above. Remark
that we have used the notation UγA = (x,·)∈A Uγx the tensor product of unitary representation
of the permutation γx = (n . . . 1) ∈ Sn for each half edges (x, ·) ∈ A.
By expanding and taking the average over random Gaussian states one obtains:
 h i 
E Tr(ρnA ) = Tr E |ψG ⟩⟨ψG |⊗n UγA ⊗ idB
O hO i 
= Tr |Ωe ⟩⟨Ωe |⊗n E |gx ⟩⟨gx |⊗n UγA ⊗ idB
e∈Eb x∈V
O O h i 
⊗n
= Tr |Ωe ⟩⟨Ωe | E |gx ⟩⟨gx |⊗n UγA ,
e∈Eb x∈V

where in the last equation above, we have used the shorthand notation UγA instead of UγA ⊗idB .
We recall the following property of random Gaussian states see [Har13]:
h i X
∀x ∈ V, E |gx ⟩⟨gx |⊗n = Uαx ,
{αx }∈Sn

with Uαx the unitary representation of αx ∈ Sn . Each permutation αx ∈ Sn acts on each

vertex Hilbert, hence implicitly on each edges associated to each vertex x ∈ V . Therefore, the
moments’ formula becomes:
X hO O i
E Tr(ρnA ) = Tr |Ωe ⟩⟨Ωe |⊗n Uαx UγA
{αx }∈Sn e∈Eb x∈V
#(γx−1 αx ) −1 −1
X Y Y Y
= D−n|Eb | D D#(idx αx )
D#(αx αy )
,
{αx }∈Sn (x,·)∈A (x,·)∈B (x,y)∈Eb

where the formula above counts the number of loops obtained by contracting the maximally
entangled states (edges) when one takes the trace. The factor of D−n|Eb | appears due to the
consequence of contracting the bulk edges, where each bulk edge contracted with itself, con-
tributes a factor of D−1 . By using the relation between the Cayley distance and the number of
loops, we obtain the result in the statement of the proposition.
□
Graphically, one can understand the formula using Figure 4 where we consider the case for
n = 3. Upon utilizing the graphical integration technique for Wick integrals as presented in
[CN11, CN16]. We obtain loops and, consequently, Cayley distances of three kinds, (a) between
idx and elements directly connected to it, from the region B, (b) between γx and elements
directly connected to it, from the region A and (c) elements neither directly connected to id nor
γ, from the bulk. Following this, we can rewrite the Hamiltonian in terms of Cayley distances
as:

(n)
X X X
HG (α) := |γx−1 αx | + | id−1
x αx | + |αx−1 αy |, (10)
(x,·)∈A (x,·)∈B (x,y)∈Eb

where (x, ·) ∈ A represents half-edges in A, (x, ·) ∈ B, represents half-edges in B and (x, y) ∈ Eb

represents edges in the bulk of the tensor network.
In the proposition above, we have addressed only the numerator term of the normalised quantum
state ρ̃A . However if one wants to compute the von Neumann and Rényi entropy (see equations
(3) and (4)), one should normalise the state and compute the moment.
The following proposition gives the moment computation of the normalisation term in ρ̃A .
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 13

Proposition 4.2. For any A ⊆ E∂ , we have

X (n)
E [(Tr ρA )n ] = Dn|E|−n|Eb |−hG (α)
, ∀n∈N (11)
|V |
α=(αx )∈Sn
(n)
where the Hamiltonian hG (α) is given by:
(n)
X X
hG (α) := | id−1
x αx | + |αx−1 αy |. (12)
(x,·)∈E∂ (x,y)∈Eb

Proof. The proof of this Proposition is a direct consequence of Proposition 4.1 when one takes
(n) (n)
A = ∅, hence we obtain hG (α) in the particular case when A = ∅ in HG (α). □

Ψ∗
Ψ

b y x

a
Figure 4. Graphical representation of the Wick theorem for the moment com-
putation with n = 3.

5. Asymptotic behaviour of moments

This section will consist of describing the leading contributing terms as D → ∞ of the moment
by using the (maximal)-flow approach. We will first introduce the (maximal)-flow approach
wich will allows us to estimate the leading terms of the moments as D → ∞ we refer to
Proposition 5.12 for more details. This result will allow us to deduce the convergence of the
moment as D → ∞ to moments of a graph dependent measure µGA|B we refer to Theorem 5.14
for more details.
We recall first the obtained results from the previous section. In Proposition 4.1 we have shown
that the moments are given by:
X (n)
E Tr(ρnA ) = Dn|E|−n|Eb |−HG (α)
|V |
α=(αx )∈Sn

where the spin valued Hamiltonian in the permutation group Sn is given by:
(n)
X X X
HG (α) := |γx−1 αx | + | id−1
x αx | + |αx−1 αy |.
(x,·)∈A (x,·)∈B (x,y)∈Eb

In particular, the contribution of the normalisation term in ρ̃A (see equation (7)) is the extended
(n) (n)
Hamiltonian hG (α) as shown in Proposition 4.2 when one takes A = ∅ in HG (α).
14 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

The main goal of this section, will consist on analysing the main contributed terms of the
moment as D → ∞. The leading terms will consist on solving the minimisation problem:
(n)
min HG (α).
|V |
α∈Sn
(n)
Particularly as a consequence, we will minimize hG (α) which will give us the leading contributed
term as D → ∞ of the normalisation term of ρ̃A . The minimisation problem addressed above,
will allow us to deduce the moment convergence as D → ∞ to the moment of graph dependent
measure µGA|B in Theorem 5.14.
The minimisation problem above will be addressed with the (maximal)-flow approach. This
approach will consist first by constructing from the original graph G a network GA|B . This
network is constructed by adding first two extra vertices γ and id to G in such a way that
all the half edges associated to A are connected to the total cycle γ, and half edges in B are
connected to id. The network GA|B has the same bulk structure of G, with the difference that
all the vertices in GA|B are valued in the permutation group Sn .
The flow approach will consist on searching of different augmenting paths in the network GA|B
that will start from id and ends to γ. This different paths will induce an order structure in
(n)
GA|B . By taking off all the augmenting paths in GA|B , we can find a lower bound of HGA|B (α)
the extended Hamiltonian in the network GA|B , we refer to Proposition 5.10 for more details.
Moreover, we will show that the minimum will be attained when the maximal flow starting
from id to γ is achieved, see Proposition 5.12. In particular we will show that the minimum of
(n)
the extended Hamiltonian hGA|B (α) is zero, see Proposition 5.16 for more details.
Before we start with our flow approach, one should mention that the contributed terms of
the moments at large dimension were analysed with the (minimal) cut approach in [CLP+ 22].
The authors assumed the existence of two disjoint minimal cut in the graph separating the
region of interest and the rest of the graph that will contribute in large bond dimension. With
the maximal flow approach, that we will introduce, we do not assume any (minimal) cut as-
sumption. By identifying different augmenting paths achieving the maximal flow and uses the
famous maximal-flow minimal-cut theorem (see e.g. [KVKV11, Theorem 8.6]) one can deduce
the different minimal cuts without any assumption.
Definition 5.1. Let the network GA|B = (Ṽ , Ẽ) defined from the initial graph G = (V, E) such
that:
Ṽ := V ⊔ {id, γ} and Ẽ := EÃ ⊔ Eb ⊔ EB̃
where the region EÃ and EB̃ are defined as:
G
EÃ := (x, γ)
x∈VA
G
EB̃ := (id, x),
x∈VB

where VA and VB denotes respectively all the vertices associated to the boundary region A and
B. Moreover the vertices are valued in the permutation group Sn where:
∀x ∈ Ṽ → αx ∈ Sn .
Remark in the definition given above, the graph GA|B is constructed in such a way all the half
edges (x, ·) ∈ A are connected to γ = (n · · · 1) ∈ Sn and the half edges (x, ·) ∈ B are connected
to id. Note also that in GA|B there is no half edges, the bulk region in the network GA|B remains
the same as the one in the graph G.
(n) (n)
Let first consider the extended Hamiltonian HGA|B (α) of HG (α) in the network GA|B given
by:
(n)
X X X
HGA|B (α) := |γ −1 αx | + | id−1 αx | + |αx−1 αy |, (13)
x∈VA x∈VB (x,y)∈Vb
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 15

where each term in the new Hamiltonian is valued in the network GA|B . Moreover, the sums in
the above formula are over the vertices VA , VB and Vb are the vertices with the respective half
edges in the region A, B and Eb .
As was mentioned earlier, the flow approach will consist on analysing different paths that start
from id and ends in γ. This will induce a natural orientation of the network GA|B , more precisely
a poset structure. In the following, we will define the set of different paths in GA|B and the
edges’ disjoint paths.
Definition 5.2. Let P(GA|B ) be the set of all possible paths from the source to the sink in
GA|B , where the source and the sink in our case are the id and γ respectively. Formally, the set
of paths P(GA|B ) is defined as:
P(GA|B ) := {πi : πi : id → γ},
where {πi }i are all the paths connecting the id to γ.
Definition 5.3. Let P̃(GA|B ) the set of all disjoint paths in P(GA|B ),
P̃(GA|B ) := {πi ∈ P(GA|B ) : {πi }i are edges disjoint }

Remark 5.4. It is clear from the definition that P̃(GA|B ) ⊆ P(GA|B ).

Searching for different paths that starts from the id and ends to γ will induce an ordering, more
precisely a poset structure in the network GA|B . First, we shall give in the following definition
of a poset structure that will allow us later to use it in our maximal flow approach to minimize
(n)
HGA|B (α).

Definition 5.5. The poset structure Po (GA|B ) is a homogeneous relation denoted by ≤ satis-
fying the following conditions:
• Reflexivity: αx ≤ αx .
• Antisymmetry: αx ≤ αy and αy ≤ αx implies αx = αy .
• Transitivity: αx ≤ αy and αy ≤ αz implies αx ≤ αz .
for all αx , αy , αz ∈ Ṽ .
Definition 5.6. Define the natural ordering as:
id ≤ α1 ≤ α2 ≤ · · · ≤ αn ≤ γ,
for a path πi ∈ P(GA|B ) given by
πi : id → α1 → α2 → · · · → αn → γ.
Another notion useful in our (maximal) flow analysis, is the permutation cluster. We define a
permutation cluster of a given permutation αx as all the edge-connected permutations to αx .
Definition 5.7. A permutation cluster [αx ] is defined as all the edge-connected permutations
to αx ∈ Sn .
Remark 5.8. With the poset structure in GA|B , we have a naturally induced ordering in the
cluster structures for each connected permutations to the permutation elemnents {αi }i∈{x,y,z}
where all the properties of the above definition can be extended to the cluster [αi ] of a given
permutation αi . More precisely the following holds:
αx ≤ αy =⇒ [αx ] ≤ [αy ].
αx = αy =⇒ [αx ] = [αy ].
αx ≤ αy ≤ αz =⇒ [αx ] ≤ [αy ] ≤ [αz ].
Definition 5.9. The maxflow in GA|B is the maximum of all the edges disjoint paths in
P̃(GA|B ):
n o
maxflow(GA|B ) := max P̃(GA|B ) : s.t. the paths in P̃(GA|B ) are edge-disjoint .
16 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

In the following proposition, we will give a lower bound of the extended Hamiltonian HGA|B (α)
which will be saturated when the maximal flow in GA|B is achieved as shown in Proposition
5.12. Hastings uses similar ideas in [Has17, Lemma 4] to lower bound the moments of a random
tensor network map.
|V |
Proposition 5.10. Let α ∈ Sn and P̃(GA|B ) be an arbitrary set of edge-disjoint paths in
GA|B , and set k := |P̃(GA|B )|, the following inequalities holds:
(n) (n)
HGA|B (α) ≥ k(n − 1) + HG F
πi (α) ≥ k(n − 1), (14)
A|B \ i∈[k]

(n)
where HG F
πi (α) defined as:
A|B \ i∈[k]

(n)
X X X
HG F
πi (α) := |γ −1 αx | + | id−1 αx | + |αy−1 αx |.
A|B \ i∈[k] F F F
x∈VA \ i∈[k] πi x∈VB \ i∈[k] πi x∼y∈Vb \ i∈[k] πi
(15)
F
One should mention that in the proposition above the sums are over β \ i∈[k] πi for β ∈
{VA , VB , Vb } which are the set of the different boundary and bulk regions when one takes off all
the different edges and vertices that will contribute in different paths πi ∈ P̃(GA|B ) in GA|B .

Proof. Let the set of edge disjoint paths {πi }i∈[k] ∈ P̃(GA|B ). Fix a path πi for a given i ∈ [k]
where:
πi : id → αx1 → αx2 → · · · → αxn → γ,
is a path that starts from id and explores {xi }i∈[n] vertices and ends in γ. By using equation
(13), and using the path defined above one obtains:
n−1
(n) (n) (n)
X
HGA|B (α) = |αx1 | + |αx−1 αxi+1 | + |αx−1 γ| + HG (α) ≥ n − 1 + HG (α),
i n A|B \πi A|B \πi
i=1

where we have used the triangle inequality of the Cayley distance and |γ| = n − 1. The
(n)
Hamiltonian HG \πi (α) is the contribution when the path πi from GA|B is used.
A|B

By iteration over all the edges disjoint paths {πi }i∈[k] ∈ P̃(GA|B ) one obtains the desired result.
(n)
The second inequality is obtained by observing that HG \πi (α) ≥ 0, ending the proof of the
A|B
proposition. □
(n)
Proposition 5.11. Given a graph G, there exist a tuple of permutations α such that HGA|B (α) =
maxflow(GA|B ).

Proof. By the celebrated max-flow min-cut theorem, the maximum flow in the network is equal
to its minimal cut. Recall that a cut of a network is a partition of its set of vertices into two
subsets S ∋ s and T ∋ t, and the size of the cut is the number of S − T edges. In our setting,
the max-flow min-cut theorem (see e.g. [KVKV11, Theorem 8.6]) implies that there exists a
partition of the vertex set Ṽ of GA|B (see Definition 5.1 into two subsets, Ṽ = S ⊔ T , with
id ∈ S and γ ∈ T , such that

maxflow(GA|B ) = {(x, y) ∈ Ẽ : x ∈ S and y ∈ T } .

Define, for x ∈ V ,
(
id if x ∈ S
αx =
γ if x ∈ T.
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 17

S T

id γ

Figure 5. The different edges that correspond to a cut S − T in the network

GA|B .

Since id ∈ S and γ ∈ T , we have:

(n)
X X X
HGA|B (α) = |γ −1 αx | + | id−1 αx | + |αx−1 αy |
x∈VA x∈VB (x,y)∈Vb
X X X
= |γ −1 αx | + | id−1 αx | + |αx−1 αy |
x∈VA x∈VB (x,y)∈Vb
x∈S x∈T x∈S and y∈T
h
= (n − 1) |{(x, ·) ∈ A : x ∈ S}| + |{(x, ·) ∈ B : x ∈ T }|+
i
|{(x, y) ∈ Eb : x ∈ S and y ∈ T }|
= (n − 1) maxflow(GA|B ),
where we have used in the last claim the fact that there are no edges between id and γ in Ẽ,
see Fig. 5. □
Proposition 5.12. For all n ≥ 1, we have
(n)
min HGA|B (α) = (n − 1) maxflow(GA|B ).
|V |
α∈Sn

Proof. This follows from the two previous propositions. □

Once we identify and remove all the augmenting paths in the network GA|B achieving the
maximal flow, we obtain a clustered graph GcA|B by identifying different remaining connected
permutations.
The following example gives an illustration of the different steps described above to analyse the
maxflow problem in the case of the tensor network represented in Figure 1.
Example 5.13. Figure 7 represents the network GA|B associated with the random tensor net-
work from Figure 1. The vertices in the network are valued in the permutation group Sn . The
network is constructed by adding two extra vertices γ and id by connecting all the half edges in
A to γ and the half edges in B to id. The flow approach induces a flow from id to γ where
the maximum flow in Figure 7 is 4 where the augmenting paths achieving it are colored. By
removing the four edge-disjoint augmenting paths we obtain the clustered graph GcA|B in Figure
8 by identifying the remaining connected edges as a single permutation cluster, i.e id with α15
to form the cluster [id, 15].
Theorem 5.14. In the limit D → ∞, we have, for all n ≥ 1,
1 h  n  i
lim E F (G ) Tr DF (GA|B )−|E∂ | ρA = mn ,
D→∞ D A|B

where mn is the number of permutations achieving the minimum of the network Hamiltonian
(n)
GA|B . These numbers are the moments of a probability measure µGA|B which is compactly
supported on [0, +∞).
(n)
Proof. For fixed n, the convergence to mn , the number of minimizers of the Hamiltonian GA|B ,
follows from Proposition 4.1 and Proposition 5.12. The claim that the numbers (mn )n are
18 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

the moments of a compactly supported probability measure follows basically from Prokhorov’s
theorem [Bil13, Section 5] (see also [Has17, Footnote 2]). Indeed, note that, at fixed D, the
quantity
1 h  n  i
E F (G ) Tr DF (GA|B )−|E∂ | ρA
D A|B

is the n-th moment of the empirical eigenvalue distribution of the random matrix DF (GA|B )−|E∂ | ρA ,
restricted to a subspace of dimension DF (GA|B ) containing its support (this follows from the fact
that DF (GA|B ) is an upper bound on the rank of ρA , see Eq. (5)). These measures have finite
second moment, so the sequence (index by D) is tight. The limiting moments satisfy Carleman’s
|V |
condition since mn ≤ Catn , proving that the limit measure µGA|B has compact support; recall
that Catn ≤ 4n is the n-th Catalan number, see Appendix A. Since the matrix ρA is positive
semidefinite, µGA|B must be supported on [0, +∞). □
Remark 5.15. The obtained moments are given by a graph dependent measure. We will show
in the following sections that such measures can be explicitly constructed if the partial order
GoA|B is series-parallel (see Section 6 and Theorem 6.4 for more details).
In all that we have described above, the contribution terms at large bond dimension D → ∞ of
(n) (n)
E Tr(ρnA ) are the ones that minimise HGA|B (α). As we have shown in Proposition 5.12 HGA|B (α)
is minimized when the maximal flow is attained in GA|B .
For later purposes, if one wants to analyse the moment of ρ̃A , one should also consider the con-
tribution of the normalisation term of ρ̃A at large bond dimension. We recall from Proposition
4.2 the contribution of the normalisation term is given by:
X (n)
E [(Tr ρA )n ] = Dn|E|−n|Eb |−hG (α) , ∀ n ∈ N
|V |
α=(αx )∈Sn

where
(n)
X X
hG (α) := | id−1
x αx | + |αx−1 αy |.
(x,·)∈E∂ (x,y)∈Eb
At large dimension D → ∞, the contributed terms are given by the one that will minimize the
(n)
extended Hamiltonian hGA|B (α) in GA|B :
(n)
X X
hGA|B (α) := | id−1 αx | + |αx−1 αy |,
x∈V∂ (x,y)∈Vb

where the first some is over all the vertices V∂ with boundary edges, and Vb are the bulk vertices.
(n)
Proposition 5.16. Let hGA|B (α) the extended Hamiltonian in GA|B . For all n ≥ 1, we have:
(n)
min hGA|B (α) = 0,
|Ṽ |
α∈Sn
achieved by identifying all the permutations with id.
(n)
Proof. To minimize the Hamiltonian hGA|B (α) we shall follow the same recipe where we connect
(n)
all half edges A to γ and half edges B to id. However in hGA|B (α), all the boundary terms will
be connected to id, hence no path starts from id that ends in γ. By the bulk connectivity of
G, the minimum is achieved by identifying all the permutations to id, therefore by Proposition
5.12 we obtain the desired result. □
(n)
Remark 5.17. In Proposition 5.16, the Hamiltonian hGA|B (α) is obtained by tacking A = ∅ in
(n)
HG (α) (see equation (9)). One should mention if B = E∂ \ A = ∅ we will have the same form
(n)
of the Hamiltonian hGA|B (α) where instead of all the half edges connected to id they will be all
connected to γ. Therefore one deduce that there is no paths that starts from id and ends to γ,
hence the minimum is 0 achieved by identifying all the permutations with γ.
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 19

Corollary 5.18. For any A ⊆ E∂ moments of the normalisation term converges to 1, more
precisely:   n
lim E Tr D−|E∂ | ρA = 1.
D→∞

Proof. By tacking the average as was shown in Proposition 4.2 one obtains the Hamiltonian
(n)
hG (α). By the maximal flow the Hamiltonian is minimised by identifying all the permutations
to the id, therefore F (GA|B ) = 0 as was shown in Proposition 5.16. Therefore by removing all
the augmenting paths achieving the maximal flow the obtained residual graph is trivial with
only two disjoint vertices γ and the identity cluster [id]. Hence by Theorem 5.14 one obtains
the desired result. □

6. Moment for ordered series-parallel network

In this section, we will introduce the notion of a series-parallel graph. This notion will allow
us to compute the moment as an explicit graph-dependent measure explicitly. More precisely
we will show with the help of free probability in the case of the obtained partial order GoA|B is
series-parallel the obtained graph-dependent measure is explicitly constructed.
In Subsection 6.1 we will introduce the notion of the series-parallel graph and the associated
measures. In Subsection 6.2 we will show in the case of a series-parallel partial order GoA|B the
moments converge to moments of a graph-dependent measure.

6.1. Series-Parallel graph. In this subsection, we introduce the notion of the series-parallel
partial orders which will allow us in the following subsection to explicitly compute the moments
as graph dependent measures.
We shall start first by recalling first the notion of series-parallel partial order [BDGR97] and
giving some crucial definitions that will play an important role in all the rest of this section.
Given two partial orders (Pi , ≤i ), i = 1, 2, one defines their series, resp. parallel, composition
as follows. The base set is P := P1 ⊔ P2 and the order relation is: x ≤ y if
• x, y ∈ Pi and x ≤i y or x ∈ P1 and y ∈ P2 in the series case;
• x, y ∈ Pi and x ≤i y in the parallel case.
It is more convenient for us to represent partial orders by their covering graphs, where to a
partial order (P, ≤) we associate an oriented graph G(V, E), with V = P and x → y ∈ E iff
x < y and ∄z s.t. x < z < y. We recall that we write x < y to denote x ≤ y and x ̸= y.
The series and parallel composition for partial orders have an elegant interpretation in terms
of directed graphs (or networks in this case). In what follows, we shall interchangeably use the
terms partial order or partial order graph.
Definition 6.1. [BDGR97] Let H1 and H2 two directed graph with there respective source si
and sink ti for i ∈ {1, 2}. A series-parallel network is a directed graph G = (V, E) containing
two distinct vertices s ̸= t ∈ V , called the source and the sink that can be obtained recursively
from the trivial network Gtriv = ({s, t}, {{s, t}}) using the following two operations:
F
• Series concatenation: G = H1 S H2 is obtained by identifying the sink of H1 with the
source of H2 , i.e t1 = s2 . F
• Parallel concatenation: G = H1 P H2 obtained by identifying the source and the sink of
H1 and H2 , i.e. s1 = s2 and t1 = t2 .

Remark 6.2. Note that the parallel concatenation is a commutative operation, while the series
concatenation is not, in general, commutative:
G G
∀G, H G P H=H P G
G G
in general G S H ̸= H S G.

We shall associate from a given series-parallel network different probability distributions con-
structed from the paralllel and the series concatenation introduced in Definition 6.1.
20 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

s1 t1 s2 t2 s1 t1 = s2 t2
H1 S H2 = H1 H2

H1
s1 t1 s2 t2 s1 = s2 t1 = t2
H1 P H2 =

H2

Figure 6. Series (top) and parallel (bottom) composition of two networks

(graphs) H1,2 .

Definition 6.3. To a series-parallel network G we associate a probability measure µG , defined

recursively as follows:
• To the trivial network Gtriv = ({s, t}, {{s, t}}), we associate the Dirac mass at 1:
µGtriv := δ1
• Series concatenation corresponds to the free multiplicative convolution of the parts, along
with the measure MP:
µG FS H := µG ⊠ MP ⊠ µH
• Parallel concatenation corresponds to the classical multiplicative convolution of the parts:

P H := µG × µH .
µG F
In the definition above we have used the free product convolution ⊠ and the Marc̆henko-Pastur
distribution MP. We refer to the Appendix A for a self-contained introduction to free probability
theory.

6.2. Moment as graph dependent measure. In this subsection, with the help of the series-
parallel notion introduced in the previous subsection, we will show the moments mn in Theorem
5.14 are explicitly constructed from a graph-dependent measure in the case of the obtained
partial order GoA|B is series-parallel.
Before we give the results of this subsection we recall first the different results obtained from
the previous sections. From a given random tensor network as represented for an example
in Figure 1, we have computed in Section 4 the moment for a normalised quantum state to
a given subregion A ⊆ E∂ of the graph (see Propositions 4.1 and 4.2). We approached the
evaluation of the moment as D → ∞ by the maximal flow approach as analysed in Section 5.
We have constructed from the graph G the network GA|B by connecting each of the regions A
and B respectively to γ and id. The flow consists of analysing the different paths starting from
id and ending in γ. By taking off all the different augmenting paths achieving the maximal
flow a clustered graph GcA|B remains by identifying different edge-connected permutations. As
represented in Figure 8 for the clustered graph associated with the network GA|B in Figure 1.
With the maximal flow, we were able in Proposition 5.12 which allows us to show the convergence
of moments given by a graph dependent measure µGA|B as shown in Theorem 5.14. Moreover
from Proposition 5.16 one deduce in Corollary 5.18 that the normalisation terms converge to 1.
From the clustered graph GcA|B , we will construct an partial order GoA|B where the vertices in
GoA|B are the different permutation clusters. See Figure 9 for the obtained partial order GoA|B
to the network GA|B in Figure 1. If the partial order GoA|B is series-parallel (see Definition
6.1), then we will explicitly show, in the following subsections, that we have a convergence in
moments of ρ̃A to an explicit partial order measure µGoA|B .
The following theorem shows the convergence to a moment-dependent measure µGoA|B in case
of obtained partial order GoA|B is series-parallel.
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 21

Theorem 6.4. For any A ⊆ E∂ , and assuming the partial order GoA|B is series-parallel, then
the limit measure from Theorem 5.14 can be explicitly constructed from the partial order:
µGA|B = µGoA|B .
In particular, the moments of the reduced tensor network matrix are given by:
1  n  Z
F (GA|B )−|E∂ |
lim E Tr D ρA = tn dµGoA|B . (16)
D→∞ D F (GA|B )

Proof. All we need to show is that the numbers mn,GoA|B are the moments of the probability
measure µGoA|B . We shall prove this using the recursive structure of the series-parallel networks
(see Definition 6.1) and that of the probability measure µGoA|B (see Definition 6.3).
If the partial order GoA|B is trivial, it consists only of two connected components, that of the
identity (the source) [id] and that of the sink, [γ]. Hence, all the permutations associated to the
connected components are fixed to be either id or γ. We have thus mn,GoA|B = 1 for all n ≥ 1,
which are the moments of the measure µGoA|B = δ1 . This shows that the claim holds for the
initial case of a trivial network.
If the partial order GoA|B is the parallel concatenation of two networks GoA|B = H1 P H2 having
F

the same source and sink as GoA|B , the geodesic equalities for GoA|B are the disjoint union of the
geodesic equalities for the vertices in H1 and those for the vertices of H2 . This implies in turn
that, for all n ≥ 1,
mn,GoA|B = mn,H1 · mn,H2 ,
since there is no geodesic inequality mixing vertices from H1 with vertices in H2 . Hence, by the
induction hypothesis, we have
Z Z Z G Z
n n n
mn,GoA|B = t dµH1 · t dµH2 = t d µH1 P µH2 = tn dµGoA|B ,
 

proving the claim for the parallel concatenation of networks.

Finally, let F
us consider the case where the network is the series concatenation of two networks
GoA|B = H1 S H2 . This means that there is a connected component, call it [β] which is common
of the two networks, being the sink of H1 and the source of H2 . All geodesic equality conditions
for the H1 are of the form
(1) (1)
id → α1 → · · · → αk1 → β,
while those of H2 are of the form
(2) (2)
β → α1 → · · · → αk2 → γ.
In particular, the geodesic equality conditions for GoA|B = H1
F
S H2 are of the form
(1) (1) (2) (2)
id → α1 → · · · → αk1 → β → α1 → · · · → αk2 → γ.
The variable β is a non-constrained non-crossing partition of [n], and summing over it cor-
responds to taking the free multiplicative convolution with respect to the Marc̆henko-Pastur
distribution:
X Z Z Z
mn,GoA|B = 1 = tn dµH1 ⊠ MP ⊠ µH2 = tn dµH1 FS H2 = tn dµGoA|B ,
β∈NC(n)
(1) (2)
αi ≤β≤αj

proving the final claim and concluding the proof. □

Example 6.5. As an example, let us consider the graph illustrated in Fig. 1. As we have de-
scribed in the previous sections, the dominant terms of moments in Proposition 4.1 are obtained
by analyzing the maximum flow in GA|B , given in Fig. 7 where maxflow(GA|B ) = 4. The partial
order GoA|B , obtained by removing from GA|B the edges that participate in the maximum flow is
depicted in Fig. 8. Using the 4 augmenting paths (displayed in colors in Fig. 7), we construct
the partial order on the connected components of the partial order, that we depict in Fig. 9.
22 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

3 4

1 2 6 13

5 12 14

7 9
id γ
10 11
15
17

16

8
Figure 7. The network associated to the random tensor network marginal from
Fig. 1. The maximum flow of this network (with source id and sink γ) is 4, the
four augmenting paths achieving this value are colored.

3 4

1 2 6 13

5 12 14

7 9
id γ
10 11
15
17

16

8
Figure 8. The clustered network corresponding to Fig. 7, obtained by removing
the four edge-disjoint augmenting paths.

[3] [4]

[1] [2]
[6, 13]

[5, 12]

[7] [9, 17]

[id, 15] [14, γ]
[10] [11]

[8, 16]

Figure 9. The order graph corresponding to the networks from . The partial
order relations are to be read from left to right. The elements of this partial or-
der relation are the connected components of the clustered network from Fig. 8,
eventually identified after taking into account the inequalities from the augment-
ing paths from Fig. 7.

This process is fundamental in our approach, we give the details for one of these geodesics next.
For example, consider the augmenting path
id → 1 → 2 → 3 → 4 → 13 → 6 → 10 → γ
depicted in red in Fig. 7. Since in the clustered graph from Fig. 8 the respective pair of points
(id, 15), and 14, γ are in the same connected components (clusters), this augmenting path gives
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 23

G2 G3

G1
Figure 10. Representation of the partial order GoA|B factorises to a series com-
bination of graphs G1 , G2 and G3 .

rise to the following list of partial order relations:

[id, 15] ⪯ [1] ⪯ [2] ⪯ [3] ⪯ [4] ⪯ [13] ⪯ [6] ⪯ [10] ⪯ [14, γ].
The other three augmenting paths, depicted respectively in blue, green, and orange in Fig. 7,
give rise to the following list of inequalities:
[id, 15] ⪯ [1] ⪯ [2] ⪯ [5, 12] ⪯ [6] ⪯ [13] ⪯ [10] ⪯ [11] ⪯ [14, γ]
[id, 15] ⪯ [7] ⪯ [9, 17] ⪯ [10] ⪯ [11] ⪯ [14, γ]
[id, 15] ⪯ [8, 16] ⪯ [9, 17] ⪯ [14, γ].
The partial order depicted in Fig. 9 is compiled from the set of inequalities coming from the
(fixed) list of augmenting paths yielding the maximum flow (here 4). Note that, importantly,
some connected components (clusters) can be identified in this partial order, due to the anti-
symmetry property x ⪯ y and y ⪯ x =⇒ x = y; this happened in this example for the clusters
[6] and [13].
As an application of Theorem 6.4, one can give explicit moments of the measure µGoA|B ,A :
h i Z
−4 −6
lim ED Tr (D ρA ) = mn,GoA|B = xn dµGoA|B .
n
(17)
D→∞

The powers of D in the normalization follow from |E∂ | = 10 (see the boundary edges in Fig. 1)
and from maxflow(GA|B ) = 4. The resulting probability measure µGoA|B associated to the partial
order from Fig. 9 is given by:
µGoA|B = MP⊠3 ⊠ (MP⊠2 × MP) × [(MP × MP) ⊠ MP] ⊠ MP⊠2 .
 
(18)
The measure given above is obtained by the iterative procedure from Definition 6.3 as follows.
First,
F observe
F that the graph in Fig. 9 can be decomposed as a series composition of three graphs
G1 S G2 S G3: hence, using µG2 = µG3 = δ1 , we have
µGoA|B = µG1 ⊠ MP ⊠ µG2 ⊠ MP ⊠ µG3 = µG1 ⊠ MP⊠2 .
Observe now that G1 is a parallel composition of two other graphs hence
µG1 = µG4 × µG5 .
Let us now analyze separately G4 and G5 . Firstly, G4 can be decomposed as a series composition
between the parallel composition of G6 and G7 , and G8 : that is
 G G
G4 = G6 P G7 S G8 =⇒ µG4 = (µG6 × µG7 ) ⊠ MP ⊠ µG8 .
Now, G6 and G7 are series compositions of two trivial graphs, so µG6 = µG7 = MP, while
µG8 = δ1 . We have thus
µG4 = (MP × MP) ⊠ MP.
Let us now turn to G5 , which can be decomposed as follows: that is
24 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

G5

G4
Figure 11. The graph G1 is factorized to the parallel composition of G4 and
G5 .

G6

G8

G7
Figure 12. The graph G4 is factorised to the series composition of the graph
G8 with the graph G6 parallel to G7 .

G11

G9 G10
G13

G12

Figure 13. The graph G5 factorises as a serie composition of G9 , G10 with G11
composed in parallel with G12 and series with G13 .

G G G G
G5 = G9 S G10 S G11 P G12 S G13 .

In terms of the associated probability measures, we have

µG5 = µG9 ⊠ MP ⊠ µG10 ⊠ MP ⊠ (µG11 × µG12 ) ⊠ MP ⊠ µG13 .
Using iteratively series compositions, we have
µG11 = MP⊠2 and µG12 = MP.
We obtain
µG5 = MP⊠3 ⊠ MP⊠2 × MP .

Putting all these ingredients together, we obtained the announced formula for µGoA|B .

Remark 6.6. In the example of the tensor network represented in Figure 1 we were able to
compute the moments from the factorised series-parallel thought the flow approach. One should
mention if one take the minimal cut approach to the problem, there exist minimal cuts in the
network represented in Figure 7 do intersect, see Fig. 14. Therefore we can compute the correc-
tion terms of the entropy as the moment of a given measure without any minimal cut assumption
considered in previous work.
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 25

3 4

1 2 6 13

5 12 14

7 9
id γ
10 11
15
17

16

Figure 14. Different cuts of size 4 in the network of Fig. 7, represented with
blue, dashed lines. Notice that some of these minimal cuts (the maximum flow
in the network is 4) share some edges, represented in red.

Remark 6.7. The obtained measure µGoA|B for a given ordered series-parallel graph GoA|B has
a compact support where it combines the Marc̆henko-Pastur distribution with classical product
measure and free product convolution constructed from the structure of GoA|B .

7. Examples of series-parallel networks

In this section we apply the results obtained previously for various random tensor networks
having an induced series-parallel order. We start from simple cases and work our way towards
more physically relevant cases.
7.1. Single vertex network. We start with the simplest possible case: a tensor network
having only one vertex, no bulk edges, and two boundary half-edges, see Fig. 15. For this
network, the associated random tensor
ΨG ∈ CD ⊗ CD
has i.i.d. standard complex Gaussian entries. The two boundary half-edges are partitioned into
two one-element sets A and B = Ā. From this tensor, we construct the reduced matrix
ρA := TrB |ΨG ⟩⟨ΨG |
obtained by partial tracing the half-edge B. Note that in this very simple case, the matrix ρA
can also be seen as a product of the matricization of the tensor ΨG with its hermitian adjoint,
hence ρA is a Wishart random matrix (see Appendix A for the definition and basic properties
of Wishart matrices).
In order to analyze the large D spectral properties of ρA , we first construct the network GA|B ,
obtained by connecting all the half-edges in G that belong to A to a new vertex γ and those
in B to a new vertex id. The flow analysis of this network is trivial: there is a unique path
from id to γ, hence the maximum flow is 1 and the residual network is empty (both edges in
the network have been used for the construction of the unique maximum flow).
Since there is a unique path achieving maximum flow and a single vertex in the network, the
partial order induced by the path is very simple: id −α1 − γ. Hence, the only condition on the
permutation α1 ∈ Sn is that it should lie on the geodesic between the identity permutation id
and the full cycle permutation γ ∈ Sn . We have thus a series network, see Fig. 15 bottom right
diagram. The limit moment distribution is MP, the Marc̆henko-Pastur distribution (of param-
eter 1). This matches previously obtained results about the induced measure of mixed quantum
states (density matrices) [ŻS01, SŻ04, Nec07]. Indeed, the matrix ρA can be interpreted in quan-
tum information theory as the partial trace of the rank-one matrix in the direction of a random
Gaussian vector ΨG ∈ Cd ⊗ Cd . Up to normalization, this random density matrix belongs to
the ensemble of induced density matrices. The fact that the two factors of the tensor product
have equal dimensions corresponds to taking the uniform measure on the (convex, compact) set
26 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

B A
1 ΨG

ρA = ΨG Ψ∗G

id α1 γ [id] [1] [γ]

Figure 15. A single vertex network. On the top row, we represent the network
and the associated random tensor ΨG . In the middle row we represent the
reduced matrix ρA , obtained by partial tracing the edge B between ΨG and Ψ∗G .
In the bottom row, we represent the network GA|B and the partial order graph
GoA|B .

of density matrices [ŻS03, ŻPNC11]. The statistics of the eigenvalues of such random matrices
have been extensively studied in the literature. In particular, the asymptotic von Neumann
entropy has been studied by Page [Pag93, FK94, SR95], who conjectured that
2D
X 1 D−1 1
ES(ρA ) = − ∼ log D − as D → ∞.
i 2D 2
i=D+1

We refer to Section 8 for a derivation of such statistics in the context of our work.

7.2. Series network. Let us now consider a tensor network consisting of s vertices arranged
in a path graph, with two half-edges at the end points. We depict this network, as well as the
various steps needed to compute the limiting spectrum distribution of the reduced matrix. The
network associated to the graph (where the partition of the half-edges is clear) has a single path
from the source to the sink, so the maximum flow is unity.

B A
1 2 ··· s

id α1 α2 αs γ
···

[id] [1] [2] [s] [γ]

···

Figure 16. A series network. The s vertices of the network are arranged in a
line, with two half-edges at the end points. The maximum flow is 1, and it is
unique. The single path realizing the flow induces a (total) order α1 ≤ α2 ≤
· · · ≤ αs on the geodesic permutations.
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 27

The residual graph, obtained by removing the edges from the unique path achieving maximum
flow, is empty. Hence, the partial order on the vertices is again a total order:
id ⪯ α1 ⪯ · · · ⪯ αs ⪯ γ.
We have thus a series network, and the final measure can be obtained by applying s times the
series concatenation procedure from Definition 6.3 to obtain
⊠ · · · ⊠ MP} = MP⊠s .
µGoA|B = |MP ⊠ MP{z
s times

Let us note that very similar results were previously obtained by Cécilia Lancien [Lan], see
also [CLP+ 24]. This measure is commonly know as the Fuss-Catalan distribution of order s
[BBCC11], see also Theorem A.6. Its moments are known in combinatorics as the Fuss-Catalan
numbers: Z  
n ⊠s 1 sn + n
t dMP (t) =
sn + 1 n
and its entropy is [CNŻ10, Proposition 6.2]
Z s+1
X 1
−t log t dMP⊠s (t) = .
i
i=2

Such tensor network states have already been considered in quantum information theory [CNŻ10,
CNŻ13, ŻPNC11]

7.3. 2D lattice. We now discuss a physically relevant network: a rectangle that is part of a
2D lattice (part of Z2 ). We have thus two integer parameters, the length L and the height H
of the rectangle, and H · L vertices. The vertices are connected by the edges inherited from the
Z2 lattice, see Fig. 17. The left-most (resp. right-most) columns of vertices have half-edges that
belong to the class B (resp. A) of the half-edge partition defining the two regions.

(1, 1) (1, 2) (1, L)

(2, 1) (2, 2) (2, L)

B A

(H, 1) (H, 2) (H, L)

Figure 17. A network corresponding to a H × L 2D lattice. Half-edges are

attached to vertices on the left and right boundary, corresponding to a tensor in
(CD )⊗2H .

The flow network corresponding to the graph and the partition A|B is depicted in Fig. 18, top
diagram. The maximum flow in this network is H: one can consider H parallel horizontal paths
which go from id to γ. Note that the set of H edge-disjoint paths in the network achieving the
maximum flow is unique. The residual network is non-empty in this case, with H clusters of
the form
Cj := {[i, j] : i = 1, . . . , L}.
The order relation on the clusters is again a total order on L points, see Fig. 18, bottom diagram.
We are thus recovering again the Fuss-Catalan distribution:
µGoA|B = MP⊠ L.
28 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

α1,1 α1,2 α1,L

α2,1 α2,2 α2,L

id γ

αH,1 αH,2 αH,L

[id] [·, 1] [·, 2] [·, L] [γ]

···

Figure 18. The newtwork associated to the H × L Z2 lattice fragment. The

maximum flow in this network is H, corresponding to horizontal edge-disjoint
paths. These H paths induce a total order on the L vertex clusters, each having
H vertices.

8. Results for normalized tensor network states

In this section, we will give our main technical contribution. With the help of all the results
obtained from the previous sections, we will be able in this section to compute the Rényi and
von Neumann entropy for a given approximated normalised state ρ̃A := D−|E∂ | ρA associated to
a given boundary subregion A ⊆ E∂ . The main results of this section consist first on showing
the weak convergence of moments associated to an approximated reduced state ρ̃A associated
with a given boundary region A in Theorem 8.4. Moreover we will show in Corollary 8.7 the
existence of correction terms as moments of a graph-dependent measure which can be explicitly
computed in the case of an obtained series-parallel partial order GoA|B .
In Subsection 8.1 we will show different concentration inequalities, which will allows us in
Subsection 8.2 to give the main results of this section.
8.1. Concentration. In this subsection, we will give different concentration results that will
allows us in the following subsection to give our main technical contribution.
First, we recall the following theorem that estimates the deviation probability of polynomials
in Gaussian random variables. This theorem will be relevant for different concentration results
that we will proof in the rest of this subsection.
Theorem 8.1. Let g be a polynomial in m variables of degree q. Then, if G1 , · · · , Gm are
independent centered Gaussian variables,
2
 1
  
∀t > 0, P g(G1 , · · · , Gm ) − E g > t(Var(g)) 2 ≤ exp −cq t q ,
where V (g) is the variance of g(G1 , · · · , Gm ) and cq is a constant which depends only on q.
Proposition 8.2. Let G a bulk connected graph and let A ⊆ E∂ then:
 |Eb |

1
 
P Tr ρ̃A − 1 > ε ≤ exp −c|E| ε D |E| 2|E| ,

where ρ̃A := D−|E∂ | ρA .

Proof. First remark that Tr ρA is a 2|E| polynomial in |gx ⟩ ∈ Hx , moreover we recall that for
random Gaussian vector |gx ⟩ ∈ Hx one have:
∀x ∈ V, E [|gx ⟩⟨gx |] = idx and E |gx ⟩⟨gx |⊗2 = idx +Fx ,
 

where the idx and Fx acts in all the edges of Hilbert space generating the local Hilbert space
for each vertex x. Moreover, it is implicitly assumed that idx ≡ id⊗2
x and the Swap operator Fx
is a unitary representation of permutation element in S2 .
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 29

It is easy to check the variance Var(Tr ρ̃A ) gives:

 
Var(Tr ρ̃A ) = E (Tr ρ̃A )2 − (E [Tr(ρ̃A )])2 = O D−|Eb | ,
 

where we have used that:

 
O O 
E (Tr ρ̃A )2 = Tr  |Ωe ⟩⟨Ωe |⊗2 E |gx ⟩⟨gx |⊗2 
  

e∈Eb x∈V
Y
Y
= 1 + D|E∂ | Tr |Ωe ⟩⟨Ωe |⊗2 Fe Tr (Fe )
e∈Eb e∈E∂
 
= 1 + O D−|Eb | ,

where in the last equality the bulk contribution is of D−|Eb | while the boundary edges contribute
with D|E∂ | . The second term of the variance is :
 
O O
E [Tr(ρ̃A )] = Tr  |Ωe ⟩⟨Ωe | E [|gx ⟩⟨gx |] = 1.
e∈Eb x∈V

By combining the variance Var(Tr(ρ̃A )) with Proposition 8.1 one have:

 |Eb |

1
 
P Tr ρ̃A − E Tr ρ̃A > ε ≤ exp −c|E| ε D |E| 2|E| ,
|Eb |
 
where we have defined ε := t D− 2 with c|E| > 0 is a constant depending only in the total
number of edges |E|.
□
Proposition 8.3. Let G a bulk connected graph and let A ⊆ E∂ we have:
 1 n 1 n
  1 1

∀n > 1, P Tr(σ A ) − E[Tr(σA )] > ε ≤ exp − c2n|E| D 2n|E| ε n|E| ,
DF (GA|B ) DF (GA|B )
where σA := DF (GA|B ) ρ̃A .
Proof. The proof of this proposition follows the same proof spirit of the proposition above.
Remark that Tr σAn is a 2n|E| polynomial in |g ⟩. Moreover the variance was estimated in
x
[Has17, Lemma 14] where:
   
1 n 1
Var Tr(σA ) = O .
DF (GA|B ) D
1
By defining ε := tD− 2 we obtain the desired result. □
8.2. Entanglement entropy. In this subsection we will introduce the main technical contri-
bution of this work. With the help of concentration results, we will first assume and work with
the approximate normalised state ρ̃A := D−|E∂ | ρA . We will show that as D → ∞ one can
compute the average Rényi and von Neumann entanglement entropy with correction terms. In
particular if the obtained partial order is series-parallel, the correction terms will be given as
moment of an partial order dependent measure µGoA|B .
We recall first from Subsection 3.2 that the rank of the approximate normalised state is upper
bounded by DF (GA|B ) . Let consider the restricted approximate normalised quantum state ρ̃A
(D)
to its support and its empirical measure µA defined as:
(D) 1 X
σA := DF (GA|B ) ρ̃SA , and µA := F (G ) δλ ,
D A|B
λ∈spec(σ ) A

where ρ̃SA
is the reduced approximate normalised state restricted on its support. The definition of
(D)
ρ̃A and the empirical measure µA will allow us to show in Theorem 8.4 the weak convergence of
30 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

(D)
µA to µGA|B . In particular if the obtained partial order GoA|B is series-parallel from Theorem
6.4 one will have weak convergence to µGA|B . This result will allow us in Corollary 8.7 to
compute the Rényi and von Neumann entanglement entropy.
Recall first, that a measure µ(D) converges weakly to a measure µ if for any continuous function
f : R → R we have:
Z Z 
(D)
∀ε > 0, lim P f (t)dµ (t) − f (t)dµ(t) ≤ ε = 1.
D→∞

(D)
Theorem 8.4. Let boundary region A ⊆ E∂ in the graph G. The empirical measure µA
associated to the approximated normalised state σA converges weakly to µGA|B . More precisely
for all continuous function f : R → R we have:
Z Z 
(D)
∀ε > 0, lim P f (t)dµA (t) − f (t)dµGA|B (t) ≤ ε = 1.
D→∞

Proof. As was shown in Theorem 5.14 the moment converges to a unique measure µGA|B . In the
particular case of an ordered series-parallel graph GoA|B we have an explicit graph dependent
measure µGoA|B . Recall from Theorem 5.14 that:
Z
1 h
n
i
F (GA|B )
E Tr (σ A ) −
− −−→ m n = tn dµGA|B (t).
D D→∞

From standard probability theory results the convergence in probability implies weak conver-
gence (see [Bil12, Theorem 25.2]. For that one needs only to show the decreasing scaling of the
variance as D → ∞. By using [Has17, Lemma 14] that:
   
1 n 1
Var F (GA|B )
Tr(σA ) = O , (D → ∞),
D D
(D)
hence the weak convergence of µA to µGA|B , in particular if the graph is series-parallel we have
µGoA|B . □
(D)
Lemma 8.5. Let boundary region A ⊆ E∂ and let mn the moment associated to the empirical
(D)
measure µA one have:
      1 h i
P E log m(D) n − log Em (D)
n > ε −− −− → 1 where m (D)
n := E Tr (σ n
A .
)
D→∞ DF (GA|B )
   
(D) (D)
Proof. By Proposition 8.3 and Jensen’s inequality that E log mn ≤ log Emn . All what
   
(D) (D)
remains to show that E log mn ≥ log Emn holds with high probability. Fix ε > 0.
From Proposition 8.3 we know that
ε
m(D)
n ≥ Em(D) n − δ with 0 < δ ≤ Em(D)n ,
ε+1
1 1
 
holds with probability 1 − exp − c2n|E| D 2n|E| δ n|E| . It is easy to check that the following
inequalities hold:
!

(D)
 
(D)
 
(D)
 δ
log mn ≥ log Emn − δ = log Emn + log 1 − (D)
Emn
  δ  
≥ log Em(D)n − (D)
≥ log Em (D)
n − ε.
Emn − δ
   
(D) (D)
Therefore we have that E log mn ≥ log Emn − ε occurs with probability at least
1 
 1 ε
n|E|
1 − exp − c2n|E| D 2n|E| δmax where δmax = Em(D)
n .
ε+1
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 31

(D)
As D → ∞, Emn converges, hence δmax = O(1), showing that the probability estimate above
converges to 1 and finishing the proof. □
We recall for completeness the following proposition from [CN11] which will play a key role for
the proof of our main result.
Proposition 8.6. [CN11, Proposition 4.4] Let f be a continuous function on R with polynomial
growth and νn a sequence ofR probability
R measures which converges in moments to a compactly
supported measure ν. Then f dνn → f dν.
Corollary 8.7. Let boundary region A ⊆ E∂ in G, and let ρ̃A the approximated reduced nor-
malised state. Then the averaged Rényi and von Neumann entropy converges weakly as D → ∞
are given by:
Z 
1 n
F (GA|B ) log D − ESn (ρ̃A ) −−−−→ log t dµGA|B ,
D→∞ n − 1
Z
F (GA|B ) log D − ES(ρ̃A ) −−−−→ t log t dµGA|B .
D→∞

where F (GA|B ) := maxflow(GA|B ) .

Proof. The poof of this corollary is a direct consequence of different obtained concentration
(D)
results from the previous subsection and the weak convergence of µA to µGA|B .
First, we shall start with the Rényi entropy, for that let consider:
1 
(D)

(D) 1 h
n
i
F (GA|B ) log D − ESn (ρ̃A ) = E log mn,A , where mn := F (G ) E Tr ((σA ) ) ,
1−n D A|B

and recall that σA := DF (GA|B ) ρ̃SA restricted on the support of ρ̃A := D−|E∂ | ρA . By using
Lemma 8.5 and in the limit D → ∞ we have:
Z 
1 n
F (GA|B ) log D − ESn (ρ̃A ) −−−−→ log t dµGA|B .
D→∞ n − 1

For the von Neumann entropy let consider {λi } ∈ spec(σA ) and {λ̃i } ∈ spec(ρ̃A ), it is direct
that:
X 1 X
ES(ρ̃A ) = −E λ̃i log(λ̃i ) = F (GA|B ) log(D) − F (G ) E λi log(λi ).
i D A|B
i
Define the function f : R → R as f (t) := t log t, by combining Proposition 8.6 and Theorem 8.4
we have the following weak convergence as D → ∞
! Z
1 X
F (GA|B ) log D − ES(ρ̂A ) = F (G ) E f (λi ) −−−−→ f (t) dµGA|B ,
D A|B
i
D→∞

where the measure µGA|B is defined on a compact support, ending the proof of the corollary.
In the particular case if the obtained poset structure GoA|B is series parallel the obtained graph
dependent measure is explicitly given µGA|B = µGoA|B by Theorem 6.4. □

9. Conclusion
From a given graph general graph with boundary region and bulk region, the main goal of
this work is to compute the entanglement entropy, the Rényi and the von Neumann entropy,
of a given sub-boundary region A of the graph. By analysing as D → ∞ the moments of a
state associated to the region A, with the help of the (maximal) flow approach we computed the
leading terms contribution to the moment. By analysing and removing all the augmenting paths
starting from id and ending in γ of the network GA|B constructed by connecting the region A to
the total cycle γ and id to the region B one obtains a cluster graph GcA|B by identifying all the
remaining edges connected permutations. The flow approach induces a natural ordering poset
structure represented by the induced poset order GoA|B . The maximal flow approach allows
us to deduce the moment convergence to the moment of a unique graph-dependent measure
32 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

µGA|B . This result allows us to deduce the higher order correction terms of the Rényi and von
Neumann entropy given by a graph-dependent measure µGA|B . Moreover, we have shown if the
obtained partial order GoA|B is series-parallel, and with the hep of free probability theory we can
explicitly give the associated graph-dependent measure µGA|B = µGoA|B that will contribute to
the higher order correction terms of each of the Rényi and von Neumann entanglement entropy.
In this work, we did not assume any assumption on the minimal cuts, in the maximal flow ap-
proach by duality one can obtain different minimal cuts which may intersect in different edges.
Moreover, the higher-order correction terms in the entanglement entropy can describe the quan-
tum corrections beyond the area law behaviour of the expected Ryu-Takayanagi entanglement
entropy in the context of ADS/CFT. It was previously argued in the literature that if one wants
to consider higher-order correction terms in the random tensor network setting one needs to go
beyond the maximally entangled state and consider general link states representing the bulk
matter field. In this work the obtained higher-order quantum fluctuation of entanglement en-
tropy with only maximally entangled states that we interpret as fluctuations of spacetime itself
without any need of bulk fields represented by a generic link state.

Acknowledgments. We would like to thank Cécilia Lancien for sharing with us preliminary
notes on very similar questions. The authors were supported by the ANR projects ESQuisses,
grant number ANR-20-CE47-0014-01, and STARS, grant number ANR-20-CE40-0008, as well
as by the PHC program Star (Applications of random matrix theory and abstract harmonic
analysis to quantum information theory). K.F. acknowledges support from a NanoX project
grant.

References
[AGZ10] G.W. Anderson, A. Guionnet, and O. Zeitouni. An Introduction to Random Matrices. Cambridge
Studies in Advanced Mathematics. Cambridge University Press, 2010. 38

[AKC22] Harriet Apel, Tamara Kohler, and Toby Cubitt. Holographic duality between local hamiltonians
from random tensor networks. Journal of High Energy Physics, 2022(3):1–43, 2022. 2

[Arm07] Drew Armstrong. Generalized noncrossing partitions and combinatorics of coxeter groups, 2007. 35

[BBCC11] Teodor Banica, Serban Teodor Belinschi, Mireille Capitaine, and Benoit Collins. Free Bessel laws.
Canadian Journal of Mathematics, 63(1):3–37, 2011. 27, 39

[BDGR97] Denis Bechet, Philippe De Groote, and Christian Retoré. A complete axiomatisation for the in-
clusion of series-parallel partial orders. In International Conference on Rewriting Techniques and
Applications, pages 230–240. Springer, 1997. 19

[Bil12] P. Billingsley. Probability and Measure. Wiley Series in Probability and Statistics. Wiley, 2012. 30

[Bil13] Patrick Billingsley. Convergence of probability measures. John Wiley & Sons, 2013. 18

[BPSW19] Ning Bao, Geoffrey Penington, Jonathan Sorce, and Aron C Wall. Beyond toy models: distilling
tensor networks in full ads/cft. Journal of High Energy Physics, 2019(11):1–63, 2019. 2, 3, 6

[BS10] Zhidong Bai and Jack W Silverstein. Spectral analysis of large dimensional random matrices, vol-
ume 20. Springer, 2010. 38

[CCW22] Bowen Chen, Bartlomiej Czech, and Zi-Zhi Wang. Quantum information in holographic duality.
Reports on Progress in Physics, 85(4):046001, 2022. 2
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 33

[CGGPG13] Benoı̂t Collins, Carlos E González-Guillén, and David Pérez-Garcı́a. Matrix product states, random
matrix theory and the principle of maximum entropy. Communications in Mathematical Physics,
320:663–677, 2013. 2

[CLP+ 22] Newton Cheng, Cécilia Lancien, Geoff Penington, Michael Walter, and Freek Witteveen. Random
tensor networks with nontrivial links, 2022. 2, 9, 14

[CLP+ 24] Newton Cheng, Cécilia Lancien, Geoff Penington, Michael Walter, and Freek Witteveen. Random
tensor networks with non-trivial links. Annales Henri Poincaré, 25(4):2107–2212, 2024. 3, 6, 27

[CN11] Benoı̂t Collins and Ion Nechita. Gaussianization and eigenvalue statistics for random quantum
channels (III). The Annals of Applied Probability, pages 1136–1179, 2011. 4, 12, 31

[CN16] Benoit Collins and Ion Nechita. Random matrix techniques in quantum information theory. Journal
of Mathematical Physics, 57(1), 2016. 12

[CNŻ10] Benoı̂t Collins, Ion Nechita, and Karol Życzkowski. Random graph states, maximal flow and fuss–
catalan distributions. Journal of Physics A: Mathematical and Theoretical, 43(27):275303, 2010.
27

[CNŻ13] Benoı̂t Collins, Ion Nechita, and Karol Życzkowski. Area law for random graph states. Journal of
Physics A: Mathematical and Theoretical, 46(30):305302, 2013. 27

[CPGSV21] J Ignacio Cirac, David Perez-Garcia, Norbert Schuch, and Frank Verstraete. Matrix product states
and projected entangled pair states: Concepts, symmetries, theorems. Reviews of Modern Physics,
93(4):045003, 2021. 2

[DQW21] Xi Dong, Xiao-Liang Qi, and Michael Walter. Holographic entanglement negativity and replica
symmetry breaking. Journal of High Energy Physics, 2021(6):1–41, 2021. 2, 9

[FH17] Michael Freedman and Matthew Headrick. Bit threads and holographic entanglement. Communi-
cations in Mathematical Physics, 352:407–438, 2017. 2

[FK94] SK Foong and S Kanno. Proof of page’s conjecture on the average entropy of a subsystem. Physical
review letters, 72(8):1148, 1994. 26

[GGJN18] Carlos E González-Guillén, Marius Junge, and Ion Nechita. On the spectral gap of random quantum
channels. arXiv preprint arXiv:1811.08847, 2018. 2

[Har13] Aram W. Harrow. The church of the symmetric subspace, 2013. 12

[Has17] Matthew B Hastings. The asymptotics of quantum max-flow min-cut. Communications in Mathe-
matical Physics, 351:387–418, 2017. 8, 11, 16, 18, 29, 30

[HNQ+ 16] Patrick Hayden, Sepehr Nezami, Xiao-Liang Qi, Nathaniel Thomas, Michael Walter, and Zhao Yang.
Holographic duality from random tensor networks. Journal of High Energy Physics, 2016(11):1–56,
2016. 2, 3, 5, 6, 9

[KFNR22] Jonah Kudler-Flam, Vladimir Narovlansky, and Shinsei Ryu. Negativity spectra in random tensor
networks and holography. Journal of High Energy Physics, 2022(2):1–74, 2022. 2

[KVKV11] Bernhard H Korte, Jens Vygen, B Korte, and J Vygen. Combinatorial optimization, volume 1.
Springer, 2011. 14, 16
34 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

[Lan] Cécilia Lancien. Personal communication. 27

[LC21] Ryan Levy and Bryan K Clark. Entanglement entropy transitions with random tensor networks.
arXiv preprint arXiv:2108.02225, 2021. 2

[LM13] Aitor Lewkowycz and Juan Maldacena. Generalized gravitational entropy. Journal of High Energy
Physics, 2013(8):1–29, 2013. 3

[LPG22] Cécilia Lancien and David Pérez-Garcı́a. Correlation length in random mps and peps. In Annales
Henri Poincaré, volume 23, pages 141–222. Springer, 2022. 2

[LPWV20] Javier Lopez-Piqueres, Brayden Ware, and Romain Vasseur. Mean-field entanglement transitions in
random tree tensor networks. Physical Review B, 102(6):064202, 2020. 2

[LVFL21] Yaodong Li, Romain Vasseur, Matthew Fisher, and Andreas WW Ludwig. Statistical mechan-
ics model for clifford random tensor networks and monitored quantum circuits. arXiv preprint
arXiv:2110.02988, 2021. 2

[Mal99] Juan Maldacena. The large-n limit of superconformal field theories and supergravity. International
journal of theoretical physics, 38(4):1113–1133, 1999. 2

[MS17] James A Mingo and Roland Speicher. Free probability and random matrices, volume 35. Springer,
2017. 35

[MVS21] Raimel Medina, Romain Vasseur, and Maksym Serbyn. Entanglement transitions from restricted
boltzmann machines. Physical Review B, 104(10):104205, 2021. 2

[MWW20] Donald Marolf, Shannon Wang, and Zhencheng Wang. Probing phase transitions of holographic
entanglement entropy with fixed area states. Journal of High Energy Physics, 2020(12):1–41, 2020.
2

[Nec07] Ion Nechita. Asymptotics of random density matrices. Annales Henri Poincaré, 8(8):1521–1538,
2007. 25

[NRSR21] Adam Nahum, Sthitadhi Roy, Brian Skinner, and Jonathan Ruhman. Measurement and entangle-
ment phase transitions in all-to-all quantum circuits, on quantum trees, and in landau-ginsburg
theory. PRX Quantum, 2(1):010352, 2021. 2

[NS06] Alexandru Nica and Roland Speicher. Lectures on the combinatorics of free probability, volume 13.
Cambridge University Press, 2006. 35, 36, 37, 38

[Pag93] Don N Page. Average entropy of a subsystem. Physical review letters, 71(9):1291, 1993. 26

[PSSY22] Geoff Penington, Stephen H Shenker, Douglas Stanford, and Zhenbin Yang. Replica wormholes and
the black hole interior. Journal of High Energy Physics, 2022(3):1–87, 2022. 2

[QSY22] Xiao-Liang Qi, Zhou Shangnan, and Zhenbin Yang. Holevo information and ensemble theory of
gravity. Journal of High Energy Physics, 2022(2):1–24, 2022. 2

[QY18] Xiao-Liang Qi and Zhao Yang. Space-time random tensor networks and holographic duality. arXiv
preprint arXiv:1801.05289, 2018. 2

[QYY17] Xiao-Liang Qi, Zhao Yang, and Yi-Zhuang You. Holographic coherent states from random tensor
networks. Journal of High Energy Physics, 2017(8):1–29, 2017. 2
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 35

[RT06] Shinsei Ryu and Tadashi Takayanagi. Holographic derivation of entanglement entropy from the
anti–de sitter space/conformal field theory correspondence. Physical review letters, 96(18):181602,
2006. 2, 9

[SR95] Jorge Sánchez-Ruiz. Simple proof of page’s conjecture on the average entropy of a subsystem.
Physical Review E, 52(5):5653, 1995. 26

[SŻ04] Hans-Jürgen Sommers and Karol Życzkowski. Statistical properties of random density matrices.
Journal of Physics A: Mathematical and General, 37(35):8457, 2004. 25

[VPYL19] Romain Vasseur, Andrew C Potter, Yi-Zhuang You, and Andreas WW Ludwig. Entanglement
transitions from holographic random tensor networks. Physical Review B, 100(13):134203, 2019. 2

[Wig93] Eugene P Wigner. Characteristic vectors of bordered matrices with infinite dimensions i. The Col-
lected Works of Eugene Paul Wigner: Part A: The Scientific Papers, pages 524–540, 1993. 38

[YHQ16] Zhao Yang, Patrick Hayden, and Xiao-Liang Qi. Bidirectional holographic codes and sub-ads local-
ity. Journal of High Energy Physics, 2016(1):1–24, 2016. 2

[YLFC22] Zhi-Cheng Yang, Yaodong Li, Matthew PA Fisher, and Xiao Chen. Entanglement phase transitions
in random stabilizer tensor networks. Physical Review B, 105(10):104306, 2022. 2

[YYQ18] Yi-Zhuang You, Zhao Yang, and Xiao-Liang Qi. Machine learning spatial geometry from entangle-
ment features. Physical Review B, 97(4):045153, 2018. 2

[ŻPNC11] Karol Życzkowski, Karol A Penson, Ion Nechita, and Benoit Collins. Generating random density
matrices. Journal of Mathematical Physics, 52(6):062201, 2011. 26, 27

[ŻS01] Karol Życzkowski and Hans-Jürgen Sommers. Induced measures in the space of mixed quantum
states. Journal of Physics A: Mathematical and General, 34(35):7111, 2001. 25

[ŻS03] Karol Życzkowski and Hans-Jürgen Sommers. Hilbert-schmidt volume of the set of mixed quantum
states. Journal of Physics A: Mathematical and General, 36(39):10115, 2003. 26

Appendix A. Basics of the combinatorial approach to free probability theory

In this section, we will recall and give the necessary material on combinatorics and free proba-
bility needed to understand the rest of this section. All the material that we shall introduce is
standard and can be found in [NS06, MS17].
Let π := {V1 , · · · , Vn }3 be a partition of a finite totally ordered set S such that i∈[n] Vi = S.
F

We call {Vi } the blocks of π. We denote by p ∼π q if p and q belongs to the same block of
π. A partition π of a set S is called crossing if there exists p1 < q1 < p2 < q2 in S such
that p1 ∼π p2 ≁π q1 ∼ q2 . We called a non-crossing partition if π is not crossing. We note
by NC(S) the non-crossing partition set of S. In particular if S = {1, · · · n}, we denote the
non-crossing partition by NC(n). The set of non-crossing partition plays a crucial in different
areas from combinatorics [Arm07] to random matrices and free probability theory which will
be our main focus. Moreover one should mention a crucial result [NS06]: there exists a one-to-
one correspondence of the non-crossing partition set and the set of permutations α in a geodesic
between γ and id i.e |α|+|α−1 γ| = |γ|. Another important fact, the cardinality | NC(n)| = Catn
where:  
1 2n
Catn := , (19)
n+1 n

3Do not confuse with π introduced in Section 5 representing the different paths.
i
36 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

are the Catalan numbers. For more combinatorial details and properties of the Catalan numbers
and the non-crossing partitions see [NS06]. Assume (α1 , · · · , αk ) k tuples of permutations in
Sn such that X
|α1 | + |αi−1 αi+1 | + |αk−1 γ| = |γ|. (20)
i∈[k−1]
are geodesics between id and γ. The cardinality of the set of the k tuple permutations satisfying
the geodesic equation (20) known as the Fuss-Catalan numbers given by:
 
1 n + nk
FCn,k := ,
nk + 1 n
generalizing the Catalan numbers for k = 1.
Now we are ready to introduce the free probability theory tools that will be used in this work.
Moreover, one should mention the intrinsic link between free probability theory and combina-
torics where we will give some examples to illustrate it. The combinatorics will allow us in the
rest of this section to understand our main result.
We recall that a non-commutative probability space is a pair (A, ω) of a unital C ∗ -algebra A
with a state state ω : A → C such that ω(1A ) = 1. One says that the elements a ∈ A define
a noncommutative variable. In the non-commutative probability space, one can associate the
distribution law µa to a ∈ A which is defined as µa = ω(a).
Before we give some concrete examples of some non-commutative probability spaces, we shall
recall the notion of freeness that plays a crucial role in the non-commutative probability world.
The notion of freeness generalizes the “classical” independence when the algebra A is com-
mutative. We say that for a given n non-commutative random variables {ai } ∈ A are free
independent if for any polynomials {pi } the following holds:
ω(a1 a2 · · · an ) = 0 (21)
whenever ω(pk (aik )) = 0 for k ∈ [n] and two no adjacent indices ik and ik+1 . One can check
that with the definition of free independence one has for given two free independent variables
a1 and a2 :
ω((a1 − ω(a1 ))(a2 − ω(a2 )) = ω(a1 a2 ) − ω(a1 )ω(a2 ) = 0, (22)
hence, generalizing the notion of standard independence in the commutative setting where
E(a1 a2 ) = E(a1 )E(a2 ) for two commutative random variables a1 , a2 in a commutative probabil-
ity space.
Definition A.1. Let (AN , ωN ) with N ∈ N and (A, ω) non-commutative probability spaces.
We say that aN ∈ AN converges weakly to a ∈ A as N → ∞ if the following holds:
lim ωN ((aN )n ) = ω(an ) ∀n ∈ N, (23)
N →∞

where ω(an ) = xn dµa (x) are the moments of a.

R

To illustrate concrete non-commutative probability spaces, we give some classical examples. The
first example we shall deal with is “classical” probability space corresponding to commutative
algebra. For that let (Ω, Σ, µ) where Ω a set, Σ a σ−algebra, and µ probability measure. Define
A := L∞− (Ω, µ) where:
\
L∞− (Ω, µ) := Lk (Ω, µ),
1≤k<∞
and the state ω as: Z
ω(a) := a(x)dµ(x), a ∈ A.
Ω
The tuple (A, ω) defines a commutative probability space. Another standard example that can
be considered is the random matrices case. Let us consider the algebra A consisting of valued
k × k matrices over L∞− (Ω, µ) where
A := Mk (L∞− (Ω, µ)).
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 37

Define the state ω on A as:

Z
ω(a) := tr(a(x))dµ(x), a ∈ A,
Ω
where tr(·) is the normalized trace. The space (A, ω) define a non-commutative probability
space which the space of random matrices over (Ω, Σ, µ).
We recall for a given non-commutative random variable a ∈ A, the nth moments of a are given
by Z
mn (µa ) := tn dµa (t). (24)

Moreover for a given random variables {a1 , · · · , an } in A, the moments are given by
X
ω(a1 · · · an ) := κπ (a1 , · · · , an ), (25)
π∈NC(n)

where κπ are the free cummulants. The equation given above is known as the moments-
cummulants formula, where the free independence can be characterized by the vanishing of
mixed cumulants (see [NS06, Chapter 11]).
In free probability theory, for two free independent random variables a1 , a2 ∈ A, one can define
a “convolution operation”. Mostly in this work, we only shall deal with the free multiplicative
convolution. Let a1 and a2 , two free independent random variables in A with their respective
distribution µa1 and µa2 . A free multiplicative convolution or simply a free product is defined
by
µa1 a2 := µa1 ⊠ µa2 , (26)
where µa1 a2 represents the distribution of a1 a2 . There exists a standard and analytical way
to compute the free product, like for the free additive convolution, which can be done via the
S-transform. The S-transform of a probability distribution µa is defined as:
Z
1
Sµa (z) := dµa (x), (27)
x−z
which is analogous to the R-transform for the free additive convolution, as we shall describe.
Moreover, it can also computed equivalently by the formal inverse of the moment-generating
formal power series given by:
1 − z −1
Sµa (z) = Ma (z), (28)
z
where Ma−1 (z) is the formal inverse of the moment-generating formal power series given by
∞
X
Mµa (z) := mk,a z k . (29)
k=1

With the help of the S-transform, one can compute the free product where:
Sµa1 a2 (z) = Sµa1 (z) Sµa2 (z) = Sµa1 ⊠µa (z). (30)
2

In the following, we shall recall some standard distributions that are well-known in the literature
and will be highly used in this work.
The first distribution we shall consider here is the semicircular law, it is one of the most
important distributions we encounter in free probability theory. The semicircular distribution
µSC (x) is defined by the density:
√
4 − x2
dµSC (x) := 1x∈[−2,2] dx. (31)
2π
For an illustration, and by standard computation, one can compute the S-transform of the
semi-circular distribution: √
−z + z 2 − 4
SµSC (z) = .
2
38 KHURSHED FITTER, FAEDI LOULIDI, AND ION NECHITA

The first link that can be made, is the moments of the semicircular distribution are intrinsically
related to the Catalan numbers. One can easily check that the following equality holds:
Z
xk dµSC (x) = Catk , (32)

where Catk are the Catalan numbers see equation (19), and Chapter 2 in [NS06] for more
details. Moreover, one should say that the S-transform gives another important link between
free probability and combinatorics by computing the moments of free product convolution of
Marc̆henko-Pastur distribution (see Theorem A.6).
Another well-known, due to Wigner [Wig93] shows the following result linking the semicircular
distribution and random Gaussian matrices.
Theorem A.2. [Wig93] Let N ∈ N, let AN be an N × N selfadjoint random Gaussian matrix.
Then AN converges weakly to a semicircular distribution µSC (x).
We refer to [AGZ10] for a complete proof. As we have shown in this particular case the
existence of a deep link between random Gaussian matrices, the semicircular law, and the
Catalan numbers. Moreover, the semicircular law plays an important role in free probability
theory as a free central limit distribution. We recall one of the main results in free probability
theory, see Theorem 8.10 in [NS06].
Theorem A.3. Let (A, ω) a non-commutative probability space and a1 , · · · , aN ∈ A free inde-
pendent and identically distributed self-adjoint random variables. Assuming that ω(ai ) = 0 for
i ∈ [N ] and denote by σ 2 := ω(a2i ) the variance of the random variables ai . Then the following
holds:
a1 + · · · + aN
√ → µSC (x).
N
converges weakly to µSC (x) as N → ∞. Where s is a semicircular of variance σ 2 .
With this particular distribution, we have shown how random matrices, combinatorics, and free
probability theory can be related.
In the following, we will give another example of distribution that will play an important role
in this work. The second distribution we shall consider is the Marc̆henko-Pastur distribution.
We shall denote by MP(t) defined by:
MP(t) := max(1 − t, 0)δ0 + νt ,
p
4t − (x − 1 − t)2
dνt (x) := 1(x−1−t)2 ≤4t dx.
2πx
Recall the Marc̆henko-Pastur distribution is deeply related to Wishart matrices. Let Z a
Whishart matrix defined Z := m 1
Y Y ∗ , where Z ∈ Mnm (C) where the entries of Y ∈ Mnm (C)
are complex random Gaussian variables. It was shown by Marc̆henko and Pastur that the em-
pirical distribution of Whishart matrices converges to the MP(t) defined above. More precisely
they have shown the following theorem:
Theorem A.4. Consider a Whishart matrix Z, and let µn,m its empirical distribution given
by:
1 X
µn,m := δz ,
n
z∈spec(Z)
Assuming that n/m converges to t as n → ∞. Then µn,m converges (weakly) to MP(t) with
t > 0.
For a proof and more detailed statement of this result, we refer to Theorem 3.6 and Theorem
3.7 from [BS10]. In particular, what will an important role in this work is the MP, where the
distribution is:
1 p −1
dMP := 4x − 1 dx, (33)
2π
where we have used the shorthand notation MP instead of MP(1).
 A MAX-FLOW APPROACH TO RANDOM TENSOR NETWORKS 39

As for the semicircular distribution described previously, one can relate the moments of free
convolution products of MP to Fuss-Catalan numbers. We shall only give some relevant results
for the Marc̆henko-Pastur distribution to be as concise as possible, we refer to [BBCC11] for
more details and proofs.
Theorem A.5. Let MP(t) the Marc̆henko-Pastur distribution. The S-transform is given by:
1
SMP(t) (z) = .
t+z
One of the main results of [BBCC11], relates the free product convolution of MP(t) and com-
binatorics, in particular, we shall only give the result for MP that will be relevant for this
work.
Theorem A.6. Let MP the Marc̆henko-Pastur distribution. Let MP⊠s with s ≥ 2, then we
have Z
xn dMP⊠s = FCn,s , (34)
R
where FCn,s are the Fuss-Catalan numbers.

Email address: [Link]@[Link]

Ecole Polytechnique Federal de Lausane, Switzerland

Email address: faedi-loulidi@[Link]

Okinawa Institute of Science Technology,Okinawa, Japan

Email address: nechita@[Link]

Laboratoire de Physique Théorique, Université de Toulouse, CNRS, UPS, France