Mittag-Leffler Institute and Yale, Winter 2005; Test your intuition: Who Played the Piano?

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.

micheldevoretposter (1)

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. (And the second, $25, the third $12.50. )

Mittag-Leffler institute: the building, Mittag-Leffler(x2), and the piano

At the end of the two weeks I wrote an email to a few friends with some thoughts about quantum fault-tolerance which eventually developed into my first paper on the subject in summer 2005. I looked at that early email, and it is not as embarrassing as I feared it might be; one mistake I made in the beginning (until Boris Tsirelson told me about it) was to refer to “entanglement” as “decoherence” and to “decoherence” as “entanglement.”

Talking with Michael Ben-Or on quantum computations in 2005 and ever-since was sheer pleasure.

About these ads

9 thoughts on “Mittag-Leffler Institute and Yale, Winter 2005; Test your intuition: Who Played the Piano?

  1. gowers

    I have a guess, but it’s a challenge to convey the guess to you without giving too much of a clue to anyone else. How about this for an attempt at a “zero-knowledge” proof that I am thinking of the right person? (If I am not thinking of the right person, then with fairly high probability the statement I am about to make is false. Furthermore, with high probability I am not thinking of the right person.)

    Take the letters of this person’s first name and convert them into numbers using the obvious method A=1, B=2, etc. Take the letters of the person’s last name and convert them into numbers using the less obvious method Z=1, Y=2, etc. Use these to form a sequence that encodes the name. (For example, John Smith would come out as 10, 15, 8, 14, 8, 14, 18, 7, 19.) Then the even-numbered terms of the sequence add up to 60 and the odd-numbered terms of the sequence add up to 62.

    If those statements are true but you need further convincing, I can provide more linear combinations.

    1. Gil Kalai Post author

      Dear Tim, Thanks so much for your answer.The path for verification is still long but it forced me so far to sing in my head the nice song A B C D … several times which is something I did not do since my children were young. Let me add another term to my offer in addition to the monetary prizes. Every guesser, right or wrong, (ok, among the first 10 guessers) is entitled to a free beer (or something equivalent) on me next time we meet!

    2. Gil Kalai Post author

      Tim’s guess is not the answer. Let me offer another challenge: try to guess Tim’s answer. Let me offer another bribe for answers: every answerer’s name will be added to this post’s tags. Multiple guesses are aloud.

      1. gowers

        The problem of guessing my answer has a classic NP-ish flavour: easy to check any given guess, but difficult to come up with the correct guess. However, the fact that I felt moved to make a guess is a clue of a kind. It won’t help many people, but there are some for whom it might be just enough to narrow things down to a reasonable search.

      2. Gil Kalai Post author

        For me the bottleneck is to apply this terrible algorithm. E. g. I immediately guessed that you guessed “Per Enflo” but checking the arithmetic will take days.

        Update: I checked the arithmetic. Tim’s guess is Per Enflo.

  2. Peter Mester

    I have a guess and if I use the trick what Tim used for the first and last name of the person I got 56 and 55 (but doing this is not completely fault tolerant). If one looks as the Hebrew wikipedia page of this person, then the most complete form of the name contains at least one “aleph”. The place where the person was born has a significant waterfront. The year this person was born gives reminder 3 when divided by 9. To return to the method Tim used, if I add the numbers which are divisible by 3 I got 33. If I add those which gives reminder 1 I got 64.

    1. Gil Kalai Post author

      Dear Peter, many thanks for your answer.

      It would be nice if people will double and triple check their calculations. The type of hints I was thinking about were different say of the kind “A major art and high-tech exhibition from Beijing.”

  3. Pingback: The Mystery Piano-Player at the Mittag-Leffler Institute | Combinatorics and more

  4. Pingback: BosonSampling and (BKS) Noise Sensitivity | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s