> So when people say quantum supremacy is impossible, do they say that the device itself is extremely complicated to build (like an earth to moon elevator for example), or that quantum supremacy isn't allowed not even in principle?

Both, actually. Some interpretations of quantum mechanics imply that QC is impossible, some imply that it's infeasible for any meaningful problems.