5 ms·

It's 2020, and I'm still waiting to see an impressive proof of work out out of a quantum computer that I can easily verify on my traditional computer (two diffe

by da-x 6y ago

It's 2020, and I'm still waiting to see an impressive proof of work out out of a quantum computer that I can easily verify on my traditional computer (two different files with identical SHA-512, for example?). Maybe a few years from now?

united893 6y ago
It's been demonstrated already using a random circuit. Two random strings that match SHA, are practically speaking just toy examples using random useless information. There's no meaning to the numbers except that when you apply an operation to them the have the same output. Now, instead of the random string, you have a random circuit. And the output is the goal. The random circuit is as useful to you as the random string. But using a quantum computer you can compute its state when operating. With a traditional computer it is very hard. https://www.nature.com/articles/s41586-019-1666-5 https://www.nature.com/articles/s41586-019-1666-5 https://www.scottaaronson.com/blog/?p=4317 https://www.scottaaronson.com/blog/?p=4317
adrianN 6y ago
The keywords to google for when looking for such things are "quantum supremacy"
- Yizahi 6y ago
  "Quantum supremacy", aside from dumb naming, as far as I understood from news is an attempt to find a possible problem to the solution they have invented (quantum device itself), to prove that their quantum device can do at least something which cannot be replicated with the same magnitude of speed (or at all) on "normal" computers. And it was contested even in such limited scope. OP asks for next step - do some useful computation. Reverse order - have the problem at start (preferably "real" problem) and compute solution to it.
takeda 6y ago
Maybe the proof exists in a different reality? :)
bawolff 6y ago
Finding an sha-512 collision is not a problem that quantum computers can help with, even in theory.* Anyways, if you want something that can be verified on a classical computer but cannot be done on a classical computer, see google's recent Quantum supremacy experiment. However it is extremely contrived. I think the most likely non contrived thing will be simulating simpilish quantum systems (to help with chemistry experiments and the like), but its probably still going to be a while before we start seeing that i think (IANA quantum scientist). *Edit: to clarify, quantum computers can speed the process up of finding a collision in theory, just not enough to help. Normally you would need O(2^256) operations to find sha512 collision (Birthday paradox), quantum (BHT) gets you down to O(2^170), which is better, but still way to high. Most crypto assumes anything greater than 2^128 is secure by a comfortable margin.
- McTossOut 6y ago
  Uhhb It's contrived because there's still nothing formal to indicate that there exists classes of problems for which a quantum computer is efficient and a deterministic computer is not... kind of a central result. However it is suspected.
- deleted 6y ago
  [deleted]
- l33tman 6y ago
  "Extremely contrived" is a little bit misleading since they did in fact run random algorithms from a general set of algorithms. So it's rather the opposite of contrived.. but I understand what you mean :)
  - bawolff 6y ago
    Contrived means "Deliberately created rather than arising naturally or spontaneously" https://www.lexico.com/en/definition/contrived https://www.lexico.com/en/definition/contrived . I think the problems used to demonstrate quantum supremacy very literally meet that definition - they were largely created for the sole purpose of demonstrating supremacy; they are not problems we naturally want to know the answers to.

by da-x 6y ago

united893 6y ago

It's been demonstrated already using a random circuit. Two random strings that match SHA, are practically speaking just toy examples using random useless information. There's no meaning to the numbers except that when you apply an operation to them the have the same output. Now, instead of the random string, you have a random circuit. And the output is the goal. The random circuit is as useful to you as the random string. But using a quantum computer you can compute its state when operating. With a traditional computer it is very hard. https://www.nature.com/articles/s41586-019-1666-5 https://www.nature.com/articles/s41586-019-1666-5 https://www.scottaaronson.com/blog/?p=4317 https://www.scottaaronson.com/blog/?p=4317

adrianN 6y ago

The keywords to google for when looking for such things are "quantum supremacy"

Yizahi 6y ago
"Quantum supremacy", aside from dumb naming, as far as I understood from news is an attempt to find a possible problem to the solution they have invented (quantum device itself), to prove that their quantum device can do at least something which cannot be replicated with the same magnitude of speed (or at all) on "normal" computers. And it was contested even in such limited scope. OP asks for next step - do some useful computation. Reverse order - have the problem at start (preferably "real" problem) and compute solution to it.

takeda 6y ago

Maybe the proof exists in a different reality? :)

bawolff 6y ago

Finding an sha-512 collision is not a problem that quantum computers can help with, even in theory.* Anyways, if you want something that can be verified on a classical computer but cannot be done on a classical computer, see google's recent Quantum supremacy experiment. However it is extremely contrived. I think the most likely non contrived thing will be simulating simpilish quantum systems (to help with chemistry experiments and the like), but its probably still going to be a while before we start seeing that i think (IANA quantum scientist). *Edit: to clarify, quantum computers can speed the process up of finding a collision in theory, just not enough to help. Normally you would need O(2^256) operations to find sha512 collision (Birthday paradox), quantum (BHT) gets you down to O(2^170), which is better, but still way to high. Most crypto assumes anything greater than 2^128 is secure by a comfortable margin.

McTossOut 6y ago
Uhhb It's contrived because there's still nothing formal to indicate that there exists classes of problems for which a quantum computer is efficient and a deterministic computer is not... kind of a central result. However it is suspected.
deleted 6y ago
[deleted]
l33tman 6y ago
"Extremely contrived" is a little bit misleading since they did in fact run random algorithms from a general set of algorithms. So it's rather the opposite of contrived.. but I understand what you mean :)
- bawolff 6y ago
  Contrived means "Deliberately created rather than arising naturally or spontaneously" https://www.lexico.com/en/definition/contrived https://www.lexico.com/en/definition/contrived . I think the problems used to demonstrate quantum supremacy very literally meet that definition - they were largely created for the sole purpose of demonstrating supremacy; they are not problems we naturally want to know the answers to.