[bawolff]

> It should also be noted that there is no prood right that any of the known quantum algorithms give an exponential speedup over the best possible classical algorithms.

True, but we also can't even prove P!=NP, which seems (intuitively) like it should be much easier than proving that there exists an exponential speedup with quantum algorithms. I feel like this statement mostly just says we have a far way to go in understanding the relations between complexity classes. Its not like we have proven all the "obvious" separations between complexity classes and qunatum stuff is just a stubborn hold out.

[tsimionescu]

Oh, absolutely, I didn't mean to imply that this should be easy. It's just important to note in these discussions what we do know for sure and what is still debatable.

My point was that one way of accounting for a belief that QCs are not fundamentally exponentially faster than classical computers despite the experiments we've seen from Google is to believe that we will find classical equivalents of every quantum algorithm that shows such a speedup. While few believe this in the community, and for good reasons, it is not proven to be a silly belief yet.

By the way, I will also mention that if P=NP (not that anyone thinks this is remotely likely), that would also imply that quantum computers have no exponential advantage over classical ones.