Hacker News new | past | comments | ask | show | jobs | submit login

I’m not really an expert—I’ve just been playing with quantum computer simulations since the supremacy paper came out, but yours is basically IBMs criticisms of that paper.

Part of the problem is that comparing a quantum computer simulation to the state of an actual quantum computer is almost inherently an apples-to-oranges thing.

We do not know of any way to compactly represent the state of a quantum computer in a classical computer; it appears to require an exponentially large state vector. So it requires an exponential number of operations just to evolve the full state vector. But it also produces the exact and full probability distribution describing the quantum computer state. Running a physical QC produces one _sample_ from that distribution, and you have to run it completely again to get another sample.

If we pretend that the simplest quantum computer state is equivalent to a coin toss, then classically simulating a fair coin would produce a distribution like {H: 0.5, T: 0.5}, while running the quantum computer would produce “H” half the time and “T” half the time. You could run the QC a bunch of times to estimate the actual probability, but there’s a fundamental difference between what the QC does and the simulation does.

There are some ways to approximately solve the classical simulation, but we haven’t found a way to compactly represent and manipulate the quantum state vector that are as fast as physics/nature seem to be able to do it in hardware. The Extended Church-Turing thesis (ECT) basically says that such an encoding and simulator should exist, and the basic premise of QC is that such an encoding and evolution process is impossible.

We don’t expect to ever conclusively prove that ECT is false (someone could always find an efficient simulator for QCs) but that doesn’t mean QCs can’t be useful in the interim, or even potentially after such a simulator is found (if it is a polynomial with a very large constant factor, for example).

The supremacy paper claimed that classically simulating their largest circuit would take 10,000 years. IBM said it would take them 2 days. The sycamore processor did it in 5 minutes. That still a big improvement, even if the classical simulator can be further optimized—and even IBM admits their simulator wouldn’t work if the quantum processor had even 1 more qubit.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact