Not necessarily. I believe it's the case that for every quantum algorithm that is exponentially better than the best known classical algorithm for solving the same problem, it is not proven that an equally good (up to polynomial overhead) classical algorithm does not exist.
Therefore, one way quantum computers could fail to be exponentially better than classical ones, without us having to revise physics, is that there are as of yet unknown classical algorithms that would erase the apparent difference between the two classes. You would have quantum computers, but not quantum supremacy.
I believe that there are quantum algorithms that are provably better than any classical one, known or unknown, but I think these only provide at most polynomial speedup, not exponential. So you might still call it quantum supremacy to have algorithms that are merely polynomially better.
I've heard it called "Aaronson's trilemma", the fact that at least one of these three things must be true:
* Quantum computers are not possible even in principle (new physics required, since current physics says they are), or
* The extended Chuch-Turing thesis is incorrect (because quantum supremacy implies not all computers are within polynomial overhead of each other), or
* There exist polynomial time classical algorithms for factoring and discrete logarithms.
I remember seeing a lecture by Aaronson where he described the idea of a “relativity computer” where you set a computer running on some exponential task, but then hop in a spaceship and fly off at nearly the speed of light, and come back to find the answer in an amount of time only polynomial for you.
He “debunked” this by mentioning to do it you’d potentially need an exponentially large supply of fuel to accelerate yourself to a speed exponentially close to the speed of light as the problem to solve grows more complex.
I wonder if something similar could be true about quantum computing. Maybe it is theoretically possible to solve problems polynomially that can only be solved exponentially in a classical computer. But maybe it requires “exponentially more” of some resource, like a power supply to power the physical devices needed to do an amount of error correction to make it physically realizable as the problem size grows.
Would it be possible for the Church-Turing thesis to be false mathematically, but for the amount of quantum error correction to require an amount of physical resources that grow prohibitively and prevent it from being practically possible (like the fuel limitation prevents the otherwise physically possible relativity computer)?
More importantly, it may be that the cost of a QC implementation for an algorithm is lower, even if there’s no quantum supremacy. As an analogy, consider the case of comparing a tape computer to a RAM computer: they’re both classical, but the RAM computer is vastly faster.
Therefore, one way quantum computers could fail to be exponentially better than classical ones, without us having to revise physics, is that there are as of yet unknown classical algorithms that would erase the apparent difference between the two classes. You would have quantum computers, but not quantum supremacy.
I believe that there are quantum algorithms that are provably better than any classical one, known or unknown, but I think these only provide at most polynomial speedup, not exponential. So you might still call it quantum supremacy to have algorithms that are merely polynomially better.
I've heard it called "Aaronson's trilemma", the fact that at least one of these three things must be true:
* Quantum computers are not possible even in principle (new physics required, since current physics says they are), or
* The extended Chuch-Turing thesis is incorrect (because quantum supremacy implies not all computers are within polynomial overhead of each other), or
* There exist polynomial time classical algorithms for factoring and discrete logarithms.