Title: Symmetry in quantum walks
Speaker: Hari Krovi
Date: Wednesday, October 10, 2007 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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 walk to have infinite hitting times. Using the irreducible representations of the automorphism group, we derive conditions under which quantum walks defined on this graph 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.