{"id":928,"date":"2005-05-27T09:19:46","date_gmt":"2005-05-27T16:19:46","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=928"},"modified":"2005-05-27T09:19:46","modified_gmt":"2005-05-27T16:19:46","slug":"928","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2005\/05\/27\/928\/","title":{"rendered":"It's Quantum So Should We Be Surprised?"},"content":{"rendered":"

Over the past few years there have been quite a few results where methods of quantum computing have been used to prove or reprove results about classical objects. Among these are lower bounds on locally decodable codes (de Wolf, Kerenidis, Wehner), limitations on classical algorithms for local search problems (Aaronson), a proof that PP is closed under intersection (Aaronson), and ways to use quantum communication complexity to prove lower bounds on classical circuit depths (Kerenidis). Now we have more to add to this mix, with quant-ph\/0505188<\/a>, “Lower Bounds on Matrix Rigidity via a Quantum Argument” by Ronald de Wolf (CWI Amsterdam). The rigidity of a matrix is the number of entries in a matrix which need to be changed in order to bring the rank of the matrix down to a certain value. What Ronald does in this paper is show how to use a quantum argument to prove some lower bounds on the rigidity of the Hadamard matrix. Very nice!
\nWhenever I see one of these quantum proofs of classical problems, I think, well: why are these quantum proofs significantly or slightly easier? But perhaps this thinking is backwards. Because the universe is quantum mechanical, should we really be surprised that the language of this theory is so powerful? One often hears the statement that it is amazing that mathematics is so useful for describing the physical world. But really this disregards the fact that different parts of mathematics are and are not useful for describing the physical world. So in a realm like computer science, where you are explicitly reasoning about physical systems, should it really be a surprise that the mathematics of these physical systems (quantum theory) is the best way to attack the problems?<\/p>\n","protected":false},"excerpt":{"rendered":"

Over the past few years there have been quite a few results where methods of quantum computing have been used to prove or reprove results about classical objects. Among these are lower bounds on locally decodable codes (de Wolf, Kerenidis, Wehner), limitations on classical algorithms for local search problems (Aaronson), a proof that PP is … <\/p>\n

Continue reading “It's Quantum So Should We Be Surprised?”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","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":[20,63],"tags":[],"class_list":["post-928","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-quantum"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/928","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=928"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/928\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=928"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=928"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=928"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}