**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.”

**A few more words about Conjecture C**

Conjecture C was meant to express in clear terms of statistical nature what is this dividing line. However, Conjecture C is no more.

**What can replace Conjecture C?**

The first answer that comes to mind is

Nothing!

Nothing can replace Conjecture C in our hearts. Nothing can replace Conjecture C in our minds. However, life should go on. We should continue the mission of Conjecture C.

The post went on to discuss what can replace Conjecture C…

# Can you hear the shape of a quantum computer

*Post 6, June 20, 2012.* *Debate round 3: Computation cannot hide the physics*

Marc Kac, who asked “can you hear the shape of a drum?”

I especially liked this post because it included some issues and ideas that arose during the debate itself.

**(Gil:) **If the universe is a large quantum computer of some sort, and if we cannot hear the shape of a quantum computer, then where does geometry come from?

## Putting a toric 4-D code on an IBM logo shape

**(Gil:)** Consider, for example, Alexei Kitaev’s four-dimensional self-correcting memory. This is a remarkable quantum analog of the 2D Ising model, and it is an outstanding open question whether 3D objects with similar properties can be constructed. Once we have a universal quantum computer we will even be able to realize Kitaev’s 4D model on an array of qubits that looks like this:

IBM

(This example and the general point regarding geometry of quantum devices came up in the discussion. It arose from Aram’s request early on that I explain why I believe my conjectures.)

## Jesus!

This time, Aram’s response was of a very general nature.

**(Aram)** However, the task of the skeptics is now a difficult one. Attempting to give a theory that would exclude quantum computers while keeping quantum mechanics reminds me of the famous saying of Jesus:

It is easier for a camel to pass through the eye of a needle than for a rich man to enter heaven.

What I like about this quote is that it expresses the idea that something may be in principle possible (a rich man going to heaven), but there are so many difficulties along the way (how one acquired one’s wealth, the fact that it hasn’t been given to those in need, etc.) that we are left with either the vivid impossibility of the camel, or the painful alternate reading of trying to thread rope made of hemp or camel hair.

(Jesus! What the heaven is Aram talking about?)

### What “from first principles,” means?

(**Gil**) Aram, can you explain what you mean by “simulating from first principles? ”

**(Aram****) **Good question.

…“first principles” means you start with something like this [the standard model]…

But in practice, we have to do some phenomenology… Then we have to also use our brains a bit ..**.**Of course it’s hard to prove upper bounds on “using our brains**”**. We can always potentially come up with something more clever.

(Hmm, I did not get it)

**(John S.)** Also, your remark

It’s hard to prove upper bounds on “using our brains.”

is a noble sentiment & hopefully we are far from approaching this upper bound.

(This sweet optimistic sentiment cannot be left unchallenged)

** (Gil) **It is even harder to prove lower bounds [on “using our brains”].

## John Sidles

John Sidles have made many many substantial contributions to the debate (like to many other Internet scientific discussions,) which demonstrate his amazing knowledge and wide horizons, wild associations, special sense of humor, and very special ability to accommodate peacefully many conflicting-looking views. John was especially interested in promoting the idea of certain geometric quantum-like evolutions, where the Hilbert space is replaced by low-dimensional manifolds. Realistic quantum evolutions, John claims, can be well-approximated, by such geometric evolutions, leading not only to effective practical computational tools, but also to important conceptual insights for quantum mechanics (and beyond(?)).

## Summer 2012: Conjecture 1 is under attack!

In summer 2012 we were ready to conclude the debate. The plan was for me to reply to Aram’s claims in his three posts, and for both of us to conclude. It is left to be seen what impact, if any, my conjectures had on the QC program, and, in particular, on creating supremacy-graded entanglements, but with Conjecture C notably missing it looked that my other conjectures were moving back home for a safe landing after their long and risky journey. After Aram’s Jesus quotation I did not expect a new argument on the technical level. However, Aram’s summation contained a nasty, long, unexpected technical attack on my first conjecture.

We had to change our plans again and to devote a special post to this.

# Quantum repetitions

*Post 7, September 16, 2012: Aram Harrow and Gil Kalai debate “Conjecture 1″*

William Wootters and Wojciech Zurek proved the “no cloning theorem”

**(Aram)** … This should be enough to dispose of Conjecture 1. After all, it is stated as applying to *all* codes. If an exception is built in for the repetition code which is the key code behind classical computing, then it starts to look rather camel-shaped.

(It took me some time to figure what is going on, but unlike the case of Conjecture C the damage to Conjecture 1 was minimal.)

## Aram’s 2-SAT/3-SAT analogy

This post was the natural place to relate to Aram’s 2-SAT/3-SAT analogy:

**(Gil:)** Quoting 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… And if you want to disprove fault-tolerant quantum computing, you need an argument that doesn’t also refute fault-tolerant classical computing.

This is correct. Proving that 3-SAT needs exponential time requires an argument that does not apply to 2-SAT and XOR-SAT. Today, after many years, we still do not have such an argument. But this does not mean that we should believe that 3-SAT behaves like 2-SAT. … Similarly, proving that fault-tolerance quantum computing is impossible will require more experimental efforts and theoretical progress. But the fundamental differences, as those described in the previous debate post, between a world with fault-tolerant quantum computing and our present reality give good reasons to believe and certainly to explore the possibility that quantum fault tolerance is not possible.

# Quantum supremacy or classical control

*Post 8, October 3 2012: Final summations of the Kalai-Harrow debate*

Bill Unruh was the debate’s last patron saint

This was the last post. It started with an overview of Aram’s claim

**(Gil)** with the exception of Conjecture C as we discussed earlier, all the technical arguments against my conjectures raised by Aram are either weak to start with or incorrect.

I explained why Aram’s arguments regarding my conjectures are incorrect. It was left to be reminded that my conjectures may be incorrect as well.

**(Gil)** While I disagree with these two out-of-hand reasons to reject my conjectures, it is quite possible that my conjectures are simply false. They should be carefully examined on a case-by-case basis.

## 2-locality revisited

**(Gil)** Joe Fitzsimons’s 2-locality argument was a specific attempt to explain why my conjectures violate known physics. It turned out, however, that a strict version of it is too strong to be realistic (see this comment by Preskill), while a weak form of 2-locality is too weak to be in conflict with my conjectures. But again, my main objection to Joe’s attempt was different: insights of this kind should emerge from the model rather than being imposed on the model.

## A response to Peter Shor

It was also a good time to refer to Peter Shor’s comment

**(Gil)** quoting Peter Shor

“…the universe needs to know what code you are using in order to foil you. This attributes both more intelligence and more malice to the universe than I am willing to believe that it has.”

This makes sense if the code is created on a universal machine. But if every code (that can be created at all) requires a specific machine, then neither malice nor intelligence on the part of the universe to tell them apart is required.

# Conclusions

**Aram**

**(Aram)** It’s been useful for me to think through these things, and has caused me to think about skepticism in a new way. (For example, am I like one of those establishment scientists who rejected continental drift out of hand? How certain can I be about my position on other controversial things, like the probability of global warming, or relativity, or my own atheism?) It has led to my work with Steve Flammia on Conjecture C, and also a new project on adversarial noise joint with Matt Hastings and Anup Rao, which I’ll talk about soon on the Pontiff blog.

(Very nice!)

**(Aram)** I hope that my participation here will turn out well for the field of quantum information, which has faced a large amount of skepticism and misunderstanding from the field of computer science.

**(Aram)** Gil’s conjectures, then, are really pre-conjectures, meaning that they are neither purely mathematical conjectures nor specific claims related to observable phenomena, but rather organizing principles around which we might look for such claims.

(Aram)The quest to build quantum computers has been fraught with difficulties, but to my knowledge none of these are rooted in error correlations increasing with system sizes. Rather, they involve the sort of problems that elephants would have in dissecting fleas. … At a certain point, we gain confidence that there is no monster hiding under the bed, not only because there hasn’t been one before, but because nothing about our knowledge of the world would suggest such a monster.

**Gil**

**(Gil)** This debate gave me a great opportunity, for which I am thankful, to discuss my work on quantum computers. …

(Gil)It may well be the case that universal quantum computers are not possible, and that “no quantum fault-tolerance” should be taken as the guiding principle in modeling quantum decoherence. Developing a theory of non-fault-tolerant quantum evolutions, and studying how quantum computers can fail, is an interesting and important endeavor.

# A.D. (After debate)

We had some further discussions in the comment thread of the last post and earlier ones.

### Time to move on

(**Aram**, emphasis mine) *In part because I don’t know how else to subscribe to comments*, let me start a little discussion about Gil’s smoothed Lindblad evolution.

(Hmm, the excitement is over; time to move on)

### Last round of comments with Aram (November 2012): Formalizing what cannot be formalized.

**(Aram)** (emphasis added): The same story can be told about the exponential-time classical emulation, except that now *the encoding is no longer a unitary, or indeed linear, map*.

I agree that the quantum emulation feels closer to the original physics than the classical emulation does. But this seems like a rather imprecise statement, and *not something that can be formalized*.

**(Gil)** This is great, Aram, in the last paragraph you say that the distinction cannot be formalized and in the previous paragraph you offer a way to formalize it!

**(Aram)** good point.

## January 2013 – over the Shtetl Optimized

Another round of discussions on quantum computers trigerred by a recent paper by Michel Dyakonov, took place over the Shtetl Optimized. It was a nice opportunity to remark on some issues that we mentioned in the GLL debate but did not get to, and to return to a few other issues.

### Getting close to Scott, relatively

**(Scott)** (agreeing to five points I have raised) Gil Kalai #95: yes, yes, yes, qualified yes, and yes! …

But it’s clear that we agree on a great deal, and in particular, that

|Me-You|<<|Me-Dyakonov| !

(the above exclamation mark is not a factorial )

### Not for long

**(Scott) ** I had wrongly assumed you (Gil) were looking for an actual explanation for why QC couldn’t work — so that for example, if the problem was noise scaling up with system size, then you wouldn’t rest until you could explain why the noise worked that way… But I finally understand what, perhaps, you’ve been trying to tell me all along: that not only have you not achieved that, **it isn’t even your goal!…**This position is so alien to my way of thinking that, in retrospect, it’s no wonder I subconsciously distorted it.

(??)

### Greg Kuperberg compares me to mom

**(Greg Kuperberg)** Scott – You have to understand what Gil has in common with my mother: They are both famous for finding important mathematical counterexamples. I do not really mean to speak for Gil. If I were in his position, I would be very happy to find any mathematically important noise model in quantum probability, that both censors QC and still allows classical computation. Even though it might well not be physically true. ..

Gil has also argued to me that it shouldn’t be relevant what any of us believe, only what we accomplish.

(I am honored)

## Why quantum computers cannot work

**(Gil)** I guess what I wrote was not clear enough. Yes, I am interested in an actual explanation, and, yes, the problem is that for universal quantum devices the noise will scale up and will cause them to fail, and here is my explanation:

Quantum systems based on special-purpose quantum devices, are subject to noise which systematically depends on the quantum evolution of the system; this dependence reflects dependence of the noise on the quantum device, and the dependence of the quantum device on the quantum evolution it is doomed to perform.

This systematic dependence can be expressed formally as follows: Quantum systems are subject to noise which is expressed by smoothed Lindblad evolutions. The amount of noise in a time interval is bounded below by a non-commutativity measure of (the projections in) the algebra spanned by unitaries describing the evolution in this interval. Smoothed Lindblad evolutions reflect the idea that quantum fault-tolerance is impossible (or not active) and, therefore, quantum noise must accumulate.

… This property of quantum systems based on special-purpose quantum devices explain why universal quantum devices are forced to fail. (The reference to “devices” applies both to human-made devices and nature-made devices.)

## Deja-Vu

(**Aram to Gil**, e-mail January 2013) Sorry for dropping the ball on the smoothed Lindblad evolutions. I still need to work through this and figure out your point about the two interpretations being different; so far I haven’t understood it. I know it’s not nice to comment on this publicly before I’ve done my homework.

(**Gil to Aram**) No problems…

(We tentatively agreed to devote a post to discuss smoothed Lindblad evolutions in Summer 2013 and asked Dick and Ken to kindly host us.)

## Some of the debate’s commentators:

Cris Moore, me, Steve Flammia, Boaz Barak, John Sidles, Craig(?), Aram Harrow, Ken Regan, Roger(?), Robert Alicki, Geordie Rose, Marcin Kotowski, Joe Fitzsimons, Scott Aaronson, Ørjan Johansen(?), Rrtucci, John Preskill, Michael Nielsen (once), Wim van Dam (once), Klas Markström, Dave Bacon (also a patron saint and Pope Emeritus), Peter Shor, Matt Leiffer, Hal Swyers, Matt, Rachel, Nurit, Elijah, Michel Dyakonov, Greg Kuperberg (Michel and Greg participated only over “Shtetl Optimized”). Pictures missing for Alexander Vlasov, Serge, Mkatkov, Jiav, Ramirez, and more.

Gil KalaiPost authorAvi Wigderson asked why to compare the difference between classical fault-tolerance and quantum fault-tolerance to the distinction between 2-SAT/3-SAT and not to the distinction between 2-SAT/MATCHING. Be that as it may be, both these computational complexity distinctions are of central importance.

Pingback: Interstellar Quantum Computation | Gödel's Lost Letter and P=NP

Alexander VlasovDear Gil,

Not long time ago I became aware about yet another sceptical opinion: academician E. Alexandrov (the new chairman of the “RAS Comission against pseudoscience and the falsification of scientific research”) said (translation from the interview, near end of text http://www.ras.ru/digest/showdnews.aspx?id=664b18fd-74a7-4b32-b414-411717606a8d&print=1 ):

“For example, I am suspicious about long-standing promises in respect of quantum computers. Wise people already are starting to realize – it is a dead-end path for the development of computer technology.”

Gil KalaiPost authorDear Alexander, I regard the question if quantum computers can be built as a great scientific question. I also regard the quantum computers endeavor in various areas of theoretical and experimental physics, theoretical computer science, mathematics, chemistry and engineering as a great scientific and technological endeavor. Usually, my feeling about off-hand skeptics is that they are missing something (of course I can be wrong myself both on how things will turn out and on how important they are). Skeptics, especially qualified scientists, who dismiss QC while ignoring the scientific challenge in finding good explanation why they cannot work (if they cannot work) remind me the story about Crookes, who observed (few years before Rontgen) that leaving a photosensitive film near the cathod-ray-tube causes damage to the film: it becomes exposed. He concluded that “Nobody should leave films near the cathod-ray-tube.” In any case, head counts and opinion polls are, in my view, not that important, just arguments, and experiments.

Alexander VlasovDear Gil, I found some translation in Internet http://ru-facts.com/news/view/16708.html

Likely, his objection — is to much effort on an exotic stuff.

Michael BaconGil,

I was wondering if you had seen this? Interesting approach I think.

http://arxiv.org/abs/1305.4499