  In this paper we present an efficiently scaling quantum algorithm which finds
the size of the maximum common edge subgraph for a pair of arbitrary graphs and
thus provides a meaningful measure of graph similarity. The algorithm makes use
of a two-part quantum dynamic process: in the first part we obtain information
crucial for the comparison of two graphs through linear quantum computation.
However, this information is hidden in the quantum system with vanishingly
small amplitude that even quantum algorithms such as Grover's search are not
fast enough to distill the information efficiently. In order to extract the
information we call upon techniques in nonlinear quantum computing to provide
the speed-up necessary for an efficient algorithm. The linear quantum circuit
requires $\mathcal{O}(n^3 \log^3 (n) \log \log (n))$ elementary quantum gates
and the nonlinear evolution under the Gross-Pitaevskii equation has a time
scaling of $\mathcal{O}(\frac{1}{g} n^2 \log^3 (n) \log \log (n))$, where $n$
is the number of vertices in each graph and $g$ is the strength of the
Gross-Pitaveskii non-linearity. Through this example, we demonstrate the power
of nonlinear quantum search techniques to solve a subset of NP-hard problems.
