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.

A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems / D. Tamascelli, L. Zanetti. - In: JOURNAL OF PHYSICS. A, MATHEMATICAL AND THEORETICAL. - ISSN 1751-8113. - 47:32(2014 Aug 15), pp. 325302.1-325302.15.

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

D. Tamascelli
Primo
;
2014

Abstract

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.
adiabatic quantum computation; graph isomorphism; quantum walk
Settore INF/01 - Informatica
15-ago-2014
Article (author)
File in questo prodotto:
File Dimensione Formato  
1751-8121_47_32_325302.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 451.74 kB
Formato Adobe PDF
451.74 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/258034
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 22
social impact