PIRSA:10010001

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

Coppersmith, S. (2010). Quantum random walks of interacting particles and the graph isomorphism problem.. Perimeter Institute. https://pirsa.org/10010001

Coppersmith, Susan. Quantum random walks of interacting particles and the graph isomorphism problem.. Perimeter Institute, Jan. 20, 2010, https://pirsa.org/10010001 

          @misc{ pirsa_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},
            year = {2010},
            month = {jan},
            note = {PIRSA:10010001 see, \url{https://pirsa.org}}
          }

Susan Coppersmith

University of Wisconsin–Madison

Talk number
PIRSA:10010001
Collection
Talk Type
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.