PTIME <= BQP <= EXPTIME This is what I mean by 'closer'. I had to use EXPTIME rather than NP because of Savitch's Theorem. > In general, quantum computers on

PTIME <= BQP <= EXPTIME This is what I mean by 'closer'. I had to use EXPTIME rather than NP because of Savitch's Theorem. > In general, quantum computers only have a quadratic speed-up as far as we know. Not really true? In the time setting, there's the case of sampling problems, hidden subgroup problems, the evaluation of linear systems, etc. There are also many other settings (Merlin-Arthur-like round complexity) and communication complexity where exponential and even superexponential increases can be had.