A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity

We introduce a new notion of distance between two graph states |Grangle and |G'rangle on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state |widehatGrangle from which both |Grangle 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 |Grangle. 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 |Grangle -- 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.