tag:blogger.com,1999:blog-3722233.post51535966223175378..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: Analogs between Quantum Computing and ParallelismLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-54746931979709650832013-12-24T10:47:28.919-06:002013-12-24T10:47:28.919-06:00If you are completely ignorant about a field, then...If you are completely ignorant about a field, then you should stick to posting about the Pumping Lemma. Quantum computing is over twenty years old now, and there aren't good excuses for ignorance. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31702614118294939192013-12-19T10:45:46.216-06:002013-12-19T10:45:46.216-06:00One big difference comes from the degree of speedu...One big difference comes from the degree of speedup promised. Since QCs promise exponential speedup for some problems, this would swamp any architectural difference (e.g. a line of qubits with nearest neighbor interactions vs a fully parallel architecture that mimics abstract quantum circuits). Thus algorithms work can be useful even if we have no idea about the architecture we will end up with. (This is not true of all quantum algorithms work - some of it is necessarily very architecture-dependent.)<br /><br />But for parallel computing, the maximum speedup is clearly the # of processors. And architecture is crucial to achieving this. There are a few things you can say that apply pretty generally across architectures. But in general you have to talk about the right architecture or you risk being irrelevant to practice.<br /><br />Basically, both are useful, but since parallel algorithms are closer to practice and have more modest speedups, architectural considerations are generally more important.aram harrowhttps://www.blogger.com/profile/01272118188252697149noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-92171598129161085682013-12-17T15:41:45.859-06:002013-12-17T15:41:45.859-06:00Stephen Jordan maintains a nice website with lots ...Stephen Jordan maintains a nice website with lots of quantum algorithms:<br />http://math.nist.gov/quantum/zoo/Ronald de Wolfhttp://homepages.cwi.nl/~rdewolf/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31322587165380020462013-12-17T13:12:51.936-06:002013-12-17T13:12:51.936-06:00I have added to my post to look at your comment to...I have added to my post to look at your comment to see far more quantum algorithms.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5720961046404753662013-12-17T13:03:34.986-06:002013-12-17T13:03:34.986-06:00The claim that there are only very few quantum alg...The claim that there are only very few quantum algorithms is simply not correct; a brief look at <a href="http://arxiv.org/pdf/0812.0380.pdf" rel="nofollow">this review</a> from 2008, which focuses on the specific area of algebraic problems, shows that there are many more than this. Even if we restrict to papers from 2013 alone, <a href="http://www.cs.tau.ac.il/~amnon/Papers/T.stoc13.IntQLog.pdf" rel="nofollow">there</a> <a href="http://arxiv.org/pdf/1311.7685" rel="nofollow">are</a> <a href="http://arxiv.org/abs/1310.3898" rel="nofollow">quite</a> <a href="http://arxiv.org/abs/1311.6777" rel="nofollow">a</a> <a href="http://arxiv.org/abs/1311.1851" rel="nofollow">few</a>, based on a number of different techniques (in fact, most of these papers date from October or later!). Finally, with respect to the last claim in the post: one of the most practically important problems to which quantum computing is likely to be applied is the simulation of quantum systems (which is mentioned only briefly previously). This is a fundamental task in (eg.) quantum chemistry and, though one of the earliest quantum algorithms discovered, is <a href="http://arxiv.org/abs/1312.1414" rel="nofollow">still</a> a topic of active research.<br />Unknownhttps://www.blogger.com/profile/00984900489341123357noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-974307735532996952013-12-17T12:12:34.843-06:002013-12-17T12:12:34.843-06:00Many of the models assumed shared memory which was...<i> Many of the models assumed shared memory which wasn't true. Even so, did the work on PRAMS and other models help the practioners? Directly? Indirectly?</i><br /><br />For the most part no. The shared memory assumption was too important to ignore. Contrast this with the theoretical work on distributed systems which has both directly and indirectly helped practitioners.<br /><br /> I don't think there is any shame on PRAM research ultimately not being very relevant. Such is the nature of research: we make bets and predictions ahead of time, some pan out, others don't. PRAM was of the latter kind. We eventually realized this and we moved on. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40055893640932757222013-12-17T08:57:24.649-06:002013-12-17T08:57:24.649-06:00I'm pretty sure I'm not a wise man, but al...I'm pretty sure I'm not a wise man, but allow me to make two comments about my book review that this post refers to <br />http://homepages.cwi.nl/~rdewolf/publ/qc/qic_books.pdf<br />It gives the number of books in 2003 as ">>20" rather than 20, and it ends with the (still) heartfelt claim "what this fields needs is more algorithms, not more books." We do have a few more quantum algorithms than we did in 2003, but also plenty more books...Ronald de Wolfhttp://homepages.cwi.nl/~rdewolfnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88360883315021206972013-12-16T19:16:54.854-06:002013-12-16T19:16:54.854-06:00Megiddo's parametric search is a widely used* ...Megiddo's parametric search is a widely used* technique to obtain (sequential) algorithms for optimization problems. It needs parallel algorithms for the associated decision problem.<br /><br />* Widely used means used in a lot of papers (hardly ever in practice). Anonymoushttps://www.blogger.com/profile/06328185728688465505noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49834292404421096852013-12-16T19:11:53.652-06:002013-12-16T19:11:53.652-06:00There is a big difference. There were parallel ...There is a big difference. There were parallel computers back in the heady days of the 1980's work on the theory of parallel computing. It was just that the processors involved were typically at least a generation behind so the parallel computers were often slower than the sequential ones. We've had to wait until recent years when clock speeds have been relatively stable and the only way to gain is by going parallel. Quantum computing is not even in close to this level of development.Paul Beamehttp://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40094518335380316912013-12-16T15:20:41.462-06:002013-12-16T15:20:41.462-06:00Certainly yes, for #3: a small random sample is: (...Certainly yes, for #3: a small random sample is: (i) derandomization, which could be viewed as getting a real start from Karp and Wigderson's NC algorithm for MISs in graphs, (ii) P-completeness which shows that flow and matching are (surprisingly) very different from the viewpoint of parallel computation, and (iii) the Isolating Lemma of Mulmuley, Vazirani, and Vazirani. aravindhttp://www.cs.umd.edu/~srinnoreply@blogger.com