Pranab Sen, Tata Institute of Fundamental Research
Consider the n-dimensional vector space over complex numbers. The usual norm that one puts on it is the Euclidean or l_2 norm. However, one can consider other norms on this space, for example, the l_1 norm.
A fundamental theorem by Dvoretzky states that for any norm on the n-dimensional space, there exists a subspace of suitably large dimension wherein the norm approximately looks like a scaled version of the l_2 norm. Another way of stating Dvoretzky's theorem is that any centrally symmetric convex body contains a suitably large section
that looks almost spherical. The subject of norm embeddings is to find suitably high dimensional almost Euclidean subspaces of normed spaces.
By quantising a classical l_2 to l_1 norm embedding algorithm of Indyk, we come up with a small set of unitary transformations such that for any pure state in n-dimensional space, its image under most of these unitaries is almost a flat superposition, that is, has l_1 norm close to sqrt{n}. These unitaries are explicit in the sense that given its index, the unitary can be implemented using polylog(n) gates. This small set of unitaries can be thought of as an explicit uncertainty relation, since for any quantum state, applying a typical unitary from this set and measuring it gives an almost uniform probability distribution.
Such an uncertainty relation with a small set of unitaries has several applications to quantum information. The most important application is that we get the first known efficient algorithm for locking classical information in a quantum state using a very small classical key. In other words, we can efficiently encode k classical bits into 2k qubits with O(log k) classical bits of key such that any party that can measure only the encoded quantum message learns almost nothing about the original classical message from the measurement result, but a party that has access to the encoded quantum message as well as the classical key can recover the original classical message exactly.
This is joint work with Omar Fawzi and Patrick Hayden.