Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Many problems require lots of huge matrix multiplications—think simulations of physical systems, i.e. weather systems or molecular interactions, or numerical optimization.


Additionally, many problems are can be converted to matrix operations, like graph algorithms.

Note that matrix multiplication takes O(n^2) time with a quantum computer, but O(n^2.807) time on a classical computer.


> but O(n^2.807) time on a classical computer

Optimizing matrix multiplication for classical computers is an open research problem, and according to wikipedia there are algorithms with O(n^2.37) running time. Also according to wikipedia, it is not proven that matrix multiplication can't be done in O(n^2).


Ah yes, we may as well add NP-completeness to this thread.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: