4 ms·

If it is able to break crypto then surely that means it can do other "interesting" mathematical calculations that are currently extremely slow/hard though?

arcticbull 3y ago
So far, to my knowledge, not faster than a classical system. We've been searching for decades for a problem with a better quantum solution than a classical solution, and it's been a tough slog. These are, at least thus far and from my limited perspective, very special-purpose accelerators. Shor's algorithm is the one thing that comes to mind tbh. "Breaking crypto" in this case isn't anything other than finding prime factors of an integer.
knorker 3y ago
Possibly. This is way beyond my knowledge. But I'm not aware of many other "search this finite part of the number line for this property", where "this finite part" is still too big for classical computers. It almost sounds like quantum computers are tailor made for the types of problems we've been building cryptosystems on. But maybe this is not all quantum computers will be able to do. I couldn't even explain exactly how they apply to simulations of quantum systems, but have only taken more knowledgeable people at their word.
- taeric 3y ago
  "Search this finite part of a number line" is probably fairly accurate in describing many Mixed Integer Programming (MIP) techniques. Such that, if you do get a breakthrough at that, you may see larger advances in optimization.
  - dotnet00 3y ago
    Exactly, ML is a potentially very valuable task for more mature quantum computers due to the ability to perform much more powerful searches than what we have to accept on classical computers.
hannob 3y ago
That's not all that clear. The problems QCs could solve regarding crypto are from number theory. That's basically a branch of math that doesn't really describe any real-world stuff. Cryptography is as far as I know the only practical application of that stuff. I couldn't think of any implication of "being able to factor large numbers quickly" or "calculating discrete logarithms quickly" that does not relate to cryptography. But I'd be curious if others think these would have any implications beyond "we'll have to get new algorithms into our cryptography".
olliej 3y ago
Nope. QC allows a very specific attack that breaks the main asymmetric algorithms today, ECC and RSA - there is no meaningful attack on anything else (Grover's algorithm is technically a sqrt improvement on symmetric algorithms but that isn't close to breaking AES256). There's nothing general purpose in the attack on RSA and ECC: you can use the quantum Fourier transform to find the period of the key, and that period tells you the key. But this is very specific - you have two algorithms that have inherently periodic behavior, where the period is meant to be secret, and so all you need from the QC is the period. It's hard to see how to extend that to other problems. I'm more curious about (and kind of wish more emphasis would be made on) programmable analog computers, which is what it seems QC should be capable of. A lot of the difficult with QC is that people seem really fixated on discrete problems (like factoring \o/) where there's a single correct answer, and so huge amounts of effort and research are going into error correction, etc. There are lots of problems (simulations as in this circuit), where the classical solution simply requires running millions of times with random variance to converge on a sufficiently accurate result where a QC would theoretically be great. The general use problem in that case becomes "how do I convert this classical problem into a QC compatible algorithm".

arcticbull 3y ago

So far, to my knowledge, not faster than a classical system. We've been searching for decades for a problem with a better quantum solution than a classical solution, and it's been a tough slog. These are, at least thus far and from my limited perspective, very special-purpose accelerators. Shor's algorithm is the one thing that comes to mind tbh. "Breaking crypto" in this case isn't anything other than finding prime factors of an integer.

knorker 3y ago

Possibly. This is way beyond my knowledge. But I'm not aware of many other "search this finite part of the number line for this property", where "this finite part" is still too big for classical computers. It almost sounds like quantum computers are tailor made for the types of problems we've been building cryptosystems on. But maybe this is not all quantum computers will be able to do. I couldn't even explain exactly how they apply to simulations of quantum systems, but have only taken more knowledgeable people at their word.

taeric 3y ago
"Search this finite part of a number line" is probably fairly accurate in describing many Mixed Integer Programming (MIP) techniques. Such that, if you do get a breakthrough at that, you may see larger advances in optimization.
- dotnet00 3y ago
  Exactly, ML is a potentially very valuable task for more mature quantum computers due to the ability to perform much more powerful searches than what we have to accept on classical computers.

hannob 3y ago

That's not all that clear. The problems QCs could solve regarding crypto are from number theory. That's basically a branch of math that doesn't really describe any real-world stuff. Cryptography is as far as I know the only practical application of that stuff. I couldn't think of any implication of "being able to factor large numbers quickly" or "calculating discrete logarithms quickly" that does not relate to cryptography. But I'd be curious if others think these would have any implications beyond "we'll have to get new algorithms into our cryptography".

olliej 3y ago

Nope. QC allows a very specific attack that breaks the main asymmetric algorithms today, ECC and RSA - there is no meaningful attack on anything else (Grover's algorithm is technically a sqrt improvement on symmetric algorithms but that isn't close to breaking AES256). There's nothing general purpose in the attack on RSA and ECC: you can use the quantum Fourier transform to find the period of the key, and that period tells you the key. But this is very specific - you have two algorithms that have inherently periodic behavior, where the period is meant to be secret, and so all you need from the QC is the period. It's hard to see how to extend that to other problems. I'm more curious about (and kind of wish more emphasis would be made on) programmable analog computers, which is what it seems QC should be capable of. A lot of the difficult with QC is that people seem really fixated on discrete problems (like factoring \o/) where there's a single correct answer, and so huge amounts of effort and research are going into error correction, etc. There are lots of problems (simulations as in this circuit), where the classical solution simply requires running millions of times with random variance to converge on a sufficiently accurate result where a QC would theoretically be great. The general use problem in that case becomes "how do I convert this classical problem into a QC compatible algorithm".