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:2111.13222 · Quantum

Quantum Motif Clustering

Chris Cade, Farrokh Labib, Ido Niesen

Published Jul 3, 2023• 4 citations
arXivHTMLPDF

Abstract

We present three quantum algorithms for clustering graphs based on higher-order patterns, known as motif clustering. One uses a straightforward application of Grover search, the other two make use of quantum approximate counting, and all of them obtain square-root like speedups over the fastest classical algorithms in various settings. In order to use approximate counting in the context of clustering, we show that for general weighted graphs the performance of spectral clustering is mostly left unchanged by the presence of constant (relative) errors on the edge weights. Finally, we extend the original analysis of motif clustering in order to better understand the role of multiple `anchor nodes' in motifs and the types of relationships that this method of clustering can and cannot capture.

DOI
10.22331/q-2023-07-03-1046

Related papers

Solving Correlation Clustering with the Quantum Approximate Optimisation Algorithm

Jordi R. Weggemans

The quantum approximation optimisation algorithm (QAOA) is one of the leading candidates for testing the applicability of gate-model quantum resources at solving optimisation problems on small-sized quantum hardware. A combinatorial problem that has been understudied with QAOA is correlation clustering: given a weighted (+1,-1) graph, where the edge weights indicate whether two nodes are similar (positive edge weight) or different (negative edge weight), the task in correlation clustering is to find a clustering that either maximises agreements, minimises disagreements or a combination of both. In this thesis, we design Hamiltonian formulations that encode correlation clustering problems such that they can be solved with QAOA. For all Hamiltonian formulations we propose circuit implementations and study their complexities. To benchmark the performances of a basic QAOA algorithm using these formulations, we use numerical simulations on complete graph data sets. For one of the formulations, which uses a multi-level approach naturally suitable to qudit systems, we investigate the performances of several optimisers and introduce heuristic strategies to further improve its performance. On all instances in our data-sets, which include complete as well as Erdős–Renyi graphs, the improved algorithm shows competitive performances for QAOA depth p ≥ 2. We also show that for this algorithm at p = 1 parameters exists such that it has a performance guarantee of 0.670 on 3-regular graphs.

•Jan 1, 2020•1 citation

Quantum Algorithms for Triangle Cut Sparsification

Shan Jiang, Pan Peng

Triangles capture higher-order structures in graphs and are fundamental to applications such as clustering and network analysis. To enable efficient use of such structures at scale, we study the problem of triangle cut sparsification, which aims to reduce the graph size while approximately preserving triangle counts across every cut. We investigate quantum algorithms for this problem, using triangle listing as our main technical ingredient. In particular, we present a quantum algorithm for triangle listing that, for a graph with $n$ vertices, $m$ edges, and $t$ triangles, runs in time $T_{\mathrm{q\text{-}list}} =$ $\widetilde{O}\bigl(\min(n^{5/4}t^{7/12} + n^{7/6}t^{7/9}, m + m^{3/4}t^{1/2},$ $n^{3/2}t^{1/2})\bigr)$, improving upon the best known classical bounds over a broad range of parameters. Our algorithm is based on a heavy-light vertex partition and an extension of triangle detection via quantum walks and Grover search. Leveraging this result, we design a quantum algorithm for constructing $\varepsilon$-triangle cut sparsifiers of size $\widetilde{O}(n/\varepsilon^2)$ in time $\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)$. Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of $Ω(n/\varepsilon^2)$ on the size of any $\varepsilon$-triangle cut sparsifiers.

quant-pharXiv:2606.06287•Jun 5, 2026•1 citation

Quantum-Inspired Graph Clustering using Amplitude Estimation

Jincheng Zhang

Graph clustering, the process of grouping nodes in a graph based on their relationships, is a cornerstone of numerous data analysis applications, including social network analysis, bioinformatics, and anomaly detection. Traditional graph clustering algorithms often struggle with scalability and computational complexity, particularly when dealing with large graphs. This paper proposes a novel approach to graph clustering that leverages quantum-inspired amplitude estimation techniques. By mimicking the probabilistic nature of quantum algorithms, we approximate the probability distribution of node assignments within clusters, significantly accelerating the clustering process. Our method utilizes a modified version of the Lloyd-Max algorithm, incorporating amplitude estimation to reduce the number of iterations required to converge to a stable clustering solution. We demonstrate, through theoretical analysis and algorithmic design, that this approach can achieve comparable or superior clustering performance compared to conventional methods, while exhibiting a markedly reduced computational footprint. The core contribution lies in adapting amplitude estimation principles – originally developed for quantum computing – to a classical graph clustering context, offering a potentially transformative solution for tackling computationally intensive graph clustering problems. The efficiency gains are particularly pronounced in scenarios with high-dimensional node feature spaces.

•Sep 5, 2026•0 citations

Grover’s quantum walk on segmented complete graphs

Gamal Mograby, Benjamin Maloy, Anastasiia Minenkova

We study Grover's quantum walk on a new class of graphs, termed segmented complete graphs, which combine high symmetry with detailed spectral properties. Using these graphs, we implement Grover's search algorithm and investigate its performance, focussing on the relationship between graph volume, optimal search time and success probabilities. Our results generalize classical findings for directed weighted graphs and provide new insights into enhancing quantum search algorithms on complex graph structures.This article is part of the theme issue 'Numerical analysis, spectral graph theory, orthogonal polynomials and quantum algorithms'.

Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Oct 9, 2025•0 citations

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•1 citation

Quantum Algorithms for Approximate Graph Isomorphism Testing

Prateek P. Kulkarni

The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on $n$ vertices drawn from the Erdős--Rényi distribution $\mathcal{G} (n,1/2)$ are considered approximately isomorphic if they can be made isomorphic by at most $k$ edge edits. We present a quantum algorithm based on MNRS quantum walk search over the product graph $Γ(G,H)$ of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity $\mathcal{O}(n^{3/2} \log n/\varepsilon)$, where $\varepsilon$ parameterizes the approximation threshold. We complement this with an $Ω(n^2)$ classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model. We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.

quant-pharXiv:2603.02656•Mar 4, 2026•0 citations
We present three quantum algorithms for clustering graphs based on higher-order patterns, known as motif clustering. One uses a straightforward application of Grover search, the other two make use of quantum approximate counting, and all of them obtain square-root like speedups over the fastest classical algorithms in various settings. In order to use approximate counting in the context of clustering, we show that for general weighted graphs the performance of spectral clustering is mostly left unchanged by the presence of constant (relative) errors on the edge weights. Finally, we extend the original analysis of motif clustering in order to better understand the role of multiple `anchor nodes' in motifs and the types of relationships that this method of clustering can and cannot capture.
The quantum approximation optimisation algorithm (QAOA) is one of the leading candidates for testing the applicability of gate-model quantum resources at solving optimisation problems on small-sized quantum hardware. A combinatorial problem that has been understudied with QAOA is correlation clustering: given a weighted (+1,-1) graph, where the edge weights indicate whether two nodes are similar (positive edge weight) or different (negative edge weight), the task in correlation clustering is to find a clustering that either maximises agreements, minimises disagreements or a combination of both. In this thesis, we design Hamiltonian formulations that encode correlation clustering problems such that they can be solved with QAOA. For all Hamiltonian formulations we propose circuit implementations and study their complexities. To benchmark the performances of a basic QAOA algorithm using these formulations, we use numerical simulations on complete graph data sets. For one of the formulations, which uses a multi-level approach naturally suitable to qudit systems, we investigate the performances of several optimisers and introduce heuristic strategies to further improve its performance. On all instances in our data-sets, which include complete as well as Erdős–Renyi graphs, the improved algorithm shows competitive performances for QAOA depth p ≥ 2. We also show that for this algorithm at p = 1 parameters exists such that it has a performance guarantee of 0.670 on 3-regular graphs.
Triangles capture higher-order structures in graphs and are fundamental to applications such as clustering and network analysis. To enable efficient use of such structures at scale, we study the problem of triangle cut sparsification, which aims to reduce the graph size while approximately preserving triangle counts across every cut. We investigate quantum algorithms for this problem, using triangle listing as our main technical ingredient. In particular, we present a quantum algorithm for triangle listing that, for a graph with nnn vertices, mmm edges, and ttt triangles, runs in time Tq-list=T_{\mathrm{q\text{-}list}} =Tq-list​= O~(min⁡(n5/4t7/12+n7/6t7/9,m+m3/4t1/2,\widetilde{O}\bigl(\min(n^{5/4}t^{7/12} + n^{7/6}t^{7/9}, m + m^{3/4}t^{1/2},O(min(n5/4t7/12+n7/6t7/9,m+m3/4t1/2, n3/2t1/2))n^{3/2}t^{1/2})\bigr)n3/2t1/2)), improving upon the best known classical bounds over a broad range of parameters. Our algorithm is based on a heavy-light vertex partition and an extension of triangle detection via quantum walks and Grover search. Leveraging this result, we design a quantum algorithm for constructing ε\varepsilonε-triangle cut sparsifiers of size O~(n/ε2)\widetilde{O}(n/\varepsilon^2)O(n/ε2) in time O~(Tq-list+mn/ε)\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)O(Tq-list​+mn​/ε). Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of Ω(n/ε2)Ω(n/\varepsilon^2)Ω(n/ε2) on the size of any ε\varepsilonε-triangle cut sparsifiers.
Graph clustering, the process of grouping nodes in a graph based on their relationships, is a cornerstone of numerous data analysis applications, including social network analysis, bioinformatics, and anomaly detection. Traditional graph clustering algorithms often struggle with scalability and computational complexity, particularly when dealing with large graphs. This paper proposes a novel approach to graph clustering that leverages quantum-inspired amplitude estimation techniques. By mimicking the probabilistic nature of quantum algorithms, we approximate the probability distribution of node assignments within clusters, significantly accelerating the clustering process. Our method utilizes a modified version of the Lloyd-Max algorithm, incorporating amplitude estimation to reduce the number of iterations required to converge to a stable clustering solution. We demonstrate, through theoretical analysis and algorithmic design, that this approach can achieve comparable or superior clustering performance compared to conventional methods, while exhibiting a markedly reduced computational footprint. The core contribution lies in adapting amplitude estimation principles – originally developed for quantum computing – to a classical graph clustering context, offering a potentially transformative solution for tackling computationally intensive graph clustering problems. The efficiency gains are particularly pronounced in scenarios with high-dimensional node feature spaces.
We study Grover's quantum walk on a new class of graphs, termed segmented complete graphs, which combine high symmetry with detailed spectral properties. Using these graphs, we implement Grover's search algorithm and investigate its performance, focussing on the relationship between graph volume, optimal search time and success probabilities. Our results generalize classical findings for directed weighted graphs and provide new insights into enhancing quantum search algorithms on complex graph structures.This article is part of the theme issue 'Numerical analysis, spectral graph theory, orthogonal polynomials and quantum algorithms'.
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.
The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on nnn vertices drawn from the Erdős--Rényi distribution G(n,1/2)\mathcal{G} (n,1/2)G(n,1/2) are considered approximately isomorphic if they can be made isomorphic by at most kkk edge edits. We present a quantum algorithm based on MNRS quantum walk search over the product graph Γ(G,H)Γ(G,H)Γ(G,H) of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity O(n3/2log⁡n/ε)\mathcal{O}(n^{3/2} \log n/\varepsilon)O(n3/2logn/ε), where ε\varepsilonε parameterizes the approximation threshold. We complement this with an Ω(n2)Ω(n^2)Ω(n2) classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model. We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.