Pacific Institute for the Mathematical Sciences - PIMS

Uncertainty, encryption and low-distortion embeddings

Abstract:

Where should one look to find bases satisfying strong
uncertainty relations? Position and momentum lead the way: it's hard to
do better than any orthonormal basis and its Fourier transform. The
natural generalization to so-called mutually unbiased bases, however,
leaves a bit to be desired when it comes to uncertainty relations.
Reframing the search in terms of low-distortion embeddings instead leads
to bases satisfying much stronger uncertainty relations than had
previously been known, plus a wealth of applications. I'll explain, for
example, how to encrypt an n-bit message using a constant-sized secret
key and how to perform equality testing of quantum states using a a
constant amount of quantum communication. Based on joint work with Omar
Fawzi and Pranab Sen. arXiv:1010.3007.