Hacker News Reader

Comment by mparlane | Hacker News Reader

Does this finding affect Shor's Algorithm which I only learnt about last night from Veritasium ?

Shor'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.

Shor'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.

You'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

As far as I understand, no. This is only about Grover's algorithm.

But 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.)

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

Reply on news.ycombinator.com