Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Fearful Symmetries: Quantum Computing, Factoring, and Graph Isomorphism

Cristopher Moore

Published Jan 1, 2005• 0 citations
Publisher
DOI
10.1007/11561071_3

Related papers

Theoretical issues in quantum computing: Graph isomorphism, PageRank, and Hamiltonian determination

Kenneth Rudinger

•Jan 1, 2014•0 citations

A proposal for an efficient quantum algorithm solving the graph isomorphism problem

P. W. Mills, R. P. Rundle, V. M. Dwyer +4 more

•Nov 27, 2017•1 citation

Quantum Random Walks and the Graph Isomorphism Problem

Kenneth Rudinger, John King Gamble, M. Wellons +4 more

Bulletin of the American Physical Society•Feb 29, 2012•0 citations

Quantum search algorithm for graph isomorphism problem

A. E. Kirichkov

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jan 1, 2008•0 citations

Distributed Graph Isomorphism using Quantum Walks

Jayaprabha Yadav

International Journal on Recent and Innovation Trends in Computing and Communication•Jan 1, 2015•0 citations

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

Kai Liu, Yi Zhang, Kai Lü +3 more

Graph isomorphism is to determine whether two graphs have the same topological structure. It plays a significant role in areas of image matching, biochemistry, and information retrieval. Quantum walk, as a novel quantum computation model, has been employed to isomorphic mapping detection to optimize the time complexity compared with a classical computation model. However, these quantum-inspired algorithms do not perform well-and even cease to work-for graphs with inherent symmetry, such as regular graphs. By analyzing the impacts of graphs symmetry on isomorphism detection, we proposed an effective graph isomorphism algorithm (MapEff) based on the discrete-time quantum walk (DTQW) to improve the accuracy of isomorphic mapping detection, especially for regular graphs. With the help of auxiliary edges, this algorithm can distinguish the symmetric nodes efficiently and, thus, deduct the qualified isomorphic mapping by rounds of selections. The experiments tested on 1585 pairs of graphs demonstrated that our algorithm has a better performance compared with other state-of-the-art algorithms.

Entropy•Jun 5, 2019•6 citations
Graph isomorphism is to determine whether two graphs have the same topological structure. It plays a significant role in areas of image matching, biochemistry, and information retrieval. Quantum walk, as a novel quantum computation model, has been employed to isomorphic mapping detection to optimize the time complexity compared with a classical computation model. However, these quantum-inspired algorithms do not perform well-and even cease to work-for graphs with inherent symmetry, such as regular graphs. By analyzing the impacts of graphs symmetry on isomorphism detection, we proposed an effective graph isomorphism algorithm (MapEff) based on the discrete-time quantum walk (DTQW) to improve the accuracy of isomorphic mapping detection, especially for regular graphs. With the help of auxiliary edges, this algorithm can distinguish the symmetric nodes efficiently and, thus, deduct the qualified isomorphic mapping by rounds of selections. The experiments tested on 1585 pairs of graphs demonstrated that our algorithm has a better performance compared with other state-of-the-art algorithms.