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.

**1. Introduction**

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

Theorem 1For each and , exists and is attained on — a cap with the correct measure (i.e., for any and such that , where ).

When — in which case is the half sphere — we get the following

Corollary 2If 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 3Let 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 4Note that the space of all subspaces of doesnotform 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 1Let , 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

Given an arbitrary quantum state we define the *quantum hamming distance* of to to be

We’ll have occasion to use the following

Lemma 5 (Operator Markov inequality)Let be a positive semidefinite operator and any density operator. Define

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.

Lemma 6Let , where and are two bounded positive semidefinite operators. Then

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

Proposition 7Let be a projection and let be a single-qubit density operator. Then

where

The proof of this proposition relies on the following seven lemmas.

Lemma 8Let be a projection. Then

*Proof:*

where we’ve used in the third line and the fact that in the fifth line. ◻

Definition 9Let be a projection and let be a single-qubit state. We define to be a projection on which has the largest dimension so that

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 10Let 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. ◻

Lemma 11Let be a projection and let be a single-qubit state. We have that

*Proof:* Consider

◻

In the next lemma we prove a crucial structure result concerning joins of locally displaced subspaces.

Lemma 12Let be a projection, and be as in Definition 9. Then

*Proof:* First, thanks to Lemma 6, we have that if

then

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 13Let 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:

◻

Lemma 14Let be a projection. Then

*Proof:* We use Lemma 8 and Lemma 13:

◻

Lemma 15Let be a projection and let be a single-qubit state. We have that

and

*Proof:* The proof follows straightforwardly from Lemma 19 and Lemma 14 ◻

We need one final lemma before proving the proposition; this lemma appears in Talagrand’s big paper:

Lemma 16Consider a measurable function on a measure space . Assume . Then we have

*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

and

Thus

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 . ◻

Corollary 17Let be a subspace. Then

*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

Choosing yields

which, upon rearranging, gives the desired result. ◻

**Discussion**

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…

Looks very interesting. Do you have any draft on this result other than this post?

Thanks,

Tasos

Dear Tasos Zouzias,

Many thanks for your interest!

Unfortunately the post this is the only draft available of this result at the current time. I’ll let you know if/when I come to write it up for publication.

Best wishes!

Sincerely,

Tobias