MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk

Area of Science:

• Computer Science
• Quantum Computing
• Graph Theory

Background:

• Graph isomorphism is crucial for pattern recognition in various fields.
• Quantum walks offer potential for faster graph isomorphism detection.
• Existing quantum-inspired methods struggle with symmetric graphs.

Purpose of the Study:

• To develop an effective graph isomorphism algorithm addressing limitations with symmetric graphs.
• To enhance the accuracy of isomorphic mapping detection using quantum walks.
• To propose a novel algorithm, MapEff, for improved graph isomorphism detection.

Main Methods:

• Utilized discrete-time quantum walk (DTQW) as the core computation model.
• Introduced auxiliary edges to efficiently distinguish symmetric nodes in graphs.
• Developed a round-based selection process for identifying qualified isomorphic mappings.

Main Results:

• The proposed MapEff algorithm demonstrates improved accuracy in isomorphic mapping detection.
• MapEff shows superior performance, particularly for regular graphs with inherent symmetry.
• Experimental results on 1585 graph pairs confirm MapEff's effectiveness against state-of-the-art algorithms.

Conclusions:

• MapEff effectively overcomes the challenges posed by graph symmetry in isomorphism detection.
• The algorithm offers a more robust and accurate solution for graph isomorphism problems.
• This work advances the application of quantum walks in computational graph theory.