On the Limitations of Graph Invariants Inspired by Quantum Walks

详细信息    查看全文

• 作者：Jamie  ; Smith¹ ;   ; ^{ja5smith@iqc.ca}
• 关键词：Graph isomorphism problem ; quantum walks ; cellular algebras
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2011
• 出版时间：1 December 2011
• 年：2011
• 卷：38
• 期：Complete
• 页码：795-801
• 全文大小：191 K

文摘

We consider two graph invariants inspired by quantum walks¡ªone in continuous time [John King Gamble, Mark Friesen, Dong Zhou, Robert Joynt, and S. N. Coppersmith. Two-particle quantum walks applied to the graph isomorphism problem. Phys. Rev. A, (81), May 2010] and one in discrete time [David Emms, Edwin R Hancock, Simone Severini, and Richard C Wilson. A matrix representation of graphs and its spectrum as a graph invariant. , May 2005, Chris Godsil and Krystal Guo. Quantum walks on regular graphs and eigenvalues. , Nov 2010]. We will associate a matrix algebra called a cellular algebra with every graph. We show that, if the cellular algebras of two graphs have a similar structure, then they are not distinguished by either of the proposed invariants. This has implications for the strength of these proposed invariants in relation to other known invariants, and gives rise to several interesting open problems.