My Quantum Debate with Aram II

This is the second of three posts giving few of the non-technical highlights of my debate with Aram Harrow. (part I)

After Aram Harrow and I got in touch in June 2011, and decided to have a blog debate about quantum fault-tolerance towards the end of 2011, the first post in our debate was launched on January 30, 2012.  The first post mainly presented my point of view and it led to lovely intensive discussions. It was time for Aram’s reply and some people started to lose their patience.

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

Flying machines of the 21st century

Post II, February 6, 2011. First of three responses by Aram Harrow

Dave Bacon was the patron saint for Aram’s first post.

(Aram) There are many reasons why quantum computers may never be built…  The one thing I am confident of is that we are unlikely to find any obstacle in principle to building a quantum computer.

(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. If you want to prove that the permanent requires super-polynomial circuits, you need an argument that doesn’t apply to the determinant. And if you want to disprove fault-tolerant quantum computing, you need an argument that doesn’t also refute fault-tolerant classical computing.

From the discussion

Why not yet? Boaz set a deadline

(Boaz Barak)  could [you] explain a bit about the reasons why people haven’t been able to build quantum computers with more than a handful of qubits yet?

Joe, Aram and Matt gave insightful explanations, which Boaz summarized:

(Boaz) From these answers I understand that right now the effort of constructing quantum computers does not seem “stuck” at any concrete bottleneck but rather has been making significant progress against several difficult challenges…  I guess that if the next decade will pass without significant additional progress, then it may make sense to start asking if there are fundamental obstacles to this enterprise, but right now there is no reason to assume this will be the case. 

Matt

(Matt) Hey, why is my awesomely insightful comment still awaiting moderation?

Matt gave awesomly insightful comments on quantum codes vs. classical codes, Bose-Eisnstein condensation, and Anyons. 

(Matt) Regarding .. anyons… Hopefully soon it will be more clear. Perhaps Majorana fermions systems will provide a cleaner test soon.

(Marijuana?)

Two-locality round one

(Joe Fitzsimons) The fact of the matter is that we know in excruciating detail the physics of how low energy particles interact with one another, and can use this to say a lot about the type of noise that a given quantum computer is subject to. The 2-local restriction on Hamiltonians found in nature significantly reduces the scope for correlated noise.”

(Gil) Excellent point!

Aram’s second post came a week later:

Nature does not conspire

Post 3, February 15, 2012: Second response by Aram Harrow

The patron saint for post 3 was Albert Einstein

(Aram) The possibility of a high rate of correlated errors seems reasonable in many ways. Claire Mathieu points out that independence of random events is the sort of thing that often gets blithely assumed, when actually it’s a major assumption. Independence is attractive … but … it is also dangerous

Quantum computing (probably) requires producing large entangled states to be interesting. Gil suggests that this entanglement may be self-limiting, by increasing the rate at which correlated errors occur. This is one of the routes he proposes for generating highly correlated errors in quantum computers. The key reason I regard this as unlikely is that quantum mechanics is linear…

…Another route to correlated errors is by piggy-backing on our computation….. for the heat to cause bit flips in just the right way to overcome software error correction would require an incredibly unlikely conspiracy of events—a conspiracy that doesn’t have a plausible mechanism, and that isn’t observed in practice.

Close your eyes

(Gil) Let me propose a thought experiment. It is so imaginary that I ask you to close your eyes.

Imagine a quantum mechanical world where in order to prepare or emulate a quantum state you need to create a special machine. Each state requires a different kind of machine. Of course, there are some quantum states you can design but cannot prepare at all, and for others it may take decades to build the machine.

…

And now open your eyes. This is the world we live in.

(I was inspired by some lawyer-movie, but I don’t remember which one.)

From the discussion

(Matt Leifer) I am trying to understand Gil’s rejoinder, but I find it a bit difficult to read the description of his thought experiment with my eyes closed 

Blind quantum computation

(Joe) However it seems like such piggy-backing is essentially impossible in general if it must only affect entangled states and not separable states, due to the existence of blind quantum computing protocols.

(This post by Joe gives an introduction to blind quantum computing and to Joe’s (and coauthors)  Science paper on experimental support for the concept.)

We discussed this blind computation issue quite a bit and went back and forth . Twenty comments later…

(Gil) I think we discussed the blind computation issue quite a bit (and it is also mentioned in my papers). I tried to express my thoughts about it as well as I could, and perhaps it is time for us to keep thinking about it off-line

(This is a single time in the debate that I lost my patience; once too much…)

It was time for Aram’s third post, which contained two exciting thought-experiments.

The Quantum Super-Pac

Post 4, March 5, 2012. What unlimited contributions might buy you in power

John Preskill was the patron saint for this post.

Needing Eve’s Advocates

(Aram) Especially while much of our field [quantum information]  is in a theoretical phase, we need more people like Gil to play “Eve’s advocate” and push forward increasingly sophisticated theories of how noise can foil us.

(Nice; I can not argue with that.)

Aram’s first thought experiment:Intergalactic QC

(Aram) One approach [for showing that quantum computers are possible in principle] would be to put the quantum computer in a place where there is very little noise other than what we introduce ourselves, like interstellar space.

(Gil) A quiet intergalactic setting will not remain quiet once we put our device there. Aram’s suggestion to choose a quiet intergalactic place reminds me of Woodstock. I have a “Woodstock number” of 2, since Jeff Kahn with whom I wrote some of my best papers was actually in Woodstock. Woodstock was a place with very little noise, but when you run a concert for a million people in this noiseless place, it will be noisy—in principle!—no matter how much money you throw at it.

Aram’s second thought experiment:Redefining the QC 

(Aram) An even more “imaginary” quantum computer sets up a view of the real world that connects to Preskill’s paper, and provides another thought experiment that refutes Gil’s conjectures. … We simply redefine what we call the “computer” to include all of the qubits in the environment that interact with it. This gives us a quantum computer that is definitely in a pure, highly entangled state, performing calculations that we have no idea how to simulate in sub-exponential time.

(Gil) So,  Aram, regarding your new even-more-imaginary quantum computer. Do you really think it is a good idea to throw the entire universe at my conjectures?

(Aram) It doesn’t have to be the entire universe.

(30 comments later…)

(Aram) Thinking about this more, it is pretty hard to make my second thought experiment work  without something drastic like bringing in the entire universe.

In the comments

Peter Shor

(Peter) (Regarding my conjecture:) …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.

Well… (2-locality again)

(Joe)  …It is simply that your conjectures (including your talk about special purpose devices) is simply incompatible with what we know about physics. You seem to now be doubting that all relevant interactions are 2-local for pretty much all systems we consider because it is in tension with your conjectures. However, we know this to be true: the Ising interaction is 2-local, the exchange interaction is 2-local, dipole couplings are 2-local, photon emission and absorption are 2-local, Coulomb repulsion is 2-local. The list goes on and on. Even literally tripping over the power cord is a series of (strong) 2-local interactions.

well

(Well!)

(Gil:) Joe has made an appealing and interesting argument against my conjectures which goes as follows:

1) All physical processes known to us are 2-local, namely the Hamiltonians can be described by terms acting on at most a pair of particles.

2) If we relax the condition of the threshold theorem and assume that the Hamiltonian describing the noise contains only terms corresponding to pairs of qubits the threshold theorem will still hold (with a smaller threshold).

3) Therefore conjectures 3 and 4 about correlated errors are in contrast with what we know from physics.

Giving up

There are different approaches about giving up.

(John Sidles) Don’t give up too soon, Gil!

(Gil) For me, giving up (on such matters) is always an option. Give me a good argument, or a good experimental evidence, and I will give up with no regrets.

Returning to Joe’s 2-locality

(Gil) It is probably time to carefully examine some aspects of Joe’s interesting locality argument. In a sense Joe’s argument is like “fighting censorship with censorship”, as it uses an interesting censorship hypothesis on the nature of natural (uncontrolled) quantum processes (2-locality) to “fight” conjectures which propose some limitations on the type of feasible states and evolutions  of controlled quantum evolutions.

(Here I refer to a well-known line by John Preskill regarding quantum fault-tolerance: “we have learned to fight entanglement with entanglement.” At the end it was John Preskill himself who explained why both parts of Joe’s 2-locality argument don’t work.)

(John Preskill)  Two-locality is not sufficient… [2-locality] alone is not enough to ensure scalability… Two-locality is not strictly true. Qubits are not elementary particles; they can actually be quite complicated objects,…

(Joe) You raise important points, …  perhaps this is a flawed idea, but I think  that it expresses what I feel is unphysical about Gil’s proposed noise model.

(It was a good point, Joe, but it was incorrect.)

Elijah

(Elijah) what distinguishes machines built by natural processes from those built or designed by man. We know Nature has built it’s version of a classical computer , what about the possibility of a natural quantum computer?

Q (Major Boothroyd)

My thought experiment: The analogy between quantum computers and universal James Bond cars.

(Gil) The James Bond car is a collective name for a series of remarkable general-purpose cars, created by Q (Major Boothroyd) for Agent James Bond (007) in the James Bond movies.  Can we have a universal James-Bond car? And is a universal James Bond car (or a universal machine) a better analogy for quantum computers compared to the common analogy with universal computing devices like digital computers (or  perhaps, the human brain)? For the analogy with James-Bond cars we can forget about the computational purposes of quantum computers and think about them as machines that create complicated quantum evolutions and states.

(Aram) But I write this message on a universal (classical) computer.  It’s even running several different programs *simultaneously*.

(Gil)  This is the crux of the matter: If quantum computers are analogous to digital computers (that can be built) or to a universal James Bond car (that cannot be built).

Blind quantum computers revisited

The universal James Bond car analogy was a good opportunity to return to the blind computation matter.

(Gil) If you assume that you can build a universal James Bond car then probably you can build also an advanced model of a blind James Bond car where James, sitting in the car as the rest of the universe does not know if the machine is an airplane and he is a pilot, or the machine is a submarine and he is a sailor, or the machine is a toaster and he is toast.

A pilot, a sailor, or toast?

Factoring and motivation

(Cris Moore, very first comment!) I am also a little confused by Gil’s motivation for his conjectures. It’s reasonable to take as a physical postulate (as Scott does) that NP-complete problems can’t be solved by a physical device in polynomial time… But I don’t see why the factoring problem deserves this status.

(Gil) I beg to disagree. Factoring deserves high status. An efficient practical algorithm for factoring will be off-off-scale achievement. I don’t remember witnessing in my academic life any scientific/technological achievement so surprising. Therefore, any specific proposal for efficient factoring should be carefully and skeptically examined. (Regarding motivation, 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.)

APPENDIX: MY CONJECTURES

Conjecture 1 (No quantum error-correction): In every implementation of quantum error-correcting codes with one encoded qubit, the probability of not getting the intended qubit is at least some , independently of the number of qubits used for encoding.

Conjecture 2 (The strong principle of noise): Quantum systems are inherently noisy with respect to every Hilbert space used in their description.

(To avoid the discussion about the entire universe we later restricted ourselves to quantum subsystems of noisy systems.)

Conjecture 3: A noisy quantum computer is subject to noise in which error events for two substantially entangled qubits have a substantial positive correlation.

Conjecture 4: In any quantum computer at a highly entangled state there will be a strong effect of error synchronization.

Sure/Shor separator: For some (small) constant , pure states on  qubits that can be approximated by noisy quantum computers can be approximated by depth- quantum circuits.

Smoothed Lindblad evolutions conjecture: Realistic noisy quantum systems can approximately be described (at any time interval) by smoothed Lindblad evolutions.

Rate of noise conjecture:  The rate of noise in a time interval is bounded below by a measure of non-commutativity of the unitary evolutions  in this interval.

Conjectures 3 and 4 are for noisy quantum computers (and supplement usual assumptions about them). My papers describe these conjectures in formal mathematical terms. Conjectures 1 and the Shur/Shor separators still relies on the tensor-product structure of the underlying Hilbert space. Conjecture 2 and the conjectures on smoothed Lindblad evolutions and the rate of noise are for general quantum systems. Smoothed Lindblad evolutions are formally described in my papers. A formal version of Conjecture 1 was proposed during the debate:

Conjecture 1 (no quantum error-correction): Denote by  the trace-distance. There exists  with the following property. Consider a realistic device which encodes a single qubit with  qubits. Suppose that  denotes the encoded state of the single-qubit state . Then there are two states  and  so that  and

The sure/Shor separator replace my original “Conjecture C” for which Steve Flammia and Aram Harrow found a counterexample.