I gathered a few of the comments made by participants of my lecture “Why quantum computers cannot work and how”, and a few of my answers. Here they are along with some of the lecture’s slides. Here is the link for the full presentation.
Last Friday, I gave a lecture at the quantum information seminar at MIT entitled “Why quantum computers cannot work and how.” It was a nice event with lovely participation during the talk, and a continued discussion after it. Many very interesting and useful remarks were made. Here are the slides. (The abstract can be found on this page.)
Aram is so nice that had it been up to me I would certainly make quantum computers possible :) (But this is not up to us and all we can do is to try to explore if QC are possible or not.)
We talked about quite a few topics starting with various exotic models of noise that treat differently classic and quantum information, the relevance of locally correctable codes and their quantum counterparts, the sum of Squares/Lasserre hierarchy, unique games and hypercontractivity, my smoothed Lindblad evolutions , NMR and spin-echo, quantum annealing and stoquasicity, and works by Mossbüer, Rekha Thomas, and Monique Laurent were mentioned.
I just returned yesterday night from Yale after a very fruitful visit. Here is a picture of a snowcar decorated with car mirrors from the great blizzard.
Michael Ben Or told me about the following great paper Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf. The paper solves an old conjecture of Yannakakis about projections of polytopes.
From the abstract: “We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.”
There are many interesting aspects to this story. The starting point was a series of papers in the 80s trying to prove that P=NP by solving TSP using linear programming. The idea was to present the TSP polytope as a projection of a larger dimensional polytope described by polynomially many linear inequalities, and solve the LP problem on that larger polytope. Yannakakis proved that such attempts are doomed to fail, when the larger LP problem keep the symmetry of the original TSP polytope.
Yannakakis asked if the symmetry condition can be removed and this is what the new paper shows. This is a very interesting result also from the point of view of convex polytope theory.
Another exciting aspect of the paper is the use of methods from quantum communication complexity.
Update: See this post over GLL for discussion and a description of a follow up paper.
Elementary school reunion: Usually, I don’t write about personal matters over the blog, but having (a few weeks ago) an elementary school reunion after 42 years was a moving and exciting event as to consider making an exception. For now, here is a picture:
Jirka’s Miraculous year
It looks like a lot is happening. From time to time I think that I should tell on my blog about exciting new things I hear about, but this is quite a difficult task. Perhaps I should at least post updates about progress on problems I discussed earlier, but even this is not easy. Jirka Matousek wrote a paper entitled The dawn of an algebraic era in discrete geometry? The paper starts as follows:
To me, 2010 looks as annus mirabilis, a miraculous year, in several areas of my mathematical interests. Below I list seven highlights and breakthroughs, mostly in discrete geometry, hoping to share some of my wonder and pleasure with the readers.
The paper lists seven startling new results. A few of these results were discussed here, a few others I have planned to discuss later, and yet a few others (like the recent solution by June Huh of the famous unimodularity conjecture for the coefficients of chromatic polynomials of graphs) caught me by a complete surprise. (Here is a link to a follow up paper by June Huh and Eric Katz.) Let me add one additional item, namely the solution (in the negative) by Boris Bukh of Eckhoff’s partition conjecture.
Other wonderful combinatorics news
These are also good times for other areas of combinatorics. I described some startling developments (e.g., here and here and here) and there is more. There were a few posts (here and here) on the Cup Set Problem. Recently Michael Bateman and Nets Katz improved, after many years, the Roth-Meshulam bound. See these two posts on Gowers’s blog (I,II). Very general theorems discovered independently by David Conlon and Tim Gowers and by Matheas Schacht show that many theorems (such as Ramsey’s theorem or Turan’s theorem) continue to hold for substructures of sparse random sets. Louis Esperet, Frantisek Kardos, Andrew King, Daniel Kral, and Serguei Norine proved the Lovasz-Plummer conjecture. They showed that every cubic bridgeless graph G has at least perfect matchings. The concept of flag algebras, discovered by Razborov, is an extremely useful tool for extremal set theory. It has led to solutions of several problems and seems to bring us close to a solution of Turan’s Conjecture (which we discussed here and here.) For example, it led to the solution by Hamed Hatami, Jan Hladký, Daniel Král, Serguei Norine, and Alexander Razborov of the question on the maximum number of pentagons in triangle-free graphs. Hamed Hatami found a structure theorem for Boolean functions with coarse thresholds w.r.t. small probabilities. This extends and sharpens results by Ehud Friedgut and Jean Bourgain. I finally caught up (thanks to Reshef Meir) with Moser-Tardos result giving a new algorithmic proof for Lovasz local lemma. Amazing! You can read about it here.
Some updates on my Internet questions
Imre Leader and Eoin Long wrote a paper entitled tilted Sperner families, which solves a question I raised in the context of polymath1. Imre and Eoin give additional results and conjectures. My motivation was to try to come up (eventually) with very very general conjectures which include density Hales-Jewett as a very special case and are also related to error-correcting codes. Raman Sanyal discovered a dual form of Tverberg’s theorem in terms of families of fans. (We asked about it here.) There is a new paper on the Entropy-Influence conjecture entitled The Fourier Entropy-Infuence Conjecture for certain classes of Boolean functions, by Ryan O’Donnell, John Wright, and Yuan Zhou, The paper contains a proof of the conjecture for symmetric Boolean functions and various other cases. This is the first new result on the conjecture for many years. Also there is nice progress for the -prime number conjecture asked about in a previous post, and a subsequent Mathoverflow question (There I will keep updating matters.). Ben Green solved the conjecture! Jean Bourgain settled the more general MO question and also found results on certain AC(2) circuits.
Newton Institute and Oberwolfach,
And it seems that things are moving along nicely in other areas close to my heart. A week ago (This was actually two months ago) I participated in a workshop at the Newton Institute on discrete harmonic analysis. And in the first week of February we had our traditional Oberwolfach meeting on geometric and topological combinatorics. Many interesting results!
A visit to IQI
In the last week of January I visited Caltech. I missed the IPAM meeting scheduled a week before because my visa arrived too late but I still made it to IQI. This was a very nice opportunity as most of my time at Caltech was devoted to quantum information/quantum computation issues related to my own work on quantum fault tolerance. So I gave an “informal” seminar describing my point of view (and gave it again the next day at USC). Here are the slides. My lecture was followed by two-hour discussion of the more technical details of my conjectures, seeking weak points and counterexamples in what I said, and trying to associate it with physics. There followed further discussions about some aspects of quantum fault tolerance and more general questions of quantum information with John Preskill, Leonard Schulman, Daniel Lidar and a few other people. (A lot of brilliant young people!) I learned quite a lot and was happy with this opportunity. (Of course, I did talk a little with Caltechian old and new friends about bona fide combinatorics questions.)
Three jokes for a dollar
On the weekend I took the LA metro (whose mere existence surprised me) and visited downtown LA and Hollywood. Next to Pershing station a person stopped me and asked if I want to buy three jokes for one dollar. I first said no, but then I reconsidered, called him back and gave him a dollar. To his disappointment and mine I did not understand the first joke, but the other two (perhaps adjusted to my revealed level of understanding) were quite good.
Hectic semester at HUJI
Here at Huji things are as hectic as always with 10-15 weekly research seminars. This week (This was two months ago; the semester have just ended). Continue reading
Scott Aaronson gave a thought-provoking lecture in our Theory seminar three weeks ago. (Actually, this was eleven months ago.) The slides are here . The lecture discussed two results regarding the computational power of quantum computers. One result from this paper gives an oracle-evidence that there are problems in BQP outside the polynomial hierarchy. The method is based on “magnification” of results on bounded depth circuits. (It is related to the Linial-Nisan conjecture.)
The second result that we are going to discuss in this post (along with some of my provoked thoughts) is a recent result of Scott Aaronson and Alex Arkhipov which asserts that if the power of quantum computers can be simulated by digital computers then the polynomial hierarchy collapses. More precisely, their result asserts that if sampling probability distribution created by quantum computers (this is abbreviated as QSAMPLE) is in P then the polynomial hieararchy collapses to its third level.
The beautiful and important paper of Aaronson and Arkhipov is now out. Its main point of view is related to what I describe in the sixth section about “photon machines”. Update: Let me mention related idependent results by Michael J. Bremner, Richard Jozsa, Dan J. Shepherd in the paper entitled: “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy“.
Here is the plan for this post
1) The polynomial hierarchy and results about hierarchy collapse
2) The Aaronson Arkhipov (AA) theorem and its proof
3) Two problems posed by AA
Those are: does P=BQP already leads to a collapse of the polynomial hierarchy? And does APPROXIMATE-QSAMPLE already leads to a collapse?
4) Does fault tolerance allow QSAMPLE (on the nose)? (Answer: yes)
5) Is there a quantum analog to Aaronson and Arkhipov’s result and what is the computational power of quantum computers?
Three Two competing scenarios
7) Aaronson and Arkhipov photon machines and the complexity class BOSONSAMPLING.