Talagrand’s inequality places nontrivial bounds on the growth of the set of strings which are hamming distance away from some subset of strings. In these notes we formulate a quantum generalisation of Talagrand’s inequality which places bounds on the growth of the dimension of the subspace formed by taking the join of all subspaces which are different from in at most places.
The results in this post are joint work with Andreas Winter.
High- (and infinite-) dimensional spaces often have counterintuitive properties. One property of certain high-dimensional geometric spaces, which has received a great deal of attention over the years, is the concentration of measure phenomenon (see the books of Milman and Schechtman and Ledoux and Talagrand).
To explain concentration of measure I’ll use the classical example of the -dimensional sphere . There is a natural metric on given by the geodesic distance which measures the length of the shortest arc connecting and (which is always part of a great circle). Let be the uniform (haar) measure on . Suppose that is a measurable subset of with measure and denote by (i.e., the “fattening” of ). Now the isoperimetric inequality (see appendix I of Milman and Schechtman) says that
When — in which case is the half sphere — we get the following
Corollary 2 If with then .
Now, before I show you the proof — which is elementary(!), let’s work out what this is saying: for really high-dimensional spheres, if you start with a half sphere and add in all the points a distance then you end up with a subset that basically has the same volume as . That is, adding all the points a vanishingly small (in ) distance away from the equator captures all the volume. Thus we say that all the measure on is concentrated near the equator and that the poles don’t contribute very much at all. Weird. (Compare with the 3d picture below, where, obviously, lots of volume lives near the poles.)
Proof: Obviously, by theorem 1, we only need to evaluate . Now the volume of , the set of points on which are a distance from (an -dimensional sphere of radius ) is proportional to . As Milman and Schechtman say, you should draw a picture. Thus we learn that
Notice that the important quantity is . Now it’s relatively easy to get the desired answer: we need to use the inequality and a change of variables :
(I’ve skipped some elementary calculations here.) Note that and so
The concentration of measure phenomenon plays a major role in several fields, including, the asymptotic theory of finite-dimensional Banach spaces, Riemannian geometry, and quantum information theory. It is near ubiquitous in spaces with some kind of product structure: it holds for the -cube (which is homeorphic to ). Additionally, and this is the result we aim to generalise, it holds for the discrete -cube of all strings of zeros and ones with the hamming distance as the metric. This is the setting of Talagrand’s inequality which is proved in great generality and puissance in Talagrand’s big paper (see Alon and Spencer for a simple exposition of the basic inequality).
In these notes we generalise Talagrand’s inequality to the quantum setting where the role of a subset is played by a subspace and the role of the (product) measure is played by a product quantum state (density operator) .
2. The quantum hamming ball
We define to be the set .
Let be a hilbert space. If is a subspace of then we write for the corresponding projection onto ; where obvious, we’ll frequently use to refer to both the subspace and the projection .
Given any family of subspaces of , there is a greatest subspace that is contained in each and a smallest closed subspace, the join, that contains each . Specifically, is while is the subspace generated by . For each family of projections we write and for the projections onto the corresponding subspaces and , respectively. Finally, if is a positive semidefinite (hence, hermitian) operator we define the range of to be the subspace
Throughout these notes our hilbert space will be that of qudits: , although, we’ll mostly assume is 2 whenever the generalisation to higher is obvious.
To begin we need to define what is meant by the quantum hamming ball. We are going to define the quantum hamming ball in a fashion similar to the classical definition based on displacement operators. Thus, for any projection , we define the displacement operator:
We also define the th displacement operator via
Note that is not a linear operator.
It is relatively easy to establish the following lemma
Lemma 3 Let be a subspace. Then
Proof: The result follows upon noting that the hilbert space join operation, also known as the subspace sum operation, is associative: . ◻
Remark 4 Note that the space of all subspaces of does not form a lattice under the subspace join and intersection operations.
Using the displacement operator we are able to make sense of the subspace , the “fattening” of , which includes all quantum states which are exactly a distance away from :
which is equivalent to
where the second inequality follows because the two projections commute: . We also define .
Example 1 Let , then
We now come to the quantum hamming distance. To make sense of how far a quantum state is from a subspace we construct the following positive semidefinite operator
We’ll have occasion to use the following
where . Then
Proof: Notice that
and taking the trace of both sides against gives us
Before we move on to the next section we’ll prove a simple but useful lemma concerning the ranges of sums of positive semidefinite operators.
where , , and .
Proof: To prove this result we study the complement of . A vector is in if and only if . That is, if and only if . (Why? Consider that implies that . Applying to both sides gives the result.) Now suppose that is in . This means that , i.e., . This occurs if and only if is in both of and , i.e., . But this means that or, after taking complements, that . ◻
3. The quantum Talagrand inequality
In these notes we aim to prove the following
The proof of this proposition relies on the following seven lemmas.
where we’ve used in the third line and the fact that in the fifth line. ◻
where the inequality refers to the positive semidefinite ordering. We also define the projection on to be the range of the partial trace over the th qubit of :
Lemma 10 Let be a projection and let be a single-qubit state. We have that
Proof: We begin by observing that
From this operator inequality we obtain
which is the desired result. ◻
In the next lemma we prove a crucial structure result concerning joins of locally displaced subspaces.
Lemma 12 Let be a projection, and be as in Definition 9. Then
Proof: First, thanks to Lemma 6, we have that if
where . Thus we learn that is generated by linear combinations of vectors of the form , where is an arbitrary single-qubit state and is an eigenvector of for some .
Now, we’re going to show that . Suppose that is a vector in . It turns out that lies in : suppose that arises as an eigenvector (corresponding to a nonzero eigenvalue) of for in . Then
lies in the subspace for all . Now write the Schmidt decomposition of as
To show the desired inclusion we apply the projector and then the rotation to :
Because is a complete orthonormal basis we have that for some so that
so that lies in for all , and hence the subspace lies in . Since is generated by all vectors of this form, we have the desired inclusion.
The reverse inclusion is easy: applying to a any vector in and using the fact that , where lie in , and that gives us the desired result. ◻
Lemma 13 Let be a projection, and be defined as in Definition 9. Then
Proof: We prove this lemma by induction. We start with the base case
which may be shown as follows. Firstly, note that
Notice that this is in the form covered by the previous lemma, so that we have
as required. We can now complete the proof by demonstrating the inductive step:
We need one final lemma before proving the proposition; this lemma appears in Talagrand’s big paper:
Proof: [Proof of Proposition 7] We proceed by induction on (the base case follows from the preceeding lemma). Suppose the result has been proved for . We prove it for as follows. Let . By Lemma 15 we have that
where we’ve defined (implicitly) the discrete measure space , with and the measurable function
Applying Lemma 16 gives
To complete the proof we now show that . We begin by taking the logarithm of :
Next we differentiate to give
Now integrate this differential inequality with the initial condition to obtain
and hence . ◻
Proof: We use the operator Markov inequality Lemma 5, as applied to the positive semidefinite operator :
Taking the trace of both sides with respect to gives
Applying the quantum Talagrand inequality gives
which, upon rearranging, gives the desired result. ◻
The main result of this post is proposition 7, but the inequality that actually best mimics Talagrand’s inequality is corollary 17. Now, what people call Talagrand’s inequality isn’t actually either result! “Talagrand’s inequality” refers to a much more general result which applies not only to the hamming distance but to much more general distance measures. At the moment it is unclear (to me, at least) how to generalise the proof here to the case where the “quantum hamming distance” (7) is replaced with something more general…