The Quantum Fault-Tolerance Debate Updates

In a couple of days, we will resume the debate between Aram Harrow and me regarding the possibility of universal quantum computers and quantum fault tolerance. The debate takes place over GLL (Godel’s Lost Letter and P=NP) blog.

The Debate

Where were we?

My initial post “Perpetual Motion of The 21st Century?” presented my conjectures regarding how noisy quantum computers and noisy quantum evolutions really behave.

Aram’s first post was entitled “Flying Machines of the 21st Century?” It mainly dealt with the question “How is it possible that quantum fault-tolerance is impossible (or really really hard) while classical fault tolerance is possible (and quite easy). Aram claimed that my conjectures, if true, exclude also classical computers.

Aram’s second post entitled “Nature does not conspire” dealt mainly with correlated errors. Aram claimed that it is unreasonable to assume strong correlation of errors as my conjectures imply and that the conjectured relation between the signal and noise is in tension with linearity of quantum mechanics.

Aram’s third  post “The Quantum super-PAC”  raised two interesting thought-experiments and discussed also intermediate models.

Each post ended with a small rejoinder, and included a short description of the ealier discussion.  The discussion was quite extensive and very interesting.

What’s next

Aram and Steve Flammia wrote an interesting manuscript with appealing counterexamples to my Conjecture C. Our next planned post (it now has appeared) will discuss this matter.

Next, I will conclude with a post discussing Aram’s two main points from his first and second posts and some related issues which I find important.

These posts are mostly written but since Aram was busy with pressing deadlines we waited several weeks before posting them. I also enjoyed the break, as the extensive discussion period was quite tiring.

A very short introduction to my position/approach

1) The crux of matter is noise

Of course, this is the main issue raised by skeptical physicists from the early days of the quantum computers idea.

Here the question is: What is the correct error-model for quantum computers? Another way to put it is: What are the feasible approximations for (pure) quantum evolutions and quantum states.

This issue is related to other aspects of quantum physics. When we discuss quantum computers we would like to control a quantum evolution up to a small error, but very similar issues arise if we want to describe a quantum evolution. Any such description requires neglecting some ingredients and this is where we need to understand the nature of approximations in quantum mechanics. Indeed, the art of expressing the effect of the neglected parts  is an important ingredient of various computations and theories in physics.

2) My conjectures are (suppose to be) strictly within Quantum Mechanics

Two disclaimers are in place: First, this point is challenged. Some people claim that it is simply impossible in principle to accept quantum mechanics and question the possibility of quantum computers.  Others raise some specific points about tension between my conjectures and QM, especially QM  linearity.  Second, my conjectures may well be in conflict with some specific claims, insights, and computation methods in the quantum physics literature. In fact, this is what make them interesting.

3) Developing a theory for modeling “non fault-tolerance quantum evolutions” is a valuable goal, independently of the feasibility of quantum computers.

Here is a lovely (and funny) picture by Daniel Gottesman,


Daniel Gottesman’s picture

Non fault-tolerance quantum evolutions refer to understanding of Daniel’s “desert of decoherence.” This is important whether fortified island of quantum fault tolerance can or cannot be created (or whether or not they are witnessed already in nature).

A taste of the discussion: Aram’s thought experiments.

I found the discussion really good. Of course, it is especially valuable for me, since it gives me an opportunity to test my conjectures against various technical and conceptual critique and it also gives me an opportunity to see what other people’s views are. I am very thankful to Aram and the other people involved for this opportunity. But I think that the discussion is also of value both to experts on quantum fault tolerance and to people interested in quantum information. Of course, I will be the first to remind people yet again that the overall stance of the quantum information community is that universal quantum computers based on quantum error correction can be built.

Let me give you a taste of two of the issues raised in the discussion (that I do not plan to discuss further in my last post.) Aram’s third post included two interesting thought-experiments. Aram’s first thought experiment offered to build a certain photonic quantum computer in a quiet intergalactic place. One of the difficulty with this suggestion is that as long as we do not understand what can go wrong with such an architecture on earth, moving it to outer space gives little help. This is also related to something Scott Aaronson wrote. (Congratulations again, Scott, on the Waterman award!) Scott said that we all agree that building a quantum computer is really really hard. Not so fast, Scott. Why is it really really hard? Without understand this hardness from first principles it will be difficult to build quantum computers or to tell if it is just “really really hard” or impossible.

Aram’s second thought experiment was thoroughly discussed in the comment thread. It relates to the fundamental question if we can have “protected” noiseless quantum process hidden in a noisy quantum process.” My conjecture 2 asserts that this is impossible. Aram’s idea was to somehow look at a huge environment around our noisy quantum process. This leads to a sort of “who will guard the guards” situation.  At the end, I think we are in agreement that this will not work (but some participants in the discussion had some thoughts on how to salvage it.)

A manuscript by John Preskill, the Caltech visit and pairwise positive correlations

One pleasant surprise was to learn that, motivated in part by our discussions in Caltech a year earlier, John Preskill wrote an interesting manuscript which pushes further the boundaries of the threshold theorem. Caltech was a fun visit. I gave a lecture which went nicely and then we had a two hours discussion with the QI group on my stuff. At the end, John challenged my claim that pairwise positive correlations can lead to error synchronization. I got a bit confused and for some time I thought that John was right. So it gave me an opportunity to make some jokes about invoking my malpractice insurance, etc. On the way to my apartment (which I shared with Keith Lee), I realized that my claim was ok. Actually, the distinction between 2-locality in terms of sums of 2-local Hamiltonians and between a description via 2-local constraints and the classical counterparts are quite important. It is related to fascinating issues in error correcting codes (classic and quantum) and in Hamiltonian complexity theory. A sort of related claim was raised by Aram on his second post.

An open problem by Tselil Schramm and me from the Caltech visit is if the name “Euro Pane Bakery” is meant as a pun (which will immediately make it a double pun).


How the debate came about?

Last June, Aram wrote to me regarding my last arxived paper, raised a few interesting questions, and proposed discussing them either privately or publically. (Actually one of Aram’s remarks required a  more careful formulation of my Conjecture 1). At that time, I preferred a private discussion so I wrote a detailed reply, and almost forgot about it. Later in November, Aram commented about my paper on GLL, and following it we decided to go ahead with a public discussion/debate on this matter that Dick and Ken kindly agreed to host on GLL.

Related posts new and old

During the debate there were several intermediate posts on GLL related directly or indirectly to the debate.  My own blog involvement started in 2006 over the Quantum Pontiff – Dave Bacon’s blog.  The Quantum Pontiff had at the time several nice discussions on related matters and my two-qubit and error-synchronization conjectures came up in one of these discussions. The first response to my conjecture came from John Sidles, see the second picture from the top of the post. At that time, I had the feeling that my skeptical view annoyed Dave so to cheer him up and to explain my philosophy I linked to my name the picture at the top of this post. (But Dave did not notice it untill now.) Beside that, on Shtetl-optimized, Scott Aaronson is quite interested in quantum computer skepticism and he discussed or referred to this issue in a large number of posts over the years. In some cases the discussion was quite interesting.

Touching base with Robert Alicki

One thing that I have learned as a byproduct from this debate is that Robert Alicki spend the year in Israel and it was great to  meet Robert again.

A last piece of trivia

I never met Aram, Ken or Dick, and I am looking forward to.

This entry was posted in Computer Science and Optimization, Controversies and debates, Physics, Quantum, Updates and tagged , . Bookmark the permalink.

6 Responses to The Quantum Fault-Tolerance Debate Updates

  1. Pingback: Quantum Refutations and Reproofs « Gödel’s Lost Letter and P=NP

  2. Pingback: Quantum World « Στα ίχνη της Γνώσης … Tracing Knowledge

  3. Pingback: Weekly Picks « — the Blog

  4. Dave Bacon says:

    I’m sorry I missed the picture you put together the first time. I’m always grumpy on my blog, but in real life I’m actually not quite so mean and thick headed.

    • Gil Kalai says:

      Dear Dave, we had nice discussions on the quantum pontif and I dont remember that you were grumpy. I had a feeling that the skeptical QC point of view annoys or saddens you and this is perfectly understandable. BTW, as I described in the very first post on this blog, the Pontiff was the first blog I heard about (from Greg K.). Also the graphic of your blog was different at that time and I tried to reconstruct it a little with the bluish background above.

  5. Pingback: The different forms of quantum computing skepticism | 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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s