Building Bridges II, and Rio ICM 2018

Combinatorics and more 2018-08-02

In this post I will talk about Building Bridges II – last week conference in Budapest, about my talk and Lex Schrijver’s talk at the conference, about two old videotaped lectures in Microsoft Research (and a prize carrying competition), and about preparation for ICM 2018 at Rio (and a request for suggestions and advice).

Building Bridges II

Just returned from Budapest from Building Bridges II – a conference celebrating Laci Lovasz’ 70th birthday. Let me share with you the (slightly edited) slides of my talk: Dismantling Bridges and Building New Ones :The argument against quantum computers, near-term predictions, and the laws of noise. (Also, based on experience, this is the safe way to share these slides with me in the future.) Here is the program with videos for most lectures.

Dismantling bridges and building new ones: The argument against quantum computers

The argument from my lecture is briefly this: Computationally superior quantum computing (aka “quantum supremacy”) requires good-quality quantum error-correction, but, on the other hand, good quality quantum error-correction is harder than quantum supremacy. So, both these tasks are doomed to fail. (The first statement relies on results by Guy Kindler and me.)

This argument is not just against the long-term goals of quantum computation, but also against the very short term goals of building stable qubits and demonstrating quantum supremacy. This argument breaks for classical computation since, while classical computation still requires error-correction, unlike the quantum case, some forms of classical error-correction are supported by very low-level computation.

Bridges and other pictures from the lecture

Lex Schrijver’s lecture

There were many great talks and let me mention one other talk. Lex Schrijver gave a wonderful lecture on $\Theta$ and $\vartheta$ . Here are the mathematical slides featuring two striking formulas for Shannon capacity and one striking formula for Lovasz’ theta function that I did not know about. One very recent formula for $\Theta$ by Jeroen Zuiddam, one quite old formula for $\Theta$ by Haemers, and one 2013 formula for $\vartheta$ of certain circular graphs by Bachoc, Pecher, and Thiery. Here is Lex’ videotaped lecture.

From left to right: Lex Schrijver, Laci Lovász, Martin Grötschel, Lex Schrijver

Old videotaped lectures at MSR

Going back to my quantum lecture, among four close friends that have heard me talking about this subject for many years, two have recently told me that they finally understand what I am saying while the other two said that they don’t understand the argument. (And I cannot assume that these four friends forms a representative sample of the rest of the world, so surely I have some way to go .) Two out of the four (one on each side) and also 6-7 other members of the Budapest audience, attended a very preliminary lecture I gave about the topic in in Microsoft Research back in August 2005 entitled “Is there an (interesting?/realistic?/universal?) model for noise which reduces quantum computation to classical computation?” While the lecture itself is somewhat obsolete by now, you may enjoy Jennifer Chayes’s entertaining introduction which is related to my entertaining opening of this earlier MSR lecture on Social Choice and Threshold Phenomena. Both lectures give great picture of the very distinguished audience members in younger days. (See some pictures below, but it looks much better on video.)

Prize carrying competition: Identify members in the audience of these videoes and drop a comment.

ICM 2018 at Rio

Update: Notices AMS just published ICM 2018 LECTURE SAMPLER with descriptions of five plenary lectures from the congress by Sanjeev Arora, Catherine Goldstein, Sylvia Serfaty, Gregory F. Lawler and me.

Early next month I go to Rio for ICM 2018 which is surely going to be an exciting event. I am already quite thrilled and a little nervous about it. I may try to blog about the second half and I am sure some capable bloggers will blog about the beginning of the congress which is bound to be exciting. My paper for the proceedings is entitled “Three puzzles on mathematics, computations, and games“. (The link is to the arXive version which is not fully updated. Also, the proceeding’s version will have full references.) The paper discusses the subtle connections between theory and reality in the context of mathematics and computation, and the three topics presented are, linear programming, noise stability of voting rules, and quantum computers.

In the lecture I plan to mainly talk about the theory of noise sensitivity and stability in the context of voting rules and percolation (starting with my work with Benjamini and Schramm), in the context of quantum computing systems (my work with Guy Kindler), and about my potentially most important yet controversial application: the argument against quantum computers.

I am still hesitating about some aspects of the lecture: power point or beamer? Should I emphasize the theory and theorems or rather the conceptual matters and interpretations? Should I talk mainly about quantum computers (like in Budapest) or also about less controversial aspects of noise stability and sensitivity?

Last-minutes suggestions, tips, requests or demands about my upcoming ICM lecture (which I plan to finalize in a week or so) are welcome, here or in private.

Getting inspired in Budapest 1: Laci and me in matching sweathers. Is it a coincidence? asked a dear Facebook friend which reminds me that we still have to discuss coincidences as promised long ago.

Getting inspired in Budapest 2: with Endre Szemeredi and Terry Tao.

From a lecture of Scott Aaronson at the Simons Institute: Ironically the main application of quantum supremacy is to disprove my argument against quantum supremacy.

Pictures from MSR 2004 lecture on social choice and threshold phenonena

The MSR 2005 lecture on quantum computers