3 ms·
How is integer factoring not the best-known possible example of a quantum speed-up? What was special about this recommender system problem?
by birbs 5y ago
How is integer factoring not the best-known possible example of a quantum speed-up? What was special about this recommender system problem?
- mirekrusin 5y agoMaybe he was scared he may solve it and didn't want to live through apocalypse.
- sgt101 5y agoThere 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.