CSI PhD Defense - Symmetry in Quantum Walks

SPEAKER: Mr. Hari Krovi, Communication Sciences InstituteABSTRACT: A quantum walk on a graph (analogue of a classical random walk) is an application of a unitary evolution operator on a Hilbert space which corresponds to the graph. Hitting time of a quantum walk is the average time it takes to go from a designated initial vertex to a designated final vertex. Symmetries of the graph, given by its automorphism group, can be inherited by the evolution operator. Symmetry can cause the hitting time for certain initial states of a quantum walk to be infinite, in contrast to a classical random walk. We give a sufficient condition for a quantum walk to have infinite hitting times. Using the irreducible representations of the automorphism group, we derive conditions under which quantum walks defined on graphs have infinite hitting times for some initial states. Another aspect of symmetry is fast hitting times. It has been shown in the literature that a quantum walk on some graphs such as the hypercube has an exponentially faster hitting time than a classical walk. We show that this is because the walk is confined to a subspace of the total Hilbert space due to symmetry inherited from the graph. We show that a quantum walk confined to the subspace corresponding to this symmetry group can be seen as a different quantum walk on a smaller "quotient" graph. The automorphisms of the quotient graph which are inherited from the original graph are the original automorphism group modulo the subgroup H used to construct it. Thus the quotient graph is constructed by removing the symmetries of the subgroup H from the original graph. Such a reduction to a smaller graph may be useful in algorithms based on quantum walks.Advisor: Prof. Todd Brun, tbrun@usc.edu

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 500

Audiences: Everyone Is Invited

Contact: Mayumi Thrasher