## Reigniting flame wars is my solemn responsibility

The New York Times on Yau. Thanks to Hoeteck Wee.

The Blog of Scott Aaronson

*Quantum computers are not known to be able*

to solve NP-complete problems in polynomial time,

and can be simulated classically with exponential slowdown.

to solve NP-complete problems in polynomial time,

and can be simulated classically with exponential slowdown.

The New York Times on Yau. Thanks to Hoeteck Wee.

Comment #1 October 17th, 2006 at 12:06 pm

Hmmmm … that

Timesarticle is pretty damp wood for starting a flame war. The summary of the article seems to be Yau is an outstanding mathematician, a committed teacher, and a reasonably decent human being, who has has encountered some significant problems and complications in the political arena. Duh.To start a flamewar, we need more kindling! So let’s link Yau’s geometric view of quantum mechanics to today’s Michel Dyakonov preprint Is Fault-Tolerant Quantum Computation Really Possible?.

Dyakonov’s preprint is only the latest broadside asserting his longstanding point of view that “the quantum computer is an analog machine and it is of secondary importance that this analog machine obeys quantum, rather than classical laws.”

As an engineer, what I like about Yau’s work is its emphasis on a geometric understanding of quantum dynamical processes, and what I like about Dyakonov’s preprint is its emphasis on physical realism and well-posed challenge problems. Also, both authors regard quantum processes as continuous, rather than discrete, which is a point of view that is very congenial to engineers.

Remark I: it is perfectly OK to regard quantum noise as a discrete process, (see, e.g., Mike and Ike’s sec. 8.2.4, Preskill’s notes sec. 3.3). But when we do so, we commit ourself to an algebraic point of view in which it is almost irresistably convenient to regard measurement processes and gate processes as instantaneous POVMs. This is an approximation that Dynakov justly criticizes as physically unrealistic. Furthermore, an exclusive focus on algebraic approaches tends to cut us off from the geometric insights and tools of Yau’s geometric school.

Remark II: It is a chess maxim (due to Tarrasch) that “when you see a good move, look for a better move.” In quantum engineering this maxim becomes, “when you see a quantum system design problem, look for a worse problem” (however discomfiting this search may be from an agnotological point of view).

So to ignite the holy flame of blogging inquiry, I will ask three questions.

Q1: Isn’t it true that Dyakonov’s challenge problem (Sec. 10) is fair, regardless of what one thinks of the rest of his preprint? This challenge being: “Let us focus on the simplest, almost trivial task of storing just one qubit and let us verify the statement that its initial state can be maintained indefinitely in the presence of low-amplitude noise.”

Q2: To make the Dyakonov’s challenge more realistic, shouldn’t we allow not only uncorrelated Markovian noise on the elementary bits, but also noise in the coupling constants of gates and unitary transforms? And shouldn’t we extend the challenge to maintaining indefinitely the quantum entanglement of three qubits (effectively, an error-corrected three-qubit storage register)?

Q3: And finally, shouldn’t we try to achieve a Yau-type geometric understanding of Dynakov’s challenge problem? The reason being, that even if Dynakov’s challenge is met, practical devices will have to be designed and built by quantum engineers, and geometric understanding is very useful to engineers.

I will remark, that if Dyakonov’s challenge can be met, it would surely provide a worthy chapter in future textbooks on quantum system engineering. And my personal opinion is that, for engineers, a Yau-style geometric analysis will provide the most useful understanding of this challenge problem.

Comment #2 October 18th, 2006 at 3:57 am

In his “longstanding point of view”, Dyakonov claims that an assembly of many qubits is similar to a system made of many classical spins.

Has anyone ever bothered to define precisely

a computation model based on this “classical spin” idea? If one could show that classical spin systems can be simulated in polynomial on an ordinary Turing machine, this would definitely show that Dyakonovs’s analogy is flawed (unless P=BQP!).

Comment #3 October 18th, 2006 at 5:31 am

John, the dry tinder was near the end:

In a twist, a flaw has been discovered in the Cao-Zhu paper. One of the arguments that the authors used to fill in Dr. Perelman’s proof is identical to one posted on the Internet in June 2003 by Bruce Kleiner, of Yale, and John Lott, of the University of Michigan, who had been trying to explicate Dr. Perelman’s work.In an erratum to run in The Asian Journal of Mathematics, Dr. Cao and Dr. Zhu acknowledge the mistake, saying they had forgotten that they studied and incorporated that material into their notes three years ago.

Comment #4 October 18th, 2006 at 5:33 am

OK, let me do all the questions and answers. If classical spin systems are what I imagine they are, the reason why one should be able to simulate them in polynomial time is that they do not allow for any entanglement :

the state of the system would be a product of one-qubit states.

If like everyone else, Dyakonov is reading this blog, I would like to have his opinion!

Comment #5 October 18th, 2006 at 6:16 am

let us verify the statement that its initial state can be maintained indefinitely in the presence of low-amplitude noiseThis is impossible. Fault-tolerance results tell us we can reduce the effective noise on an encoded qubit with a polylogarithmic overhead in resources. This allows us to increase the time we can reliably store an initial state, but not indefinitely.

Since even a polylogarithmic overhead is presently a daunting challenge to experimeters, such proof-of-principle experiments will be extremely limited, but they will most certainly be appearing in the near future.

shouldn’t we allow not only uncorrelated Markovian noise on the elementary bits, but also noise in the coupling constants of gates and unitary transforms?Threshold theorems already allow for both.

I have shamelessly adopted Scott’s retort to criticisms of fault-tolerant quantum computing. The critics are essentially saying they don’t believe quantum mechanics, and it would be nice if they’d (a) be more honest about it and (b) specify exactly where they expect quantum mechanics to break down.

Comment #6 October 18th, 2006 at 9:36 am

Gee, it’s nice to see these comments.

I wonder whether some people are criticising Dyakonov’s preprint, without having read it?

Dyakonov’s calculations do

nottreat qubits as classical objects. In fact, his calculations do not depart from quantum orthodoxy in any respect.Rather, Dyakonov argues that because fault-tolerant algorithms have become central to building actual quantum computers–with many young people’s careers at stake, and large resources invested in expectation of a practical benefit—it is now obligatory to do a detailed end-to-end design analyses of these algorithms.

In particular, Dyakonov’s thesis that we should be “extremely vigilant to the explicit or implicit presence of ideal elements within the error-correcting theoretical schemes” is a well-accepted principle in engineering.

To show why, I will mention that last week, the Chair of our Mechanical Engineering Department spent several hours evaluating (in the Chair’s office!) a “working prototype” of a perpetual motion machine.

Needless to say, this machine wasn’t

quiteworking yet … it needed only a few “minor” improvements in a few “inessential” mechanisms. The point being, that Dyakonov’s suspicion of ideal elements is well-founded in engineering practice.It is often the case that elements that seem innocuous from an algebraic point of view seem unphysical from a geometric point of view. One example (of many) is projection operators that satisfy P^2=P. When one actually designs devices that implement projection operators, it is much more common to obtain operators that satisfy

(P^dagger)^2 P^2 = P^dagger P

which is not at all the same thing! The difference amounts to a phase noise that has a natural geometric interpretation as a “fuzz” on the state space trajectories.

My own (very tentative) opinion is that, per the classic rabbi joke, “everyone is absolutely right.”

Given any one error mechanisms, or a few of them, then a fault-tolerant design can be found. These algorithms are wonderfully ingenious, and they point to deep theorems in many areas of mathematics–we’re surely a long way from understanding what they mean. But it is equally well-justified to ask whether the resulting ensembles of quantum trajectories are geometrically physical — they are Hilbert-space filling fractal-like manifolds whose resolution along certain axes can be made arbitrarily fine, according to the error-threshold theorems.

Dyanokov’s challenge problem is, IMHO, a good way to illuminate these issues.

Now, when doing direct quantum simulations, my laptop can handle Hilbert space dimensions of up to 2^18 (thanks,

Mathematica!). But it is not clear (to me) whether 256,0000 dimensions is enough to protect even a single qubit against realistic errors, much less two or three entangled qubits.Nonetheless, it would be fun—and highly instructive—to give Dyakonov’s challenge a try, specifically, by attempting to error-protect the entanglement of two or three qubits, implementing all calculations with weak POVMs, finite detector efficiencies, and error-prone unitary transformations.

Maybe over the Holidays?

Comment #7 October 18th, 2006 at 10:43 am

“I wonder whether some people are criticising Dyakonov’s preprint, without having read it?”:

John, The analogy with a system of classical spins does not come from the preprint but from the abstract of an old talk by Dyakonov (“quantum computing: view from the ennemy camp”) that you pointed out in your first message.

Comment #8 October 18th, 2006 at 11:48 am

I wonder whether some people are criticising Dyakonov’s preprint, without having read it?OK. I admit I stopped reading it after the first page or so. Here are some quotes which should suggest why

1) “The enormous literature devoted uirto this subject is purely mathematical. It is mostly produced by computer scientists with a limited understanding of physics”

It’s rather surprising to hear Manny Knill, Wojciech Zurek, John Preskill, Alexei Kitaev and others described as computer scientists with a limited understanding of physics.

2) “the number of continuous variables that we are supposed to control, is 2^1000 ∼ 10^300.”

No. We’re supposed to control 1000 qubits, and infinite precision is not necessary even under ideal circumstances.

3) “This striking statement implies among other things that, once the spin resonance is narrow enough, it can be made arbitrarily narrow by active intervention with imperfect instruments.”

It says nothing of the sort.

4) “How is it possible that by using

only other identical pointers (also subject to random rotations) and some external fields (which cannot be controlled perfectly), it might be possible to maintain indefinitely a given pointer close to its initial position?”

It’s not.

Statements (3) and (4) are particularly troubling, as no-one who understood fault-tolerant quantum computing would ever say such things. So there is little reason to read the rest of the paper, except for the excellent drawing of a lion in Figure 1.

Comment #9 October 18th, 2006 at 12:30 pm

Chris, I completely agree with your emotional response to Dyakonov’s preprint … some of it is rudely & adversarily phrased in a manner that is completely unnecessary.

E.g., Dyakonov could have made his point about the need for theoretical caution and humility with regard to noise mechanisms much more politely, and with greater respect for academic tradition, by reference to (from my bibtex database):

@inCollection{Orbach:72, author = {R. Orbach and H. J. Stapleton}, title = {Electron Spin-Lattice Relaxation}, booktitle = {Electron Paramagnetic Resonance}, pages = {121–216}, editor = {S. Geschwind}, publisher = {Plenum Press}, city = {New York-London}, year = 1972, jasnote = {This article give a humility-inducing history of our understanding of spin-lattice relaxation, in which (a) theorists predict low relaxation rates, (b) experimentalists measure much higher relaxation rates, following which (c) theorists improve their theorys (d) experimentalists clean up their experiments, and (e) the cycle begins anew. Theorist: Waller Experiment: Gorter Theorist: Heitler, Teller, and Fierz, Kramers, Kronig, Van Vleck, Dyson, etc, 1932-1972. 146 references! } }

Notice, by the way, all the famous physicists whose names are cited!

I guess the main respect in which I differ with your post is with regard to line-widths. Here it seems to me that Dyakonov is raising an interesting point, which he does not fully explain … here’s what I made of it:

Suppose we have a fault-tolerant, two-qubit storage register. Then we can identify the (time-increasing) error probability of that register with a traditional linewidth via the following

gedankenexperiment:(1) Prepare an ensemble of 2-qubit registers, all having the same initialization.

(2) Perform the following step N times:

2A: store the registers for a time dt such that the error probability is amall

2B: remove the registers, apply a magnetic field (to lift the energy degeneracy of the qubits), and apply a traditional NMR 2pi-pulse to each qubit. Then apply a reverse magnetic field to undo the energy shift.

(3) After the N steps, read out the registers. The measured quantity is the no-error probability P(omega), where omega is the carrier frequency of the NMR 2pi pulse.

The whole point of error correction (it seems to me) is to increase the on-resonance probability P(omega).

So I agree that Dyakonov’s language is imprecise (error correction makes the spectral peak P(omega) get higher, not narrower), but still, his basic point that quantum error correction has well-defined and extremely interesting implications for spectroscopy, seems correct to me.

Comment #10 October 18th, 2006 at 4:54 pm

One technical point … Dyakonov’s challenge problem has a built-in “gotcha”. Namely, the stipulation that “All qubits experience continuous random uncorrelated rotations [and] once the ancillas are out of the refrigerator, they become subject to the same random rotations” suffices to guarantee that the overall Hilbert space has no decoherence-free subspaces.

Whether this is a fair restriction or not depends on your point-of-view (obviously).

Comment #11 October 20th, 2006 at 9:29 am

Golly, 48 hours with no responses. I … am … StopThreadacus … !!!.

Last night, I did something in bed that I had never done before—I read chapter ten

Quantum Error Correctionof Nielsen and Chuang! Yes, it was “good for me”!You see, for the great majority of practical quantum system engineering purposes, the elegant exegesis of chapters two, eight, nine, and eleven is all you need (and these chapters are pretty self-contained).

The portion of Nielsen and Chuang seemingly most relevant to Dyakonov’s challenge problem is section 10.2

The Shor Code. On first reading, it seems perfectly feasible to protect a a single-qubit storage register by iterative applications of the Shor code. Am I right in this?And surely, it is numerically feasible (but lengthy) to implement the Shor code in a manner consistent with the conditions of the challenge problem, i.e., white noise applied to each of the nine Shor code qubits, measurements by weak POVM, finite detector efficiency, noise also in gate transforms, errors in Bloch axis alignment, etc.

The part of the Nielsen and Chuang discussion that perturbs Dyakonov’s physical intuition, and thus motivates his challenge problem, is the assertion (p. 433) “The Shor code protects against completely

arbitraryerrors, provided they affect only a single qubit! The error can be tiny—a rotation about the Bloch axis by pi/263 radians, say.”I have to say, this statement perturbs my physical intuition too. If I were going to attempt the challenge—and I haven’t made up my mind to do so, ‘cuz it would be a lot of work—I would simplify it to “The weak Dyakonov challenge problem” by allowing all gates to be ideal and all Bloch axes to be perfectly aligned. But I would retain the nonideal Dyakonov elements of weak POVMs and finite detection efficiency for all measurements.

As for the challenge problem’s independent Markovian qubit noise, I would numerically implement it in the manner most congenial to engineers, namely, as a covert measurement process, rather than classical white noise. This is of course a purely conventional choice of noise POVMs that cannot affect the outcome of the trial.

This approach would give the Dyakonov challenge problem a unique informatic cast, and possibly some cryptographic content. “If someone is spying on your qubit, can you maintain its coherence?”

Surely, a central principle of quantum cryptography will be found lurking nearby!

Comment #12 October 23rd, 2006 at 7:22 am

I’m still thinking about making a holiday-season attempt to meet the Weak Dyakonov Challenge.

But it takes me a while to think about these things. And as Lowell Brown used to say, “Don’t start a long calculation until you know the answer.”

The key to the Weak Dyakonov Challenge does seem to be, “Can projective measurements be implemented with weak POVMs and finite detector efficiencies?”

Projective measurements are a good example of an quantum concept that is extremely simple and natural from an algebraic point of view, yet very complicated and hard-to-achieve from an engineering point of view.

What about the geometric point of view of Yau and his colleagues (that began this thread)? My present feeling is that Kähler geometry supplies the unifying conceptual link between the algebraic and engineering points of view.

The Weak Dyakonov Challenge seems to be a fun place to tie these ideas together.

Comment #13 October 24th, 2006 at 8:20 am

As the “keeper of the flame” for this thread, I will note that there is a complementary Dyakonov flame burning on Dave Bacon’s

Quantum Pontiff.Hmmmm … maybe “complementary” is not the right word? Many of the blogging posts are just as polemic as Dyanakov’s preprint.

When dueling polemics become widespread, isn’t that a pretty reliable indicator than neither side has good ideas or a clear plan (kinda like the Iraq War)?

Myself, I’m going to keep reading the gospel (namely, Mike and Ike Ch. 10), and also look forward enormously to reading Jonathan Israel’s second volume

Enlightenment Contested(when, oh when, will it reach this side of the pond?).Hopefully, these two works will prepare me for tackling the weak Dyanokov challenge over the holidays; a challenge that I am beginning to perceive as partaking equally of technology and agnotology.

Just to make two specific prediction:

(1) Over the next six months, we’ll all be reading reviews—in many different scholarly and popular journals—of both Israel’s

Enlightenment Contestedand its earlier volumeRadical Enlightenment. Some of us will even read the books ourselves.(2) Yes, people will take up Dyanokov’s challenge problem: physicists, mathematicians, and engineers, each in their own style, and we will all learn a lot in doing so.

We should prepare to have our agnotology perturbed … which is good.

Essential, in fact.

Comment #14 October 26th, 2006 at 3:41 pm

Gregory Perelman now has a myspace profile:

http://www.myspace.com/115573699