{"id":954,"date":"2005-06-22T07:21:40","date_gmt":"2005-06-22T14:21:40","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=954"},"modified":"2005-06-22T07:21:40","modified_gmt":"2005-06-22T14:21:40","slug":"954","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2005\/06\/22\/954\/","title":{"rendered":"Hyperbole Wednesdays"},"content":{"rendered":"

Two posts over at Quantum Algorithms<\/a>, one on D-Wave Systems<\/a> and another one on a supposed algorithm for solving NP-complete problems efficiently on a quantum computer.
\nWhen I was a graduate student at Berkeley, when a paper came out claiming that quantum computers could solve NP-complete problems, we would all race to see who could figure out where the problem in the paper was. I usually don’t like to write blog articles about papers like the one commented upon in Quantum Algorithms (for the preprint, see here<\/a>), but I’m not about to get a blogger username to just comment on the site cus I’m lazy, so I thought I’d just stick my comments here. As far as I can tell the paper is incorrect. In particular if you examine Figure 3, the circuit described does not perform as described. If I understand correctly, the state after the oracle gate is [tex]${1 over 2^n} sum_{x,y=0}^{2^n-1}(-1)^{f(x)}|y>|x>$[\/tex]. The author then applies a unitary gate between the y and x registers and then a measurement of the qubits. This is supposed to allow one to identify a place where [tex]$f(x)=1$[\/tex], but as far as I can tell, one only gets an exponentially small information about such a location if there is only one marked item.
\nThe other article on Quantum Algorithms points to an article<\/a> in the MIT Technology Review about the Vancouver based D-Wave systems. Here the hyperbole is even more mysterious:<\/p>\n

\nVancouver startup D-Wave Systems, however, aims to build a quantum computer within three years. It won’t be a fully functional quantum computer of the sort long envisioned; but D-Wave is on track to produce a special-purpose, “noisy” piece of quantum hardware that could solve many of the physical-simulation problems that stump today’s computers, says David Meyer, a mathematician working on quantum algorithms at the University of California, San Diego.
\nThe difference between D-Wave’s system and other quantum computer designs is the particular properties of quantum mechanics that they exploit. Other systems rely on a property called entanglement, which says that any two particles that have interacted in the past, even if now spatially separated, may still influence each other’s states. But that interdependence is easily disrupted by the particles’ interactions with their environment. In contrast, D-Wave’s design takes advantage of the far more robust property of quantum physics known as quantum tunneling, which allows particles to “magically” hop from one location to another.\n<\/p><\/blockquote>\n

It sounds to me, from the article, that the proposal is a quantum computer which implements a quantum adiabatic algorithm. The question of whether adiabatic quantum algorithms can be more efficient than classical algorithm is, from what I know, fairly controversial (see, for example, here<\/a>.) I would have a hard time telling a venture capitalist to put money in something quite so controversial, but hey, what do I know, I’m just a lowsy academic nerd and a chicken. If they can sell solutions to hard problem instances and actually succeed, then what do I know! And they will be rich!
\nUpdate: Suresh says I’m lazy<\/a>. And I am. So looking again at quant-ph\/0506137<\/a>, the main problem is already apparent in equation (5). There the author has miscontrued the tensor product. If we take the output of this circuit seriously, the initial state [tex]$|00rangle$[\/tex] is transformed into [tex]$0$[\/tex]. Not the state zero. The amplitude for the first qubit in this formula is zero. <\/p>\n","protected":false},"excerpt":{"rendered":"

Two posts over at Quantum Algorithms, one on D-Wave Systems and another one on a supposed algorithm for solving NP-complete problems efficiently on a quantum computer. When I was a graduate student at Berkeley, when a paper came out claiming that quantum computers could solve NP-complete problems, we would all race to see who could … <\/p>\n

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