Quantum random walks of interacting particles and the graph isomorphism problem.

          @misc{ scivideos_PIRSA:10010001,
            doi = {10.48660/10010001},
            url = {https://pirsa.org/10010001},
            author = {Coppersmith, Susan},
            keywords = {},
            language = {en},
            title = {Quantum random walks of interacting particles and the graph isomorphism problem.},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2010},
            month = {jan},
            note = {PIRSA:10010001 see, \url{https://scivideos.org/index.php/pirsa/10010001}}
          }
          

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 investigations of quantum particles walking on graphs and their implications for possible algorithms for GI. We find that 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.