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

Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other compatible player.

Recording Details

PIRSA Number: 


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.