A quantum-walk-inspired adiabatic algorithm for graph isomorphism

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.

10 pages, 5 figures

References in corpus (6)

• Exponential algorithmic speedup by quantum walk
• Bounds for the adiabatic approximation with applications to quantum computation
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Non-local updates for quantum Monte Carlo simulations
• High-Performance Physics Simulations Using Multi-Core CPUs and GPGPUs in a Volunteer Computing Context

Cited by in corpus (14)

• Feature Selection for Recommender Systems with Quantum Computing
• On the quantumness of multiparameter estimation problems for qubit systems
• Quantum spatial search in two-dimensional waveguide arrays
• Quantum-classical dynamical distance and quantumness of quantum walks
• What do QAOA energies reveal about graphs?
• Efficient implementation of discrete-time quantum walks on quantum computers
• Decoherence enhances performance of quantum walks applied to graph isomorphism testing
• Experimental Control of the Degree of Non-Classicality via Quantum Coherence
• The super-Virasoro singular vectors and Jack superpolynomials relationship revisited
• Continuous-time quantum walks in the presence of a quadratic perturbation
• An Enhanced Photonic Quantum Finite Automaton
• Optimizing Quantum Walk Search on a Reduced Uniform Complete Multi-Partite Graph
• Simon's Period Finding on a Quantum Annealer
• Perturbed graphs achieve unit transport efficiency without environmental noise