{"id":"arxiv/2607.09469","url":"https://arxiv.org/abs/2607.09469","tags":["cs.DS","cs.DM","quant-ph"],"score":0,"title":"A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity","domain":"cs.DS","source":"arxiv","authors":["Romain Bourneuf","Nathan Claudet","Sang Yoon Kim","Rose McCarty","Blair D. Sullivan","Stéphan Thomassé"],"reviews":0,"subject":"cs.DS","summary":"We introduce a new notion of distance between two graph states $|G\\rangle$ and $|G'\\rangle$ on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state $|\\widehat{G}\\rangle$ from which both $|G\\rangle$ and $|G'\\rangle$ 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}