undefined | Better HN

0 pointstsimionescu2y ago0 comments

I couldn't quickly find any info, but does this algorithm show the kind of exponential quantum speed up needed to break RSA? Because if it's just slightly faster than the best known classical algorithms, then it's enitely irrelevant to the question of when we need to switch our encryption schemes (even though it may be a significant advancement in the area of quantum algorithms research).

0 comments

eigenket2y ago

I think its unknown, but my feeling is that the answer is almost certainly no.

These sort of variational algorithms are appealing (to some people) because they're potentially usable on the sort of noisy small quantum computers we have today and in the near term future, but they aren't very fancy. I think in general what you'd expect to get out of them is a sort of Grover's algorithm-like square root speedup.

adgjlsfhk12y ago

it's generally believed that the algorithm is somewhere in between ecm and quadratic sieve (so slower by a super-polynomial factor than NFS which is the best classical algorithm)

j / k navigate · click thread line to collapse

0 comments

eigenket2y ago

I think its unknown, but my feeling is that the answer is almost certainly no.

adgjlsfhk12y ago

it's generally believed that the algorithm is somewhere in between ecm and quadratic sieve (so slower by a super-polynomial factor than NFS which is the best classical algorithm)

j / k navigate · click thread line to collapse