5 ms·

I'm one of the authors on this paper and can answer questions if people have some.

agsamek 7y ago
Hi. I would like to take the opportunity to get your opinion on quantum computing. My understanding is that there is a significant work in theoretical quantum computing done by you and many people. Results presented by you seems impressive. Congratulations. On the other hand - everything I read, hear and try to interpret about D-wave seems like a nonsense. They show approximation computations and compare it to classical algorithms that provide exact results. But classical approximation algorithms work much better than their quantum computers. I do not see how scaling this approach could lead to anything that you describe in your paper. In this regard - is my understanding of D-wave correct or does it provide some value that is better than classical computers? Can d-wave or IBM's creation be used to do computations described in your paper? Is their approach worth anything? [edit] Of course I'm not asking about now - my question is whether there is anything connected to exact results (like factoring) and exponential speed-up in d-wave approach.
- Strilanc 7y ago
  I don't really know a lot about D-wave to be honest. I defer to Scott Aaronson's posts [1] and to the opinion that the main criteria for success is "solve hard problems" as opposed to "solve hard problems with a quantum computer" [2]. [1]: https://scottaaronson.com/blog/?s=dwave https://scottaaronson.com/blog/?s=dwave [2]: https://youtu.be/XbFoXT73xVQ?t=355 https://youtu.be/XbFoXT73xVQ?t=355
  - scottlocklin 7y ago
    Without hardware, you're not solving any problems. Glass bead game != solving problems. At no point in human history as this sort of "detailed theoretical wanking" turned into progress in science; the hardware comes first.
    - mannykannot 7y ago
      How do you get the idea to build something without any thought about what it will do?
    - kuzehanka 7y ago
      Convnets were detailed 1980s and didn't become viable until hardware caught up in the 2010s.
    - deleted 7y ago
      [deleted]
    - sgt101 7y ago
      I was under the impression that theoretical physics detailing underpinning mechanisms proceeded the transistor, nuclear weapons and fibre optics.
      - behringer 7y ago
        That's true of most inventions. We had programming and boolean logic before we had computers. And of course we would, you can't build a boat without water to sail on.
        NeutronStar 7y ago
        You can't build a boat if you never had the idea of what a boat is supposed to be.
  - agsamek 7y ago
    Hmmmmm. I tried to follow this youtube, but it doesn't make sense for me. The guy is saying that D-wave would be a success even if it was not a quantum but only solved a hard problem. I could buy this, but they do not solve any problem yet that was not solvable with probabilistic classical algorithms before. I would also give them a credit if they didn't solve any problem yet but showed real quantum computer at work. Eg. could do factoring of 50 digit number. Or are on the way to do this somehow and made understandable progress in the area. Even though they didn't fully succeed yet. What they do to my understanding is: * approach a problem that is hard in general. * solve only a simple and already solvable case * when asked that it may not be a quantum thay say that even if it was not quantum then ok because the problem is hard (while it is not) * if asked about the problem being easy they say that maybe the problem is easy but this is quantum. Do I understand this correctly? I would really appreciate more explanation
    - Strilanc 7y ago
      I agree with all of that.
deleted 7y ago
[deleted]
mikorym 7y ago
Is your approach here to focus on the theoretical background or is it also to comment on feasibility on hardware in the next x years?
- Strilanc 7y ago
  I'm having a hard time parsing your question. Our goal in this paper was to better understand the resources required to factor with a quantum computer. These estimates can then be fed into decisions about the rate post-quantum cryptosystems need to be deployed. We don't make predictions about the expected capabilities of hardware over time. We do frame our results in terms of specific hardware assumptions (e.g. particular gate speeds and errors rates), but most of the improvements we make are about how to do arithmetic and so they generalize beyond these assumptions.
  - mikorym 7y ago
    Cool, I think that does answer my question. You do both, but the feasibility part is in the form of hardware assumptions that don't comment on the current or future state of hardware.
truth_seeker 7y ago
Does it mean we can decode 128 bit SSL/HTTPS encrypted traffic in few minutes ?
- Strilanc 7y ago
  See title of paper.
  - deleted 7y ago
    [deleted]
  - Jeff_Brown 7y ago
    The fact that someone would ask implies that the title does not make it obvious. The time to factor one giant number is interesting, but so too is how this method applies to other, especially more common, problems.
    - Strilanc 7y ago
      RSA with keys less than 1024 bits long is not considered to be secure against classical attack, so SSL/HTTPS is presumably not using such key lengths. The construction in the paper still takes hours on 1024 bits, therefore it will not break SSL/HTTPS in minutes. If you were to, very inadvisably, use RSA with 128 bit long keys (maybe that's what they were asking?) then yes it would take minutes. But you can already break such keys in minutes using classical computers.

Hi. I would like to take the opportunity to get your opinion on quantum computing. My understanding is that there is a significant work in theoretical quantum computing done by you and many people. Results presented by you seems impressive. Congratulations. On the other hand - everything I read, hear and try to interpret about D-wave seems like a nonsense. They show approximation computations and compare it to classical algorithms that provide exact results. But classical approximation algorithms work much better than their quantum computers. I do not see how scaling this approach could lead to anything that you describe in your paper. In this regard - is my understanding of D-wave correct or does it provide some value that is better than classical computers? Can d-wave or IBM's creation be used to do computations described in your paper? Is their approach worth anything? [edit] Of course I'm not asking about now - my question is whether there is anything connected to exact results (like factoring) and exponential speed-up in d-wave approach.

Strilanc 7y ago
I don't really know a lot about D-wave to be honest. I defer to Scott Aaronson's posts [1] and to the opinion that the main criteria for success is "solve hard problems" as opposed to "solve hard problems with a quantum computer" [2]. [1]: https://scottaaronson.com/blog/?s=dwave https://scottaaronson.com/blog/?s=dwave [2]: https://youtu.be/XbFoXT73xVQ?t=355 https://youtu.be/XbFoXT73xVQ?t=355
- scottlocklin 7y ago
  Without hardware, you're not solving any problems. Glass bead game != solving problems. At no point in human history as this sort of "detailed theoretical wanking" turned into progress in science; the hardware comes first.
  - mannykannot 7y ago
    How do you get the idea to build something without any thought about what it will do?
  - kuzehanka 7y ago
    Convnets were detailed 1980s and didn't become viable until hardware caught up in the 2010s.
  - deleted 7y ago
    [deleted]
  - sgt101 7y ago
    I was under the impression that theoretical physics detailing underpinning mechanisms proceeded the transistor, nuclear weapons and fibre optics.
    - behringer 7y ago
      That's true of most inventions. We had programming and boolean logic before we had computers. And of course we would, you can't build a boat without water to sail on.
      - NeutronStar 7y ago
        You can't build a boat if you never had the idea of what a boat is supposed to be.
- agsamek 7y ago
  Hmmmmm. I tried to follow this youtube, but it doesn't make sense for me. The guy is saying that D-wave would be a success even if it was not a quantum but only solved a hard problem. I could buy this, but they do not solve any problem yet that was not solvable with probabilistic classical algorithms before. I would also give them a credit if they didn't solve any problem yet but showed real quantum computer at work. Eg. could do factoring of 50 digit number. Or are on the way to do this somehow and made understandable progress in the area. Even though they didn't fully succeed yet. What they do to my understanding is: * approach a problem that is hard in general. * solve only a simple and already solvable case * when asked that it may not be a quantum thay say that even if it was not quantum then ok because the problem is hard (while it is not) * if asked about the problem being easy they say that maybe the problem is easy but this is quantum. Do I understand this correctly? I would really appreciate more explanation
  - Strilanc 7y ago
    I agree with all of that.

deleted 7y ago

[deleted]

mikorym 7y ago

Is your approach here to focus on the theoretical background or is it also to comment on feasibility on hardware in the next x years?

Strilanc 7y ago
I'm having a hard time parsing your question. Our goal in this paper was to better understand the resources required to factor with a quantum computer. These estimates can then be fed into decisions about the rate post-quantum cryptosystems need to be deployed. We don't make predictions about the expected capabilities of hardware over time. We do frame our results in terms of specific hardware assumptions (e.g. particular gate speeds and errors rates), but most of the improvements we make are about how to do arithmetic and so they generalize beyond these assumptions.
- mikorym 7y ago
  Cool, I think that does answer my question. You do both, but the feasibility part is in the form of hardware assumptions that don't comment on the current or future state of hardware.

truth_seeker 7y ago

Does it mean we can decode 128 bit SSL/HTTPS encrypted traffic in few minutes ?

Strilanc 7y ago
See title of paper.
- deleted 7y ago
  [deleted]
- Jeff_Brown 7y ago
  The fact that someone would ask implies that the title does not make it obvious. The time to factor one giant number is interesting, but so too is how this method applies to other, especially more common, problems.
  - Strilanc 7y ago
    RSA with keys less than 1024 bits long is not considered to be secure against classical attack, so SSL/HTTPS is presumably not using such key lengths. The construction in the paper still takes hours on 1024 bits, therefore it will not break SSL/HTTPS in minutes. If you were to, very inadvisably, use RSA with 128 bit long keys (maybe that's what they were asking?) then yes it would take minutes. But you can already break such keys in minutes using classical computers.