Hacker News Reader

Comment by devodo | Hacker News Reader

> (Pro-strong-AI)... This is basically a disbelief in the ability of physics to correctly describe what happens in the world — a well-established philosophical position. Are you giving up on physics?

This is a very strong argument. Certainly all the ingredients to replicate a mind must exist within our physical reality.

But does an algorithm running on a computer have access to all the physics required?

For example, there are known physical phenomena, such as quantum entanglement, that are not possible to emulate with classical physics. How do we know our brains are not exploiting these, and possibly even yet unknown, physical phenomena?

An algorithm running on a classical computer is executing in a very different environment than a brain that is directly part of physical reality.

View on HN

> there are known physical phenomena, such as quantum entanglement

QC researcher here, strictly speaking, this is false. Clifford circuits can be efficiently simulated classically and they exhibit entanglement. The bottom line is we're not entirely sure where the (purported) quantum speedups come from. It might have something to do with entanglement, but it's not enough by itself.

Re: about mermin's device, im not sure why you think it can not be simulated classically when all of the dynamics involved can be explained by 4x4 complex matrices.

Could you accurately simulate the device on a computer precisely following the rules of the challenge? So that means the devices are isolated and therefore no global state is allowed. The devices are not aware of each others state nor results. You are only allowed to use local state to simulate the entangled particle. You can use whatever local hidden variables you want as long as it doesn't break the global state rule.

> there are known physical phenomena, such as quantum entanglement, that are not possible to emulate with classical physics

This is wrong. You can even get a mod for Minecraft which implements quantum mechanics.

https://www.curseforge.com/minecraft/mc-mods/qcraft-reimagin...

More precisely: you can emulate quantum mechanics using a classical computer, but the best known algorithms to do so take exponential running time.

This is not true. For example, Mermin's device cannot be done using classical physics regardless of running time. https://en.wikipedia.org/wiki/Mermin%27s_device

The first reference in the article you linked is titled "Computer simulation of Mermin's quantum device".

The paper is saying that attempting to simulate the device in code is a valuable lesson to students for precisely the reason that it cannot be done (correctly), thereby illustrating the limits of classical computation.

> In the current paper, we make use of the recently published work in quantum information theory by Candela to have students write code to simulate the operation of the device in that article. Analysis of the device has significant pedagogical value—a fact recognized by Feynman—and simulation of its operation provides students a unique window into quantum mechanics without prior knowledge of the theory.

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.

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.

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.

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.

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

Reply on news.ycombinator.com