Quantum Computation and Information Seminar 

07/02/2006, 15:00 — 16:00 — Room P4.35, Mathematics Building
Ashwin Nayak, U Waterloo & Perimeter Institute

Approximate Encryption of Quantum States

Randomization of quantum states is the quantum analogue of the classical one-time pad. Hayden, Leung, Shor, and Winter (2004) showed that for randomizing an arbitrary $d$-dimensional quantum state to a state close to the completely mixed state, a set of $O(d\hspace{0.5em}\log d/{ϵ}^2)$ unitary operations suffice. This relaxed scheme cuts approximately by a factor of 2, the number of key bits required for perfect randomization. Soon after, Ambainis and Smith (2004) gave explicit constructions of such sets. We will present an improved efficient construction of an approximately randomizing map that uses $O(d/{ϵ}^2)$ Pauli operators. Then, we will show that a random set with $O((d/{ϵ}^2)\log (1/ϵ))$ unitaries chosen from a suitable set randomize $d$-dimensional states to within $ϵ$ in trace distance with high probability. This is joint work with Paul Dickinson.