Quantum search algorithm for similar subgraph identification under fixed edge removal

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'}||_F². 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!}Nloglog 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'}||_F² 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.