| Abstract: | The graph isomorphism (GI) problem plays a central role in the theory of computational complexity and has importance in physics and chemistry as well. While no general efficient algorithm for solving GI is known, it is unlikely to be NP-complete; in this regard it is similar to the factoring problem, for which Shor has developed an efficient quantum algorithm.
In this talk I will discuss our attempts to understand how the quantum physics of interacting systems can be exploited to develop new approaches towards the development of algorithms for GI, in particular by investigating the behavior of quantum walks of multiple particles. We find that particle interactions give rise to algorithms using single-particle quantum random walks fail to distinguish some nonequivalent graphs that can be distinguished by random walks with two interacting particles. The implications of these observations for classical and quantum algorithms for GI will be discussed. |
