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)?

The universe may not see any difference between the two states!

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.

At the moment the problem of superseding ordinary computers still looks like one of technical/engineering nature. If achieving this is not possible even in principle it could lead to some new developments.

There are some people considering/working on superdeterminism as a possible interpretation of quantum mechanics (the idea that everything, every outcome of an measurement is predetermined by the universe in such a way for us not to gain the complete information about the quantum system. I would not like to discourage anyone, but in fact this would be a conspiracy theory on a cosmic scale. In some discussion on physics stackexchange it was pointed out by Peter Shor that if it were true we wouldn't be able to achieve quantum supremacy.

It is true that Gerard 't Hooft, the most famous proponent of superdeterminism is an asymptotic quantum supremacy skeptic, but I don't think superdeterminism implies no quantum supremacy. I'm a fan of superdeterminism, but I consider it to be in a pre-interpretation level of maturity, where the idea isn't even completely fleshed out. I hope that some day it can be turned into a proper interpretation like Many-Worlds and QBism, and at that point it will give all the standard predictions of QM, including the possibility of quantum supremacy.

> If quantum supremacy was not possible, wouldn't that mean that something is wrong with our physics understanding?

Yes, but that's not outrageous. For instance, Shor's algorithm on a cryptographically interesting factorization problem would be testing the predictions of QM in a new regime (exact cancellation of a sum with roughly as many terms as the size of the product being factored, during the quantum fourier transform.) It's quite reasonable to think that QM is an approximation which will break down at that level of precision.

You are right - most physicists believe that quantum supremacy is possible, and if we discover that in fact it is not, then we'll need to understand why.

> So when people say quantum supremacy is impossible, do they say that the device itself is extremely complicated to build (like an earth to moon elevator for example), or that quantum supremacy isn't allowed not even in principle?

Both, actually. Some interpretations of quantum mechanics imply that QC is impossible, some imply that it's infeasible for any meaningful problems.

Quantum computing is a typical example of taking a model (QM), further than it was ever intended to.

Instead of recognizing the fallacy, they blindly accept its promises : cramming an infinite computational power using very little mass.

They then uses the excuse that it's extremely complicated to build to cover for the lack of results demonstrating the model is holding its promises.

After a few decades, they will achieve at tremendous cost a "success" where quantum computer are typically faster by a factor 10^6 than a classical computer, and with better energy efficiency, and recognize then that the model had indeed its limits, and that quantum supremacy was never about delivering an exponential speed-up (who would be stupid enough to believe such fallacies, of course all models have their limits) but just a better way of computing.

Is there a way to find how far a model stays valid other than taking it further than it was ever intended to? I personally like to think that physics can be explained by a discrete finite automaton so quantum computers are not possible, but believing this would be more stupid than believing the opposite. Whichever alternative is true, there is a good reason to try to build quantum computer, because the process itself will improve our understanding. And implying that there is some conspiracy to pretend quantum computers are real, is strange to say the least.

If your model can't predict its limits, it is an indication that you are already past its limits.

When you build a model, you build it to map the range of behaviors you are interested in. When mathematical infinities of any kind (like infinite computational power) emerge it's usually a strong hint that the model is not applicable, not an invitation to fantasize about the things you will be able to achieve following your model outside of its region of trust.

You question your hypothesis and then look for an alternative model that is more probable. You don't spend your resources doubling down on blind model following.

Assuming some priors and Bayesian updating your beliefs about how the world works is probably a better strategy.

I am not a Physicist so I don't have skin in this game, but the QM scene really look like a mix between snake oil vendor and religion, and doing more of this "science" by marketing firms isn't really any scientist should wish for.

All the physical theories we had so far require infinite computational power, because they work with real numbers, it's easy to say that it is wrong, but that's not really useful without saying what is right.

There are several interpretations of quantum mechanics that predict quantum computers not working in different ways, to find which one of them is correct you need an experiment that is not described by traditional view. Building quantum computers is the first experiment that has a chance to show what exactly is wrong with QM. Even the people who think there is nothing wrong with QM agree that quantum computer not working would be a bigger discovery than working, and are considering all the alternatives, so i don't see how it is anything like a religion.

Working with real numbers, doesn't mean requiring infinite computational power. Numerical integration can make the integration error arbitrary small, even without symplectic integrators, this mean you can work with finite-precision number instead.

The thing with building a quantum computer is that the original hard test (breaking RSA) is being watered down. Until you prove that you've done it you only get non-results telling you that you are not there yet but you don't know why and require ever more funds. So the incentives are badly aligned and you prove a softer test that you try to sell as something as good as the hard test. If you are not familiar with bias you might even fool yourself into thinking you are making progress because you managed to reach the softer goal you have set for yourself while you are adding complexity to obscure your theoretical shortcomings.

>Building quantum computers is the first experiment that has a chance to show what exactly is wrong with QM.

Don't blindly trust experiments : Bell officially proved that what's very probably wrong is right. Especially when they require expensive equipment or specialized knowledge to reproduce. If there is something wrong with the protocol you can easily falsely convince yourself. Putting a non-zero prior on unknowns unknowns should be a must.

If you ever try to question the Gospel of Non-Locality, you will find yourself cast aside like many before as the vast literature show.