Quantum search algorithm for similar subgraph identification under fixed edge removal

Ruben Kara, Sven Danz, Tobias Stollenwerk, Andrea Benigni

arXivarxiv/2604.02027Apr 2, 2026quant-phscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.02027
curl -X POST /api/v1/records/arxiv/2604.02027/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.02027/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'