Search via Quantum Walks

演讲人: Ashwin Nayak University of Waterloo, and Perimeter Institute for Theoretical Physics
时间: 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).