Indeed, the whole point of Mermin's device is to give a very simple illustration for how it is impossible to replicate the behaviour of two entangled particles using classical particles (with hidden variables).

Now is this specific characteristic of entanglement an absolute requirement for quantum computing speedups? Could we have similar speedups with probabilistic hidden-variable algorithms? Probably not, but it is a good question. It is true that if you spend time reading research papers in the field, it is still not clear what the edge is between problems that can be sped up by quantum computers and which cannot, or if there is even an edge at all.

The only way to simulate accurately on a classical computer is to use global state but this goes against the instruction that the devices must be isolated from each other.

> This is immaterial, however. It is a well known fact that BQP is in PSPACE and Clifford circuits (a subclass of quantum circuits) can not only be simulated classically, but done so efficiently. It is not controversial.

Yes, BQP problems are solvable and a "subclass" of quantum circuits can be simulated efficiently. But the fact is there are known aspects of reality that cannot be simulated on a classical computer.

P ⊆ BPP ⊆ BQP ⊆ PSPACE

BQP problems can be solved on quantum computers in polynomial time, some of these problems may be outside of P and BPP (Bounded-error Probabilistic Polynomial-time), so they may not be possible to solve in polynomial time in classical computers, even with probabilistic algorithms.

It is true that there's still room for BPP = BQP, that has not been disproven, but it is somewhat controversial to expect so, at this point many smart people have spent their lifetimes prodding at it.