5 ms·

At the moment I believe they can only solve toy problems (like factoring the number 15 - it's apparently 3 * 5 with high probability) and/or ones that are speci

At the moment I believe they can only solve toy problems (like factoring the number 15 - it's apparently 3 * 5 with high probability) and/or ones that are specifically contrived to show quantum supremacy.

nradov 5y ago
What is the probability that 15=2*7?
- FartyMcFarter 5y ago
  Slightly lower :)
- amelius 5y ago
  Exactly 1, for large values of 2.
  - rbanffy 5y ago
    Or low values of 15. We must consider that other possibility.
  - Frost1x 5y ago
    I'd say exactly 1 for very moderate or average values of 2. The very large values might converge on 21 but I'll have to flip a coin on it.
- Razengan 5y ago
  What is 2? What is 7?
  - ohhhhhh 5y ago
    now youre asking the right questions lol
    - Razengan 5y ago
      We must run enough samples of 2 and 7 through the AI/ML to be sure.
- marcosdumay 5y ago
  You mean "what's the probability that your computer will say that 15=2*7"? Well, that's nonzero for any classical deterministic algorithm you can run on your computer too.
TheRealSteel 5y ago
"like factoring the number 15 - it's apparently 3 * 5 with high probability" I thought you were talking about deep learning there for a second
- rbanffy 5y ago
  The values of 3 and 5 will have to be very precise if you want a good 15 out of the multiplication. You may also have a high 5, that could compensate for a low value of 2.
  - vorticalbox 5y ago
    Do you happen to have some links about high 5 and low 2? Interested in what these mean.
    - notamy 5y ago
      I imagine they just mean something like how 15/5.9=2.54
    - yreg 5y ago
      15 ≈ 5.8 * 2.6
upofadown 5y ago
Supposedly the factorization of 15 is controversial. It is claimed that the process implicitly assumed the correct result. Not even a single logical qubit has been achieved to date, even with error correction, so it might be a bit soon to talk of factoring anything.
- Qu3tzal 5y ago
  What do you mean? I thought we were able to run programs on these processors already.
  - klyrs 5y ago
    "Running programs" is easy. Getting correct answers, not so much. In the case of factoring 15, afaik, nobody has been able to execute Shor's algorithm faithfully -- instead, they simplify the factoring problem using knowledge of the answer. This isn't necessarily about Google -- last I looked, IBM holds the "factorization record" where they were either using a modified Grover's algorithm that incorporated knowledge of the factors. This isn't my area of expertise, but if it was, I'd be hugely embarrassed by the industry. And then off in the corner, we've got D-Wave, who everybody loves to hate on, doing their own thing with an optimization-based approach to factoring which actually seems to work on (iirc) 10-ish bit semiprimes and zero foreknowledge.
spywaregorilla 5y ago
I've come to understand quantum computing problems are basically just specific formulations of things where multiple bad paths will just cancel out due to some sort of probability amplitude summing to 0. I suppose this makes sense then that the answer would be associated with some probability rather than a fixed answer. Is this theoretically likely to give near certain probability to the right answer on large problems or will it be affected by local minimums and what not? Is that the issue with scale? That noise propagates through the system and renders the uplift in problem solving moot?
- tylerhou 5y ago
  Many quantum algorithms can be iterated to find a solution with arbitrarily high probability. For example, Grover's algorithm has an amplification step, and Shor's algorithm can be repeated (with a different seed guess) creating a new solution with roughly independent probability.
wydfre 5y ago
No, quantum supremacy has been displayed already by google[0]. [0]: https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html https://ai.googleblog.com/2019/10/quantum-supremacy-using-pr...
- FartyMcFarter 5y ago
  That's an example of what I meant by problems that "are specifically contrived to show quantum supremacy". Scott Aaronson explains this quite well: https://www.scottaaronson.com/blog/?p=4317 https://www.scottaaronson.com/blog/?p=4317 > So, tl;dr, the quantum computer is simply asked to apply a random (but known) sequence of quantum operations—not because we intrinsically care about the result, but because we’re trying to prove that it can beat a classical computer at some well-defined task.

nradov 5y ago

What is the probability that 15=2*7?

FartyMcFarter 5y ago
Slightly lower :)
amelius 5y ago
Exactly 1, for large values of 2.
- rbanffy 5y ago
  Or low values of 15. We must consider that other possibility.
- Frost1x 5y ago
  I'd say exactly 1 for very moderate or average values of 2. The very large values might converge on 21 but I'll have to flip a coin on it.
Razengan 5y ago
What is 2? What is 7?
- ohhhhhh 5y ago
  now youre asking the right questions lol
  - Razengan 5y ago
    We must run enough samples of 2 and 7 through the AI/ML to be sure.
marcosdumay 5y ago
You mean "what's the probability that your computer will say that 15=2*7"? Well, that's nonzero for any classical deterministic algorithm you can run on your computer too.

TheRealSteel 5y ago

"like factoring the number 15 - it's apparently 3 * 5 with high probability" I thought you were talking about deep learning there for a second

rbanffy 5y ago
The values of 3 and 5 will have to be very precise if you want a good 15 out of the multiplication. You may also have a high 5, that could compensate for a low value of 2.
- vorticalbox 5y ago
  Do you happen to have some links about high 5 and low 2? Interested in what these mean.
  - notamy 5y ago
    I imagine they just mean something like how 15/5.9=2.54
  - yreg 5y ago
    15 ≈ 5.8 * 2.6

upofadown 5y ago

Supposedly the factorization of 15 is controversial. It is claimed that the process implicitly assumed the correct result. Not even a single logical qubit has been achieved to date, even with error correction, so it might be a bit soon to talk of factoring anything.

Qu3tzal 5y ago
What do you mean? I thought we were able to run programs on these processors already.
- klyrs 5y ago
  "Running programs" is easy. Getting correct answers, not so much. In the case of factoring 15, afaik, nobody has been able to execute Shor's algorithm faithfully -- instead, they simplify the factoring problem using knowledge of the answer. This isn't necessarily about Google -- last I looked, IBM holds the "factorization record" where they were either using a modified Grover's algorithm that incorporated knowledge of the factors. This isn't my area of expertise, but if it was, I'd be hugely embarrassed by the industry. And then off in the corner, we've got D-Wave, who everybody loves to hate on, doing their own thing with an optimization-based approach to factoring which actually seems to work on (iirc) 10-ish bit semiprimes and zero foreknowledge.

spywaregorilla 5y ago

I've come to understand quantum computing problems are basically just specific formulations of things where multiple bad paths will just cancel out due to some sort of probability amplitude summing to 0. I suppose this makes sense then that the answer would be associated with some probability rather than a fixed answer. Is this theoretically likely to give near certain probability to the right answer on large problems or will it be affected by local minimums and what not? Is that the issue with scale? That noise propagates through the system and renders the uplift in problem solving moot?

tylerhou 5y ago
Many quantum algorithms can be iterated to find a solution with arbitrarily high probability. For example, Grover's algorithm has an amplification step, and Shor's algorithm can be repeated (with a different seed guess) creating a new solution with roughly independent probability.

wydfre 5y ago

No, quantum supremacy has been displayed already by google[0]. [0]: https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html https://ai.googleblog.com/2019/10/quantum-supremacy-using-pr...

FartyMcFarter 5y ago
That's an example of what I meant by problems that "are specifically contrived to show quantum supremacy". Scott Aaronson explains this quite well: https://www.scottaaronson.com/blog/?p=4317 https://www.scottaaronson.com/blog/?p=4317 > So, tl;dr, the quantum computer is simply asked to apply a random (but known) sequence of quantum operations—not because we intrinsically care about the result, but because we’re trying to prove that it can beat a classical computer at some well-defined task.