Quantum embedding of graphs for subgraph counting
This work provides a novel quantum approach to subgraph counting, a fundamental problem in graph theory, with potential exponential speedup over classical methods.
The authors developed a quantum framework for subgraph counting that encodes a graph into a quantum state using O(N^2) gates and estimates subgraph counts via measurements. The method yields quantum logspace algorithms for motif counting with no known classical counterpart.
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.