Title:Search via Quantum Walks
Speaker: Ashwin Nayak University of Waterloo, and Perimeter Institute for Theoretical Physics
Time: 2006-03-21 14:30-2006-03-21 14:30


Randomization of quantum states is the quantum analogue of the classical one-time pad. We present an improved, efficient construction of an approximately randomizing map that uses O( d /epsilon^2) Pauli operators to map any d-dimensional state to a state that is within epsilon (in trace distance) of the completely mixed state. Our bound is a log d factor smaller than that of Hayden, Leung, Shor, and Winter (2004), and Ambainis and Smith (2004).
Then, we show that a random sequence of essentially the same number of unitaries (chosen from an appropriate set) approximately randomize d-dimensional with high probability. Finally, we will discuss the optimality of these schemes via connections to different notions of pseudorandomness.
This is joint work with Paul Dickinson (University of Waterloo).

Short Bio: