The \emph{max-flow min-cut theorem} has been recently used in the theory of random tensor networks in quantum information theory, where it is helpful for computing the behavior of important physical quantities, such as the entanglement entropy. In this paper, we extend the max-flow min-cut theorem to a relation among different \emph{partial orders} on the set of vertices of a network and introduce a new partial order for the vertices based on the \emph{min-cut structure} of the network. We apply the extended max-flow min-cut theorem to random tensor networks and find that the \emph{finite correction} to the entanglement Rényi entropy arising from the degeneracy of the min-cuts is given by the number of \emph{order morphisms} from the min-cut partial order to the partial order induced by non-crossing partitions on the symmetric group. Moreover, we show that the number of order morphisms corresponds to moments of a graph-dependent measure which generalizes the free Bessel law in some special cases in free probability theory.
The \emph{max-flow min-cut theorem} has been recently used in the theory of random tensor networks in quantum information theory, where it is helpful for computing the behavior of important physical quantities, such as the entanglement entropy. In this paper, we extend the max-flow min-cut theorem to a relation among different \emph{partial orders} on the set of vertices of a network and introduce a new partial order for the vertices based on the \emph{min-cut structure} of the network. We apply the extended max-flow min-cut theorem to random tensor networks and find that the \emph{finite correction} to the entanglement Rényi entropy arising from the degeneracy of the min-cuts is given by the number of \emph{order morphisms} from the min-cut partial order to the partial order induced by non-crossing partitions on the symmetric group. Moreover, we show that the number of order morphisms corresponds to moments of a graph-dependent measure which generalizes the free Bessel law in some special cases in free probability theory.
The classical max-flow min-cut theorem describes transport through certain idealized classical networks. We consider the quantum analog for tensor networks. By associating an integral capacity to each edge and a tensor to each vertex in a flow network, we can also interpret it as a tensor network and, more specifically, as a linear map from the input space to the output space. The quantum max-flow is defined to be the maximal rank of this linear map over all choices of tensors. The quantum min-cut is defined to be the minimum product of the capacities of edges over all cuts of the tensor network. We show that unlike the classical case, the quantum max-flow=min-cut conjecture is not true in general. Under certain conditions, e.g., when the capacity on each edge is some power of a fixed integer, the quantum max-flow is proved to equal the quantum min-cut. However, concrete examples are also provided where the equality does not hold. We also found connections of quantum max-flow/min-cut with entropy of entanglement and the quantum satisfiability problem. We speculate that the phenomena revealed may be of interest both in spin systems in condensed matter and in quantum gravity.
The entanglement entropy of a random tensor network (RTN) is studied using tools from free probability theory. Random tensor networks are simple toy models that help in understanding the entanglement behavior of a boundary region in the anti-de Sitter/conformal field theory (AdS/CFT) context. These can be regarded as specific probabilistic models for tensors with particular geometry dictated by a graph (or network) structure. First, we introduce a 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). The entanglement spectrum of the resulting random state is analyzed along a given bipartition of the local Hilbert spaces. The limiting eigenvalue distribution of the reduced density operator of the RTN state is provided in the limit of large local dimension. This limiting value is described through 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, an explicit formula for the limiting eigenvalue distribution is provided using classical and free multiplicative convolutions. The physical implications of these results are discussed, allowing the analysis to move beyond the semiclassical regime without any cut assumption, specifically in terms of finite corrections to the average entanglement entropy of the RTN.
We study the evaluation of Rényi multi-entropies Sn(q) in Random Tensor Network (RTN) states in the large bond-dimension limit. For the case of Rényi index n=2 and arbitrary number of parties q, we prove that that multi-entropies are determined by minimal multiway cuts through the network. When the minimal multiway cut is degenerate, we characterize the full minimizer set via compatible families of minimal cuts and give a criterion for all minimizers to come from ordinary cut partitions. For n=2, this gives a natural generalization of the minimal cut description of bipartite entanglement to multipartite systems with arbitrarily many parties. For the case of integer n>2, we show that the minimal multiway cut conjecture is in general \emph{not true} by providing explicit counter examples for both the single random tensor and for the network built from isometric tilings. We discuss the implication for our results on the multipartite entanglement structures in RTN and holography.
The max-flow min-cut theorem is a cornerstone result in combinatorial optimization. Calegari et al. (arXiv:0802.3208) initialized the study of quantum max-flow min-cut conjecture, which connects the rank of a tensor network and the min-cut. Cui et al. (arXiv:1508.04644) showed that this conjecture is false generally. In this paper, we establish a quantum max-flow min-cut theorem for a new definition of quantum maximum flow. In particular, we show that for any quantum tensor network, there are infinitely many n, such that quantum max-flow equals quantum min-cut, after attaching dimension n maximally entangled state to each edge as ancilla. Our result implies that the ratio of the quantum max-flow to the quantum min-cut converges to 1 as the dimension n tends to infinity. As a direct application, we prove the validity of the asymptotical version of the open problem about the quantum max-flow and the min-cut, proposed in Cui et al. (arXiv:1508.04644 ).
Abstract A confining, non-Abelian gauge connection Uij ∈ SU(N) defined on the links of a dynamical graph has been proposed as the microscopic origin of classical spacetime geometry: the metric is reconstructed from the coset (soldering-form) sector of an enlarged connection, and black-hole and boundary-cut entropy are obtained as the logarithm of a combinatorial microstate count, matched, via the Freedman–Headrick theorem, to the bit-thread (max-flow/min-cut) formulation of holographic entanglement entropy. That matching is exact as a statement about counting, but it is not, by itself, a statement about the entanglement entropy of any specific quantum state: nothing in the combinatorial construction distinguishes a classical ensemble of flux occupation numbers from a genuine quantum wavefunction, so its connection to the entanglement/tensornetwork program of emergent geometry (Van Raamsdonk, Swingle, Ryu–Takayanagi, and the random-tensor-network derivation of Hayden, Qi, Kim, and Preskill) remains an analogy rather than a derivation. This paper closes that gap. We first restate the flux-gauge connection ensemble in full – its partition function, its block-link renormalization-group coarse-graining with closed-form Migdal–Kadanoff coefficients, its emergent metric and Newton’s-constant identification, and its combinatorial boundary-cut entropy – so that the paper is self-contained. We then show, by an exact character-expansion/Peter–Weyl derivation standard in lattice gauge theory but not previously applied to this construction, that the SU(N) link ensemble is a tensor network: each flux-tube segment (link) carries a bond dimension equal to the dimension of the SU(N) representation it transports, and each flux-tube junction (node) carries a gauge-invariant intertwiner tensor, fixed by representation theory rather than assumed. Only a single, narrowly scoped statistical assumption – on the distribution of intertwiners within the multiplicity space that gauge invariance already guarantees – is needed to complete this exact, deterministic tensor network into a genuine random tensor network in the technical sense of Hayden–Qi–Kim–Preskill (HQKP). We further identify the renormalization-group layers of Section 2’s coarse-graining as the isometric maps of a multi-scale entanglement renormalization ansatz (MERA), giving the emergent radial holographic direction a literal tensor-network origin rather than a scaling-dimension analogy. We then investigate, analytically and how the entanglement entropy of such a network reproduces the Ryu–Takayanagi/min-cut law. An exactly solvable limit built from classical (GHZ-type) perfect tensors reproduces the combinatorial law exactly for single-cut (boundary-anchored) regions but is shown to be degenerate for interior, two-sided regions, exposing a genuine gap in the combinatorial entropy argument: classical flux-occupation counting does not, by itself, certify multi-region (entanglement-wedgelevel) quantum entanglement structure. We then construct a genuinely quantum (non-classical, Gaussian-random) tensor-network realization of the link ensemble and confirm numerically, on chains of up to sixteen sites, (i) a clean area-law plateau in which the entanglement entropy of an interior region becomes independent of its size once the region is large enough, in place of continued volume-law growth, and (ii) a linear scaling of the plateau entropy with the logarithm of the bond dimension, S(A) = κNcut(A) logD, fit with R2 = 0.996 and an O(1) efficiency coefficient κ ≈ 0.68 for this finite, non-isometric network. We interpret κ < 1 as a genuine, quantifiable finite-network correction relative to the idealized D → ∞ isometric-projector limit in which HQKP prove κ → 1, and we list the construction of that idealized limit, directly on the SU(N) link ensemble, as the key open numerical task. We close by proposing an explicit correspondence between the tensor-network minimal surface of this paper and the Cartan soldering-form metric of the gauge-connection construction, framed as a falsifiable consistency conjecture rather than an established result.
A bstract For general random tensor network states at large bond dimension, we prove that the integer Rényi reflected entropies (away from phase transitions) are determined by minimal triway cuts through the network. This generalizes the minimal cut description of bipartite entanglement for these states. A natural extrapolation away from integer Rényi parameters, suggested by the triway cut problem, implies the holographic conjecture S R = 2EW, where S R is the reflected entropy and EW is the entanglement wedge cross-section. Minimal triway cuts can be formulated as integer programs which cannot be relaxed to find a dual maximal flow/bit-thread description. This sheds light on the gap between the existence of tripartite entanglement in holographic states and the bipartite entanglement structure motivated by bit-threads. In particular, we prove that the Markov gap that measures tripartite entanglement is lower bounded by the integrality gap of the integer program that computes the triway cut.