2026/06/05 by Tristan Cam, Cyril Gavoille, Yvan Le Borgne +1 · 1 voice
Computer Science · #cs.DM
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)).