A quantum-walk-inspired adiabatic algorithm for graph isomorphism
arXiv:1401.1278 · doi:10.1088/1751-8113/47/32/325302
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.
arXiv comment10 pages, 5 figures
References in corpus (19)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum random walks - an introductory overview
- Exponential algorithmic speedup by quantum walk
- An example of the difference between quantum and classical random walks
- Bounds for the adiabatic approximation with applications to quantum computation
- Quantum algorithms for algebraic problems
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Anderson localization casts clouds over adiabatic quantum optimization
- Two-particle quantum walks applied to the graph isomorphism problem
- Localization and its consequences for quantum walk algorithms and quantum communication
- The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
- Isotropic Markov semigroups on ultra-metric spaces
- Dissipative ground-state preparation of a spin chain by a structured environment
- A Quantum Computer Architecture using Nonlocal Interactions
- Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs
- Solving the Graph Isomorphism Problem with a Quantum Annealer
- Non-local updates for quantum Monte Carlo simulations
- High-Performance Physics Simulations Using Multi-Core CPUs and GPGPUs in a Volunteer Computing Context
- Scalable universal holonomic quantum computation realized with an adiabatic quantum data bus and potential implementation using superconducting flux qubits
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