4 ms·

If quantum supremacy was not possible, wouldn't that mean that something is wrong with our physics understanding? So when people say quantum supremacy is impos

If quantum supremacy was not possible, wouldn't that mean that something is wrong with our physics understanding? 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?

jjeaff 7y ago
I'm not an expert. But a lot of quantum mechanics has to do with things being unknown or completely different until they are measured or observed. 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.
masteranza 7y ago
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.
- skinner_ 7y ago
  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.
6nf 7y ago
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.
doubleunplussed 7y ago
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.
- thechao 7y ago
  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.
- mlthoughts2018 7y ago
  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)?
AlexCoventry 7y ago
> 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.
naasking 7y ago
> 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.
GistNoesis 7y ago
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.
- chr1 7y ago
  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.
  - GistNoesis 7y ago
    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.

jjeaff 7y ago

I'm not an expert. But a lot of quantum mechanics has to do with things being unknown or completely different until they are measured or observed. 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.

masteranza 7y ago

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.

skinner_ 7y ago
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.

6nf 7y ago

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.

doubleunplussed 7y ago

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.

thechao 7y ago
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.
mlthoughts2018 7y ago
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)?

AlexCoventry 7y ago

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

naasking 7y ago

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

GistNoesis 7y ago

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.

chr1 7y ago
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.
- GistNoesis 7y ago
  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.