2 ms·
Is it correct that the claim “that it can still best classical computers on some subset of these tiny problems” based on classical computers simulating quantum
by brown9-2 7y ago
Is it correct that the claim “that it can still best classical computers on some subset of these tiny problems” based on classical computers simulating quantum circuitry to compute those problems?
I’m wondering if there is some other way the problem could be computed without having to simulate qubits.
- comicjk 7y agoA lot of work has gone into looking for classical algorithms for these sampling problems since the mid-2000s, and we have found some speedups, but everything still suggests that they are truly exponential on classical hardware. The classical algorithms for these problems don't involve modeling qubits directly, but they do involve sampling exponentially many states and averaging over the results, which is a lot like modeling qubits.