Re:Who needs qubits? Factoring algorithm run on a probabilis...
by sokrates85 on Friday September 20, 2019 @02:52PM
(#21029997)
I agree that the integer factorization is a poor choice. Last statement in the Abstract talks about sampling and optimization which could be the bigger point.
Their pre-processing seems like simply expanding out their cost function that's of the form E= (F - XY)^2. Of course it's a lot of multiplications since X and Y are binary and multi-dimensional. Not sure if it would be NP-hard though.
Skimming over the paper it seems their method of translating factorization to the optimization problem consists of simplifying equations without justification that this can be done efficiently. I suspect that their preprocessing step is already NP-hard.
The second and more important issue, is that the overall strategy---of translating a problem with a sub-exponential classical complexity (via the Number Field Sieve) to an optimization problem with exponential runtime---is not expected to succeed, as confirmed by careful measurements in our paper.