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:2604.02027

Quantum search algorithm for similar subgraph identification under fixed edge removal

Ruben Kara, Sven Danz, Tobias Stollenwerk, Andrea Benigni

quant-phSubmitted Apr 2, 2026• Announced Apr 3, 2026• 0 citations
arXivHTMLPDF

Abstract

We introduce a novel quantum algorithm for similar subgraph identification in form of an NP-hard cardinality-constrained binary quadratic optimization problem. Given a weighted reference graph with Laplacian $\boldsymbol{B}$, our algorithm determines the subgraph featuring Laplacian $\boldsymbol{B'}$ on the same vertex set, but $x$ out of $N$ inactive edges, minimizing the Frobenius distance $||\boldsymbol{B} - \boldsymbol{B'}||_\mathrm{F}^2$. We represent the $\binom{N}{x}$ graph topologies by an equal-weight superposition in form of a Dicke state, enabling controlled transformations applied to the quantum state associated with the vectorized Laplacian of the reference graph. Combined with amplitude estimation and a minimum finding approach, our algorithm provides a polynomial speed up $\mathcal{O}(\sqrt{N^{x}/x!}N\log\log N)$ compared to $\mathcal{O}(N^{x+1}/x!)$ of classical brute-force search algorithms. We demonstrate the application of our method on standard test cases, which represent electric power grids, by reconstructing $||\boldsymbol{B} -\boldsymbol{B'}||_\mathrm{F}^2$ from measurements and show how our approach can be additionally used to calculate energy functional like quadratic forms of the Laplacians with respect to a given vector.

Related papers

Explicit Quantum Search Algorithm for the Densest k-Subgraph Problem

Yu. A. Biriukov, R. D. Morozov, I. V. Dyakonov +1 more

This paper addresses the problem of finding the densest $k$-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.

quant-pharXiv:2604.27782•May 1, 2026•0 citations

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

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem

Joonas Ilmavirta, Matti J. Lassas, Jinpeng Lu +2 more

We consider an inverse problem for a finite graph $ (X, E) $ where we are given a subset of vertices $ B\subset X $ and the distances $ d_{(X, E)}(b_1, b_2) $ between all pairs of vertices $ b_1, b_2\in B $. The distance between vertices $ x_1, x_2\in X $ is defined as the minimal number of edges in paths connecting the vertices. This problem can be regarded as a discrete version of the boundary rigidity problem in Riemannian geometry or the inverse travel time problem in geophysics. We develop quantum computing methods to find a solution to the problem, and show that the solution is unique under certain conditions. We prove the following uniqueness result: when $ (X, E) $ is a tree and $ B $ is the set of leaves of the tree, the graph $ (X, E) $ is uniquely determined in the class of all connected graphs having a fixed number of vertices. We present a quantum algorithm which, under arbitrary conditions, produces the graph $ (X, E) $, or one of those, which has the given number of vertices and the required distances between vertices in $ B $. To this end we develop an algorithm that takes in a qubit representation of a graph and combine it with Grover's search algorithm. The algorithm can be implemented using only $ O(|X|^2) $ qubits, the same order as the number of elements in the adjacency matrix of $ (X, E) $, and it has a quadratic improvement in computational cost compared to standard classical algorithms. Finally, we consider applications in the theory of computation, and show that a slight modification of the inverse problem above is NP-complete: all NP-problems can be reduced to a discrete inverse problem that we consider.

arXiv:2306.05253•Inverse Problems and Imaging•Dec 5, 2024•1 citation

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

A Quantum Framework for Combinatorial Optimization Problem over Graphs

Meng Shi, Sai Wu, Ying Li +3 more

Abstract Combinatorial optimization problems over graphs, such as the traveling salesman problem, longest path problem, and maximum independent set problem, are well-known for being computationally costly, some even NP-hard problems. In this paper, we propose a general quantum algorithm framework searching for approximate solutions to combinatorial optimization problems with linear objective functions. Our framework provides APIs (application programming interfaces) that enable developers to encode weighted graph structures onto quantum circuits and utilize variational algorithms to generate approximate solutions. One key advantage of our framework is that it allows developers to design new graph algorithms for the graph problem represented as linear combinations of edge weights without requiring expertise in quantum programming. Besides, it only uses a logarithmic level of quantum bit scale, making our framework work on quantum computers with limited physical resources. Our experimental results demonstrate that our framework can provide good approximations for the traveling salesman problem compared to current quantum algorithm.

Data Science and Engineering•Jan 24, 2025•4 citations

Superlinear Quantum Query Lower Bounds for Subgraph Detection

Amin Shiraz Gilani, Xingyu Zhou

Subgraph detection asks whether an $n$-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph $H$. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of $H$ is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed $r\ge 4$, detecting the clique $K_r$ requires $n^{λ_r-o(1)}$ queries, where $λ_4=19/18$, the exponents $λ_r$ increase strictly with $r$, and $λ_r\ge 2-4\sqrt{2/r}+O(1/r)$. More generally, we prove superlinear lower bounds for detecting every fixed connected graph $H$ with chromatic number $c\ge 4$. These bounds approach quadratic as $c$ grows: for sufficiently large $c$, detection requires $n^{2-O(\sqrt{\log\log c/c})-o(1)}$ queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph $K_{r,r}$ requires $n^{β_r-o(1)}$ queries, where $β_{10}=181/180$ and $β_r\ge 2-O(1/\sqrt{r})$. Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.

quant-pharXiv:2609.40263•Oct 1, 2026•0 citations
We introduce a novel quantum algorithm for similar subgraph identification in form of an NP-hard cardinality-constrained binary quadratic optimization problem. Given a weighted reference graph with Laplacian B\boldsymbol{B}B, our algorithm determines the subgraph featuring Laplacian B′\boldsymbol{B'}B′ on the same vertex set, but xxx out of NNN inactive edges, minimizing the Frobenius distance ∣∣B−B′∣∣F2||\boldsymbol{B} - \boldsymbol{B'}||_\mathrm{F}^2∣∣B−B′∣∣F2​. We represent the (Nx)\binom{N}{x}(xN​) graph topologies by an equal-weight superposition in form of a Dicke state, enabling controlled transformations applied to the quantum state associated with the vectorized Laplacian of the reference graph. Combined with amplitude estimation and a minimum finding approach, our algorithm provides a polynomial speed up O(Nx/x!Nlog⁡log⁡N)\mathcal{O}(\sqrt{N^{x}/x!}N\log\log N)O(Nx/x!​NloglogN) compared to O(Nx+1/x!)\mathcal{O}(N^{x+1}/x!)O(Nx+1/x!) of classical brute-force search algorithms. We demonstrate the application of our method on standard test cases, which represent electric power grids, by reconstructing ∣∣B−B′∣∣F2||\boldsymbol{B} -\boldsymbol{B'}||_\mathrm{F}^2∣∣B−B′∣∣F2​ from measurements and show how our approach can be additionally used to calculate energy functional like quadratic forms of the Laplacians with respect to a given vector.
This paper addresses the problem of finding the densest kkk-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.
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.
We consider an inverse problem for a finite graph $ (X, E) $ where we are given a subset of vertices $ B\subset X $ and the distances $ d_{(X, E)}(b_1, b_2) $ between all pairs of vertices $ b_1, b_2\in B $. The distance between vertices $ x_1, x_2\in X $ is defined as the minimal number of edges in paths connecting the vertices. This problem can be regarded as a discrete version of the boundary rigidity problem in Riemannian geometry or the inverse travel time problem in geophysics. We develop quantum computing methods to find a solution to the problem, and show that the solution is unique under certain conditions. We prove the following uniqueness result: when $ (X, E) $ is a tree and $ B $ is the set of leaves of the tree, the graph $ (X, E) $ is uniquely determined in the class of all connected graphs having a fixed number of vertices. We present a quantum algorithm which, under arbitrary conditions, produces the graph $ (X, E) $, or one of those, which has the given number of vertices and the required distances between vertices in $ B $. To this end we develop an algorithm that takes in a qubit representation of a graph and combine it with Grover's search algorithm. The algorithm can be implemented using only $ O(|X|^2) $ qubits, the same order as the number of elements in the adjacency matrix of $ (X, E) $, and it has a quadratic improvement in computational cost compared to standard classical algorithms. Finally, we consider applications in the theory of computation, and show that a slight modification of the inverse problem above is NP-complete: all NP-problems can be reduced to a discrete inverse problem that we consider.
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.
Abstract Combinatorial optimization problems over graphs, such as the traveling salesman problem, longest path problem, and maximum independent set problem, are well-known for being computationally costly, some even NP-hard problems. In this paper, we propose a general quantum algorithm framework searching for approximate solutions to combinatorial optimization problems with linear objective functions. Our framework provides APIs (application programming interfaces) that enable developers to encode weighted graph structures onto quantum circuits and utilize variational algorithms to generate approximate solutions. One key advantage of our framework is that it allows developers to design new graph algorithms for the graph problem represented as linear combinations of edge weights without requiring expertise in quantum programming. Besides, it only uses a logarithmic level of quantum bit scale, making our framework work on quantum computers with limited physical resources. Our experimental results demonstrate that our framework can provide good approximations for the traveling salesman problem compared to current quantum algorithm.
Subgraph detection asks whether an nnn-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph HHH. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of HHH is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed r≥4r\ge 4r≥4, detecting the clique KrK_rKr​ requires nλr−o(1)n^{λ_r-o(1)}nλr​−o(1) queries, where λ4=19/18λ_4=19/18λ4​=19/18, the exponents λrλ_rλr​ increase strictly with rrr, and λr≥2−42/r+O(1/r)λ_r\ge 2-4\sqrt{2/r}+O(1/r)λr​≥2−42/r​+O(1/r). More generally, we prove superlinear lower bounds for detecting every fixed connected graph HHH with chromatic number c≥4c\ge 4c≥4. These bounds approach quadratic as ccc grows: for sufficiently large ccc, detection requires n2−O(log⁡log⁡c/c)−o(1)n^{2-O(\sqrt{\log\log c/c})-o(1)}n2−O(loglogc/c​)−o(1) queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph Kr,rK_{r,r}Kr,r​ requires nβr−o(1)n^{β_r-o(1)}nβr​−o(1) queries, where β10=181/180β_{10}=181/180β10​=181/180 and βr≥2−O(1/r)β_r\ge 2-O(1/\sqrt{r})βr​≥2−O(1/r​). Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.