(See this paper by Scott Aaronson: “NP-complete Problems and Physical Reality”)
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; for example, he tried using soap bubbles to compute minimal spanning trees, which people thought were naturally solving a NP-complete problem, and discovered that no, actually they just converge to easy local minima and aren’t doing anything special. So if you think you’ve discovered some super-hard to compute behavior, it may simply be finding local minima or interfering with itself or doing something which winds up being ‘easy’ for a universe-simulating computer.
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.
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; for example, he tried using soap bubbles to compute minimal spanning trees, which people thought were naturally solving a NP-complete problem, and discovered that no, actually they just converge to easy local minima and aren’t doing anything special. So if you think you’ve discovered some super-hard to compute behavior, it may simply be finding local minima or interfering with itself or doing something which winds up being ‘easy’ for a universe-simulating computer.
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.