07 December 2015
Daniel Spielman of Yale University, together with postdoc Adam Marcus, now at Princeton University, and his graduate student Nikhil Srivastava, now at the University of California, Berkeley, have succeeded in solving the famous Kadison-Singer problem. This problem is one of the paramount problems in C*-algebras and quantum physics that had remained unsolved for almost 50 years.
Over the past two years, the experts in the Kadison-Singer problem have had to work hard to assimilate the ideas of the proof, which was first released in 2013. But whilst mathematicians are still grappling with its intricacies, computer scientists have been quick to exploit the new techniques. Last year, for instance, two researchers made use of these new mathematical tools to enhance their understanding of the famously difficult traveling salesman problem.
The original question Richard Kadison and Isadore Singer posed in 1959 asks how much it is possible to learn about a “state” of a quantum system if you have complete information about that state in a special subsystem. Their question builds on Werner Heisenberg’s uncertainty principle, which says that certain pairs of attributes, like the position and the momentum of a particle, cannot simultaneously be measured to arbitrary precision.
Kadison and Singer — now at the University of Pennsylvania and the Massachusetts Institute of Technology (emeritus), respectively — posed their question at a moment when interest in the philosophical foundations of quantum mechanics was entering a renaissance. Although some physicists had begun to shun studying the mathematical foundations and implications of quantum theory, other more mathematically inclined physicists pounced on the Kadison-Singer problem, which they understood as a fundamental and profound question about C*-algebras.
In 1979, Joel Anderson, now an emeritus professor at Pennsylvania State University, popularized the problem by proving that it is equivalent to an easily stated question about when matrices can be broken down into simpler chunks. Suddenly, the Kadison-Singer problem became applicable almost everywhere from computer science to engineering to signal processing.
Another more recently-discovered equivalent formulation of the Kadison-Singer problem was made in 2005 by Nik Weaver, of Washington University in St. Louis. Weaver’s version distilled the problem down to a natural-sounding question about when it is possible to divide a collection of vectors into two groups that each point in roughly the same set of directions as the original collection.
See more here.