[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.