4 ms·

They have proved that it's physically possible for quantum computers to do things that classical computers can not. In other words, they have proved that quantu

by 6nf 7y ago

They have proved that it's physically possible for quantum computers to do things that classical computers can not. In other words, they have proved that quantum supremacy is real.

lisper 7y ago
No, they haven't. There is nothing that a QC can do that a CC cannot. CC's are universal. They can compute any computable function. What QC's can do in theory is perform some computations much faster than a CC can. One QC has actually done that, but the computation was of a function that cannot reasonably be called "useful". The potentially useful things that QCs can do is speed up factoring, protein folding analysis, simulation of chemical reactions... no QC has come anywhere near doing any of those things.
- 6nf 7y ago
  You don’t agree with Google’s November paper then I guess? You KNOW what quantum supremacy means. Please don’t nit pick my layman’s description we are all adults here. You know what I meant.
  - lisper 7y ago
    I'm not taking issue with your definition of quantum supremacy, I'm taking issue with your (implied) definition of "almost useful". Personally, I don't consider the demonstration of quantum supremacy in and of itself to be useful. It is very interesting, but IMHO it is not (yet) fair to say that QCs have done anything useful, even if you hedge with "almost".
    - meowface 7y ago
      Everything you've been posting is technically correct whereas the parent was technically incorrect, but it's still huge progress and an important step. No, they're not at the useful stage yet, but we can see now that it's inevitable, whether it's years or decades away.
      - lisper 7y ago
        Yes, it's huge progress, but huge progress != useful. And getting to useful, while very likely a matter of when and not if, is not inevitable. The number of qbits in current technology is measured in the dozens whereas the number of qbits needed to do something useful is likely in the thousands (because error correction will almost certainly be needed). QCs don't scale like CCs do. There could be some pretty significant obstacles between here and useful. C.f. fusion power, which has been 10 years away from being useful for about 40 years now.
- kragen 7y ago
  To nitpick your nitpick, we define "computable function" to mean any function that a classical computer can compute in finite time. There are a number of formal models of "hypercomputation" that could compute things that a classical computer can't compute, if they turned out to be physically realizable, but so far we don't have any evidence suggesting that they are, Tao's theorem about exploding coffee notwithstanding, since actually existing fluids are composed of atoms. So it is correct that quantum computation only allows us to, hypothetically, compute more quickly, rather than allowing us to compute things in finite time that classical computers can't compute in finite time. But it's circular logic, and therefore sloppy thinking, to say "CC's are universal. They can compute any computable function." It is of course true that quantum computers are still far from being practical tools for more rapid computation.
  - lisper 7y ago
    > it's circular logic, and therefore sloppy thinking, to say "CC's are universal. They can compute any computable function." No, it's not. In fact, it might not even be true. This is the Church-Turing thesis, and it is unproven and probably unprovable, but nonetheless almost certainly true. An actual counterexample would probably be the biggest news in the history of science.
    - kragen 7y ago
      Well, that's true if by "computable" you mean "possible to compute in practice in the physical universe" rather than "possible for a Turing machine (or the λ-calculus, etc.) to compute." But usually we use "computable" for the second class, not the first. In particular, you were using it to mean "possible for a Turing machine to compute" rather than "possible to compute in a physically realizable computer" when you said that classical computers are just as capable of performing protein-folding calculations and factoring as quantum computers, only more slowly. In fact, it is straightforward to construct factoring problems that cannot be performed by physically realizable classical computers by any known algorithm because it will take longer than the lifetime of the universe — or, at least, the matter in it. To be concrete, the current factoring record is RSA-240, a 795-bit number that was factored in November. This required about 2.37 × 10²³ steps of computation by my calculation, and was completed in 4000 core-years. I'm not sure how long it took in real time, nor do I remember how parallelizable GNFS is (I seem to recall it has a bottlenecked step.) To take a thousand times as much computation, you need a 1048-bit semiprime; for a million, 1344 bits; for a thousand million, 1685 bits (which, you'll note, gets us close to the age of the universe on one core); for 10¹² times as much, 2075 bits (close to the age of the universe on a thousand cores); for 10¹⁰⁰ times as much, 43687 bits. The Eddington number is that there are about 10⁸⁰ baryons in the observable universe, so if your computing cores are larger than a single proton, it will take you at least 10²⁰ times those 4000 core-years to factor a 43687-bit number with GNFS, that is, about 4 × 10²³ years. import math nfsln = lambda ln: math.exp(((64/9)**(1/3)) * ln**(1/3) * math.log(ln)**(2/3)) nfsln(43687*math.log(2))/nfsln(math.log( 12462036678171878406583504460810659043482037465167 88057548187888832896668011882108550360395702725087 47509864768438458621054865537970253930571891217684 31828636284694840530161441643046806687569941524699 3185704183030512549594371372159029236099 )) But that's still a relatively short time; yes, it's 10¹³ times longer than the universe has existed so far (and 10¹³ times longer than it will exist if the Big Rip happens, and about 10¹¹ times longer than it will exist if the Big Crunch happens), but it's possible that the universe might last longer than that. The Stelliferous Era is due to end in 10¹⁴ years, so that's a billion times longer than the Stelliferous Era will last, but red dwarfs will continue burning and providing power for another hundred times that long. Still, though, new red dwarfs will be formed from time to time, and perhaps they could power your classical computer for long enough to factor that number. Skipping over the Black Hole Era (can your computer survive the Black Hole Era?) all the black holes are conventionally predicted to have decayed via Hawking radiation in about 1.7 × 10¹⁰⁶ years. So a semiprime of 161133 bits, which will take about 2.37 × 10²⁰⁶ operations to factor with GNFS, cannot be factored in that time with the GNFS on classical computers as long as every Xeon-speed processor is bigger than a baryon. But wait! Maybe your processors can run faster; at the scale of nuclear reactions, a Xeon's few GHz is unimaginably slow. But there's still a speed limit: you can't realistically do more than one operation per Planck time, about 5.4 × 10⁻⁴⁴ seconds. So you can maybe get a speedup of up to about 10³⁵ by making your smaller classical processors go faster, using digital logic mechanisms yet unknown, perhaps shockwaves traveling around a neutron star or something. (All the nuclear reactions we know about run enormously slower than this, though.) Well, if you can run your proton-sized processors at 10⁴⁴ Hz, that means that by the end of the Black Hole Era you can factor a semiprime of 240857 bits or so on a classical computer. So that's probably pretty much the limit in the physical universe. If you can build a quantum computer, using Shor's algorithm, you can factor such a number in about 833586709574 operations (8.3 × 10¹¹) times whatever the constant factor is. shorln = lambda ln: ln**2 * math.log(ln) * math.log(math.log(ln)) shorln(math.log(2) * 240857) So, while you can definitely factor a 240857-bit semiprime on a Turing machine, which is a theoretical construct, you cannot factor it on a physically realizable computer — unless we can build a large quantum computer (one with almost half a million qubits), in which case we can do it in, probably, a few minutes. In conclusion, either your use of "computable" and "CC" in your original comment referred to computability in a particular family of abstract models of computation, not in physically realizable classical computers; or your statements in that post about the relative computing power of classical and quantum computers were simply mistaken with respect to current knowledge, because (assuming QCs are physically realizable) physically realizable QCs can compute things that physically realizable CCs are not known to be able to compute. I say not known to be able to compute because the question of whether BQP = P is still undecided. It might turn out that classical computers can simulate quantum computers in polynomial time, thus providing a polynomial-time algorithm for factoring — although this is unlikely, we don't have a proof that it's impossible. Even if BQP ≠ P, it's possible that integer factorization is in P, and we just haven't found an efficient algorithm for it yet, despite thousands of years of trying. But it's not the way to bet. It is of course correct that it would be an enormous and improbable breakthrough for someone to find a way to build a physically realizable computer that can compute things that an abstract, theoretical Turing machine cannot. That would be a counterexample to the Church–Turing thesis.
Koshkin 7y ago
> physically possible Was that a mathematical proof?
- 6nf 7y ago
  No google built a physical machine.
core-questions 7y ago
Google's quantum supremacy is BS, does anyone believe it? It can't do anything besides "not be simulated well".
- zozbot234 7y ago
  That's not BS, it's literally what "supremacy" means. Usefulness is an entirely different metric. And Google didn't come up with the term "quantum supremacy" (which is a rather awkward phrasing anyway), it was well established in QC research prior to anyone actually claiming it.
  - core-questions 7y ago
    It's only an awkward phrase because of what it reminds you of; maybe stop thinking about the bogeyman so much.
- meowface 7y ago
  It's not BS at all. It proved that they could use a quantum computer to compute something that would be infeasible for a classical computer to solve in a reasonable time frame. That's huge. It's a toy computation, sure, but that's still a major step. It has to be scaled up much more before it can do useful things, and the scaling process is very difficult and costly. But we now have confirmation that the idea is sound.
  - core-questions 7y ago
    > It proved that they could use a quantum computer to compute something that would be infeasible for a classical computer to solve in a reasonable time frame. Yeah, but they were basically computing noise, and it's bloody difficult to say that the ability to do that is meaningful enough to have claimed "supremacy" already. It's a huge premature celebration for a team that has had incredible difficulty trying to scale up beyond a tiny number of noisy qubits; like, good for them, but the purpose of this effort really seems to be to make for good water-cooler conversation among the Google execs than it is to actually do useful science.

by 6nf 7y ago

They have proved that it's physically possible for quantum computers to do things that classical computers can not. In other words, they have proved that quantum supremacy is real.

lisper 7y ago

No, they haven't. There is nothing that a QC can do that a CC cannot. CC's are universal. They can compute any computable function. What QC's can do in theory is perform some computations much faster than a CC can. One QC has actually done that, but the computation was of a function that cannot reasonably be called "useful". The potentially useful things that QCs can do is speed up factoring, protein folding analysis, simulation of chemical reactions... no QC has come anywhere near doing any of those things.

6nf 7y ago
You don’t agree with Google’s November paper then I guess? You KNOW what quantum supremacy means. Please don’t nit pick my layman’s description we are all adults here. You know what I meant.
- lisper 7y ago
  I'm not taking issue with your definition of quantum supremacy, I'm taking issue with your (implied) definition of "almost useful". Personally, I don't consider the demonstration of quantum supremacy in and of itself to be useful. It is very interesting, but IMHO it is not (yet) fair to say that QCs have done anything useful, even if you hedge with "almost".
  - meowface 7y ago
    Everything you've been posting is technically correct whereas the parent was technically incorrect, but it's still huge progress and an important step. No, they're not at the useful stage yet, but we can see now that it's inevitable, whether it's years or decades away.
    - lisper 7y ago
      Yes, it's huge progress, but huge progress != useful. And getting to useful, while very likely a matter of when and not if, is not inevitable. The number of qbits in current technology is measured in the dozens whereas the number of qbits needed to do something useful is likely in the thousands (because error correction will almost certainly be needed). QCs don't scale like CCs do. There could be some pretty significant obstacles between here and useful. C.f. fusion power, which has been 10 years away from being useful for about 40 years now.
kragen 7y ago
To nitpick your nitpick, we define "computable function" to mean any function that a classical computer can compute in finite time. There are a number of formal models of "hypercomputation" that could compute things that a classical computer can't compute, if they turned out to be physically realizable, but so far we don't have any evidence suggesting that they are, Tao's theorem about exploding coffee notwithstanding, since actually existing fluids are composed of atoms. So it is correct that quantum computation only allows us to, hypothetically, compute more quickly, rather than allowing us to compute things in finite time that classical computers can't compute in finite time. But it's circular logic, and therefore sloppy thinking, to say "CC's are universal. They can compute any computable function." It is of course true that quantum computers are still far from being practical tools for more rapid computation.
- lisper 7y ago
  > it's circular logic, and therefore sloppy thinking, to say "CC's are universal. They can compute any computable function." No, it's not. In fact, it might not even be true. This is the Church-Turing thesis, and it is unproven and probably unprovable, but nonetheless almost certainly true. An actual counterexample would probably be the biggest news in the history of science.
  - kragen 7y ago
    Well, that's true if by "computable" you mean "possible to compute in practice in the physical universe" rather than "possible for a Turing machine (or the λ-calculus, etc.) to compute." But usually we use "computable" for the second class, not the first. In particular, you were using it to mean "possible for a Turing machine to compute" rather than "possible to compute in a physically realizable computer" when you said that classical computers are just as capable of performing protein-folding calculations and factoring as quantum computers, only more slowly. In fact, it is straightforward to construct factoring problems that cannot be performed by physically realizable classical computers by any known algorithm because it will take longer than the lifetime of the universe — or, at least, the matter in it. To be concrete, the current factoring record is RSA-240, a 795-bit number that was factored in November. This required about 2.37 × 10²³ steps of computation by my calculation, and was completed in 4000 core-years. I'm not sure how long it took in real time, nor do I remember how parallelizable GNFS is (I seem to recall it has a bottlenecked step.) To take a thousand times as much computation, you need a 1048-bit semiprime; for a million, 1344 bits; for a thousand million, 1685 bits (which, you'll note, gets us close to the age of the universe on one core); for 10¹² times as much, 2075 bits (close to the age of the universe on a thousand cores); for 10¹⁰⁰ times as much, 43687 bits. The Eddington number is that there are about 10⁸⁰ baryons in the observable universe, so if your computing cores are larger than a single proton, it will take you at least 10²⁰ times those 4000 core-years to factor a 43687-bit number with GNFS, that is, about 4 × 10²³ years. import math nfsln = lambda ln: math.exp(((64/9)**(1/3)) * ln**(1/3) * math.log(ln)**(2/3)) nfsln(43687*math.log(2))/nfsln(math.log( 12462036678171878406583504460810659043482037465167 88057548187888832896668011882108550360395702725087 47509864768438458621054865537970253930571891217684 31828636284694840530161441643046806687569941524699 3185704183030512549594371372159029236099 )) But that's still a relatively short time; yes, it's 10¹³ times longer than the universe has existed so far (and 10¹³ times longer than it will exist if the Big Rip happens, and about 10¹¹ times longer than it will exist if the Big Crunch happens), but it's possible that the universe might last longer than that. The Stelliferous Era is due to end in 10¹⁴ years, so that's a billion times longer than the Stelliferous Era will last, but red dwarfs will continue burning and providing power for another hundred times that long. Still, though, new red dwarfs will be formed from time to time, and perhaps they could power your classical computer for long enough to factor that number. Skipping over the Black Hole Era (can your computer survive the Black Hole Era?) all the black holes are conventionally predicted to have decayed via Hawking radiation in about 1.7 × 10¹⁰⁶ years. So a semiprime of 161133 bits, which will take about 2.37 × 10²⁰⁶ operations to factor with GNFS, cannot be factored in that time with the GNFS on classical computers as long as every Xeon-speed processor is bigger than a baryon. But wait! Maybe your processors can run faster; at the scale of nuclear reactions, a Xeon's few GHz is unimaginably slow. But there's still a speed limit: you can't realistically do more than one operation per Planck time, about 5.4 × 10⁻⁴⁴ seconds. So you can maybe get a speedup of up to about 10³⁵ by making your smaller classical processors go faster, using digital logic mechanisms yet unknown, perhaps shockwaves traveling around a neutron star or something. (All the nuclear reactions we know about run enormously slower than this, though.) Well, if you can run your proton-sized processors at 10⁴⁴ Hz, that means that by the end of the Black Hole Era you can factor a semiprime of 240857 bits or so on a classical computer. So that's probably pretty much the limit in the physical universe. If you can build a quantum computer, using Shor's algorithm, you can factor such a number in about 833586709574 operations (8.3 × 10¹¹) times whatever the constant factor is. shorln = lambda ln: ln**2 * math.log(ln) * math.log(math.log(ln)) shorln(math.log(2) * 240857) So, while you can definitely factor a 240857-bit semiprime on a Turing machine, which is a theoretical construct, you cannot factor it on a physically realizable computer — unless we can build a large quantum computer (one with almost half a million qubits), in which case we can do it in, probably, a few minutes. In conclusion, either your use of "computable" and "CC" in your original comment referred to computability in a particular family of abstract models of computation, not in physically realizable classical computers; or your statements in that post about the relative computing power of classical and quantum computers were simply mistaken with respect to current knowledge, because (assuming QCs are physically realizable) physically realizable QCs can compute things that physically realizable CCs are not known to be able to compute. I say not known to be able to compute because the question of whether BQP = P is still undecided. It might turn out that classical computers can simulate quantum computers in polynomial time, thus providing a polynomial-time algorithm for factoring — although this is unlikely, we don't have a proof that it's impossible. Even if BQP ≠ P, it's possible that integer factorization is in P, and we just haven't found an efficient algorithm for it yet, despite thousands of years of trying. But it's not the way to bet. It is of course correct that it would be an enormous and improbable breakthrough for someone to find a way to build a physically realizable computer that can compute things that an abstract, theoretical Turing machine cannot. That would be a counterexample to the Church–Turing thesis.

Koshkin 7y ago

> physically possible Was that a mathematical proof?

6nf 7y ago
No google built a physical machine.

core-questions 7y ago

Google's quantum supremacy is BS, does anyone believe it? It can't do anything besides "not be simulated well".

zozbot234 7y ago
That's not BS, it's literally what "supremacy" means. Usefulness is an entirely different metric. And Google didn't come up with the term "quantum supremacy" (which is a rather awkward phrasing anyway), it was well established in QC research prior to anyone actually claiming it.
- core-questions 7y ago
  It's only an awkward phrase because of what it reminds you of; maybe stop thinking about the bogeyman so much.
meowface 7y ago
It's not BS at all. It proved that they could use a quantum computer to compute something that would be infeasible for a classical computer to solve in a reasonable time frame. That's huge. It's a toy computation, sure, but that's still a major step. It has to be scaled up much more before it can do useful things, and the scaling process is very difficult and costly. But we now have confirmation that the idea is sound.
- core-questions 7y ago
  > It proved that they could use a quantum computer to compute something that would be infeasible for a classical computer to solve in a reasonable time frame. Yeah, but they were basically computing noise, and it's bloody difficult to say that the ability to do that is meaningful enough to have claimed "supremacy" already. It's a huge premature celebration for a team that has had incredible difficulty trying to scale up beyond a tiny number of noisy qubits; like, good for them, but the purpose of this effort really seems to be to make for good water-cooler conversation among the Google execs than it is to actually do useful science.