Popular articles on quantum computers sometimes portray them as mythical devices that speed up any computation by an exponential factor. The truth is much more subtle, and over the last decade and a half we have learned a great deal about the circumstances under which Nature allows us access to its exponential computational resources. This has a bearing on our understanding of the foundations of both computer science and quantum physics. In this talk I will try to outline some of these issues. No background in quantum physics will be assumed.