In this paper we determine the class of quantum states whose density matrix representation can be derived from graph Laplacian matrices associated with a weighted directed graph and we call them graph Laplacian quantum states. Then we obtain structural properties of these graphs such that the corresponding graph Laplacian states have zero quantum discord by investigating structural properties of clustered graphs which provide a family of commuting normal matrices formed by the blocks of its Laplacian matrices. We apply these results on some important mixed quantum states, such as the Werner, Isotropic, and X-states.
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, our algorithm determines the subgraph featuring Laplacian B′ on the same vertex set, but x out of N inactive edges, minimizing the Frobenius distance ∣∣B−B′∣∣F2. We represent the (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!NloglogN) compared to 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 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.