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