Scott Aaronson has written a nice article “Ten Semi-Grand Challenges for Quantum Computing Theory”. If you are a computer science theory researcher interested in what to work on in quantum computing, I highly recommend the list. One thing I find very interesting about theory work in computer science is how religious researchers are about not sharing the problems they are working on. So it is very nice of Scott to share what he thinks are big open problems in quantum computing theory today.
One thing that Scott leaves out of the list, which I would have included, are questions along the lines of “how can quantum computing theory contribute to classical computing theory.” Scott explicitly says he does not include this question because it is “completely inexhaustible,” and I agree that this is certainly true, but this may be exactly the reason one should work on it! The idea behind this line of research is to prove results in classical computational theory by insights gained from quantum computational theory. An analogy which may or may not be stretching things a bit is the relationship between real analysis and complex analysis. Anyone who has studied these two subject knows that real analysis is much more difficult than complex analysis. Physicists best know this in that they often cannot easily do certain real integrals unless they pretend their real variables are complex and integrate along a particularly well choosen countour. Similarly, many results in real analysis have counterparts in complex analysis which are easy to prove. So the line of research which asks whether quantum computation can contribute to classical computation is basically “as complex analysis is to real analysis, so quantum computing is to classical computer.” I’ve discussed this possibility (along with Scott’s contribution to it) here.
O brave new quantum world!
when you say it’s “interesting” how theory CS researchers don’t share problems, can you elaborate ? 🙂
Heh. Well it just seems they are very guarded about what they are working on. I’m not sure this is a bad thing, but it is certainly different from physics. Or maybe it’s just that I like to blab about what I’m working on 😉
We definitely are guarded: I can’t decide whether it is a function of our strange conference system or just a general cultural thing. It’s certainly not the case that we are in constant danger of getting “scooped”, so…
I think the conference system certain has something to do with this. Interestingly, I think mostly it is the fact that the conferences have deadlines which leads to this effect, not the fact that this is an informal method of publication. For example, posting on the arXiv in physics is now the de facto standard for deciding precedence. So when you’ve figured something out, you can immediately publish it, whereas in CS theory, you have to wait for the conference to come along. Hence the code of conduct about not talking?
This is interesting, and if you don’t mind, I’d like to explore it further. In what way does arXiv publication guarantee precedence ? For example, will journals allow citations to arxiv papers that are possibly under review by some other journal ?
Yes, physics journals do allow citations to arXiv papers. I don’t think arXiv publication “guarantee”‘s precedence, but it is very close to the de facto standard for precedence, at least in quantum computation. In string theory I also get the impression the publication on the arXiv establishes precedence.