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

DOI10.1088/1751-8113/47/32/325302zbMATH Open1311.68071arXiv1401.1278OpenAlexW1978536401MaRDI QIDQ2878633FDOQ2878633

Authors: Dario Tamascelli, Luca Zanetti 

Publication date: 4 September 2014

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Abstract: We present a 2-local quantum algorithm for graph isomorphism GI based on an adiabatic protocol. By exploiting continuous-time quantum-walks, we are able to avoid a mere diffusion over all possible configurations and to significantly reduce the dimensionality of the visited space. Within this restricted space, the graph isomorphism problem can be translated into the search of a satisfying assignment to a 2-SAT formula without resorting to perturbation gadgets or projective techniques. We present an analysis of the execution time of the algorithm on small instances of the graph isomorphism problem and discuss the issue of an implementation of the proposed adiabatic scheme on current quantum computing hardware.

Full work available at URL: https://arxiv.org/abs/1401.1278

Recommendations

• 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

zbMATH Keywords

graph isomorphismquantum walksadiabatic quantum computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cited In (20)

• Graph isomorphism and Gaussian boson sampling
• Treating the independent set problem by 2D Ising interactions with adiabatic quantum computing
• Quantum walk and its application domains: a systematic review
• QUBO formulations for the graph isomorphism problem and related problems
• Constructing quantum hash functions based on quantum walks on Johnson graphs
• Novel two-party quantum private comparison via quantum walks on circle
• An alternative adiabatic quantum algorithm for the Hamiltonian cycle problem
• Hash function based on quantum walks
• An enhanced classical approach to graph isomorphism using continuous-time quantum walk
• Solving problem of graph isomorphism by membrane-quantum hybrid model
• A classical approach to the graph isomorphism problem using quantum walks
• A bounded-error quantum polynomial-time algorithm for two graph bisection problems
• Physically-motivated dynamical algorithms for the graph isomorphism problem
• A graph isomorphism algorithm using signatures computed via quantum walk search model
• On the circuit model of two quantum adiabatic search algorithms
• Quantum search algorithm for exceptional vertexes in regular graphs and its circuit implementation
• Quantum state transfer on unsymmetrical graphs via discrete-time quantum walk
• Optimization on large interconnected graphs and networks using adiabatic quantum computation
• Quantum walk inspired algorithm for graph similarity and isomorphism
• On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism

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)