Figures 3 and 4 are...interesting?

I must admit, I still don't get why there is all the fuss about entanglement sudden death. This paper gives a nice summary of results, and I was hoping it would help me understand the fuss. Isn't it obvious that entanglement (as measured, say, by concurrence) gets destroyed in a finite time? It is also true, for example, that classical markovian noise destroys the resources necessary to classically compute after a finite amount of time (because it can be strong enough to get under the threshold for classical computation.) Anytime you talk about a resource which has different functionality in different regimes aren't you going to get "sudden death." What am I missing?!?!

One point which is not clear to me is how realistic it is to consider >2 body interactions which are long range. For example, if I try to use perturbation theory gadgets to get these interactions, it seems to me that the number of ancillas needed to couple a single spin to the rest of the spins is equal to the size of the system. Where do you put these extra spins? (i.e. assume that you have long range 2-local interactions, how do you turn these 2-local interactions into long range 4-local interactions in 2 or 3 spatial dimensions?)

What Scott said: http://scottaaronson.com/blog/?p=369

An example of a quantum proof of a classical computer science problem which, at least if you know quantum computing, is much simpler. (Of course your mileage will vary according to your comfort with quantum computation.)

I finally got a chance to read this paper which has been sitting on my desk since it was published. This is a very cute result about Kitaev's toric code (and a host of related models.) Basically the authors show how the ground state of Kitaev's toric code can be thought of as a MERA state. What this means in practice is that they show a series of unitary transformations followed by a discarding of qubits such that the toric code stabilizer on a lattice is mapped to a toric code stabilizer on a lattice with double the lattice constant. I'm still trying to wrap my head around uses for this, but I'm sure there are some out there.

The original GHZ paper. It's interesting that the abstract says "deterministic" local model. I would say that Bell's theorem rules out all probabilistic or stochastic local models.

An extremely interesting model of qubits in the presence of wormholes between different times. This is short, sweet, and probably deserves to be widely pondered.

Maximal p-norm multiplicativity had previously been shown to be violated when p>4.79, then for all p>2, and now, in this paper, for all p between 1 and 2. This indicates that approaches to proving the additivity conjecture using the Renyi entropy, if they are to work, need to approach p=1 from the 1>p>0 region.

Hey I never said it was unreasonably fast switching all the time! I had question marks on my comment! (But just to press the point wouldn't the times for dynamic decoupling pulses be unreasonable, if, for instance, you wanted to use it to get rid of spontaneous emission for a standard ion trap qubit?)

The pulse intervals in this paper can be so small because the interactions between the nuclei in the bath are so weak (~10 Hz), right?

BTW, it is a nice paper and am impressive numerical simulation.

Just a clarification. My argument about the lambda involved applies not just to system-bath coupling, but also to system coupling. I agree that under suitable (although experimentally daunting?) settings dynamic decoupling might help with the first, for the second, i.e. for the universal part of your construction, I don't see how imprecision in the universal Hamiltonian can be overcome. This later setting (i.e. universal Hamiltonian error) is what most troubles me.

"In short, as a purely theoretical exercise it is interesting to ask if AQC can be made fault tolerant without introducing any fast timescales."

I disagree that it is purely theoretical. If I were to write down a way to perform FT QC with only adiabatic interactions, I'm sure some experimentalists would be extremely happy. BTW. The problem is that your title pretty much insinuates that you're doing everything adiabatic. Maybe you need an (*) where you can write "with fast decoupling pulses."

I'd also point out that a full fault-tolerant adiabatic quantum computer would be a big step in proving the quantum equivalent of the PCP theorem, so it's not something that is just a child's playtoy, I think.

2b) Touche! I'll take that black eye.

3) "may be" is not very definitive.

Look the problem is fairly simple, right? I mean suppose you have a single qubit interaction of strength lambda on each qubit. This will give an energy shift of order lambda^2/gap (okay so of course there are all sorts of sublties here, since the single qubit terms will excite high energy states as well as low energy states, but still for simple models, this will be of the right order, I think, since you have n single qubit terms contributing.) Now you want this shift to not destroy the gap, so you want lambda^2/gap to be less than 1/poly(n). Thus your lambda has to be less than 1/O(poly(n)), right?

Oh yeah, and I forgot. Another reason to not call just error correction/protection (in whatever form it may come) fault-tolerance is because the major source of errors in most implementations of quantum computers right now are the gate / movement errors.

p.s. sorry for the editing problems, comment system still in alpha, apparently.

Ding, ding, ding. Round 3. Wait I'm fighting the guy who taught me quantum error correction. He knows all my moves. Doh.

2a) My conservative view comes because what I think is important to determine whether adiabatic quantum computing, as a universal quantum computer, is _by itself_ a robust model of computation. Practically, bringing in fast pulses may or may not be fine, it depends on your physical system, of course. Further such a result might be important, if for example, you were a well known critic who wrote a critical paper on fault-tolerant quantum computers.

2b) I think we differ on that deep philosophical issue of whether a simulation of adiabatic evolution is really adiabatic evolution. I personally think (a matter of my liberal thinking probably) that since if for all practical purposes you cannot tell a simulation for the real thing then you might as well call it the real thing :) The point however is that if you have fast gates like you need for the dynamic decoupling result, we already know how to make a fault-tolerant simulation. On the other hand, I do agree that it would be silly to not use dynamic decoupling, if you really are in that super fast gate regime where it will work.

3) I've read reference 12 many times. I'd love to hear the details because my reading is that while there are cases where noise doesn't hurt (and can help) it is also clear that for a realistic model, adiabatic evolution is just not inherently robust. For a more recent critique which I think is serious see http://arxiv.org/abs/quant-ph/0608212v1

2a) My point was that if you had a system which previously only had adiabatic evolutions, this scheme would not be of use. Thus, from an architectural standpoint, calling this an adiabatic quantum computer seems a stretch. Poor D-wave with its adiabatic architecture won't be able to use your scheme, no?





2b) Suppose I have really fast gates. I use standard fault-tolerant quantum computing. I implmenent the evolution exp(iH(t) dt) for small dt as a circuit. I do this repeatedly. I see little if no difference. If you insist that adiabatic quantum computation must involve continuous time, then I will insist that you show me a continuous measuring clock.





3) I think the word "fault-tolerant" should be reserved for constructions which tolerate ALL the relevant errors. Thus I think the papers you cite (including my own) use the word incorrectly. I would further note that thresholds exists in schemes which are not fault-tolerant. For example quantum error correction has a threshold, the memory threshold, but I wouldn't call a simple threshold quantum error correction scheme fault-tolerant. But this is mostly symantics and I'll admit that I myself have done nothing to uphold the sacred use of the word "fault-tolerant." But I'll bet if you get the right/wrong referee's they'll nab you on this :)





I disagree with your interpretation of reference 12. In particular, for example, with single qubit errors the paper shows that the adiabatic algorithm fails. The coupling must scale like 1/n (n:=number of qubits) in order to not harm the algorithm. This seems like an unreasonable physical assumption.




Oh, and you should site your own paper Daniel ;)

According to the title of this paper, it claims to show how to make an adiabatic quantum computer fault-tolerant. The basic way in which it does this is to use dynamic decoupling schemes. Annoying the main calcualtion for this decoupling scheme is a reference [15] which has not been published. But beyond this minor detail, there are two major reasons why I do not believe this paper merits the title, so to speak, and that a true theory of fault-tolerant adiabatic quantum computation still awaits full illucidation.

The first reason is perhaps a matter of taste. The dynamic decoupling schemes used here require fast switching, which is pretty much the opposite of adiabatic coupling. Thus I wouldn't call the described system in an adiabatic quantum computer anymore. Why does this matter? Because there is already a trivial way to achieve fault-tolerant adiabatic quantum computation in this regime. Simply use the circuit model to simulate adiabatic evolution. There you can use fast gates in a starndard fault-tolerant scheme and then use standard simulation results to simulate the desired adiabatic Hamiltonian. To me, both of these feel like cheating. The goal of a fault-tolerant adaibatic quantum computing, in my mind, is to _always_ work with slow interactions. (Now whether measurement (slow, fast, natural) is allowed is another question for these constructions, one about which I am more agnosti.)

The second problem is, I think, more damaging. This problem is that the construction detailed about is not fault-tolerant in the error correcting sense of the word. In particular, which the construction detailed in the paper is for a universal set of controlling Hamiltonians (for AQC), there is no method to deal with errors in the encoded Hamiltonian. Sure nothing outside of the universal set of terms survives the dynamical decoupling, but on the other hand, errors in the strengths of these couplings are not addressed. Thus, unlike in fault-tolerant constructions, where even the gate errors are taken care of, in this construction errors in the Hamiltonian coupling strengths are not corrected.

In conclusion, this paper describes a dynamic decoupling scheme which can be used for universal adiabatic quantum comptuation. However, for the two reasons illucidated above, I do not believe it shows how to build a fault-tolerant adiabatic quantum computer.

I don't understand the claim in this paper about the quantum glued trees algorithm. In particular the claim seems to rest on claims about the inappropriateness of the oracle model. The authors seem to claim that if they restrict the orcale where the trees are glued together to be polynomial time evaluatable, then they can use this information to extract information about the permutation in the middel of the graph. Doesn't this contradict everything we know about one-way functions?