k-Boson Quantum Walks Do Not Distinguish Arbitrary Graphs
By Jamie Smith. 2010
11 citations recorded by the source corpus.
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].
Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics, Computational Theory and Mathematics, Quantum Computing, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Atomic and Molecular Physics, and Optics
In Computational Theory and Mathematics
In Quantum Computing
In Algorithms & Complexity
Citations in the corpus
- The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, methodology): “In relating these results to general k-equivalent graphs, we note that not much is known regarding possible general properties of such graphs, as the known cases were, as mentioned, introduced as token counterexamples, and with the exception of the work of [9, 31] the properties of k-equivalent grap”