{"id":1464,"date":"2007-03-16T08:49:43","date_gmt":"2007-03-16T15:49:43","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=1464"},"modified":"2007-03-16T08:49:43","modified_gmt":"2007-03-16T15:49:43","slug":"quantum-versus-classical-exponent-smackdown","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2007\/03\/16\/quantum-versus-classical-exponent-smackdown\/","title":{"rendered":"Quantum versus Classical: Exponent SMACKDOWN!"},"content":{"rendered":"

The world is quantum mechanical, damnit, and so (the party line goes) it shouldn’t be surprising if we find that a theory of computation based on quantum theory is more elegant than one based on machines whose concept of reality is so restrictive as to not allow cats both alive and dead. Okay, so we can say this half in jest, half seriously, but does it really hold any water? In order to solve this question of asthetics (joke about mathematics deleted), I propose that we hold a Quantum versus Classical beauty contest. Now since quantum computers are at least as powerful as classical computers, we can’t just say that an algorithm is better because it has a better runtime or better use of space, etc. Instead we need to use our artistic taste, i.e. pretend we have a clue about what it means for a result to be elegant (and yes, that was a dig at a certain popular science book \ud83d\ude09 )
\nRound 1<\/b>
\nSo I propose we perform this artistic measuring with a quantum versus classical exponent SMACKDOWN! (the exclamation mark is a part of the word.) Consider, for example, the recent quantum algorithm for evaluating a NAND tree (here<\/a> and here<\/a> with an explanation by the traveling<\/a> complexity theory salesman here<\/a>. Also the awesome NAND formula paper here<\/a>) This quantum algorithm has a running time of [tex]$O(N^{1\/2 + epsilon})$[\/tex]. Now compare this with the best and optimal classical algorithm for this problem. The result? [tex]$O(N^{0.753 dots})$[\/tex] where [tex]$0.753 dots approx log_2(1+sqrt{33})-2$[\/tex]. Bleh. Round One of the Quantum Versus Classical Exponent SMACKDOWN! most certainly goes to the quantum world. One half is certainly better than something which is has both a logarithm and a square root of thirty three!
\nRound 2<\/b>
\nBut ha, say the classical complexity theorists. What about Grover’s problem? Sure in this unstructured query search the quantum world achieves a speedup from [tex]$O(N)$[\/tex] classically to [tex]$O(N^{1\/2})$[\/tex] quantum mechanically, but look at your exponent. One half? Who the hell ordered one half. I mean if you had gotten log of N or even constant, then you would have something to brag about. But a square root speedup. Who ordered that? Round two of the Quantum verus Classical Exponent SMACKDOWN! most certainly goes to the classical world were weird square root speedups are not ubiquitous for straightforward unstructured query searches.
\nRound 3<\/b>
\nTo be continued!<\/p>\n","protected":false},"excerpt":{"rendered":"

The world is quantum mechanical, damnit, and so (the party line goes) it shouldn’t be surprising if we find that a theory of computation based on quantum theory is more elegant than one based on machines whose concept of reality is so restrictive as to not allow cats both alive and dead. Okay, so we … <\/p>\n

Continue reading “Quantum versus Classical: Exponent SMACKDOWN!”<\/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-1464","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\/1464","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=1464"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/1464\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=1464"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=1464"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=1464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}