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.