## Test Your Intuition (18): How many balls will be left when only one color remains?

(Thanks to Itai Benjamini and Ronen Eldan.) Test (quickly) your intuition:  You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same colour. How many balls will be left (as a function of n)?

1) Roughly  εn for some ε>0.

2) Roughly $\sqrt n$?

3) Roughly log n?

4) Roughly a constant?

## Another Forgotten Bet: Is Don Zagier About to Owe Me 1000 Shekels For The Proof of the ABC Conjecture?

Like everybody else I heard with great interest the news about the attempted solution of the ABC conjecture by Shinichi Mochizuki. (See, e.g.,  herehere, here, and here.) I did not think that this has much to with me until I discovered yesterday in my room the following remarkable document from 1999.

A bet

If the ABC conjecture is proved Professor Zagier will pay G. Kalai 1000 (one thousand)  Isreali Shekels. Professor Zagier received 1 shekel in advance from G. Kalai.

Signed August 31, 1999, Tel Aviv

Don Zagier

ABC conjecture: $a+b+c=0_{(a,b)=1}\Rightarrow\prod_{p |abc}p\gg_{\epsilon}c^{1-\epsilon}$

Witnesses:  Noga Alon  Laszló Lovász

***

Amazing! I almost forgot about the whole thing, but now all left to say is:

# Go  Shinichi  Go!

Posted in Number theory, Rationality | | 7 Comments

## Erdős’ Birthday

Paul Erdős was born on March 26, 1913 2013 a hundred years ago. This picture (from Ehud Friedgut’s homepage) was taken in September ’96 in a Chinese restaurant in Warsaw, a few days before Paul Erdős passed away. The other diners are Svante Janson, Tomasz Łuczack and Ehud Friedgut. Erdős’ influence is felt everywhere in combinatorics, mathematics as a whole, and this blog as well. (A few more links: my most decorated MO answer is about Erdős, a recent heated discussion on the “two cultures in mathematics,” a new post on Erdős discrepancy problem on GLL,  and, most important, a link to Erdős centennial conference, in Budapest July 1-5, 2013. Join the celebration!)

Do not hesitate to contribute a comment!

Posted in Combinatorics | Tagged | 3 Comments

## My Quantum Debate with Aram III

This is the third and last post giving a timeline and some non technical highlights from my debate with Aram Harrow.

### Where were we

After Aram Harrow and I got in touch in June 2011, and decided to have a blog debate towards the end of 2011, the first post in our debate describing my point of view was launched on January, 2012 and was followed by three posts by Aram. The discussion was intensive and interesting.  Here is a link to my 2011 paper that initiated the debate and to a recent post-debate presentation at MIT.

## Back to the debate: Conjecture C is shot down!

In addition to his three posts, Aram and Steve Flammia wrote a paper refuting one of my Conjectures (Conjecture C).  We decided to devote a post to this conjecture.

# Quantum refutations and reproofs

### Post 5, May 12, 2012. One of Gil Kalai’s conjectures refuted but refurbished

Niels Henrik Abel was the patron saint this time

The first version of the post started with this heartbreaking eulogy for Conjecture C. At the end most of it was cut away. But the part about Aram’s grandchildren was left in the post.

## Eulogy for Conjecture C

(Gil; old version:) When Aram wrote to me, inn June 2011, and expressed willingness to publicly discuss my paper, my first reaction was to decline and propose having just private discussions. Even without knowing Aram’s superb track record in debates, I knew that I put my beloved conjectures on the line. Some of them, perhaps even all of them, will not last. Later, last December, I changed my mind and Aram and I started planning our debate. My conjectures and I were fully aware of the risks. And it was Conjecture C that did not make it.

### A few words about Conjecture C

Conjecture C, while rooted in quantum computers skepticism, was a uniter and not a divider! It expressed our united aim to find a dividing line between the pre- and post- universal quantum computer eras.

### Aram’s grandchildren and the world before quantum computers

When Aram’s grandchildren will ask him: “
Grandpa, how was the world before quantum computers?” he could have replied: “I hardly remember, but thanks to Gil we have some conjectures recording the old days, and then he will state to the grandchildren Conjectures 1-4 and the clear dividing line in terms of Conjecture C, and the grandchildren will burst in laughter about the old days of difficult entanglements.” Continue reading

This is a little “flashback” intermission in my posts about my debate with Aram Harrow. This time I try to refer to Cris Moore’s question regarding  the motivation for my study. For the readers it gives an opportunity to win a $50 prize! Let me also bring to your attention an interesting discussion (starting here) between Peter Shor and me regarding smoothed Lindblad evolutions. (Cris Moore, the debate’s very first comment!) I am also a little confused by Gil’s motivation for his conjectures. (My response:) To the best of my memory, my main motivation for skeptically studying quantum fault-tolerance was that I thought that this is a direction worth pursuing and that I had a shot at it. While listening with Ravi Kannan to this 2002 lecture by Michel Devoret at Yale, I wondered if there are enough scientists working on the “mirage” side. # Flashback: Mittag-Leffler 2005 I started systematically thinking about quantum fault-tolerance in February 2005. There were several things that triggered my interest to the question in the previous fall and I decided to spend some time learning and thinking about it in our winter break. One of those triggers was something Dorit Aharonov told me a few months earlier: she said that once, when she was telling her students about quantum computers, she suddenly had a feeling that maybe it was all just nonsense. Another trigger came from a former student who told me about a Polish scientist (whose name he could not remember) who wrote an article about impossibility of quantum error-correction. I thought that the lack of a quantum analog of the repetition code, and the unique properties of the majority function in terms of sensitivity to noise that I studied with Itai Benjamini and Oded Schramm earlier could be a good starting point for looking skeptically at quantum computers. In our 2005 winter break, I spent two weeks at Yale and then additional two weeks at the Mittag-Leffler institute near Stockholm. At Yale, I only had little time to think about quantum computers. I had to finish a survey article with Muli Safra about threshold phenomena (To a volume that Cris Moore and Allon Perkus were among the editors). One of the last days in Yale we went to dinner with two guests, Chris Skinner who gave the colloquium talk, and Andrei Okounkov who visited me and gave a talk about partition enumeration and mirror symmetry. At the dinner Andrew Casson asked, out of the blue, if we think that quantum computers can be built and it almost seemed as if that Andrew was reading my mind on what I plan to work on the weeks to come. My answer there was the same as my answer now, that I tend to find it implausible. Mittag-Leffler Institute February 2005 with Xavier Viennot and Alain Lascoux In Sweden I spent most of my time on quantum fault-tolerance. I was jet-lagged and being jet-lagged in the Mittag-Leffler institute already worked for me once, when finding my subexponential randomized variant of the simplex algorithm was a substitute for sleeping some night in fall 1991 . In 2005 it was not as bad, I just came to my office very early in the morning and started working. And very early in the morning somebody was already playing the piano. And who was playing the piano at the institute in the cold Swedish mornings of February 2005? The first reader to guess correctly, and convince me in a comment that she or he knows the answer without revealing it to everybody else will get$50. Continue reading

## My Quantum Debate with Aram II

This is the second of three posts giving few of the non-technical highlights of my debate with Aram Harrow. (part I)

After Aram Harrow and I got in touch in June 2011, and decided to have a blog debate about quantum fault-tolerance towards the end of 2011, the first post in our debate was launched on January 30, 2012.  The first post mainly presented my point of view and it led to lovely intensive discussions. It was time for Aram’s reply and some people started to lose their patience.

(rrtucky) Is Aram, the other “debater”, writing a dissertation in Greek, as a reply?

# Flying machines of the 21st century

### Post II, February 6, 2011. First of three responses by Aram Harrow

Dave Bacon was the patron saint for Aram’s first post.

(Aram) There are many reasons why quantum computers may never be built…  The one thing I am confident of is that we are unlikely to find any obstacle in principle to building a quantum computer.

(Aram) If you want to prove that 3-SAT requires exponential time, then you need an argument that somehow doesn’t apply to 2-SAT or XOR-SAT. If you want to prove that the permanent requires super-polynomial circuits, you need an argument that doesn’t apply to the determinant. And if you want to disprove fault-tolerant quantum computing, you need an argument that doesn’t also refute fault-tolerant classical computing.

## From the discussion

### Why not yet? Boaz set a deadline

(Boaz Barak could [you] explain a bit about the reasons why people haven’t been able to build quantum computers with more than a handful of qubits yet? Continue reading

## How the debate came about

(Email from Aram Harrow, June 4,  2011) Dear Gil Kalai, I am a quantum computing researcher, and was wondering about a few points in your paper

(Aram’s email was detailed and thoughtful and at the end he proposed to continue the discussion privately or as part of a public discussion.)

(Gil to Aram) Thank you for your email and interest. Let me try to answer the points you raised. …   (I gave a detailed answer.) …  Right now, I don’t plan on initiating a public discussion. How useful such public discussions are (and how to make them useful) is also an interesting issue. Still they were useful for me, as two of my conjectures were raised first in a discussion on Dave Bacon’s blog and another one is partially motivated by a little discussion with Peter Shor on my blog. Continue reading

## Test Your Intuition (17): What does it Take to Win Tic-Tac-Toe

(A few more quantum posts are coming. But let’s have a quick break for games.)

Tic Tac Toe is played since anciant times. For the common version, where the two players X and O take turns in marking the empty squares in a 3 by 3 board – each player has a strategy that can guarantee a draw.

Now suppose that the X player has a budget of Y dollars, the O playare has a budget of 100 dollars and before each round the two players bid who makes the next move. The highest bidder makes the move and his budget is reduced by his bid.

For example, if, to start with, the X player have 120 dollars, and if for the first move X bids 40 dollars and O bids 30 dollars, then X will make the first move and will be left with 80 dollars while O will be left with his 100 dollars.

What would you expect the minimal value of Y is so the X player has a winning strategy? Of course if Y>300, X can make 3 uninterrupted moves and win, but perhaps much less is enough?

(Thanks to Reshef Meir and Moshe Tennenholtz)

Update: Another variant of this game is when the player winning the turn pays his bid to the other player. (This version is called “Richman game,” while the variant above is called “Poorman game”. In this case if Y> 800 the X player can play three moves and win. And again the question is what is the infimum value of Y for which the X player can force a win…

## A Few Slides and a Few Comments From My MIT Lecture on Quantum Computers

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.

## Meeting with Aram Harrow, and my Lecture on Why Quantum Computers Cannot Work.

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

After having an almost a year-long debate with Aram Harrow, I finally met Aram in person, and we had nice time together during my visit.

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.

### More

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.