×

A graph isomorphism algorithm using signatures computed via quantum walk search model. (English) Zbl 1309.05187

Summary: In this paper, we propose a new algorithm based on a quantum walk search model to distinguish strongly similar graphs. Our algorithm computes a signature for each graph via the quantum walk search model and uses signatures to distinguish non-isomorphic graphs. Our method is less complex than those of previous works. In addition, our algorithm can be extended by raising the signature levels. The higher the level adopted, the stronger the distinguishing ability and the higher the complexity of the algorithm. Our algorithm was tested with standard benchmarks from four databases. We note that the weakest signature at level 1 can distinguish all similar graphs, with a time complexity of \(O({N}^{3.5}),\) which that outperforms the previous best work except when it comes to strongly regular graphs (SRGs). Once the signature is raised to level 3, all SRGs tested can be distinguished successfully. In this case, the time complexity is \(O({N}^{5.5})\), also better than the previous best work.

MSC:

05E30 Association schemes, strongly regular graphs
15A18 Eigenvalues, singular values, and eigenvectors
37A35 Entropy and other invariants, isomorphism, classification in ergodic theory
60G50 Sums of independent random variables; random walks
81R50 Quantum groups and related algebraic methods applied to problems in quantum theory
17B37 Quantum groups (quantized enveloping algebras) and related deformations
PDFBibTeX XMLCite
Full Text: DOI