I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

Absent an ultimate theory of fundamental physics, we're unlikely to have a full answer to your question -- e.g., to be able definitively to rule out the possibility of "hypercomputers" solving NP-hard problems in polynomial time. What we can do is

(1) to explain the failure (often, the forehead-bangingly obvious, don't-point-to-the-exponential-elephant-in-the-room failure) of all EXISTING proposals along these lines, and

(2) to point to deep discoveries in fundamental physics -- most notably, the Bekenstein bound https://en.wikipedia.org/wiki/Bekenstein_bound -- which seem to constrain any future quantum theory of gravity to have a form that would rule out these sorts of hypercomputers (for example, by limiting the amount of energy that can be pumped into a finite region, without causing the region to collapse to a black hole, and by likewise ruling out computer components that are smaller than 1 Planck length across or that do more than 1 step per Planck time).

I've often speculated that ultimately, the hardness of NP-complete problems in the physical world might come to be seen as analogous to the impossibility of faster-than-light signalling or perpetual motion machines---i.e., something that we simply take as primitive and then use to explain other phenomena in physics. But while the hardness of NP-complete problems sometimes gets used in that way already, I also think we have a lot more work to do before the situations are truly parallel. (For starters, we could prove P!=NP. :-) )

Imagine you are a parent/teacher in a room full of happy kids, playing their kid games. Some kindergarten playground or something. They're generally all doing some kind of stuff, and doing it in parallel. Is this "doing work in parallel"? Every one of them is doing something totally else, one kid is building a castle, the other is throwing bricks at it and destroying it ("interference cancelling each other's work"). One is digging holes in a sandbox, another just kicked the sand inside, filling the holes back.

Now, you are just one, insignificant adult in this room. Imagine you would want them to do something for you. Can you just shout at them, "do me some parallel computation"? "Build me a castle of bricks"? Meh, sure you can, but they'll look at you funny, maybe a few of them will start, but their attention will be soon diverted by others, and anyway they'll soon get bored and start fudging around.

But here comes the fun part - if you're a smart and creative teacher/parent/..., you can actually do much better: you can "trick" them into doing your work; you have to either find some kind of a "system", or a "fun game", that they will like, that will fit their abilities and sensibilities, so that they'll choose to generally more or less contribute in the direction you want them to. You have to find a way of doing the task that will be "compatible" with them. Then, collectively, you can actually have them make your work done! But if you don't find the trick - sorry, no free lunch for you :) But you can still keep enjoing watching in awe and wonder how they're having fun, the little buggers... erm, sweethearts :P

In a somewhat similar way, in QC, you have to invent a system that can trick all the qubits, who have their particular, peculiar ways of living and behaving, to contribute to some particular result that will be meaningful and useful to you. Otherwise, they'll totally do some kind of "parallel work", but the result will be just irrelevant mess. To make the challenge even more tricky, you're actually outside the room when the work is happening. You don't see the "calculation" ([wavefunction] vector) each kid... umm, qubit is contributing, you only see the one final result. Nah; that would be too easy still; you can only see the shape of the result's shadow (just the length of the final vector).

(edit: ah, and I forgot the most important thing: if I'm not wrong, each extra kid is are actually contributing exponentially more work; if you have N qubits, you are trying to trick 2^N vectors to work for you)

Sorry for still being very vague and handwavy :)

Hmm, one more vague analogue could be to "computer proof systems/theorem provers", e.g. Idris, or trying to prove/enforce something with GADTs. You have this set of rules/mechanisms; now, you have to sit and squeeze and tear your brain in different ways to invent how to force those limited rules to encode the thing you want to prove. Not easy. But sure a challenging and potentially fun brainteaser :)

2^2, 47, 8121293, 1210175511547330273998081353233737902915153751853051779316281348898985913176974726270161034273517189585147616550512413067820157568220278077881421197895369014359432790978536356806591021