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?
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.
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)?
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.
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.
Both, actually. Some interpretations of quantum mechanics imply that QC is impossible, some imply that it's infeasible for any meaningful problems.
It's possible that there is no way to get useful data from quantum phenomena as anything happening on that level is unknowable by it's very nature.
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.
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.
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.
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.