We present a quantum algorithm for solving graph isomorphism problems that is based on an adiabatic protocol. We use a collection of continuous time quantum walks, each one generated by an XY Hamiltonian, to visit the configuration space. In this way we avoid a diffusion over all the possible configurations and significantly reduce the dimensionality of the accessible Hilbert space. Within this restricted space, the graph isomorphism problem can be translated into searching for a satisfying assignment to a 2-SAT (satisfiable) formula and mapped onto a 2-local Hamiltonian without resorting to perturbation gadgets or projective techniques. We present an analysis of the time for execution of the algorithm on small graph isomorphism problem instances and discuss the issue of an implementation of the proposed adiabatic scheme on current quantum computing hardware.
|Titolo:||A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems|
TAMASCELLI, DARIO (Primo)
|Parole Chiave:||adiabatic quantum computation; graph isomorphism; quantum walk|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||15-ago-2014|
|Digital Object Identifier (DOI):||10.1088/1751-8113/47/32/325302|
|Appare nelle tipologie:||01 - Articolo su periodico|