[deepburner]

Nowhere in the text you quoted (nor in the article body) it is said that simulation of this device can not be done. Had you read the paper you'd see that it _is_ about simulating this device. From the introduction: "After students are introduced to several projects in quantum computer simulation, they write code to simulate the operation of Mermin’s quantum device."

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.

[oersted]

Of course, Mermin's device can be simulated in a classical computer, we do quantum physics simulations for research all the time. That doesn't entail that we can have quantum computer speedups on a classical computer.

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.

[devodo]

The device cannot be accurately simulated using a classical computer because it relies on quantum entanglement that has no counterpart in classical physics. The results cannot be simulated even if hidden local variables are used.

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.

[justinpombrio]

> 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.

No shit. Of course you can't take a simulation method that takes exponential running time in terms of the size of the thing you're simulating (two Mermin devices), then simulate each half (each Mermin device) independently. If you could split it up like that you'd have a polynomial time simulation method!

[oersted]

BQP (Bounded-error Quantum Polynomial-time) is in PSPACE sure, but that doesn't mean much.

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.