Hacker News new | ask | show | jobs
by mda 2428 days ago
What if it is linear but angle is so steep that you require all the sands in the world to achieve parity with a classical computer, does it still count?
3 comments

Of course. Quantum supremacy is a claim about computational complexity. 200 seconds vs 2.5 days is 1000x slowdown. In practical terms, x^10 is even worse than 1000x (linear), but if quantum computer could be simulated in x^10, that would definitely disprove quantum supremacy.
I think in that case you would probably be able to formulate the problem in a different way to show that the angle arises through an exponential process (or more) and that the problem isn't truly linear.
Maybe but 1) that's hard to prove and 2) it's hard to achieve unless you're looking at some sub-problem where the quantum and classical algorithm actually do scale differently.