  Comparative analyses of graph structured datasets underly diverse problems.
Examples of these problems include identification of conserved functional
components (biochemical interactions) across species, structural similarity of
large biomolecules, and recurring patterns of interactions in social networks.
A large class of such analyses methods quantify the topological similarity of
nodes across networks. The resulting correspondence of nodes across networks,
also called node alignment, can be used to identify invariant subgraphs across
the input graphs.
  Given $k$ graphs as input, alignment algorithms use topological information
to assign a similarity score to each $k$-tuple of nodes, with elements (nodes)
drawn from each of the input graphs. Nodes are considered similar if their
neighbors are also similar. An alternate, equivalent view of these network
alignment algorithms is to consider the Kronecker product of the input graphs,
and to identify high-ranked nodes in the Kronecker product graph. Conventional
methods such as PageRank and HITS (Hypertext Induced Topic Selection) can be
used for this purpose. These methods typically require computation of the
principal eigenvector of a suitably modified Kronecker product matrix of the
input graphs. We adopt this alternate view of the problem to address the
problem of multiple network alignment. Using the phase estimation algorithm, we
show that the multiple network alignment problem can be efficiently solved on
quantum computers. We characterize the accuracy and performance of our method,
and show that it can deliver exponential speedups over conventional
(non-quantum) methods.
