Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.02027 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918425576603648 |
|---|---|
| author | Kara, Ruben Danz, Sven Stollenwerk, Tobias Benigni, Andrea |
| author_facet | Kara, Ruben Danz, Sven Stollenwerk, Tobias Benigni, Andrea |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_02027 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Quantum search algorithm for similar subgraph identification under fixed edge removal Kara, Ruben Danz, Sven Stollenwerk, Tobias Benigni, Andrea Quantum Physics 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. |
| title | Quantum search algorithm for similar subgraph identification under fixed edge removal |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2604.02027 |