4 ms·

"This is a very nice demonstration of quantum advantage. While a great achievement academically, the algorithm used does not really have real world practical ap

by taeric 3y ago

"This is a very nice demonstration of quantum advantage. While a great achievement academically, the algorithm used does not really have real world practical applications, though." Not having real world applications is not necessarily damning, of course. Curious to know what implications this has for general algorithms. Reading this, it almost makes it sound like there will be some algorithms that quantum is better at and that they won't necessarily be the same algorithms that "classical" computing uses.

knorker 3y ago
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.
dwheeler 3y ago
The real question to me, is how it will take to get more (useful) qubits.
OkayPhysicist 3y ago
> It almost makes it sound like there will be some algorithms that quantum is better at and that they won't necessarily be the same algorithms that "classical" computing uses. This is exactly correct. While you can simulate classical computations on a quantum computer, it doesn't make a lot of sense to. However, there exists a class of problems for which there exist solutions that have lower time complexities than anything we can run on a classical computer, if only we had a quantum computer of sufficient size. Examples of such algorithms are the famous two, Shor's and Grover's algorithms, of which Shor's is more interesting because it factors integers in polynomial time whereas the best known classical algorithm runs in exponential time (this is the one that's scary for cryptography). Grover's algorithm is basically function inversion (find the x given a function f and some desired value y such that f(x)=y) in O(sqrt(N)) over the domain of the function, which on a classical computer requires O(N) operations. Those were discovered in the 90's, so they're pretty widely understood by now. There's a few newer ones, such as the quantum algorithm for linear systems of equations, which solves for a scalar result of an operation applied to the unknown vector x such that Ax=b in O(log(N)k^2) time versus the classical O(nk), where n is the number of matrix elements and k is a measure of how sensitive to error the problem is. Basically, there's a handful of useful algorithms, and another dozen or so theoretically interesting ones, that can run faster on a quantum computer. For everything else, there's zero advantage to using one.
jfengel 3y ago
Quantum computing is not a competitor for general computing. It solves certain categories of problems much faster, but not most of them. In fact, nobody yet really knows what those problems are. There are a few real-world problems that quantum computers could theoretically help with, like factoring large numbers, but nobody is really all that close to implementing them. There are problems that can be implemented, like this one, but they are of no use whatsoever. They just happen to be feasible to implement. The implementation does suggest that they're building up a toolbox of physical parts that could some day (years, less than decades) be used on real-world problems. The class of such problems appears very small so far, but there is reason to think that we could find other problems that matter. (For example, in the realm of AI, which is very compute-intensive -- though thus far nobody seems to have any specific implementation.) Think of a quantum computer as a magic box on the side that solves a few problems. If you had it, you might completely reconsider what kinds of problems you want to solve. Solving it via the magic box might require a complete reconsideration of how you frame the question -- like discovering a wormhole that lets you get from Atlanta to Seattle instantly, so how would you redesign a trip from New York to LA?

by taeric 3y ago

knorker 3y ago

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.

dwheeler 3y ago

The real question to me, is how it will take to get more (useful) qubits.

OkayPhysicist 3y ago

> It almost makes it sound like there will be some algorithms that quantum is better at and that they won't necessarily be the same algorithms that "classical" computing uses. This is exactly correct. While you can simulate classical computations on a quantum computer, it doesn't make a lot of sense to. However, there exists a class of problems for which there exist solutions that have lower time complexities than anything we can run on a classical computer, if only we had a quantum computer of sufficient size. Examples of such algorithms are the famous two, Shor's and Grover's algorithms, of which Shor's is more interesting because it factors integers in polynomial time whereas the best known classical algorithm runs in exponential time (this is the one that's scary for cryptography). Grover's algorithm is basically function inversion (find the x given a function f and some desired value y such that f(x)=y) in O(sqrt(N)) over the domain of the function, which on a classical computer requires O(N) operations. Those were discovered in the 90's, so they're pretty widely understood by now. There's a few newer ones, such as the quantum algorithm for linear systems of equations, which solves for a scalar result of an operation applied to the unknown vector x such that Ax=b in O(log(N)k^2) time versus the classical O(nk), where n is the number of matrix elements and k is a measure of how sensitive to error the problem is. Basically, there's a handful of useful algorithms, and another dozen or so theoretically interesting ones, that can run faster on a quantum computer. For everything else, there's zero advantage to using one.

jfengel 3y ago

Quantum computing is not a competitor for general computing. It solves certain categories of problems much faster, but not most of them. In fact, nobody yet really knows what those problems are. There are a few real-world problems that quantum computers could theoretically help with, like factoring large numbers, but nobody is really all that close to implementing them. There are problems that can be implemented, like this one, but they are of no use whatsoever. They just happen to be feasible to implement. The implementation does suggest that they're building up a toolbox of physical parts that could some day (years, less than decades) be used on real-world problems. The class of such problems appears very small so far, but there is reason to think that we could find other problems that matter. (For example, in the realm of AI, which is very compute-intensive -- though thus far nobody seems to have any specific implementation.) Think of a quantum computer as a magic box on the side that solves a few problems. If you had it, you might completely reconsider what kinds of problems you want to solve. Solving it via the magic box might require a complete reconsideration of how you frame the question -- like discovering a wormhole that lets you get from Atlanta to Seattle instantly, so how would you redesign a trip from New York to LA?