3 ms·

I wouldn't say "emulate", because a classical computer wouldn't be trying to solve it the same way as the quantum computer. The point (which would be amazing if

I wouldn't say "emulate", because a classical computer wouldn't be trying to solve it the same way as the quantum computer. The point (which would be amazing if true) is that a classical supercomputer would take 10,000 years to solve the same problem, no matter what method/algorithm it used.

sanxiyn 7y ago
Of course "any algorithm" part can't be proved, because that is equivalent to proving P vs PSPACE. (PSPACE is as powerful as any quantum computer.) Just like everything in computational complexity, proof is under "standard assumptions".