4 ms·
Does this finding affect Shor's Algorithm which I only learnt about last night from Veritasium ?
by mparlane 4y ago
Does this finding affect Shor's Algorithm which I only learnt about last night from Veritasium ?
- sebzim4500 4y agoThis finding does not affect either Shor's Algorithm or Grover's algorithm, as far as I can tell. I haven't read it in detail, but the abstract is so absurd that I won't bother.
- msm_ 4y agoAs far as I understand, no. This is only about Grover's algorithm.
- amluto 4y agoBut it's also about another of Peter Shor's famous results: the Threshold theorem! But only in the sense that the authors seem to have never heard of it. (See my other comment.)
- Pepe1vo 4y agoShor's algorithm and Grovers algorithm are fundamentally very different. Most conventional asymmetric crypto algorithms are essentially all hidden sub group problems which are NP hard for classical computers. What Shor's algorithm does is reduce hidden sub group problems to P on quantum computers. Grover's algorithm is quite complex and I'm not qualified to say much about how it works, but I do know that the underlying mathematics is very different.
- yarvos 4y agoShor's algorithm absolutely does not reduce NP hard problems to P (or BQP). These kinds of problems with quantum speedups reside in an intermediate class of difficulty sometimes called NP-intermediate which may or may not already be in P, and which NP complete problems do not reduce to.
- Pepe1vo 4y agoYou're correct, I got some of the terminology mixed up. It's after all been a long time since I've been in the field :p