Symmetry in quantum walks
arXiv:0711.1694
Abstract
A discrete-time quantum walk on a graph is the repeated application of a unitary evolution operator to a Hilbert space corresponding to the graph. Hitting times for discrete quantum walks on graphs give an average time before the walk reaches an ending condition. We derive an expression for hitting time using superoperators, and numerically evaluate it for the walk on the hypercube for various coins and decoherence models. We show that, by contrast to classical walks, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition for their existence. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Symmetries of a graph, given by its automorphism group, can be inherited by the evolution operator. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. Symmetry can also cause the walk to be confined to a subspace of the original Hilbert space for certain initial states. 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 and we give an explicit construction of the quotient graph. We conjecture that the existence of a small quotient graph with finite hitting times is necessary for a walk to exhibit a quantum speed-up. Finally, we use symmetry and the theory of decoherence-free subspaces to determine when the subspace of the quotient graph is a decoherence-free subspace of the dynamics.
136 pages, Ph.D. thesis, University of Southern California, 2007
References in corpus (14)
- A Quantum Random Walk Search Algorithm
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Controlling discrete quantum walks: coins and intitial states
- The quantum to classical transition for random walks
- Quantum Walks driven by many coins
- Connecting the discrete and continuous-time quantum walks
- Quantum random walks with decoherent coins
- Quantum Random Walks Hit Exponentially Faster
- Quantum walks on quotient graphs
- Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups
- Analysis of Absorbing Times of Quantum Walks
- Decoherence, Control, and Symmetry in Quantum Computers
- Quantum walks on directed graphs