3 ms·
Does anyone know if you get a bump from PSPACE closer to EXPSPACE with a quantum harddrive similar to how BQP gets you closer to EXPTIME from PTIME?
by xnull1guest 12y ago
Does anyone know if you get a bump from PSPACE closer to EXPSPACE with a quantum harddrive similar to how BQP gets you closer to EXPTIME from PTIME?
- adrianN 12y agoBQP doesn't really get you closer to EXPTIME at all. We don't even know yet whether it gets you closer to NP. In general, quantum computers only have a quadratic speed-up as far as we know.
- xnull1guest 12y agoPTIME <= 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.