4 ms·

Following the quantum supremacy controversy is very frustrating. It gets constantly framed as a decisive step that changes everything, which is wrong. But then

by knzhou 7y ago

Following the quantum supremacy controversy is very frustrating. It gets constantly framed as a decisive step that changes everything, which is wrong. But then there's also an opposite and equally wrong reaction that any challenges to the claim prove that quantum computing doesn't work at all. The reality is that quantum computing technology has been improving at the same steady pace for decades, and quantum supremacy was recently invented as a concrete but not very useful goal that people could realistically aim for in the near term. That is a totally standard and legitimate way of guiding technological progress. The problem is that quantum supremacy is vaguely defined (what does "infeasible on any classical computer" mean? what computers can you use, and for how long?) but it is presented to the public as a sharp boundary -- which means that every company in the field has a huge incentive to claim they are the first. This IBM claim is not a fundamental objection. Given that everything they say is correct, Google could still achieve quantum supremacy by their standards just by incremental improvement, slapping a few more qubits on. So why even bother disputing Google's claim? Because it will set them back a few years, and that's enough time for IBM to make a claim of its own. That's why academics, who have no stake in what company gets the hype, will just consider this whole episode rather distasteful.

sanxiyn 7y ago
Quantum supremacy is a big deal. It is a goddamn experimental evidence against Extended Church-Turing Thesis. If you never believed ECT (for example, all physicists seem to think ECT is obviously false) it may not matter to you, but it still is a serious claim. Yes, Google probably can achieve quantum supremacy by slapping a few more qubits. But a few more qubits were, in fact, not slapped yet. So quantum supremacy is very much not achieved, and Google should not claim so.
- knzhou 7y ago
  It is serious, but as I said, it's also vaguely defined. We can continue quibbling over details for decades to come. Suppose Google does slap on more qubits so the time estimate goes up from 2.5 days to 25000 years. Is that quantum supremacy yet? Well, maybe if you used literally every classical computer in the world in parallel, and also used a very optimized algorithm, it would only take 2.5 years, which isn't that long if you're patient. So you could say that Google needs to slap on yet more qubits. That's why arguing over whether it's really quantum supremacy is just not useful. People can always move the goalposts, so we might as well ban that word from discussion. The underlying fact, which nobody is debating, is that quantum computers are regularly doing tasks that are harder and harder for classical computers to. And yes, the ECT is obviously false -- or at the very least, not obviously true. I'm surprised at how many CS people think it is some unassailable principle. Most CS courses devote precisely zero time to non-classical models of computation. If you've never studied a model of computation that could challenge ECT, then how can you be so sure of it? This is like being absolutely certain that I am the tallest person in the world, and refusing to ever leave my house to check.
- calf 7y ago
  How does quantum computation conflict with the ECT? I think Aaronson had talked about this but I don't remember his position on this.
  - Cybiote 7y ago
    The original Church Turing thesis concerns itself with computability and quantum computers do not violate it. The Extended version goes on to say a probabilistic TM can efficiently simulate all realistic models of computation. Quantum computers very likely violate the efficiency claim and this supremacy result is strong evidence in support.
- scottlegrand2 7y ago
  I think the problem is that perfectly wonderful science has been put in the hands of marketing people. And those are the same marketing people that kept telling us L5 autonomy was right around the corner. Or more lately that we couldn't discount the possibility of a near-term AGI. Great science, lousy PR IMO.
jgmatpdx 7y ago
> Just by adding a few more qubits IBM's algorithm scales approximately linearly in the number of qubits. So, you'd need more than a few more qubits...
- knzhou 7y ago
  No, in order to get linear time, they used an algorithm which requires exponential space. Once you add a few more qubits that breaks down too.
  - deleted 7y ago
    [deleted]
- nuncanada 7y ago
  No. It scales linearly with circuit size. Exponentially with qubits size. Just read Scott Aaronson's blog, probably the greatest expert on this subject. https://www.scottaaronson.com/blog/?p=4372 https://www.scottaaronson.com/blog/?p=4372
tomelders 7y ago
It sounds like Quantum Supremacy is the Turing Test of our time. A worthwhile milestone to aim for, but not the holy grail people thought it was.
ngold 7y ago
Since I had to look it up on Wikipedia. Quantum supremacy is the potential ability of quantum computing devices to solve problems that classical computers practically cannot. The weaker term Quantum advantage refers to the potential to solve problems faster. In computational-complexity-theoretic terms, this generally means providing a superpolynomial speedup over the best known or possible classical algorithm. The term was originally popularized by John Preskill but the concept of a quantum computational advantage, specifically for simulating quantum systems, dates back to Yuri Manin's and Richard Feynman's proposals of quantum computing.

by knzhou 7y ago

sanxiyn 7y ago

Quantum supremacy is a big deal. It is a goddamn experimental evidence against Extended Church-Turing Thesis. If you never believed ECT (for example, all physicists seem to think ECT is obviously false) it may not matter to you, but it still is a serious claim. Yes, Google probably can achieve quantum supremacy by slapping a few more qubits. But a few more qubits were, in fact, not slapped yet. So quantum supremacy is very much not achieved, and Google should not claim so.

knzhou 7y ago
It is serious, but as I said, it's also vaguely defined. We can continue quibbling over details for decades to come. Suppose Google does slap on more qubits so the time estimate goes up from 2.5 days to 25000 years. Is that quantum supremacy yet? Well, maybe if you used literally every classical computer in the world in parallel, and also used a very optimized algorithm, it would only take 2.5 years, which isn't that long if you're patient. So you could say that Google needs to slap on yet more qubits. That's why arguing over whether it's really quantum supremacy is just not useful. People can always move the goalposts, so we might as well ban that word from discussion. The underlying fact, which nobody is debating, is that quantum computers are regularly doing tasks that are harder and harder for classical computers to. And yes, the ECT is obviously false -- or at the very least, not obviously true. I'm surprised at how many CS people think it is some unassailable principle. Most CS courses devote precisely zero time to non-classical models of computation. If you've never studied a model of computation that could challenge ECT, then how can you be so sure of it? This is like being absolutely certain that I am the tallest person in the world, and refusing to ever leave my house to check.
calf 7y ago
How does quantum computation conflict with the ECT? I think Aaronson had talked about this but I don't remember his position on this.
- Cybiote 7y ago
  The original Church Turing thesis concerns itself with computability and quantum computers do not violate it. The Extended version goes on to say a probabilistic TM can efficiently simulate all realistic models of computation. Quantum computers very likely violate the efficiency claim and this supremacy result is strong evidence in support.
scottlegrand2 7y ago
I think the problem is that perfectly wonderful science has been put in the hands of marketing people. And those are the same marketing people that kept telling us L5 autonomy was right around the corner. Or more lately that we couldn't discount the possibility of a near-term AGI. Great science, lousy PR IMO.

jgmatpdx 7y ago

> Just by adding a few more qubits IBM's algorithm scales approximately linearly in the number of qubits. So, you'd need more than a few more qubits...

knzhou 7y ago
No, in order to get linear time, they used an algorithm which requires exponential space. Once you add a few more qubits that breaks down too.
- deleted 7y ago
  [deleted]
nuncanada 7y ago
No. It scales linearly with circuit size. Exponentially with qubits size. Just read Scott Aaronson's blog, probably the greatest expert on this subject. https://www.scottaaronson.com/blog/?p=4372 https://www.scottaaronson.com/blog/?p=4372

tomelders 7y ago

It sounds like Quantum Supremacy is the Turing Test of our time. A worthwhile milestone to aim for, but not the holy grail people thought it was.

ngold 7y ago

Since I had to look it up on Wikipedia. Quantum supremacy is the potential ability of quantum computing devices to solve problems that classical computers practically cannot. The weaker term Quantum advantage refers to the potential to solve problems faster. In computational-complexity-theoretic terms, this generally means providing a superpolynomial speedup over the best known or possible classical algorithm. The term was originally popularized by John Preskill but the concept of a quantum computational advantage, specifically for simulating quantum systems, dates back to Yuri Manin's and Richard Feynman's proposals of quantum computing.