News for hackers. Stuff that matters.
Re:Major Quantum Computing Advance Made Obsolete by Teenager... by birbs on Sunday September 05, 2021 @05:36AM (#28422796)
How is integer factoring not the best-known possible example of a quantum speed-up? What was special about this recommender system problem?
Re:Major Quantum Computing Advance Made Obsolete by Teenager... by mirekrusin on Sunday September 05, 2021 @07:11AM (#28423344)
Maybe he was scared he may solve it and didn't want to live through apocalypse.
Re:Major Quantum Computing Advance Made Obsolete by Teenager... by sgt101 on Sunday September 05, 2021 @01:23PM (#28425958)
There don't seem to be many practical applications of integer factoring - basically it's good for cracking PKI. On the other hand these recommender algorithms looked really useful for the applications that folks use recommenders in now and for extending to deal with potentially other sparse matrix problems as well. Which is good because the paper here produced a good classical alternative.

This is a problem for QC though because there really aren't many actual algorithms to run on these things that are going to be that useful afaik. At least with analytical complexity results (I think quantum neural nets don't have these yet?) - I would love to see counter examples!

Note - a lot of QC algorithms provide only modest speedups like ^2 improvements - the ^n improvements are the ones we want and are v.rare.