Entanglement in quantum graph states is intrinsically linked to rank-width, a graph complexity measure introduced by Oum and Seymour. In this work, we enable the preparation of maximally entangled deterministic graph states in constant depth by developing a general method to derive lower bounds on the rank-width of regular graphs from their edge expansion. By bridging edge-isoperimetric inequalities with the strong chromatic index and Jelínek's approach for lower bounding cut-rank, we systematically establish lower bounds for the rank-width of Cartesian products, including hypercubes, Hamming graphs, and grids. Extending this framework via Boolean function analysis, using a generalization of the Kahn-Kalai-Linial's Theorem, we strengthen the bounds for all Cartesian products by a non-trivial logarithmic factor. These methods result in the discovery of deterministic families of graphs on $n$ vertices with a provably maximum rank-width $Θ(n)$. Our results fill the previous gap in the literature for deterministic graph families of rank-width greater than $Θ(\sqrt{n})$.
Entanglement in quantum graph states is intrinsically linked to rank-width, a graph complexity measure introduced by Oum and Seymour. In this work, we enable the preparation of maximally entangled deterministic graph states in constant depth by developing a general method to derive lower bounds on the rank-width of regular graphs from their edge expansion. By bridging edge-isoperimetric inequalities with the strong chromatic index and Jelínek's approach for lower bounding cut-rank, we systematically establish lower bounds for the rank-width of Cartesian products, including hypercubes, Hamming graphs, and grids. Extending this framework via Boolean function analysis, using a generalization of the Kahn-Kalai-Linial's Theorem, we strengthen the bounds for all Cartesian products by a non-trivial logarithmic factor. These methods result in the discovery of deterministic families of graphs on n vertices with a provably maximum rank-width Θ(n). Our results fill the previous gap in the literature for deterministic graph families of rank-width greater than Θ(n).
Graph states provide a bridge between graph theory and multipartite quantumentanglement, with cut-rank, rank-width, and related parameters playing a centralrole in both structural graph theory and the characterization of stabilizer states.Building on this interplay, we introduce a new scalar invariant—the S M NazmuzSakib entanglement rank entropy—defined as the Shannon entropy of the cut-rankdistribution over vertex subsets of fixed cardinality. For a simple graph G = (V, E)of order n, and k ∈ {1, . . . , n − 1}, we consider the random variable ρG(X) whereX ⊆ V is a uniformly random k-subset, and we define the Sakib entanglementrank entropy H(k)ρ (G) as the Shannon entropy (in bits) of its distribution.Forgraph states, where ρG(X) coincides with the Schmidt rank exponent across thebipartition (X, V \ X), H(k)ρ (G) is precisely the Shannon entropy of the bipartiteentanglement (in ebits) seen by random size-k bipartitions.We formally define the S M Nazmuz Sakib entanglement rank entropy, provethat it is invariant under local complementation and hence a local-Clifford invariantfor graph states, and study a balanced version Hbalρ (G) = H(n/2)ρ(G) (for even n).We then perform a data-based analysis on explicit graph families (paths, cycles,stars, complete graphs, and 2 × m grid graphs) of size up to n = 12, computingHbalρ (G), the average cut-rank, and the full cut-rank distributions. The resultingdataset shows that, while complete and star graphs have vanishing Sakib entangle-ment rank entropy, more “distributed” structures such as paths, cycles, and gridsexhibit increasing entropy with system size, despite similar ranges of cut-rank.Motivated by these observations, we formulate the S M Nazmuz Sakib entan-glement heterogeneity hypothesis, proposing that, at fixed rank-width and averagecut-rank, a larger Sakib entanglement rank entropy correlates with higher classicalsimulation complexity of the corresponding graph states.We outline how pub-licly available graph-state orbit datasets and average cut-rank techniques can becombined with the proposed invariant to further test this hypothesis.
We introduce a new notion of distance between two graph states ∣G⟩ and ∣G′⟩ on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state ∣G⟩ from which both ∣G⟩ and ∣G′⟩ can be ``easily prepared''. (When preparing graph states, we are only allowed to use one-qubit Clifford gates, one-qubit Pauli measurements, and classical communication.) We give a graphical description of this distance through the lens of vertex-minors. We then show how this distance yields quantum network analogs of many graph edit-distance problems.
Using this framework, we develop classical algorithms for identifying the ``highly entangled clusters'' of a graph state ∣G⟩. The ancilla integrity problem asks, given a graph G and integer k, for the minimum -- over all graph states ∣G′⟩ with distance at most k from ∣G⟩ -- of the maximum component size of G′. Up to a factor of 2 in the number of ancilla qubits, this problem is equivalent to rank integrity, where the distance between G and G′ is instead the minimum rank of the sum of their adjacency matrices over GF(2). We prove that rank integrity is XP parameterized by k. We also prove the complementary hardness result that rank integrity is W[1]-hard in k. Finally, we give an explicit O(n6)-time algorithm for ancilla integrity when G has n vertices and k=1.
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
We present two results derived from the sharp log-Sobolev inequality for the uniform measure on a complete graph which concern the von Neumann entropy and the Entanglement of Formation of a state of finite and infinite-dimensional quantum systems.
The first result is a sharp Lipschitz lower semicontinuity bound for the von Neumann entropy at any mixed state ρ with uniform positive spectrum (i.e. a state proportional to a projector) w.r.t. the fidelity deficit: the inequality S(ρ)−S(σ)≤Cρ(1−F(ρ,σ)) valid for any state σ, where Cρ is a constant depending on the rank of ρ.
The second result is a sharp Lipschitz lower semicontinuity bound for the Entanglement of Formation at any pure state ρ with uniform positive spectrum of marginal states w.r.t. the fidelity deficit: the inequality EF(ρ)−EF(σ)≤Cρ(1−Trρσ) valid for any state σ, where Cρ is a constant depending on the Schmidt rank of ρ.
In both cases the optimal constant Cρ is equal to the optimal constant Kd in the log-Sobolev inequality for the complete graph with d vertices: in the first case d=rankρ, in the second one d=rankρA=rankρB.
The authors are grateful to GPT 5.6 for valuable discussion and technical help in preparing this note.
Graph states are multipartite entangled states that correspond to mathematical graphs, where the vertices of the graph now play the role of quantum multilevel systems and edges represent interactions of the systems. Graph states are the basis of quantum error correction and one-way quantum computer. We systematically study the entanglement of non-binary graph states. Using iterative algorithm and entanglement bounds, we calculate the entanglement of all the ternary graph states up to nine vertices and parts of quaternary and quinary graph states modulo local unitary transformations and graph isomorphisms. The entanglement measure can be the geometric measure, the measure of relative entropy of entanglement or the measure of logarithmic robustness. We classify the graph states according to the entanglement values obtained. The closest product states obtained in the calculations are studied.
One of the best lower bound methods for the quantum communication complexity of a function H (with or without shared entanglement) is the logarithm of the approximate rank of the communication matrix of H. This measure is essentially equivalent to the approximate gamma-2 norm and generalized discrepancy, and subsumes several other lower bounds. All known lower bounds on quantum communication complexity in the general unbounded-round model can be shown via the logarithm of approximate rank, and it was an open problem to give any separation at all between quantum communication complexity and the logarithm of the approximate rank. In this work we provide the first such separation: We exhibit a total function H with quantum communication complexity almost quadratically larger than the logarithm of its approximate rank. We construct H using the communication lookup function framework of Anshu et al. (FOCS 2016) based on the cheat sheet framework of Aaronson et al. (STOC 2016). From a starting function F, this framework defines a new function H=F_G. Our main technical result is a lower bound on the quantum communication complexity of F_G in terms of the discrepancy of F, which we do via quantum information theoretic arguments. We show the upper bound on the approximate rank of F_G by relating it to the Boolean circuit size of the starting function F.