CS Paper Radar

Entanglement Geometry Beyond Polygons: Graph-Theoretic Entanglement Inequalities

Masoud Gharahi

cs.IT quant-phmath-ph ·submitted 2026-11-18 19:00 UTC · v1
theory

Abstract

Entanglement entropies of pure multipartite states can be constrained by organizing subsystem cuts as edges (hyperedges) of graphs (hypergraphs). Starting from the one-party entanglement polygon inequality, we derive these constraints from strong subadditivity and pure-state complementarity, with optimal coefficients and explicit equality conditions. Our central result determines, for a distinguished two-party cut and an arbitrary weighted family of cuts, the optimal polygon coefficient: the smallest total weight of the cuts separating a member of the distinguished pair from a remaining party. A refinement involving three mutual information terms gives the exact minimum of the weighted sum at fixed entropies of the two parties and of their union, attained by at most three independent bipartite pure states. This criterion recovers the cycle and complete-graph inequalities and shows that uniform incidence parity, which we prove sufficient for polygon inequalities on hypergraphs, is not necessary. Averaging strong subadditivity over both sides of a bipartition gives a sharp $k$-marginal inequality with coefficient $2\binom{n-2}{k-1}$, and we determine uniformly optimal coefficients for collective hyperstar inequalities. For paths and overlapping hyperchains, the deficits are exact sums of conditional mutual information terms; genuinely multipartite entangled cluster states saturate the hyperchain inequality while the chain inequality remains strict. We characterize pure chain equality states, bound the trace distance to cycle equality states independently of the number of parties and local dimensions, and obtain bond-dimension bounds for matrix product states and sequential-recovery error estimates.

Comment
29 pages, 3 figures, comments are welcome

Closest papers

Nearest neighbours by meaning across the whole index.

No cardinality bound for squashed entanglement

cs.IT quant-ph ·2026-09-12 ·Rabsan Galib Ahmed, Graeme Smith
hot direction similarity 0.61
Abstract · 6 pages

Squashed entanglement is an additive bipartite entanglement measure. For a state $ρ_{AB}$, it is defined as the infimum of all conditional mutual information $I(A:B\mid E)$ evaluated on extensions $ρ_{ABE}$. It was unresolved whether there is a bound on the dimension of the conditioning system, $E$, needed for this optimization. We show that no such cardinality bound is possible. Explicitly, we find that the squashed entanglement for a partially dephased Bell pair on two qubits cannot be achieved for any finite dimensional extension $E$. A crucial ingredient of this proof is a direct sum step, which in a sense, symmetrizes two purifying systems while keeping the conditional mutual information unchanged and the coherence no worse.

0.25

Static classical-quantum-entanglement trade-offs: an entropic converse and single-letter characterizations

cs.IT quant-ph ·2026-09-20 ·Mark M. Wilde
similarity 0.61
Abstract · 81 pages, 5 figures

The direct static capacity region of a bipartite quantum state describes its asymptotic conversion into classical communication, quantum communication, and entanglement, with all communication directed from Alice to Bob. This paper gives a unified entropic converse for this region. The proof treats generated and consumed resources simultaneously and derives all three information inequalities for one local instrument. Its main ingredients are no-signalling, the chain rule, strong subadditivity, and continuity of conditional entropy. A supporting-hyperplane characterization leads to the static capacity formula, which is helpful in determining single-letterization of the capacity region. For a pure state of entanglement entropy $h$ subjected to erasure with probability $p$, the complete region is the convex hull of $0$ and $(0,-ph,(1-p)h)$, plus the unit-resource cone. This statement holds for arbitrary collective instruments by using subset-entropy inequalities related to earlier methods used for the dynamic capacity region of the erasure channel. Complete characterizations also hold for symmetrically extendible states and locally flagged pure-state mixtures. For maximally correlated states, the optimization over local instruments admits an exact matrix formulation and an additive outer bound. An explicit qubit example shows that a nonorthogonal discarded quantum memory can outperform every efficient instrument and every instrument with conditionally commuting discarded states. For states obtained by qubit dephasing of Schmidt-aligned pure states, an exact threshold characterizes when the static capacity formula vanishes, at every blocklength and after regularization. Full single-letter characterizations for general Hadamard states and for the remaining trade-offs for dephased states remain open, with sufficient additivity conditions identified.

0.21

Subadditivity and the failure of strong subadditivity in the Nichols--Wootters family of entropies

cs.IT quant-phmath-ph ·2026-11-11 ·Lin Zhang, Wenlin Zhang, Haobo Ma
theory similarity 0.61
Abstract · 110 pages

We prove subadditivity for the Nichols--Wootters family of entropies interpolating between the von Neumann entropy and the subentropy, with all spectra evaluated in one common ambient dimension. Beyond the von Neumann entropy, equality holds exactly when at least one marginal is pure. This settles the subadditivity conjecture concerning subentropy. Every member except the von Neumann entropy fails strong subadditivity, already on a maximally entangled two-qubit state tensored with a mixed qubit. Its strong-subadditivity defect takes both signs on quantum Markov states. For a pure bipartite state tensored with an ancillary state, we identify the defect with a separately concave product gap and determine its exact maximum under rank constraints. For arbitrary bipartite states, we obtain an explicit lower bound in the marginal purities. For two-qubit states, we determine the optimal coefficient multiplying the product of the smaller marginal eigenvalues in every common ambient dimension, including the subentropy coefficient $1/3$. A positive representation by Haar averages of compressed matrix entropies gives the pinching inequality underlying these results and also yields entropy-gain bounds for unital quantum channels.As an application, each entropy equals the classical communication capacity retained after a specified isotropic partial projective measurement, at a prescribed average input state, even when entangled block encodings are allowed.

0.20

Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers

cs.DM math.CO ·2026-10-10 ·Yusuke Watanabe
theorycode/data similarity 0.60
Abstract · 39 pages. Main Theorems A-C formalized in Lean 4; code: https://github.com/ywatanabex/coefficientwise-rigidity-lean

Let $G$ be a finite bipartite graph and let $\widetilde G$ be an $M$-fold cover. We compare independent sets of $\widetilde G$ with those of the trivial cover, consisting of $M$ disjoint copies of $G$, after prescribing how many vertices are selected above each vertex of $G$. A conjecture from 2011, motivated by the Bethe approximation, asserts that the trivial cover maximizes every such count. We prove this for every feasible occupation profile whose active graph has treewidth at most two or is chordal bipartite. Equality holds exactly when the restricted cover is flat, meaning that fibre relabelings make it trivial. For $M\ge2$ and positive feasible occupations, a nonflat cover of a connected bipartite graph of treewidth at most two has a deficit of at least twice the coefficient of $p_G^{M-2}$ with every occupation reduced by one. A holonomy-dependent bound improves the factor to three for odd-order holonomy; both uniform constants are sharp. Comparison and rigidity survive finite compositions along an edge or a vertex, and quantitative bounds from one piece propagate to the whole graph, giving results beyond the two original classes. On any bipartite base, the first nonzero homogeneous defect is determined by the shortest cycles with nontrivial holonomy. At singleton occupations, our counts are numbers of DP-colorings of full covers. The dual DP color function on these classes and their finite seam compositions equals the chromatic polynomial, with equality attained precisely by canonical labelings. Dong's chromatic-polynomial inequality then yields the Dual-DP Shameful inequality on the same graph class. The main theorems have been formalized in Lean 4.

0.28

Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width

cs.DB math.CO ·2026-09-30 ·Matthias Lanzinger, Timo Camillo Merkl, Dan Suciu
theory similarity 0.59
Abstract

We describe one explicit simple graph G on 32 vertices whose adaptive, normal, linear, entropic, and submodular widths are pairwise distinct. We compute all these widths exactly, except for the entropic width, where we only give a lower and upper bound. We use Ingleton's inequality and the Zhang-Yeung inequality for upper bounds, and give explicit constructions of modular, normal, linear, entropic, and non-entropic polymatroids for lower bounds.

0.23

A Proof of the Imbalance Conjecture

cs.DM math.CO ·2026-08-10 ·James Alexander Schreib, Yousof Yavari
theory similarity 0.58
Abstract · 5 pages, no figures; added reference to an earlier independent proof; mathematical content unchanged

For an edge $uv$ of a finite simple graph $G$, its imbalance is $|d_G(u)-d_G(v)|$, and the imbalance multiset $M_G$ consists of the imbalances of all edges of $G$. Kozerenko and Skochko conjectured that $M_G$ is graphic whenever every edge has positive imbalance. We prove this conjecture. The main ingredient is the following capacity bound: for every set $A$ of $k$ edges, \[ \sum_{e\in E(G)\setminus A}\min\{k,\operatorname{imb}_G(e)\} \ge k\max\{Δ-k,0\}, \] where $Δ$ is the maximum degree of $G$. This bound yields all Erdős--Gallai inequalities directly; a parity computation completes the proof.

0.07

Entanglement of purification for Werner states: canonical purification and nonadditivity

cs.IT quant-ph ·2026-10-02 ·Zahra Baghali Khanian, Amir-Reza Negari
theory similarity 0.58
Abstract

We prove that the von Neumann entanglement of purification is nonadditive. For two-qubit Werner states $W(f)$ with singlet weight $1/64\le f\le1/4$, we show that canonical purification is globally optimal: its entanglement, also known as reflected entropy, gives the exact entanglement of purification. In contrast, the regularized entanglement of purification lies strictly below the reflected entropy for $0<f<f_\ast$, where $f_\ast\approx0.017$. Together, these results establish nonadditivity throughout $1/64\le f<f_\ast$. Our canonical-optimality proof generalizes the proof in [1], which established Rényi nonadditivity for $0\leα<1$ using classical two-qubit states. We thus resolve the additivity question at $α=1$. Remarkably, nonadditivity is again witnessed by separable states and no entanglement in the underlying states is required.

0.36

Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates

cs.LG ·2026-09-16 ·Yingquan, Wu, Jason Cong
theory similarity 0.57
Abstract

We study the maximum strong independent set problem in a finite hypergraph: find the largest vertex set that intersects every hyperedge in at most one vertex. This objective arises whenever each observed block is a local incompatibility constraint but transitive closure across overlapping blocks is not justified. A motivating example is multi-band LSH-MinHash deduplication, where each collision bucket gives local evidence, while connected-component contraction can impose spurious global equivalences. The paper develops an incidence-structural toolkit for this problem. We prove exact reductions for dominance, incidence twins, and weight-1 blocks; derive closed-form and low-weight upper bounds; introduce puncturing and covering certificates that sharpen those bounds; and analyze a layered greedy clustering algorithm driven by block weights and residual incidence. The algorithmic analysis includes feasibility, maximality, conditional optimality, a layered witness-matching upper bound, and incidence-local complexity bounds. The results give correctness, termination, fixed-point, and optimality certificates for broad incidence families, together with examples showing when different certificates separate or coincide.

0.33