Investigation Fermionic Quantum Walk for Detecting Nonisomorph Cospectral Graphs

摘要

The graph isomorphism (GI) is investigated in some cospectral networks. Two graphs are isomorphic when they are related to each other by a relabeling of the graph vertices. The GI in two scalable (n+2)-regular graphs G4(n; n+2) and G5(n; n+2), is studied analytically by using the multiparticle quantum walk. These two graphs are a pair of non-isomorphic connected cospectral regular graphs for any positive integer n. In order to investigation GI in these two graphs, the adjacency matrices of graphs have been rewritten in the antisymmetric fermionic basis. These fermionic basis are in a form that the adjacency matrices in these basis will be 8×8 for all amounts of n. Then it is shown that the multiparticle quantum walk is able to distinguish pairs of non-isomorph graphs. Rewriting the adjacency matrices of graphs in these basis reduces the complexity of calculations. Also we construct two new graphs T4(n; n + 2) and T5(n; n + 2) and repeat the same process of G4 and G5 to study the GI problem by using multiparticle quantum walk. Finally the GI has been discussed in some examples of cospectral graphs.