I’m delighted to announce that Aram Harrow will be joining us at UW as a visiting professor for the coming academic year. Aram is one of the young leaders in quantum information and computation. During a recent visit, Aram started to explain to me how ideas from asymptotic geometric analysis have started to become important in quantum information.
The capacity of quantum channels
A mixed quantum state on is represented by a density matrix , which is Hermitian, positive semi-definite matrix with . The von Neumann entropy of is given by
If is the space of matrices with complex entries, then a quantum channel is a mapping
for some , which sends PSD matrices to PSD matrices and preserves the trace. Finally, the minimal output entropy of a quantum channel is
where ranges over all mixed states on . Since the entropy is a concave function, this minimum is achieved at a pure state.
Work of Shor showed that the following conjecture is equivalent to a number of long-standing problems in quantum information theory.
Additivity conjecture for minimal output von Neumann entropy: Is is true that, for every two quantum channels and , we have:
Observe that we always have above, by considering the product state where and are minimizers for and , respectively. The conjecture is about whether we can get a smaller output entropy by entangling the the inputs to .
Hastings’ counterexample and Dvoretzky’s theorem
Hastings proved that the conjecture is false: By appropriately choosing randomly constructed quantum channels, it is possible to achieve
Remarkably, it has recently been shown by Aubrun, Szarek, and Werner that this counterexample follows from an appropriate version of Dvoretzky’s theorem on almost-Euclidean subspaces of normed spaces (for a refresher, see this earlier post on pseudorandom subspaces).
Let be the space of matrices with complex entries. We will consider two norms on matrices : The Hilbert-Schmidt norm , and the Schatten -norm , where . This latter quantity is precisely the norm of the singular values of . Dvoretzky’s theorem tells us (qualitatively) that an appropriate random subspace of the normed space will be nearly Euclidean.
More precisely, for every , a uniformly random subspace of dimension will, with high probability, satisfy: For every ,
i.e. it will be -Euclidean. This strong quantitative version follows along the lines of enhancements to Milman’s proof of Dvoretzky’s theorem.
Oscillations and chaining
The proof of the preceding quantitative bound is based on a version of Dvoretzky’s theorem for Lipschitz functions, which I will state here in the real case for simplicity. We will use for the -dimensional unit sphere, and then for a function and a subset , we write
where is the average value of on .
Theorem 1 If is a 1-Lipschitz function, then for every , if is a random subspace of dimension , then with high probability,
A standard way to prove this lemma would be to use the fact that every -Lipschitz function is highly concentrated on (Levy’s lemma) and then to take a union bound over an -net on whose size is bounded by . Unfortunately, this leads to an extra term on the right-hand side of (1) which, remarkably, would lead to a version of Dvoretzky’s theorem that is too weak to imply Hastings’ counterexample to the additivity conjecture.
Gordon originally proved Theorem 1 using comparison results for Gaussian processes. (In fact, we will see a main technical step called Slepian’s Lemma in our next post on majorizing measures.) Alternately, Schechtman showed that one can use concentration of measure and a more sophisticated chaining argument, of the type discussed in our previous post.