Events at Physics

<< Fall 2011 Spring 2012 Summer 2012 >>
Subscribe your calendar or receive email announcements of events
Condensed Matter Theory Group Seminar
Multiparticle Quantum Walks and the Graph Isomorphism Problem
Date: Monday, April 16th
Time: 4:30 pm
Place: 5310 Chamberlin
Speaker: Kenny Rudinger, UW-Madison
Abstract: We investigate the quantum dynamics of particles on graphs ("quantum walk"), with the aim of developing quantum algorithms for determining whether or not two graphs are isomorphic. We investigate such walks on strongly regular graphs (SRGs), a class of graphs with high symmetry. We explore the effects of particle number and interaction range on a walk's ability to distinguish non-isomorphic graphs. We numerically find that both non-interacting three-boson and three-fermion continuous time walks have the same distinguishing power on a dataset of 70,712 pairs of SRGs, each distinguishing over 99.6% of the pairs. We also find that increasing to four non-interacting particles further increases distinguishing power on this dataset. While increasing particle number increases distinguishing power, we prove that any walk of a fixed number of non-interacting particles cannot distinguish all SRGs.
Add this event to your calendar