Most accounts of the Kadison-Singer problem mention that it arose from considerations in the foundations of quantum mechanics. Specifically, a question about “extensions of pure states.” See, for instance, Gil’s blog. But trying to reconcile this question with my (limited) knowledge of QM proved frustrating. There is also an intuitive explanation posted at soulphysics, along with mathematical notes. But I couldn’t figure that one out either, because it only deals with “normal” quantum states (those corresponding to countably additive measures; see below). I think the KS problem for normal states is trivial. For the meat of KS, one has to think not only about infinite-dimensional spaces, but about “pathological” (non-constructible) measures. In particular, one has to think about “quantum states” that don’t have density matrices.
What follows are my notes on the matter, all of which are either well-known or wrong. Skip to the end for the very simple formulation with no mention of quantum states. Even better advice is to just Read Nick Harvey’s survey.
How I understand quantum measurement
A (mixed) quantum state 
A pure state is given by a density matrix of the form 
Quantum logic
There is another way to think about quantum measurement. Let 
![{[0,1]}](https://s0.wp.com/latex.php?latex=%7B%5B0%2C1%5D%7D+&bg=FFFFFF&fg=000000&s=0 "{[0,1]}")
Note that we have allowed here the possibility that 
Theorem 1 Let
, we have
.
In other words, every
Restricted purity
Note that a measure on projections corresponds to a pure state if and only if it cannot be written as a non-trivial convex combination of measures on projections. In this way, we can also define purity with respect to a restricted family of projections.
Consider, for example, the Hilbert space 
But when 
Kadison-Singer Problem: Is it the case that every pure, finitely-additive
The answer is clearly positive for
In their original work, Kadison and Singer showed that the answer is false if one constructs the MASA using the continuous Hilbert space ![{L^2([0,1])}](https://s0.wp.com/latex.php?latex=%7BL%5E2%28%5B0%2C1%5D%29%7D+&bg=FFFFFF&fg=000000&s=0 "{L^2([0,1])}")
![{S \subseteq [0,1]}](https://s0.wp.com/latex.php?latex=%7BS+%5Csubseteq+%5B0%2C1%5D%7D+&bg=FFFFFF&fg=000000&s=0 "{S \subseteq [0,1]}")
Note that states corresponding to finitely additive (but not
A 
In the above setting, we said there are finitely-additive pure 
Indeed, for every partition 
Take the Hilbert space 
![{\mu : \mathcal S \rightarrow [0,1]}](https://s0.wp.com/latex.php?latex=%7B%5Cmu+%3A+%5Cmathcal+S+%5Crightarrow+%5B0%2C1%5D%7D+&bg=FFFFFF&fg=000000&s=0 "{\mu : \mathcal S \rightarrow [0,1]}")
Now let 
Kadison-Singer problem: Can every finitely-additive pure measure on
Note that the real question is about uniqueness of the extension. There always exists a pure extension; see the comments.
such that for any 
, the following holds? Let 
be a collection of 
orthonormal bases and define 
. Then there are subsets 
with 
and 
.
vectors cannot possibly “fill” 
points for this.
on 
for all subsets 
with 
. Here, 
denotes all the nodes that are in 
to 
for some orthonormal bases 
such that the endpoints of every edge are mapped at most 
apart (as 
).]
is the uniform measure on 
, then any two sets of 
measure are at distance 
by concentration of measure. Thus it is impossible to find 
in Theorem 1 of the 
factor, or even an optimal bound of 
.
and let 
-dimensional sphere 
. For the purpose of this question, one can assume that 
,
, a collection of (measurable) subsets 
such that 
for each 
, and such that for 
, we have
and 
. In 
somewhat, though the best-known is still 
for some 
.
? One could even hope for 
.
. In the first case, one can easily achieve 
(in fact, one could even get 
sets satisfying these bounds). In the second case, taking each set to contain a single basis vector achieves 
and 
.
sets instead of 
sets, then it is indeed possible to achieve 
. [Update: This is actually impossible for the reasons stated above. To get the corresponding bounds, we do a random projection into 
dimensions. This only preserves the original Euclidean distances on average.] Furthermore, for 
is a connected, 
-vertex, 
-regular graph. Define the Laplacian by 
, where 
is the adjacency matrix of 
. We will think of 
as acting on 
, the space of functions 
equipped with the 
by
, we define the expansion of 
, where 
is the indicator function of 
, we define the 
.
which are disjoint and non-empty and which satisfy 
. Then certainly 
is a 
satisfies 
because if 
, then
and 
, then
witnesses the fact that 
.
, there is a subset 
such that
. Observe that for each 
, one has 
. For 
denote the edges of 
thus
. 
such that 
for each 
denote 
for each 
via
. (Since 
, the function 
takes value 
everywhere, hence 
is never zero and this is well-defined.)
and 
, there exist 
satisfying the conditions:
, and
and 
, then
. 
by
, we have 
is identically 
on 
, we have 
are disjointly supported. This immediately implies that the 
are disjointly supported. If 
for some 
and 
such that 
and 
. But then by the triangle inequality, 
, violating condition (ii).
. For any 
, we have
in 
, there are subsets 
which satisfy:
.
and 
, then 
,
. 
by taking disjoint unions of the sets 
. Begin with the family 
and repeatedly replace two sets 
and 
by their union if they each satisfy 
.![{\sum_{v \in T} \|F(v)\|^2 \in [\frac12, 1+\frac{1}{2k}]}](https://s0.wp.com/latex.php?latex=%7B%5Csum_%7Bv+%5Cin+T%7D+%5C%7CF%28v%29%5C%7C%5E2+%5Cin+%5B%5Cfrac12%2C+1%2B%5Cfrac%7B1%7D%7B2k%7D%5D%7D+&bg=FFFFFF&fg=000000&s=0 "{\sum_{v \in T} \|F(v)\|^2 \in [\frac12, 1+\frac{1}{2k}]}")
, and possibly one set for which 
. By (i), we must end with at least 
. 
are orthornormal in 
. Then there is an 
.
,
matrix 
. For any 
, we have 
of the unit sphere in 
, we put 
. Fix some 
and let 
denote the diameter of 
, then by 
, then 
be a partition of 
. For any such square 
, we let 
denote the set of points which are at Euclidean distance at least 
from every side of 
. Observe that 
. Since 
, 
. Furthermore, by construction, for any 
and 
with 
, we have
. If we choose a uniformly random axis-parallel translation 
of the partition 
and define the value
are i.i.d. random 
. This looks somewhat similar to the corresponding value
are i.i.d. standard normal random variables. But while 
can be characterized (up to universal constant factors) by the Fernique-Talagrand 
. One stark difference between the two cases is that 
whenever 
such that for every 
such that
and 
, equations 
has property (T). See Section 4.2 of the book of 
, one can consider the family of graphs 
, where 
contains edges from every 
to each of
and 
.
with vertex set 
and edges
to represent the transpose of a matrix 
).
has positive Cheeger constant, then 
is a family of expander graphs. 
such that every finite subset 
has at least 
edges with exactly one endpoint in 
.
where 
and 
and let 
be the corresponding edge set. We will prove that 
has positive Cheeger constant.
, we have 
. 
. This is the first quadrant, without the 
-axis and the origin. Define 
similarly by rotating 
by 
, 
, and 
degrees, respectively, and note that we have a partition 
.
. We will show that 
. Since our graph is invariant under rotations of the plane by 
, this will imply our goal:
. Furthermore, we have 
because 
and 
In particular, this yields 
for any 
. An elementary analysis yields the following characterization.
, it holds that 
. 
then 
or infinite order (the other possibilities) and 
then the graphs are expanders.
be the reflection across the line 
where 
. We can characterize expansion of these graphs as well.
is an expander family if and only if 
. 
. The edges are given by two maps 
and 
. So the edges are 
and 
. Clearly 
is not adjacent to anything. Except for the origin, this graph is an expander in the following sense.
denotes the edges leaving 
represent the four quadrants of 
then 
. Similarly, 
and 
and 
, while all the respective pairs 
and 
and 
are disjoint.
is at least
. The preceding argument shows 
. We will show that 
. Averaging these two inequalities with weights 
and 
completes the proof.
, and 
. Then we have the bounds: 
is connected to exactly two elements of 
, and each element of 
is connected to 
and 
, while 
.
is connected to two unique points of 
, e.g. 
and 
. The final inequality follows from the fact that 
from our first argument (since 
does not touch the axes), and because 
with vertex set 
, where 
. There are four types of edges in 
: A vertex 
is connected to the vertices
,
is the second-smallest eigenvalue of the Laplacian on 
. 
now have torsion, and thus our expansion result for 
be the 2-dimensional torus equipped with the Lebesgue measure, and consider the complex Hilbert space
.
\ 
such that 
. Define its continuous extension 
as follows: Under the natural embedding of 
into 
, every point 
sits inside a grid square with four corners 
. Writing a local convex combination 
, we define
. It is also easy to verify that 
for some 
, we still get a contribution from 
to 
on this square because we are taking a weighted average.)
in 
‘s square to the corners of 
‘s square. A similar fact holds for 
. In fact, this is the only place where we need to use the fact that edges of the form 
and 
are present in 
to 
can be charged against a term in 
, and similarly for 
. We will use the Fourier transform to “remove the torsion.” The point is that 
and we define 
by 
, then 
forms an orthonormal Hilbert basis for 
. In particular, every 
can be written uniquely as
. The Fourier transform is defined as a map 
, where 
. In particular, 
is a linear isometry.
and 
. Then for any 
, we have
and 
. The final thing to note is that 
. So now if we simply apply the Fourier transform (a linear isometry) to the expression in 
is precisely
by 
in 
.
the Laplacian on 
.
is the minimal expansion of any set not containing the origin. Thus we have indeed unwrapped the torsion and returned to our initial question. Lemma 
, yielding the desired lower bound on 
