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

Jul 16, 2026

A combinatorial framework defines a new distance between quantum graph states using restricted operations with ancilla qubits, one-qubit Clifford gates, one-qubit Pauli measurements, and classical communication, characterized graph-theoretically via vertex-minors. The distance supports quantum network analogs of graph edit-distance clustering tasks and motivates “integrity” and robustness notions. Classical algorithms identify highly entangled clusters, yielding an ancilla-integrity optimization and an equivalence to rank integrity, with proofs of XP and W[1]-hardness and an explicit O(n^6) algorithm for k=1.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages37

Reading Time1 h 33 min

AccessFree to download

Introduction

A combinatorial framework for clustering graph states

Graph-state distance via ancillas and restricted operations

Vertex-minor characterization of the distance

arXiv :2607 .09469v 1 [ cs .DS] 10 Jul 2026 A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity Romain Bourneuf Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France Nathan Claudet University of Innsbruck, Department of Theoretical Physics, Technikerstraße 21a, A-6020 Innsbruck, Austria Sang Yoon Kim School of Computer Science, Georgia Institute of Technology, USA Rose McCarty School of Computer Science and School of Mathematics, Georgia Institute of Technology, USA Blair D. Sullivan Collegium de Lyon, ENS de Lyon, LIP, France Kahlert School of Computing, University of Utah, USA Stéphan Thomassé Univ. Lyon, ENS de Lyon, UCBL, CNRS, LIP, France ~~ Abstract ~~ We introduce a new notion of distance between two graph states |G⟩ and |G′ ⟩ on the same set of q| uGb⟩itsan.dT| hiGs′⟩ dcistanan bcee“iseatshie minly preimumparedn”umb(Wehreofnancprepillaariqngubitgrsapin a graph states,hswtate aere | ⟩lfryoam whichllowed toboutshe 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 . 2012 ACM Subject Classification Theory of computation → Parameterized complexity and exact algorithms; Mathematics of computing → Graph algorithms; Theory of computation → Quantum computation theory Keywords and phrases graph states, integrity, robustness, flips, vertex-minors, rank, splits 1 Introduction There is a vast literature of graph edit distance problems where the goal is to transform a given graph G into a member of some target graph class by making as few changes as possible. The most commonly studied changes are vertex and edge deletion and insertion. This framework is very flexible and also includes other graph modification and connectivity augmentation problems such as those studied in [17, 50] . How much more “connectivity” can be added to a road network by building a few more lanes? How much can be destroyed by putting a few lanes out of service? In this manner, graph edit distance problems can be used to “cluster” a graph into “highly connected pieces” and to compute its “resiliency”, 2 A combinatorial framework for clustering graph states “robustness”,“vulnerability”, and so on. Many different notions of edit distance, many different target graph classes, and many different measures of connectivity have been considered; see [22, 36 , 39] for surveys. Edit distance problems such as feedback vertex set – can k vertices be deleted from G to obtain a forest?– also form the foundation of modern parameterized complexity. In this paper we introduce a new notion of edit distance for graphs/graph states which is motivated by quantum networking. It captures whether a network provider can use a few ancilla qubits to transform one distributed quantum network into another. To explain this idea, consider two n-qubit graph states |G⟩ and |G′ ⟩ on the same set of qubits V. We conthesiddiesjroi|Gnt⟩uannidon | Gof′ ⟩Vtoabned “saimilasmallrs”eif a networt of ancillakqpro

FAQs

What does the paper define as the distance between two quantum graph states?

It defines distance between two graph states on the same qubits as the minimum amount of additional ancilla qubits needed to transform one state into the other using restricted operations consisting of one-qubit Clifford gates, one-qubit Pauli measurements, and classical communication.

How is the new quantum distance characterized graph-theoretically?

The paper gives a graphical characterization through vertex-minors, defining the distance between underlying graphs as the minimum k such that a larger graph contains both graphs as vertex-minors.

What computational results are proved for rank integrity and ancilla integrity?

The ancilla-integrity problem is shown (up to a factor of 2 in ancilla qubits) equivalent to rank integrity, which is proven to be XP parameterized by k, while rank integrity is also proven W[1]-hard in k; additionally, an explicit O(n^6)-time algorithm is provided for ancilla integrity when k=1.

Jul 16, 2026

Upload by Theodora