tag:blogger.com,1999:blog-3722233.post117244313757614930..comments2024-08-02T19:37:12.269-05:00Comments on Computational Complexity: On NP in BQPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-12930228507123174962017-10-05T12:23:31.005-05:002017-10-05T12:23:31.005-05:00There's also the complicating factor that D-wa...There's also the complicating factor that D-wave CAN solve NP-complete problems efficiently, but it does so by being a massively parallel, hardware quantum annealing device--i.e. it finds good solutions to those NP-complete problems that can be stated as optimization problems, and does not solve NP in general. Unknownhttps://www.blogger.com/profile/14344336220373737053noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9303152613199703722016-03-18T03:24:00.569-05:002016-03-18T03:24:00.569-05:00I laughedI laughedDiego Alonso Cortezhttps://www.blogger.com/profile/01699300213385475503noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1172627188568617052007-02-27T19:46:00.000-06:002007-02-27T19:46:00.000-06:00How about consequences of BQP = QMA. We must have...How about consequences of BQP = QMA. We must have some of these?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1172490668163707622007-02-26T05:51:00.000-06:002007-02-26T05:51:00.000-06:00"Quantum-computer technology can solve what is kno..."Quantum-computer technology can solve what is known as “NP-complete” problems."<BR/><BR/>Note that also classical computers <I>can</I> solve NP-complete problems. What they misleadingly suggest is just that this was possible efficiently on quantum computers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1172483163623401012007-02-26T03:46:00.000-06:002007-02-26T03:46:00.000-06:00I fear it is not the Economist who did the mistake...I fear it is not the Economist who did the mistake, it is D-Wave who believes that their quantum computer can solve NP.<BR/><BR/>"Quantum-computer technology can solve what is known as “NP-complete” problems."<BR/><BR/>(Source: <A HREF="http://www.dwavesys.com/index.php?mact=News,cntnt01,detail,0&cntnt01articleid=4&cntnt01origid=15&cntnt01returnid=21 " REL="nofollow">D-Wave News</A>)<BR/><BR/>I am not sure whether this increases my trust in their announcements...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1172446093341452672007-02-25T17:28:00.000-06:002007-02-25T17:28:00.000-06:00I had a brief bit of dismay when I read that artic...I had a brief bit of dismay when I read that article the other week; they're usually fairly good about getting such details right.<BR/><BR/>If I'd been near a computer at the time I'd have written in a letter myself. Sadly I forgot to do so later...<BR/><BR/>Complicating things is fact that I strongly suspect that we can go as far as PSPACE "practically", just not with anything so pedestrian as a quantum computer. The full argument is too small to fit in the margin here, however...Anonymousnoreply@blogger.com