PIRSA:10010001

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

APA

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

MLA

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

BibTex

          @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}}
          }
          

Susan Coppersmith University of Wisconsin–Madison

Talk numberPIRSA:10010001
Source RepositoryPIRSA
Collection
Talk Type Scientific Series

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.