# Request For Article: Many-Worlds Quantum Computing

Through a path more tortuous than is worth describing, I ended up talking to friends about the quantum effects which are exploited by photosynthesis. There's an article describing the topic we were talking about here.

The article describes how quantum effects allow the molecular machinary of the chloroplasts to "simultaneously sample all the potential energy pathways and choose the most efficient one."

Which is essentially how Quantum Computing is usually described in the press too, only we get to set what we mean by "most efficient" to be "best solution to this problem".

Since I usually find myself arguing that "there is no wave collapse," the conversation has lead me to trying to picture how this "exploring" can happen unless there is also some "pruning" at the end of it.

Of course even in the Copenhagen Interpretation "wave collapse" always happens in accordance with the probabilities described by the wave function, so presumably the system is engineered in such a way as to make that "most efficient" result the most probable according to those equations.

It's not somehow consistently picking results from the far end of the bell-curve of probable outcomes. It's just engineered so that bell-curve is centred on the most efficient outcomes.

There's no 'collapse', it's just that the system has been set up in such a way that the most likely and therefore common universes have the property that the energy is transferred.

Or something. Dunno.

Can someone write an article describing how quantum computing works from a many-words perspective rather than the explore-and-then-prune perspective that it seems every press article I've ever read on the topic uses?

Pretty please?

I'd like to read that.

## Comments (55)

BestI'm about to start writing up my doctoral thesis in experimental quantum computing.

If people are interested I might be able to write a few posts introducing quantum computing/quantum algorithms and many worlds over the next couple of months. I'm by no means an expert in the theory side, but I'll try to chat about it with people who are.

From a personal perspective it might help me to start the words flowing.

At first I wanted to say, "Please do, that would be awesome!", but then I realized it may not be within the domain of 'refining the art of rationality'. Anyone have any rationalizations so that we could talk about quantum computing at Less Wrong? There have been posts on the singularity, after all.

By the way, if you haven't already viewed it, Michael Nielsen's talk at the singularity summit is fascinating: Quantum Computing: What It Is, What It Is Not, What We Have Yet to Learn.

Ah, thanks for the link. The only summit video I've seen before was Jurgen Schmidhuber's, perhaps I should watch more of 'em.

They're definitely worth taking the time to watch, imho. I've gone through most of them over the past couple of weeks, and have just a handful more to watch (and will probably skip Kurzweill and the econ/vc ones). My favorites so far have been Schmidhuber, Hutter, Drescher, and Nielsen (Quantum Computing). Anna Saloman's talks were both very good as well, as was Eliezer's if you haven't heard his existential risk and cognitive biases lecture many times before.

Learning more about quantum computing and physics would (for most of us) result in more accurate models/beliefs/priors, so it seems on-topic to me.

Having said that though, we have to draw the line somewhere, otherwise any scientific topic would be on-topic, such as "analysis of proteins contained in the albumen of chicken eggs", which I doubt many of us think belongs on this site.

Since physics and computing are so foundational -- witness their frequent discussion and the long sequences that Eliezer devoted to quantum physics -- I think we could safely say that any general topic in physics or computing that has ramifications for rationality in other contexts (that we are likely to make use of), as is the case here with quantum computing, is welcome to be discussed, and that suggests a broader criterion for scientific topics as those that have ramifications for rationality in other contexts and that we are likely to make use of.

This reddit engine supports multiple categories or something, right? Why not have a "Physics" channel?

First of all consider a computer is incomplete without a program, so lets just think of a programmed computer - whether in hardware or software doesn't matter for our purposes.

This gives us a system that goes from some known start state to some outcome state through a series of intermediate steps. If each of these steps is deterministic, then the entire system reaches the same outcome in all universes where it had the same starting point.

If those steps were stochastic, perhaps because there is chance of memory corruption in our computer or because of a random guess, than in some universes the system arrives as a different outcome, based on the probability of that branch of the intermediate states. This can produce many branches, but because each of these branches cannot affect the others the result is tree of intermediate states, leading to the outcomes of our computer and its program.

Now, both of these are classical computers, but it helps to know what a classical computer looks like in a many worlds interpretation, before mapping a quantum computer there. This is because all computers, classical or quantum share a property - they are computers. This means there must be a path from the starting state to the outcome state. We can influence that path in many ways, but the path is part of how we define and build a computer and a program.

In quantum mechanics, there is a phenomena called entanglement, which loosely means that the events in very similar worlds can affect the probabilities of events in all of those worlds. You can think of this as the boundaries between the many worlds smoothing out as you get to a small scale.

This means that unlike our stochastic tree of states, the quantum computer can have a more complex structure. It is even possible, for two branches to converge back into one and to have branches cancel out.* In practice, these are more approximate than precise, so you will find a dominant combination of two branches or a near cancellation. Using this interaction a skilled quantum algorithm designer can use a variety of tricks to make correct answers more likely, by canceling wrong answers, and by increasing the probability of correction ones.

There is no uniform solution to this problem, for example, the best known quantum algorithm, the Shor algorithm for prime factorization exploits frequency of a possible prime factorization using number theory. This works well on quantum computers because the frequency difference is also a critical value for determining the probability of the combination of two quantum variables.

In each case, a computer and its program produce a path of execution, but by exploiting the features of or needing to deal with the problems of non-determinism and quantum mechanics, the nature of that computation becomes more complex and difficult to see. Any one world's view is not sufficient, especially in the case of quantum computing where the probabilities which govern a world's execution are not derived solely from within that world.

Thanks folks, sounds like the entire point of quantum computing is to avoid the kinda differences in interpretation that Copenhagen/MWI are concerned with, so my suspicion that a MW computational image would help is mistaken. Which is good, read around some Quantum Algorithms a bit. Have a better grasp of how that actually works than the terrible "explore all possibilities and pick the best" line that seems to come up so much.

Still leaves me a bit at a loss with these quantum effects in photosynthesis though:

Seems likely that line about "simultaneously sampling all the potential energy pathways and choosing the most efficient one" is just as misleading as the similar line in explaining how to quantumly factor a number.

Humm. Oh well. Can't expect to clear up all my confusion in one day. It's Friday Night, I should go find something fun to do.

Quantum computing is

totallyfun.My post does describe a distinct model based on a Many Worlds interpretation where the probabilities are computed differently based on whether entanglement occurs or not - i.e. whether the universes influence each other. It is distinct from the typical model of decoherence.

As for photosythesis, it ought to behave in much the same way, as a network of states propagating through entangled universes, with the interactions of the states in those branches causing the highest probabilities to be assigned to the branches which have the lowest energy barriers.

Of note, there are other, more esoteric models based on even more unusual interpretations of quantum mechanics, but I suspect that's not something we need to get into here.

Right now it looks unlikely that a quantum algorithm is being enacted anyway.

The key to a quantum algorithm is getting wrong answers to cancel out (opposing complex amplitudes) and right answers to build up (harmonizing complex amplitudes). Exploring all branches simultaneously is

easy. Thehardpart is getting the evolution of a linear, unitary quantum process to make "wrong" configuration amplitudes cancel and "correct" configuration amplitudes add. Peter Shor's critical insight in the quantum-factoring algorithm had something to do with the circularity of something to do with factors (I don't know the details).See here (and linked pages).

*2 points [-]Voted down for being off-topic. Feel free to delve into a deep discussion about the merits of doing this and what should be considered off-topic. Meanwhile, I'll say what I have to say anyway. Feel free to delve into a deep discussion about the merits of doing

thisas well.The thing is, quantum mechanics

lookslike the Copenhagen interpretation. That's why Copenhagen hasn't been falsified. We've barely managed to produce any evidence against it. (I'm not considering its low-ish prior probability to be evidence, of course.) Therefore, if you want to explain an observed phenomenon, it's perfectly valid to explain it in terms of wavefunction collapse.Note to self: ponder, and write something about, when it makes sense to explain something in terms of a mechanism you don't know exists.Saying that a quantum algorithm is "simultaneously sampling all possibilities and choosing the best one" has always been, I've found, a strange way of putting it, since it suggests that quantum computing can do a lot more than it actually can. (Quantum superintelligence: simultaneously sample every possible process of reasoning and choose the most interesting one. Unfortunately, you can't actually do that.)

A quantum algorithm such as Grover's algorithm simply works by changing the probability amplitudes (i.e. the heights of the wavefunctions, the things that can interfere constructively and destructively, the things that determine the probability of each outcome) in such a way that the probability of the desired answer is much higher than the probability of any other answer. ("Probability" here is just a specific function of probability amplitude, which happens to be consistent with both quantum evolution and the laws of probability.) When you perform the observation, then, the majority of Bornstuff goes to the world where the answer observed is the desired one.

How does Grover's algorithm work, specifically? Well, there's a plane where one line is the algorithm's starting point, and another line is the correct answer; it uses reflections to rotate the point for a certain amount of time, until it's very close to the correct answer. I dunno. For details, see Wikipedia.

Using the same logic:

That's why Russel's teapot hasn't been falsified. We've barely managed to produce any evidence against it. Therefore, if you want to explain an observed phenomenon, it's perfectly valid to explain it in terms of Russel's teapot.

http://en.wikipedia.org/wiki/Russell's_teapot

Though I think you could have picked a better analogy (specifically, one that makes significant predictions about the future), I agree with what you're saying. Let me say what I should have said:

The thing is, quantum mechanics

lookslike the Copenhagen interpretation. The Copenhagen interpretation and the many-worlds interpretation are practically identical in the predictions they make. Therefore, if you want to explain an observed phenomenon, it's perfectly valid to explain it in terms of wavefunction collapse.*0 points [-]The same "logic" would actually be:

Analogy fail.

*0 points [-]Um, I

didsubstitute directly into the text of the post I was quoting from.I shouldn't need to spell this sort of thing out - but the main problem with both the Copenhagen interpretation and Russel's teapot is that they violate Occam's razor - not that there is observational evidence against them.

Your analogy fails to, well, be analogous if you include the first sentence of Warrigal's full argument. I don't disagree with you about Occam's razor; I just think you argued the point poorly.

*1 point [-]Voted down because I think your downvote is silly, perhaps even absurd. pre is attempting to overcome a common misunderstanding that appeals too much to the human intuition. He is attempting to do so by eliminating his own confusion. More on topic than a lot of the stuff we yabber on about.

*1 point [-]Is every attempt at overcoming an intuitive misunderstanding on-topic? Should we have articles about the different sizes of infinity*, the fact that every pair of different real numbers has a rational number between the two, the fact that ZFC has countable models, and so on? Should we post tutorials about monads, calculus, and special relativity in order to eliminate confusion about those topics?

I don't think so. We aren't a general-purpose academic blog. We cover topics that aren't covered elsewhere; topics we don't cover are covered elsewhere. Whatever it is we do, this makes us better at it.

It would be nice if we had a good definition of rationality. Please don't cite Eliezer's "epistemic rationality" and "instrumental rationality"; by those definitions, knowing Mandarin and Spanish probably makes a person roughly as rational as knowing Bayes' law.

* In ZFC, which has an axiom stating that infinite sets exist.

*1 point [-]Possibly. If they are suitably interesting to enough of us.

Yes please. I haven't looked into that too much.

Well, if you really want to. That's more 'trivial' than off topic.

I'm a bit rusty on that one too.

Which kind? That word does overtime.

If it is particularly high quality.

If someone requests an explanation and someone is willing to take the time then by all means.

Yes, I could go back to, for example, a MENSA newsgroup or assorted blogs that cover specific academic blogs for every different topic. But I don't want that. The signal to

wooratio is far too high. At least here there are specific cultural pressures in place to counter some of the worst kinds signalling bulls@#$ that hinders the discussion of actual information. I can tolerate this particular place without leaving in disgust for longer than at most other places where I engage intellectually.I liked those two definitions when they were supplied. The reason that I liked it was that I had been quite often making replies pointing out the difference between those two issues when 'rational' was being thrown around recklessly. Being supplied with 'epistemic' and 'instrumental' as labels saved me typing. I suspect I will much prefer those two definitions than the one you are aiming for. They are simple references to the technical issues. Alternative usages that people sometimes throw about tend to be far more about using the term as an indicator of in-group status and all the kinds of things that the in group people do. For example I've seen 'rational' being thrown in when 'in fitting with libertarian philosophy' would be more appropriate.

The good thing about the karma system is that we don't need to agree. You can vote stuff down and I can vote stuff up. If enough people prefer your exclusive focus on, well, whatever it is that you are trying to focus on then you will get your way. If not, then you can simply ignore the thread and you lose only several seconds parsing the (quite informative!) title.

*2 points [-]Voted up for being a valid, well-argued position that I can clearly see isn't just a mistake. I do wonder, though, if being this sort of general-purpose web site is something we could actually pull off. What causes us to have our unusual level of quality? Do we attract people who tend to be especially tolerable? Do we train people to be especially worthwhile?

I think significant evidence for the former is the fact that virtually everyone here uses capitalization and punctuation (I have seen

onecounterexample, and much fuss was made over it) and, for the most part, correct spelling and grammar. I assume that reading Yudkowsky doesn't cause one's language abilities to improve. I would hate to see what would happen if someone incapable of spelling reasonably well came on here.(Can I mention that using "the reason being" as a determiner phrase irritates me? It sounds like a misinterpretation of the dependent clause "the reason being that X" as being the independent clause "the reason being is that X".)

I think we attract people who favour a certain type of thought, one that I find relaxing to engage with. I may suggest that it is the style of thought that sometimes begets labels like 'autistic spectrum'.

Firefox spellchecker. Grammar incapabilities would be a problem. Although I suspect proficiency with grammar comes with the aforementioned turf.

Now that I reread the phrase it makes me cringe. Edited.

Shirley understanding yew possible obtain conditionally at writer intelligence? Pure concept only necessary at communicate, intelligence writer mind have intelligence concept, mode of language transmission mere inconvenient.

Conversely, the idiom tongue is the lips of a giggling crow.

*0 points [-]"Epistemic rationality" and "instrumental rationality"

arethe standard terms.Reason is deduction plus induction plus Occam.

Rationality is using reason to pursue goals.

What do you mean by "standard"? They're not so well-accepted by the community that I like them.

*0 points [-]I mean that it's not really a case of "Eliezer's "epistemic rationality" and "instrumental rationality"" - since he didn't originate those terms.

The terms do seem to be a bit duff. The underlying concepts are OK - but IMO, the terminology leaves something to be desired.

When I said 'Eliezer's "epistemic rationality" and "instrumental rationality"', I was talking specifically about this. Perhaps I'm mistaken, and these definitions are an oral tradition passed on through the generations by mouth before Eliezer finally wrote them down.

*1 point [-]Er, there were plenty of pages on the internet about "epistemic rationality" and "instrumental rationality" long before that. Like I say, they are the standard terms:

http://en.wikipedia.org/wiki/Instrumental_rationality

http://www.amazon.com/Theory-Epistemic-Rationality-Richard-Foley/dp/0674882768

Indeed, misleading and annoyingly common and the kinda thing that's always encouraging my more cosmic hippy friends down blind alleys. I'm hoping to find a better way, it seemed to me that MWI might have done that.

Maybe it doesn't, I'm certainly not an expert, hard for me to tell without being able to read a good one :)

This is better, certainly:

Not far off my assumptions in the original request which is always encouraging.

Yes, I think that's a good explanation. One question it raises is ambiguity in thinking of QM via "many worlds". What constitutes a "world"? If we put a system into a coherent superposition, does that mean there are two worlds? Then if we transform it back into a pure state, has a world gone away? What about the fact that whether it is pure or in a superposition depends arbitrarily on the chosen basis? A pure-state vertically polarized photon is in a superposition of states using the diagonal basis. How many worlds are there, two or one? This interpretation can't be more than very metaphorical - it is "as though" there are two worlds in some sense.

Or do we only count a "world" when we have (some minimal degree of) decoherence leading to permanent separation? That way worlds never merge.

The explanation of QC in terms of MWI will vary depending on which interpretation we use. In the second one (worlds on decoherence) the explanation is pretty much the same as in any other interpretation. We put a system into a coherent state, manipulate it into a pure state, and the measurement doesn't do anything as far as world splitting.

But in the first interpretation, we want to say that there are many different worlds, once for each possible value in the quantum registers. Then we change the amplitude of these worlds, essentially making some of them go away so that there is only one left by the time we do the measurement. It's an odd way to think of worlds.

I agree that unitary wavefunction evolution is a MUCH better name than the misleading "Many Worlds".

Then, of course, you say that computation takes place within the evolving wavefunction and that you are part of that computation everywhere certain patterns in that computation take place. Still some handwaving here, but SO MUCH better than the standard misunderstandings of Many Worlds.

Thanks, I've been wanting a better name to use than 'Many Worlds' for some time! To be honest I would have settled for 'Greebo' or "Bliggle', so long as it got away from the confusion bait.

I advocate "no collapse."

Even though it has a technical meaning, I think "unitary wavefunction evolution" would be worse for communication than "Greebo."

That works.

I suspect you are right. This leaves me with 'Greebo', 'QM without collapse' or, I could just say 'quantum mechanics' and choose not to talk to people about such topics when they persist in advocating a collapse beyond the first time they hear it isn't necessary.

This made me chuckle. I suppose that as the intelligence and amount of knowledge held by the average member of an intellectual group goes up, their lower bounds on the amount of knowledge someone must have in order for that member to have an intellectual conversation with them goes up as well.

I'm horrible at communicating clearly, so I'll give an example.

4chan poster: You're a scientologist!? Idiot.

RationalWiki member: You're a creationist?! I refuse to speak to you.

Less Wrong member: You insist that there is such thing as waveform collapse in quantum mechanics?! I see you cannot be saved.

Creationists I can accept. Ardent 'qualia' and 'philosophical zombie' advocates on the other hand I will not speak with. Creationists often acknowledge that their beliefs are based on faith. 'Qualia' folks are more likely to claim philosophical or intellectual authority, invoking my eternal contempt. This ties back in with your original point: it's about having intellectual conversations. For me at least it is those encroaching on intellectual territory in particular that must be held to higher standards.

That's a good point. I've never actually interacted with someone in real life that even knew what philosophical zombies were, so my 'intellectual' conversations take place along the lines of 'atheism versus theism', sadly. Maybe there is some merit to joining Mensa after all?

*0 points [-]Do you like debating? That is, do you like throwing about very clever non-sequiturs and a whole bunch of straw men to prove your high status amongst a tribe of high IQ monkeys?

I've let my membership lapse. I keep in touch with some of the guys to play games with but the MENSA around here is mostly an online thing and decidedly inferior to lesswrong as far as intellectual stimulation goes. Although I must admit some of the Mensa guys were great to get business and professional advice from.

Interesting. Sounds like you're saying that the entire process of quantum computation aims to keep the system coherent, and so avoid splitting the universe. Which make sense. They tell me the difficulty, in an engineering sense, is to stop the system de-cohering.

Is that remotely accurate?

Yes. Except that the universe doesn't ever split. It's always continuous. But we're trying to keep two blobs of amplitude in close contact rather than letting them diverge, so that some parts can overlap and add up or cancel out.

This makes me wonder something. It seems that the many-worlds theory involves exponential branching: if there's 1 world one moment, there are 2 the next, then 4, then 8, and so on. (To attempt to avoid the objection you just raised: if 1 pure state, defined intuitively, has significant amplitude one moment, then . . .) Since this grows exponentially, won't it eventually grow to cover every possible state? Admittedly, the time this would take is more or less proportional to the number of particles in the universe, and so I really don't know how long it would take for coinciding to happen, but it seems that this would produce observable consequences eventually, maybe-maybe-not while minds are still around.

Yes. The process is observable as entropy. And the extremum (equalization of most or all of configuration space) is the conjectured heat-death of the universe.

I agree that equalization of configuration space is the heat death of the universe. I'm not sure, given this, that there won't be significant interaction until most of the decay has occurred.

Ugh. To be honest, quantum computing is a waste. A complete dead end. So you can do a few calculations a little faster. Big deal. The same efforts would be better spent on improving manufacturing methods so that we can turn out products faster, especially those that involve shaping of scrap metal.

Was torn between upvoting and downvoting this but decided on downvote after deliberation.

*0 points [-]Okay, here is how I think it might work - I am not a quantum computer programmer, so take my ideas with lots of salt.

Imagine a completely classical world. Imagine a bit (e.g. a coin faceup or facedown) inside of a container (e.g. a cup). Imagine a fundamental physical operation something like shaking the cup. If you don't know whether the bit is faceup or facedown, then you might imagine that inside the cup are two superimposed worlds. That is, you can imagine that the world is one possibility thin where you are, and then bubbles out to be two possibilities thin inside the cup.

When you shake the cup and then open the cup, one way to describe what happens is that the superimposed worlds "collapse", nondeterministically, into one of the possibilities. This is something like popping the bubble. Another way to describe what happens is that the bubble expands through you, splitting you, and one of the copies sees one of the possibilities, and the other copy sees the other possibility.

We can model entanglement in this classical world - imagine taking the cup-coin combination, and passing it through a duplicator. You still don' t know whether the coin is heads or tails, but "collapsing" one will also "magically" collapse the other.

This is all well and good, you say - but it isn't quantum computation.

My understanding here is fuzzier. As I understand it, there's an additional "imaginary" dimension in the quantum computation than there is in the classical possibility-worlds that we've been talking about. Sometimes, the bubble or stack of possible worlds, when viewed from the outside, can have constructive or destructive interference, as if the different worlds were transparencies that one can stack and look through.

To the QC novices - does that make sense? To the QC experts - is that even roughly true?

I recommend some reading: http://en.wikipedia.org/wiki/Quantum_computer Start with this and then if you want more detail look at: http://arxiv.org/pdf/quant-ph/9812037v1 The math isn't to difficult if you are familiar with math involved in QM, things like vectors, and matrices etc. http://www.fxpal.com/publications/FXPAL-PR-07-396.pdf This paper I skimmed it seems worth a read.

As to the author of the post to whom your responding what is your level of knowledge of quantum computing and quantum mechanics? By this I mean is your reading on the topic confined to Scientific American and what Eliezer has written or have you read for example Bohm on Quantum Theory?

Vague grasp of what the maths is

supposedto do, without ever having actually worked through most of it. More than just SA and Eleizer, but mostly pretty much around that level.The trouble with the explore-and-prune way of describing these things is it automatically makes people fall into speculation on what's doing the choosing, how maybe 'consciousness' is picking the 'best' of the results and shaping the universe.

Understand enough to know it ain't that, and that the maths tells us the probabilities of the outcomes, there's no 3rd party 'picking' the one most advantageous to 'em.

But it's hard to get people to understand that without a good intuitive picture of what's really going on, just seemed to me that the problem was probably the 'collapse-like' system which everyone seems to fall back on when trying to produce this intuitive picture.

Personally I should probably work through the maths at some point. It's on the list. The list is long though and I have a goddamned job so I never seem to get proper time for stuff.

Not sure that having done that would help to convince people who certainly won't be working through the numbers that there's no special consciousness effect going on though.

*0 points [-]That's quite an intuitive QC explanation as far as I can tell but I don't think it was what pre was after.