Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.09469

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

Romain Bourneuf, Nathan Claudet, Sang Yoon Kim, Rose McCarty, Blair D. Sullivan, Stéphan Thomassé

cs.DScs.DMquant-phSubmitted Jul 10, 2026• Announced Jul 13, 2026• 0 citations
arXivHTMLPDF

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$.

Related papers

Quantum embedding of graphs for subgraph counting

Bibhas Adhikari

We develop a unified quantum framework for subgraph counting in graphs. We encode a graph on $N$ vertices into a quantum state on $2\lceil \log_2 N \rceil$ working qubits and $2$ ancilla qubits using its adjacency list, with worst-case gate complexity $O(N^2)$, which we refer to as the graph adjacency state. We design quantum measurement operators that capture the edge structure of a target subgraph, enabling estimation of its count via measurements on the $m$-fold tensor product of the adjacency state, where $m$ is the number of edges in the subgraph. We illustrate the framework for triangles, cycles, and cliques. This approach yields quantum logspace algorithms for motif counting, with no known classical counterpart.

quant-pharXiv:2604.18754•Apr 22, 2026•0 citations

Transforming graph states using single-qubit operations

Axel Dahlberg, Stephanie Wehner

Stabilizer states form an important class of states in quantum information, and are of central importance in quantum error correction. Here, we provide an algorithm for deciding whether one stabilizer (target) state can be obtained from another stabilizer (source) state by single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. What is more, we provide a recipe to obtain the sequence of LC+LPM+CC operations which prepare the desired target state from the source state, and show how these operations can be applied in parallel to reach the target state in constant time. Our algorithm has applications in quantum networks, quantum computing, and can also serve as a design tool—for example, to find transformations between quantum error correcting codes. We provide a software implementation of our algorithm that makes this tool easier to apply. A key insight leading to our algorithm is to show that the problem is equivalent to one in graph theory, which is to decide whether some graph G ′ is a vertex-minor of another graph G . The vertex-minor problem is, in general, -Complete, but can be solved efficiently on graphs which are not too complex. A measure of the complexity of a graph is the rank-width which equals the Schmidt-rank width of a subclass of stabilizer states called graph states, and thus intuitively is a measure of entanglement. Here, we show that the vertex-minor problem can be solved in time O (| G | 3 ), where | G | is the size of the graph G , whenever the rank-width of G and the size of G ′ are bounded. Our algorithm is based on techniques by Courcelle for solving fixed parameter tractable problems, where here the relevant fixed parameter is the rank width. The second half of this paper serves as an accessible but far from exhausting introduction to these concepts, that could be useful for many other problems in quantum information. This article is part of a discussion meeting issue ‘Foundations of quantum mechanics and their impact on contemporary society’.

arXiv:1805.05305•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•May 28, 2018•51 citations

Multipartite Entanglement in Quantum Networks Using Subgraph Complementations

Aniruddha Sen, Kenneth Goodenough, Don Towsley

Quantum networks are important for quantum communication and consist of entangled states that are essential for many tasks such as quantum teleportation, quantum key distribution, quantum sensing and quantum error correction. Graph states are a specific class of multipartite entangled states that can be represented by graphs. We propose a novel approach for distributing graph states across a quantum network. We show that the distribution of graph states can be characterised by$\boldsymbol{a}$system of subgraph complementations, which we also relate to the minimum rank of the underlying graph and the degree of entanglement quantified by the Schmidt-rank of the quantum state. We analyse resource usage for our algorithm and show it to match or be improved in the number of qubits, bits for classical communication and EPR pairs utilised, as compared to prior work. The number of local operations is efficient, and the resource consumption for our approach scales linearly in the number of vertices. This presents a quadratic improvement in completion time for several classes of graph states represented by dense graphs, and implies a potential for improved fidelity in the presence of noise. Common classes of graph states are classified along with the optimal time for their distribution using subgraph complementations. We also provide a framework to similarly find the optimal sequence of operations to distribute an arbitrary graph state, and prove upper bounds along with providing approximate greedy algorithms.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•1 citation

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

Rafail Ostrovsky

We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.

quant-pharXiv:2609.22669•Sep 22, 2026•0 citations

Counting single-qubit Clifford equivalent graph states is #P-complete

Axel Dahlberg, Jonas Helsen, Stephanie Wehner

Graph states, which include Bell states, Greenberger-Horne-Zeilinger (GHZ) states, and cluster states, form a well-known class of quantum states with applications ranging from quantum networks to error-correction. Whether two graph states are equivalent up to single-qubit Clifford operations is known to be decidable in polynomial time and has been studied in the context of producing certain required states in a quantum network in relation to stabilizer codes. The reason for the latter is that single-qubit Clifford equivalent graph states exactly correspond to equivalent stabilizer codes. We here consider that the computational complexity of, given a graph state |G⟩, counting the number of graph states, single-qubit Clifford equivalent to |G⟩. We show that this problem is #P-complete. To prove our main result, we make use of the notion of isotropic systems in graph theory. We review the definition of isotropic systems and point out their strong relation to graph states. We believe that these isotropic systems can be useful beyond the results presented in this paper.

arXiv:1907.08024•Journal of Mathematical Physics•Feb 1, 2020•8 citations

Polynomial-time local-unitary equivalence of graph states

Yuxuan Zhang

Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on $n$ labelled vertices in $\widetilde O(n^{6.38})$ bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost $\widetilde O(n^5)$ bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.

quant-pharXiv:2610.00527•Oct 2, 2026•0 citations
We introduce a new notion of distance between two graph states ∣G⟩|G\rangle∣G⟩ and ∣G′⟩|G'\rangle∣G′⟩ on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state ∣G^⟩|\widehat{G}\rangle∣G⟩ from which both ∣G⟩|G\rangle∣G⟩ and ∣G′⟩|G'\rangle∣G′⟩ 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⟩|G\rangle∣G⟩. The ancilla integrity problem asks, given a graph GGG and integer kkk, for the minimum -- over all graph states ∣G′⟩|G'\rangle∣G′⟩ with distance at most kkk from ∣G⟩|G\rangle∣G⟩ -- of the maximum component size of G′G'G′. Up to a factor of 222 in the number of ancilla qubits, this problem is equivalent to rank integrity, where the distance between GGG and G′G'G′ is instead the minimum rank of the sum of their adjacency matrices over GF(2)\text{GF}(2)GF(2). We prove that rank integrity is XP parameterized by kkk. We also prove the complementary hardness result that rank integrity is W[1]-hard in kkk. Finally, we give an explicit O(n6)\mathcal{O}(n^6)O(n6)-time algorithm for ancilla integrity when GGG has nnn vertices and k=1k=1k=1.
We develop a unified quantum framework for subgraph counting in graphs. We encode a graph on NNN vertices into a quantum state on 2⌈log⁡2N⌉2\lceil \log_2 N \rceil2⌈log2​N⌉ working qubits and 222 ancilla qubits using its adjacency list, with worst-case gate complexity O(N2)O(N^2)O(N2), which we refer to as the graph adjacency state. We design quantum measurement operators that capture the edge structure of a target subgraph, enabling estimation of its count via measurements on the mmm-fold tensor product of the adjacency state, where mmm is the number of edges in the subgraph. We illustrate the framework for triangles, cycles, and cliques. This approach yields quantum logspace algorithms for motif counting, with no known classical counterpart.
Stabilizer states form an important class of states in quantum information, and are of central importance in quantum error correction. Here, we provide an algorithm for deciding whether one stabilizer (target) state can be obtained from another stabilizer (source) state by single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. What is more, we provide a recipe to obtain the sequence of LC+LPM+CC operations which prepare the desired target state from the source state, and show how these operations can be applied in parallel to reach the target state in constant time. Our algorithm has applications in quantum networks, quantum computing, and can also serve as a design tool—for example, to find transformations between quantum error correcting codes. We provide a software implementation of our algorithm that makes this tool easier to apply. A key insight leading to our algorithm is to show that the problem is equivalent to one in graph theory, which is to decide whether some graph G ′ is a vertex-minor of another graph G . The vertex-minor problem is, in general, -Complete, but can be solved efficiently on graphs which are not too complex. A measure of the complexity of a graph is the rank-width which equals the Schmidt-rank width of a subclass of stabilizer states called graph states, and thus intuitively is a measure of entanglement. Here, we show that the vertex-minor problem can be solved in time O (| G | 3 ), where | G | is the size of the graph G , whenever the rank-width of G and the size of G ′ are bounded. Our algorithm is based on techniques by Courcelle for solving fixed parameter tractable problems, where here the relevant fixed parameter is the rank width. The second half of this paper serves as an accessible but far from exhausting introduction to these concepts, that could be useful for many other problems in quantum information. This article is part of a discussion meeting issue ‘Foundations of quantum mechanics and their impact on contemporary society’.
Quantum networks are important for quantum communication and consist of entangled states that are essential for many tasks such as quantum teleportation, quantum key distribution, quantum sensing and quantum error correction. Graph states are a specific class of multipartite entangled states that can be represented by graphs. We propose a novel approach for distributing graph states across a quantum network. We show that the distribution of graph states can be characterised bya\boldsymbol{a}asystem of subgraph complementations, which we also relate to the minimum rank of the underlying graph and the degree of entanglement quantified by the Schmidt-rank of the quantum state. We analyse resource usage for our algorithm and show it to match or be improved in the number of qubits, bits for classical communication and EPR pairs utilised, as compared to prior work. The number of local operations is efficient, and the resource consumption for our approach scales linearly in the number of vertices. This presents a quadratic improvement in completion time for several classes of graph states represented by dense graphs, and implies a potential for improved fidelity in the presence of noise. Common classes of graph states are classified along with the optimal time for their distribution using subgraph complementations. We also provide a framework to similarly find the optimal sequence of operations to distribute an arbitrary graph state, and prove upper bounds along with providing approximate greedy algorithms.
We prove that the quantum code distance is NP-hard to approximate within an additive error of cNc NcN, for some constant c>0c >0c>0, where NNN is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to Ω(N)Ω(N)Ω(N) and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical XXX- and ZZZ-check spaces, and with a constant rate and constant relative distance. For every fixed λ>1λ>1λ>1, there is a constant c>0c>0c>0 such that hardness still holds even when every nonidentity stabilizer has weight greater than λλλ times the quantum distance. We also improve the hardness gap of graph state distance on NNN vertices of Grigorescu, Jha, and Samperton from cube-root to Ω(N)Ω(N)Ω(N), resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most NNN. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code CCC of length mmm into a self-dual code A(C)A(C)A(C) of length N=Θ(m)N=Θ(m)N=Θ(m) while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of CCC. It comes with a linear embedding τ:F2m↪F2Nτ: \mathbb F_2^m \hookrightarrow \mathbb F_2^Nτ:F2m​↪F2N​. The embedding doubles all Hamming distances between vectors in F2m\mathbb F_2^mF2m​ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of A(C)A(C)A(C) of weight at most 2m2m2m are exactly τ(C)τ(C)τ(C).
Graph states, which include Bell states, Greenberger-Horne-Zeilinger (GHZ) states, and cluster states, form a well-known class of quantum states with applications ranging from quantum networks to error-correction. Whether two graph states are equivalent up to single-qubit Clifford operations is known to be decidable in polynomial time and has been studied in the context of producing certain required states in a quantum network in relation to stabilizer codes. The reason for the latter is that single-qubit Clifford equivalent graph states exactly correspond to equivalent stabilizer codes. We here consider that the computational complexity of, given a graph state |G⟩, counting the number of graph states, single-qubit Clifford equivalent to |G⟩. We show that this problem is #P-complete. To prove our main result, we make use of the notion of isotropic systems in graph theory. We review the definition of isotropic systems and point out their strong relation to graph states. We believe that these isotropic systems can be useful beyond the results presented in this paper.
Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on nnn labelled vertices in O~(n6.38)\widetilde O(n^{6.38})O(n6.38) bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost O~(n5)\widetilde O(n^5)O(n5) bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.