My Quantum Debate with Aram Harrow: Timeline, Non-technical Highlights, and Flashbacks I

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.

I did not know much about Aram before his email, but Aram’s name came up again the next day:

(Email from Leonard Schulman June 5, 2011) Your nudge in which direction to think was tremendously helpful. We [Leonard and Alexandra Kolla] kept hammering away at it, also with Aram Harrow, and after studying a lot an old paper of Stein, I think we have basically figured out how to do it. Ie, an L2 constant-factor maximal inequality for the hypercube.

(wow, terrific)

The main reason for not wanting to commit to a public discussion at that time was the open-heart surgery I was scheduled to have on June 20; All went well with the surgery and I returned to post blog–comments and MO answers about a week after the operation. But I forgot about Aram’s email.

November/December 2011

On November 2011 Aram posted a remark on GLL concerning my paper on quantum computers. Following it we got in touch again.

(Aram to Gil) Hi Gil, I’m sorry for not responding to this email, and instead posting in a public forum… (Gil to Aram ) Dear Aram, no problems at all. I enjoyed seeing your comment in Dick’s blog. It would be nice to discuss these ideas publicly (as you suggested several months ago) and Dick’s blog can be an ideal place for it… if Dick and Ken will host us. (They had a very fruitful series of posts analyzing Deolalikar’s claimed proof about NP=P.) (Aram) I think a public discussion on Dick&Ken’s blog would be fun!  … a lot of people will chime in in the comments, but that should make it only more interesting.  We asked Dick and Ken…

Ken Regan

(Dick to us) Sounds interesting. Let ken and I chat, but should work, (Ken to us)  Dick and I waited to discuss it by voice in late afternoon so we could “properly” give an enthusiastic “yes” answer.  

Dick Lipton

During the public debate itself the four of us had a rather extensive private email correspondence. Most of the posts were authored by Ken who, at times, understood us better than we did ourselves.

Perpetual Motion of the 21st Century

Post I, January 30, 2012; Are quantum errors incorrigible? Discussion between Gil Kalai and Aram Harrow

 

Dorit Aharonov, Robery Alicki, Michael Ben-Or and me (Jerusalem, left 2012; right 2005). Every post on GLL has one or more “patron saints,” and I chose Robert, Dorit and Micahel.

(The title of the first post looked at first overly provocative to me. But in hindsight it was good.)

(Gil) I will now go on to describe my conjectures regarding how noisy quantum computers really behave.

The body of the first post described and explained in some details my conjectures on  noisy quantum systems. They will not be reproduced here.

(Gil)  Let me explain why I think that my conjectures are correct—also mindful of this nice post by Shmuel Weinberger on what “a conjecture” means for a mathematician. I regard it as implausible that universal quantum computers are realistic, and I think that the issue of noise is indeed the main issue… as far as I can see, my conjectures on the behavior of noise do not violate any principle of quantum mechanics.

…let me briefly say why I tend to regard universal quantum computers as unrealistic. An explanation for why universal quantum computers are unrealistic may require some change in physics theory of quantum decoherence. On the other hand, universal quantum computers … propose a major change in physical reality.

Aram laid his roadmap for a response.

(Aram)  1) Any argument that FTQC (fault-tolerant quantum computing)  is impossible must also deal with the fact that classical computing is evidently possible.

2) The key assumption of FTQC is (approximately) independent errors. Conversely, Gil’s skepticism is based on error models that may have low single-qubit error rates, but are highly correlated even across large distances.  I’ll give both theoretical and experimental evidence that such error models don’t occur in nature

3)  I’ll propose a thought-experiment implementation of a quantum computer, which is not meant to be practical, but where correlated errors are highly implausible.

In the comments:

(In green, a few of my afterthoughts are added.)

Cris Moore

The very first comment by Cris Moore was the basis of a long further discussion:

(Cris) ..Skeptics of quantum computing are really skeptics of quantum mechanics. … Thus I would be much more interested in engaging with the skeptics if, rather than computer science-style conjectures that certain algorithms are impossible, they made conjectures about the underlying physics, proposing an alternative to QM that would explain the phenomena we have observed while making large-scale quantum computing impossible.

(Gil)  Just to make it clear: I do not believe in any nonlinearities in the Schrödinger equation. I am not a skeptic of quantum mechanics and if my conjectures are in conflict with QM I will happily admit that they are wrong. If you are interested in engaging in a conversation with somebody skeptical of QM you need to find somebody else.

Geordie Rose

(Geordie) BTW I side with Gil in the debate going on here, but for different (but related) reasons. The ideas underlying the circuit model of quantum computation are not good ideas, and I don’t think useful quantum computers based on circuit model ideas will ever be built. But this doesn’t mean that using quantum mechanics to make better computers won’t work.

Robert Alicki

(Robert) As my name was mentioned by Gil I think, I should present my view on the discussed issue. First of all, I like the title of this debate corresponding to my last preprint on this topic – “Quantum memory as a perpetuum mobile of the second kind”, because I believe that impossibility of fault-tolerant quantum computations (FTQC) should follow from the existing, perhaps refined, laws of thermodynamics…

Joe Fitzsimons

As you will see below, Joe Fitzsimons has made great pointed critical comments regarding my conjectures throughout the debate. Let me quote first an interesting comment he made on his feelings towards the debate itself.

(Joe) I have found the debate so far very interesting (if somewhat infuriating, as I find it hard to understand what could possibly lead someone knowledgeable in the area to conjecture that building a quantum computer is impossible),

(Robert) In my case the answer is simple : 35 years of experience in the theory of quantum open systems which exactly deals with quantum noise, decoherence , stability etc.

John Sidles

John was the most prolific commentator in the entire debate. It will probably take a special post to describe his point of view and contributions. Here is his very first comment:

(John S) Oh boy! Gil and Aram are two researchers whom I respect greatly … so this is one debate that (IMHO) both sides are sure to win.

How can both sides win the debate? Easily … even naturally!

John Preskill

(Happy birthday-conference, John)

(John P) I hope Robert Alicki realizes that I have always taken his criticism seriously. … I have also found Gil Kalai’s skepticism stimulating, and I enjoyed our discussions during Gil’s visit to Caltech last year.

Flashback:  Visiting Caltech

(Email from John Preskill, October 1 2010) Dear Gil, I am writing to invite you to visit Caltech, and speak at our quantum information seminar, sometime during the 2010-2011 academic year.  You would be welcome to stay for as long as you please…, 

It would be a long trip for you, of course, so it would make sense for you to stay here for a while, if you can get away for long. I would enjoy the opportunity to learn more about your ideas concerning fault-tolerant quantum computing. I hope you will be able to come.

(I had some correspondence with John in 2005 and 2006, but this nice invitation came out of the blue. It caught me (on my birthday) in the US soon before returning to Israel so the trip to Caltech would indeed be very long. Should I go?)

(Gil to John, eleven minutes later:) Dear John, thanks a lot, this sounds great. Let me try to think about the best time.

Groucho Marx (disclaimer: this blog discourages smoking)

I went to Caltech in January, and stayed a little over a week. It was an enjoyable and fruitful visit. On the fifteen hour direct flight from Tel Aviv to LA I thought that the Marx brothers would have been very proud! (Groucho Marx famously talked about the caring to enter a club only if it does not want you as a member.)

I recall some phone calls that I made from Caltech with my family in Jerusalem:

Hagai (My son; over the phone): So, did you win the quantumists?

Gil: But Hagai, it is not about winning or losing, and I am a quantumist myself.

(Who am I kidding)

My wife (over the phone): So, did they convince you?

Me: Well, not yet…

Back to the debate; John Preskill

(John P) Gil’s visit provided the impetus for me to work out some sufficient conditions for scalable quantum computing, something I had been meaning to do anyway. The results are a bit much to explain in a blog post, but I have posted my notes at…

(Nice and unexpected)

(John P (cont.)) Gil believes that Hamiltonian noise models like the one discussed in my notes are not physically realizable; that could well be, though I would like to understand better his reasons for holding that opinion.

(It took me almost a year to come up with a reason that is not related to quantum fault tolerance for why John’s models are not realistic)

(John P (cont.)) Gil says that while he is skeptical of quantum computing he is not skeptical of quantum mechanics. Therefore, I presume he takes for granted that a quantum computer (the “system”) and its environment (the “bath”) can be described by some Hamiltonian, and that the joint evolution of the system and bath is determined by solving the time-dependent Schroedinger equation. If Gil’s conjectures are true, then, no matter how we engineer the system, the Hamiltonian and/or the initial quantum state of the joint system must impose noise correlations that overwhelm fault-tolerant quantum protocols as the system scales up.

(I could not have said it better myself)

(John P) It is useful to formulate the question mathematically. Then we can focus our attention on which assumptions in the mathematical arguments ought to be questioned.

(I like that…)

Boaz Barak

(Boaz) Gil, I understand from this you believe that physically realizable quantum computers offer no superpolynomial speedup over classical computers, and hence there is a polynomial time algorithm to simulate them. Do you have a sense of what this algorithm is?

(Gil) Boaz, …  Do you ask if quantum computers that satisfy Conjectures 1-4 can be simulated classically? (The answer is that I don’t know.) Or is your question different?

Scott Aaronson: Whether or not God plays dice, I do

(Scott) The “debate” format makes it seem like we have a conflict between two competing theories: one that says scalable QC is possible and one that says it isn’t. But that’s not the situation at all: this is a conflict between (a) a theory, and (b) attempts to poke holes in that theory, without proposing a replacement.

This can be seen most clearly in the exchange between Gil and Boaz above. In response to Boaz’s extremely-pertinent question, of whether, if FTQC is impossible, that means there’s an efficient classical simulation of realistic quantum systems (and if so, what is it?), Gil basically says that he doesn’t know … This sort of response might be fine in a legal defense (“if not my client, who DID commit the murder? who knows? maybe aliens, maybe the boogeyman. I don’t have to explain it, I just have to cast enough doubt on the prosecution’s case!”). But it’s more problematic in science,

(“Dont call me ‘son.’ I am a lawyer and an officer in the US navy!”)

(Gil) I agree with what Scott writes in the first paragraph about the asymmetry…  Just to make it clear: the theory we discuss is *not* quantum mechanics, but the postulate that universal quantum computers are possible…

… 100,000$?, 10%?, something?

(Scott Aaronson: (over his blog)) For better or worse, I’m now offering a US$100,000 award for a demonstration, convincing to me, that scalable quantum computing is impossible in the physical world.  This award has no time limit other than my death, and is entirely at my discretion (though if you want to convince me, a good approach would be to convince most of the physics community first).  

(I should have said $200,000 )

(Nobody pays such bets, Avi Wigderson still owes me $5000 bets from Princeton 1995.  Avi drove me into seven separate 1000 dollars bets, but luckily I won six of them.)

(Scott) Believing quantum mechanics but not accepting the possibility of QC is somewhat like believing Newtonian physics but not accepting the possibility of humans traveling to Mars. 

(Somewhat)

(Scott) If you read Gil’s paper, he’s honest enough to admit that many of his conjectures seem “merely” to reduce QC to logarithmic-depth—i.e., still enough to implement Shor’s factoring algorithm!

(Honest enough!, what is that?)

(Scott (cont.)) Not just QC researchers, but chemists, nuclear physicists, high-energy physicists, etc., few of whom think there’s any problem of principle with QC.

(There is a big problem in understanding what “problem of principle” means.  Beside that, people tend to tell you what they expect you want to hear, and people tend to hear what they expect and want to hear…)

Changing people’s prior beliefs

(Gil) Let me make one “meta” comment which is simply to repeat what I said here on the blog last June , and on several occasions earlier: Overall, I don’t think that my work and other skeptical works should change people’s a priori beliefs on the feasibility of quantum computers.

Quantum Groundhog Day

A follow-up post by Dick and Ken, February 2 2011

(Gil) One aspect of the discussion that I find puzzling is the following: Some people are much more ready to accept a reality where QC are possible in principle, but it will take a hundred years to build them, or even that they will not be built at all, compared to a reality that there is a 10% chance that a principle explaining why quantum computers are infeasible will be discovered, but otherwise they will be built in a few decades.

Not yet like the standard model

(Aram) The evidence for quantum mechanics is overwhelming, and no one has a physical theory that permits quantum mechanics but not quantum computing.  Gil is trying to develop one,

(Yap, this is correct, a theory of noise, within quantum mechanics, of course!)

but it’s not yet the kind of theory like the Standard Model that you can use to make precise physical predictions.

(Yes, I cannot argue with that)

Some commentators started losing their patience for Aram’s reply

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