# Quantum Algorithms and the Strange Nature of Quantum Theory

Over at Information Processing, the InfoProcessor talks about teaching Bell's theorem:

I find that the hardest thing about teaching this material in class is that, after half a year of training students' brains to think quantum mechanically, it is extremely difficult to get them to feel the weirdness of Bell's theorem and spooky action. It all seems quite normal to them in the context of the course -- they know how to calculate, and that's just how quantum mechanics works!

In the comments an anonymous commenter says that this is all backward, that Bell's theorem isn't strange, and that we should just shut up and calculate. Which got me thinking. Now I personally think that Bell's theorem is an indication that quantum theory has components which are bizarre. I would never have predicted the world worked that way, and it is shocking that our naive ideas about "elements of reality" and "locality" aren't compatible with quantum theory. But there is also a long list of other things which make quantum theory seem strange. And to me these add more to the argument that quantum theory is indeed strange, above and beyond what just Bell's theorem by itself provides.

For example, there are large swaths of quantum algorithms which I find truly bizarre. Take, for instance, Simon's problem. In Simon's problem you are given a function from n bit strings to n bit strings. This function is guaranteed to be constant on an hidden xor mask. That is f(x)=f(y) if and only if x is equal to y+s (s not zero) where "+" here is a bitwise xor. The goal of Simon's problem is, given the ability to query the function f, identify the hidden xor mask s. Classically it is (almost laughingly?) obvious that this is difficult. To find s you really need to query two values of the function where f(x)=f(y) (from which you can find s by s=x+y...remember bitwise xor here.) But such collisions are exceedingly rare. Thus you need to query the function a huge number of times to figure out what s is (a bit of calculation shows you need something like 2n/2 queries). Therefore it is, to me, a complete shock, that if you are allowed to query this function quantum mechanically, then you can find the hidden xor mask s in about n queries. By asking quantum questions of machines in the world, we can obtain the answer faster than if you ask classical questions. And this is just the beginning of whole host of quantum algorithmic speedups which are, truly, quite shocking. And if you're not shocked by this result, then I guess you're really haven't understood classical information processing. That quantum theory leads to a different notion of information processing? That's absolutely astounding.

So I guess as I grow old and jaded, and while I certainly understand the calculations about quantum theory I perform, I find it more and more strange, not less and less, this bizarre quantum theory of our world.

Tags

### More like this

"I think it is safe to say that no one understands quantum mechanics."

Hah! Wayne Dyer not only mastered it but shows us, for \$29.95, how to apply to making money.

By JohnQPublic (not verified) on 03 Mar 2008 #permalink

I found that the weirdness of quantum mechanics and the power of quantum information is very well illustrated with quanum teleportation. Especially if you set up the roblem first and give the (QM) protocol after everybody is convinced it cannot possibly work.

Granted, this does not tell you about asymptotic complexity, but most undergraduate physicists do not really know much classcial information processing.

"That is f(x)=f(y) if and only if x is equal to y+s (s not zero) where "+" here is a bitwise xor. The goal of Simon's problem is, given the ability to query the function f, identify the hidden xor mask s."

Dave, that is awesome! I did not know about Simon's problem until this. Sorry for the sudden burst of uncharacteristic enthusiasm, but blogs like this allow me access to academic information I probably never would find otherwise.

By JohnQPublic (not verified) on 03 Mar 2008 #permalink

I dunno, I don't feel that nonlocality is all that weird. I mean, to me it's a very short step from "there are fields influencing things" (e.g. the magnetoelectric fields) to "oh yeah, and sometimes there are influences that don't have a speed limit" (influences 'causing' correlations, in this case). I mean, if we were insisting on a particle picture then it might be a bit unusual (since then the particles would be traveling faster than the speed limit), but if we're picturing the whole setup as a field (i.e. as Bohm does) then it seems quite reasonable. Of course this is all a lot of talk about how I "picture" things, so your mileage may vary.

It may be that I don't understand classical information processing, but I feel like I might be too grounded in math (or something) to be shocked by your next example either. There are two ways that I'm seeing this: 1) on a theoretical basis, we have Turing machines, and then we have Turing machines plus this magic quantum operation. "Obviously" this magic quantum operation will allow us to do new and possibly better things, no? 2) on a physical basis, if we're doing 'physical information processing' and querying the 'information processor,' then yeah, opening up the ability to query it via a different branch of physics seems likely to yield some different results and approaches.

Thoughts? Did I miss the point entirely?

Domenic: To me, at least, it is the combination of non-locality and no-signalling (actually more CHSH) that is particularly weird. Why are the correlations just so? Stronger than classically possible but weak enough not to allow signalling or non-local boxes. That's really not what I would naively have expected.

Yeah... that's a puzzling one. Why should everyday run-of-the-mill undergraduate non-relativistic quantum mechanics, which knows nothing about special relativity, just happen to be consistent with no-signaling? It's because of that question that I should either live much closer or much farther away from campus, making my walk either a bit shorter, or much much much longer. And I say that as though a two hour walk from my house to campus would actually help settle whether this is a huge coincidence or insanely deep. All I've managed to settle on is that it's probably not in the middle.

My experience has been that students really are suitably freaked out by Bell's inequalities. But maybe that's because I accidentally bias the expository discussions so that being freaked out is the "expected response." Really, I have to suspect that the response you get is a product of the spirit with which the curriculum is developed. I can definitely see that an extremely operational approach would numb people into a type of linear algebraic submission where little is surprising or unsurprising. I've had [very good] quantum mechanics classes that took very different approaches: one completely axiomatic and the other heavily dependent on physics constructions, like symmetries and conserved currents. The latter definitely brewed more wonderment.

So, back to my class. Now that we're studying the interaction between a two-level atom and the quantized electromagnetic field, I would say that no one seems particularly uneasy with the entanglement that is generated between the atom and the field, and I wonder why. Is it because they already got hit with teleportation last semester? Or is it because the mathematical process of quantizing Maxwell's equations induced the same catatonic state I complained about above? In any case, no-signaling got built into the theory because QED seems to know something about special relativity.

Maybe it's because we've doing intro quantum fields that lately I've been leaning toward the feeling that the connection between non-locality and no-signaling in non-relativistic quantum is just a huge coincidence and that Nelson Muntz must have been the person to establish the rules of the universe. It seems that stressing over that convenient agreement between non-locality and no-signaling would be much more productive if we didn't already have quantum field theory under our belts.

Or maybe maybe I'm now just jaded, like Dave. :)

By JM Geremia (not verified) on 03 Mar 2008 #permalink

What I find interesting about Bell's theorem is that a deceptively simple algebraic proof can make such a profound statement about the nature of reality, i.e., quantum correlations are too strong to be explained by purely local causes.

It's sort of like Fermat's last theorem, IMO. Something that looks to be a simple statement but was deep enough to avoid proof for 350 years.

Thanks for the clarifying comment, Joe; that is indeed the crux of the issue.

My impression is that the partition of causal influences into "correlations" (extant in QM) and "signals" (disallowed in QM) is not something inherent in SR, and so maybe the connection isn't as clear as you might at first expect. Bell himself often liked to point out that, while not violating the math of SR, Bell correlations definitely violated the "spirit" of locality (indeed, he has several papers in which he defines the term locality---in terms of light cones---and shows that QM violates it).

And as has been mentioned, QFT seems like it might create a whole host of new problems. Then again, it (hopefully) is wrong anyway in light of some theory of quantum gravity, so who knows if it's really an improvement to try to frame these questions in QFT instead of QM.

I apologize, since I was apparently very unclear. I was trying to make a statement about pedagogy, not about quantum mechanics or information theory, and I think that commenter Geremia phrased it much more eloquently than I did:

My experience has been that students really are suitably freaked out by Bell's inequalities. But maybe that's because I accidentally bias the expository discussions so that being freaked out is the "expected response."

Basically, if you tell students they should be totally freaked out by something, you are encouraging them to freak out over it. But being weirded out is simply not required in order to be struck by the wonder of it all, and to tell your students this is to do them a true disservice, as if they could not ever partake in the grandeur and beauty of the field.

You aren't initiating them into the mysteries of the Illuminati or something, you are providing a place to learn fundamental aspects of the universe as best we can describe it and an opportunity to partake of the wonder along with you. There is no weirdness in the rainbow created by total internal reflection, yet it is just as wonderful.

Er,

"and to tell your students this is to do them a true disservice, as if they could not ever partake in the grandeur and beauty of the field" should have "without being totally weirded out" or something similar at the end.

What happens when we arrive at the generation who thinks its easier to trust the math of quantum mechanics than to believe the non-intuitiveness of some of the odd features of classical mechanics? I say that because I've been alive the vast, vast majority since Bell's theorum's been tested and feel more comfortable with trusting quantum mechanics than believing my own eyes.

I thin I'm part of the generation that aren't so freaked out by Bell's theorem. To me non-locality/causality issues in QM never seemed like that big a deal. I think though that this had an aweful lot to do with the way in which I was taught classical mechanics and the way in which I thought about EM theory.

I did a lot of classical Hamiltonian mechanics in undergrad before learning any QM or QFT beyond the standard intro to the Schroedinger equation that everyone gets in 1st year.

What I always found more shocking is the way in which we use classical conjugate variables to determine our field theories. That always seemed random. Then again, if you showed me classical Hamiltonian dynamics without studying Newton's laws etc it'd probably seem pretty random as well.

*sigh* upon re-reading my comment I was really that clear as I didn't really elaborate on WHY I find it kinda unsurprising.

I think my first calculations involving Bell's theorem were all about demonstrating in particular physical systems the way in which Bell's inequalities are violated. To do this I was shown how to calculate the equations of motion for all of the observables that are used in the correlations functions for a CHSH inequality.

Looking at the Heisenberg equations of motion in these systems, it looked very much as though all of the non-classical or "entangling" correlations were due to the initial conditions of the equations of motion. Essentially the entanglement was created through an interaction between two particles (actually this was optics so it was field modes, whatever) and then the equations of motion for Alice and Bob's observables then behaved locally modulo the initial conditions.

Oh and I'm so with Dave when he says that Simon's algorithm is very surprising. There is a lot about quantum mechanics that I find really intriguing (otherwise I wouldn't study it for a living), and I think that Bell's theorem is really just the tip of the iceberg...

*sigh* upon re-reading my comment I was really that clear as I didn't really elaborate on WHY I find it kinda unsurprising.

I think my first calculations involving Bell's theorem were all about demonstrating in particular physical systems the way in which Bell's inequalities are violated. To do this I was shown how to calculate the equations of motion for all of the observables that are used in the correlations functions for a CHSH inequality.

Looking at the Heisenberg equations of motion in these systems, it looked very much as though all of the non-classical or "entangling" correlations were due to the initial conditions of the equations of motion. Essentially the entanglement was created through an interaction between two particles (actually this was optics so it was field modes, whatever) and then the equations of motion for Alice and Bob's observables then behaved locally modulo the initial conditions.

Oh and I'm so with Dave when he says that Simon's algorithm is very surprising. There is a lot about quantum mechanics that I find really intriguing (otherwise I wouldn't study it for a living), and I think that Bell's theorem is really just the tip of the iceberg...

Got to be honest and say I skimmed most of the posts, so forgive me if I repeat something someone else already said. In any case, Schrödinger felt the difference between the classical and quantum worlds boiled down to entanglement, i.e. the quantum world allows for the existence of entangled states while the classical world does not. I've heard classical or semi-classical explanations for virtually everything else except this (see Rob Spekkens' theory which is getting more robust as the years roll on). It is, of course, the existence of these entangled states that allows quantum computers to do things classical computers can't do. I seriously suspect that many of the surprising aspects of the quantum world you and others above have mentioned, can ultimately be traced back to the existence of and ability to manipulate entangled states.

Keeping the thread going agm: It's funny because I get so angry at people on TV who purport to be in the news and information industry but then inject a blatant political stance into the stories of the day (actually, I don't watch TV news- but why ruin a good story). By this argument, I guess we should teach quantum mechanics completely axiomatically and not prejudice people by telling them how the equations should make them feel. I can picture a very monotone lecture, "it would be historically accurate to point out that some physicists have expressed varying degrees of concern about this subject." And then... hope the class, now having seen the material for all of 15 minutes, immediately reinvents multiple generations worth of opinions on the subject ranging from "ho-hum" to "good god, satellites going to fall from the sky!".

I guess it is also our responsibility to bolster the pure mathematics with context, background, etc. Looking back, my favorite lecturers in both grad school and undergrad were people who infused their classes with a lot of extra stuff based on their own experience. After all, why else make someone stand in front of the class if not to provide perspective. So, to avoid doing too many disservices, I suppose, our goal should be to provide a fair and balanced presentation of quantum mechanics, just like FOX news, but not at all like FOX news.

In any case, following a talk by Paul Davies on time-travel last week, this discussion has inspired me to steal 15 minutes from today's lecture on the interaction picture for the electric dipole Hamiltonian and talk about why time-travel and quantum mechanics might not make good bedfellows. Fortunately, being a physicist, I'm not really sure what the word "bedfellows" means, so I expect I'll be able to avoid predisposing people to any particular opinion. Seriously though- it's good to think about this stuff, because I'll definitely go to lecture today making a conscious effort to be more fair to GR, rather than to hate Roger Clemens for no reason besides being a registered Democrat.

Dave: sorry I've been so absent from your blog for a while now... you know... the whole "new academic position" thing got the best of me. Fortunately, UNM electricians killed the air handler to my lab (yet again), so I have some free time on my hands. :)

Entanglement isn't so strange, and is perfectly allowable classically, unless you use redefine entanglement to mean "entangled enough to be classically forbidden". The only hard part is that two things can be correlated without this being because they actually have definite values for all possible measurements.

Roger Clemens is a Democrat? What Barry Bonds? Are all the (acused) steriod users Democrats?

JMG:
I think we largely agree here, at least about basing things without an easy physical intuition on an axiomatic approach. Or rather, a physically-informed axiomatic approach. I'm teaching for the first time this semester, intro physics with a focus on conservation laws of fundamental quantities since I want to emphasize way of thinking instead of equations. I'm seeing way more than ever before how weird normal people think physics and physicists can be, even if I think that obtuse mathematics aren't weird anymore, just unfamiliar.

Perhaps a more important question is whether we ever reach a point where the practitioners are weirder than the practice :-)

"Perhaps a more important question is whether we ever reach a point where the practitioners are weirder than the practice"

Stephen Wolfram comes to mind. A New Kind of Science??

By JohnQPublic (not verified) on 04 Mar 2008 #permalink

... [that I am] ... --- I should probably read what I write before I hit "post" to avoid grammar problems that also reverse the meaning of my statements. :)

By JM Geremia (not verified) on 04 Mar 2008 #permalink

Aaron:

What Schödinger and others meant was that there does not seem to be a classical analogue to maximally entangled states, i.e. non-factorable states.

The whole idea that there is anything 'weird' (as opposed to simply unfamiliar) about quantum mechanics (and arguably the non-locality in QM as well) is merely the result of certain prejudices we import from our experiences with macroscopic objects plus a good dose of beguiling historical practice.

The primary reason that QM seems weird is that people insist on taking QM to be offering a description of the dynamics of classical particles, i.e., that wave function is some kinda of weird probabilitesque smear of a classical point partical. Even many physicists who would reject this description if asked still at some level conceive of what is going on in this fashion. However, I would argue that this is exactly what Bell's theorem and some of strong non-locality type theorems are rejecting.

Instead a better way to understand QM (well basic QM though something similar can probably be said about field theory) is as the study of *wave functions*. This approach to talking about QM would avoid the silly talk about objects being in two places at once or being both particles and waves (they are neither they are wave functions). While these concerns are perhaps less likely to trouble a real scientists I certainly think it would be a better approach to describing the subject.

As far as non-locality is concerned the problem is easily solved by eliminating collapse. Or more precisely emphasizing that collapse is only an apparent property of the system. While it was super confusingly written Everett's original paper on this handled the math to show that in a no collapse view an observer's experiences mimix exactly the properties of collapse. As long as we stay away from stupid names like "many worlds" which points in exactly the wrong way (the point is that there is one physical reality filled with wave functions that gives rise to experiences in a way that creates the perception of collapse) what's the problem?

Sure from a philosophical point of view or a common sense one this position might be mind boggling but you can't complain about having a simple elegant theory that fits the facts because you don't like what it predicts.

TruePath, how in the world can you justify the idea that the collapse doesn't really happen? You have a wave function of an electron say coming from a source at the center of a sphere, then there is a "hit" at some specific spot on the sphere. The electron can't be anywhere else, and it could have hit any spot. You can't really explain why it ended up in one spot rather than another, and if you do the experiment over (to whatever degree of "sameness" is possible in principle to attain) the hit could be anywhere on the sphere, it has no relation to that one instance. In looking at what you have said, and the descriptions I see of "decoherence", I see nothing but double talk and circular arguments about "appearances" of collapse "not really" being collapse etc.

You also have to take into account the Renninger negative result or partial collapse issue, where failure of a reliable detector to measure a hit (on say a hemisphere) forces redistribution of the WF to the other half direction, but it still hasn't collapsed (in the sense of being reduced to a specific locale.)

To me the Pauli exclusion principle embodies some of its own quantum weirdness.

How does a fermion "know" at a "distance" what the quantum states of all nearby fermions are, in order to choose its own unique set of quantum numbers? What if the collection of neighbors is very large, as in a neutron star?