{"ID":6497658,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09469","arxiv_id":"2607.09469","title":"A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity","abstract":"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 edit-distance problems. Using this framework, we develop classical algorithms for identifying the ``highly entangled clusters'' of a graph state $|G\\rangle$. The ancilla integrity problem asks, given a graph $G$ and integer $k$, for the minimum -- over all graph states $|G'\\rangle$ with distance at most $k$ from $|G\\rangle$ -- 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 $\\text{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 $\\mathcal{O}(n^6)$-time algorithm for ancilla integrity when $G$ has $n$ vertices and $k=1$.","short_abstract":"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 ar...","url_abs":"https://arxiv.org/abs/2607.09469","url_pdf":"https://arxiv.org/pdf/2607.09469v1","authors":"[\"Romain Bourneuf\",\"Nathan Claudet\",\"Sang Yoon Kim\",\"Rose McCarty\",\"Blair D. Sullivan\",\"Stéphan Thomassé\"]","published":"2026-07-10T14:42:55Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"quant-ph\"]","methods":"[]","has_code":false}