A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems
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.
- A classical approach to the graph isomorphism problem using quantum walks
- An alternative adiabatic quantum algorithm for the Hamiltonian cycle problem
- An enhanced classical approach to graph isomorphism using continuous-time quantum walk
- A graph isomorphism algorithm using signatures computed via quantum walk search model
- Quantum walk inspired algorithm for graph similarity and isomorphism
- Solving problem of graph isomorphism by membrane-quantum hybrid model
- QUBO formulations for the graph isomorphism problem and related problems
- Constructing quantum hash functions based on quantum walks on Johnson graphs
- Quantum search algorithm for exceptional vertexes in regular graphs and its circuit implementation
- Hash function based on quantum walks
- Treating the independent set problem by 2D Ising interactions with adiabatic quantum computing
- Quantum walk and its application domains: a systematic review
- Quantum walk inspired algorithm for graph similarity and isomorphism
- Novel two-party quantum private comparison via quantum walks on circle
- On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
- An enhanced classical approach to graph isomorphism using continuous-time quantum walk
- Physically-motivated dynamical algorithms for the graph isomorphism problem
- Quantum state transfer on unsymmetrical graphs via discrete-time quantum walk
- A graph isomorphism algorithm using signatures computed via quantum walk search model
- An alternative adiabatic quantum algorithm for the Hamiltonian cycle problem
- A classical approach to the graph isomorphism problem using quantum walks
- Optimization on large interconnected graphs and networks using adiabatic quantum computation
- On the circuit model of two quantum adiabatic search algorithms
- A bounded-error quantum polynomial-time algorithm for two graph bisection problems
- Graph isomorphism and Gaussian boson sampling
This page was built for publication: A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2878633)
