5 ms·

My understanding is that quantum computers only have two real use cases, as of today: 1. Breaking crypto. 2. Simulating other quantum systems. For (1) it's ba

My understanding is that quantum computers only have two real use cases, as of today: 1. Breaking crypto. 2. Simulating other quantum systems. For (1) it's basically all downsides. For (2) unless you're a particle phycisist you'll never need quantum computers. But that's now. Maybe there will be a killer app for it some day, changing everything. Or indeed, we could get it indirectly. Maybe simulating quantum systems we could invent new battery technologies, which in turn changes our lives.

esrauch 3y ago
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".
jfindley 3y ago
I think there are some other areas where qc is likely to deliver better results than classical computers beyond these two. Modelling turblent flows is one such example. They certainly aren't common, but I think this overstates the case somewhat.
staunton 3y ago
(2) can be very relevant to material science and chemistry. Those things have huge ranges of important practical applications. For example, people currently struggle to do accurate calculations of the band structures of materials and it doesn't look like there will be much progress there using only classical computers (using more computing power or better approximation tricks). Big enough quantum computers could do this. Band structure calculations are very interesting for pretty much all semiconductor development.
- knorker 3y ago
  Indeed. That's what I meant by my example of indirect benefit. Simulating physical systems better, faster, and more completely, can have many practical applications. But unless you're already today trying to simulate physical systems like that, then QC probably won't help you one bit.
pyrale 3y ago
Basically, quantum computers can solve problems of the BQP class in a time that is a polynomial function of input size. These same problems, on a traditional computer, can take exponential time. It is hard to tell with certainty what can be done with quantum computers, but having powerful quantum computers will certainly open new fields of research, like trying to figure out if quantum algorithms for NP-class problems have better complexity than classical algorithms. Simply finding subexponential algorithms for problems that would have required exponential time on a traditional computer, may prove valuable. Basically, outside of the immediately available problems, this opens up an entirely new complexity class from which to attempt to crack other classes of complexity. Trying to break NP-problems with turing machines, if not successful in an academic sense, has proved immensely valuable and profitable. By getting another architecture, we get a shot at similar breakthroughs.
- knorker 3y ago
  This is so extremely well put that I want to reply just to highlight it. What you said was the optimist view, that there's a world of possibilities. It's just that at the moment we just have the two I mentioned. Maybe there's much more, and if we build it (the hardware), they (the algorithms) will come. But for now really just the two. AFAIK.

esrauch 3y ago

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".

jfindley 3y ago

I think there are some other areas where qc is likely to deliver better results than classical computers beyond these two. Modelling turblent flows is one such example. They certainly aren't common, but I think this overstates the case somewhat.

staunton 3y ago

(2) can be very relevant to material science and chemistry. Those things have huge ranges of important practical applications. For example, people currently struggle to do accurate calculations of the band structures of materials and it doesn't look like there will be much progress there using only classical computers (using more computing power or better approximation tricks). Big enough quantum computers could do this. Band structure calculations are very interesting for pretty much all semiconductor development.

knorker 3y ago
Indeed. That's what I meant by my example of indirect benefit. Simulating physical systems better, faster, and more completely, can have many practical applications. But unless you're already today trying to simulate physical systems like that, then QC probably won't help you one bit.

pyrale 3y ago

Basically, quantum computers can solve problems of the BQP class in a time that is a polynomial function of input size. These same problems, on a traditional computer, can take exponential time. It is hard to tell with certainty what can be done with quantum computers, but having powerful quantum computers will certainly open new fields of research, like trying to figure out if quantum algorithms for NP-class problems have better complexity than classical algorithms. Simply finding subexponential algorithms for problems that would have required exponential time on a traditional computer, may prove valuable. Basically, outside of the immediately available problems, this opens up an entirely new complexity class from which to attempt to crack other classes of complexity. Trying to break NP-problems with turing machines, if not successful in an academic sense, has proved immensely valuable and profitable. By getting another architecture, we get a shot at similar breakthroughs.

knorker 3y ago
This is so extremely well put that I want to reply just to highlight it. What you said was the optimist view, that there's a world of possibilities. It's just that at the moment we just have the two I mentioned. Maybe there's much more, and if we build it (the hardware), they (the algorithms) will come. But for now really just the two. AFAIK.