center devoted to quantum computing and involving faculty and researchers from both physics and computer science communities. As part of this they are advertising a posdoctoral fellowship.)
A long time ago people in theory did a lot of work on parallel computing before
there were many parallel computers build. Today people are doing a lot of work on quantum computing before quantum computers are build. What is similar and different here?
- When parallel computers were actually built they were not like PRAM's. 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?
- Are the models of quantum computing studied now helping the practioners? Is the development of quantum computers at too early a stage to even ask this question?
- Even if no quantum computers are ever built the study has been a sucess since some classical problems have been solved using quantum techniques (and I think this will happen more and more). And some interesting math has come out of it. And physicists and others have learned more about quantum mechanics from quantum computing. Could the same thing have been said for parallelism- even if parallel computers had not been built would the study of them have still be useful?
- One big difference- many problems can be parallelized in some form and solved that way (and some cannot be solved any other way). A wise man named Jon Katz referred above to a wise man named Ronald de Wolf who wrote, in a review of 3 books on quanum computing:
A quick survey on amazon.com shows that the number of books on quantum computing (at least 20) is more than 10 times as high as the number of quantum algorithms (2: Shor's and Grover's). (Footnote: Note that this review was written in 2003 so this statement is no longer true.)
While I think he meant there are more quantum algorithms (quantum random walks, quantum simulations, quantum selection-type problems?, quantum number-theory-type-problems?) now than in 2003, I will note that there are also more books on quantum computing now than then- on a cursory look at amazon I think I counted 30, but with the uncertainly principle, its hard to tell. The point is, aside from factoring and of course quantum simulation I wonder if when quantum computers, if they are build, will be able to do much more
BUT SEE NEXT PARAGRAPH. (Every year my students are surprised to find out that quantum computers probably CANNOT solve SAT in poly time.)
ADDED LATER: Comment 6 has a pointer to a survey of MANY quantum algorithms for MANY algebraic problems, and also a pointer to a more recent article on quantum algorithms. I will be delighted if the number of quantum algorithms now exceeds the number of books on quantum computing.
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.
ReplyDeleteThere 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.
ReplyDeleteMegiddo's parametric search is a widely used* technique to obtain (sequential) algorithms for optimization problems. It needs parallel algorithms for the associated decision problem.
ReplyDelete* Widely used means used in a lot of papers (hardly ever in practice).
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
ReplyDeletehttp://homepages.cwi.nl/~rdewolf/publ/qc/qic_books.pdf
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...
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?
ReplyDeleteFor 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.
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.
The claim that there are only very few quantum algorithms is simply not correct; a brief look at this review 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, there are quite a few, 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 still a topic of active research.
ReplyDeleteI have added to my post to look at your comment to see far more quantum algorithms.
DeleteIf 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.
DeleteStephen Jordan maintains a nice website with lots of quantum algorithms:
ReplyDeletehttp://math.nist.gov/quantum/zoo/
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.)
ReplyDeleteBut 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.
Basically, both are useful, but since parallel algorithms are closer to practice and have more modest speedups, architectural considerations are generally more important.