A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems (Q2878633)

Besides its practical importance (for instance in chemioinformatics, in mathematical chemistry and in electronic design automation), the Graph Isomorphism (GI) problem is relevant in computational complexity theory as it is one of a very small number of problems belonging to NP (Nondeterministic Polynomial time) neither known to be solvable in polynomial time nor to be NP-complete: it is one of only 12 such problems listed by \textit{M. R. Garey} and \textit{D. S. Johnson} [Computers and intractability. A guide to the theory of NP-completeness. San Francisco: W. H. Freeman and Company (1979; Zbl 0411.68039)], and one of only two of that list whose complexity remains unresolved (the other being Prime Factorization). As the authors recall, the best classical general algorithm solves GI for graphs of \(n\) vertices in time \(O(c^{ \sqrt{n} \log n})\) where \(c\) is a constant. Starting from 2005, however, there have also been several proposals of quantum algorithms based either on \textit{non-isomorphism witnesses} (observable quantities that assume different values only if the two input graphs are non-isomorphic), or on the \textit{adiabatic quantum computation} paradigm. NEWLINENEWLINENEWLINE Adopting this second approach, in the present paper the authors propose an algorithm that solves GI by finding, if it exists, a permutation that transforms one of the two input graphs into the other. In order to do that they first define a suitable cost function for every permutation of the 0-1 variables used to describe the graphs; then they look at it as an \(n\)-SAT (\(n\)-satisfiability) Boolean formula; and finally they map their problem into that of finding the state of lowest energy of a suitable Hamiltonian: if the two graphs are isomorphic, then there exists a zero-energy configuration. They next assign a quantum spin (qubit) to each Boolean variable and guess an initial Hamiltonian \(H_I\) from the structure of their \(n\)-SAT formula: as a consequence ``the exploration of the configuration space is performed through \(n\) continuous time quantum walks on linear graphs''.NEWLINENEWLINEThe authors proceed then to show their empirical estimates of the annealing time \(T\) for instances of (a priori) isomorphic graphs up to the size \(n=12\). These results are admittedly rather preliminary due to the small size of these tractable instances which ``makes it impossible to infer anything about the behavior of the algorithm on large GI instances''. They are able to show that ``the annealing time scales linearly from \(n = 6\) to \(n = 10\). Then there is some kind of phase transition'' and \(T\) grows still linearly, but more steeply. The authors then conjecture that this ``will most likely imply an exponential dependence of the annealing time on the input size; the rate of such transitions, however, will determine the presence of any quantum speed-up with respect to the best classical algorithm.'' They are hence very careful in their statements about the running time of the algorithm where they see ``no evidence of any quantum speed-up with respect to the best classical algorithm for GI'', and finally remark that a substantial enlargement of the size \(n\) of the tractable graphs and the consequent ``real check of the performance of the procedure described in this work will be possible only by implementing it on a quantum computer.''