k-Boson Quantum Walks Do Not Distinguish Arbitrary Graphs

Abstract

In this paper, we define k-equivalence, a relation on graphs that relies on their associated cellular algebras. We show that a k-Boson quantum walk cannot distinguish pairs of graphs that are k- equivalent. The existence of pairs of k-equivalent graphs has been shown by Ponomarenko et al. [2, 6]. This gives a negative answer to a question posed by Gamble et al. [7].

5 pages

Cited by in corpus (2)

• The Weisfeiler-Lehman Method and Graph Isomorphism Testing
• Quantum Walks on Regular Graphs and Eigenvalues