To expand on this: in this paper, Scott Aaronson points out, it’s quite hard to find a problem which looks like it is computing anything interestingly hard aside from quantum effects
Yes. OTOH, quantum effects don’t seem to provide a general solution for ‘easily-checkable’ problems (beyond the modest improvement that Grover’s algorithm brings to black-box search). However, closed timelike curves would provide easy solutions for any problem in PSPACE, which does include NP.
Yes. OTOH, quantum effects don’t seem to provide a general solution for ‘easily-checkable’ problems (beyond the modest improvement that Grover’s algorithm brings to black-box search). However, closed timelike curves would provide easy solutions for any problem in PSPACE, which does include NP.