{"id":1853,"date":"2008-03-03T10:55:31","date_gmt":"2008-03-03T17:55:31","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=1853"},"modified":"2008-03-03T10:55:31","modified_gmt":"2008-03-03T17:55:31","slug":"quantum-algorithms-and-the-strange-nature-of-quantum-theory","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2008\/03\/03\/quantum-algorithms-and-the-strange-nature-of-quantum-theory\/","title":{"rendered":"Quantum Algorithms and the Strange Nature of Quantum Theory"},"content":{"rendered":"

Over at Information Processing<\/a>, the InfoProcessor talks about teaching Bell’s theorem<\/a>: <\/p>\n

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!<\/p><\/blockquote>\n


\nIn 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.
\nFor 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<\/sup> 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.
\nSo 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.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 … <\/p>\n

Continue reading “Quantum Algorithms and the Strange Nature of Quantum Theory”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[63,65],"tags":[],"class_list":["post-1853","post","type-post","status-publish","format-standard","hentry","category-quantum","category-quantum-computing"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/1853","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=1853"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/1853\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=1853"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=1853"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=1853"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}