News for hackers. Stuff that matters.

A comment on Ask HN: What scientific phenomenon do you wish someone would explain better?. Parent comment

Re:Ask HN: What scientific phenomenon do you wish someone wo... by TJSomething on Monday April 27, 2020 @03:35AM (#22993738)
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.

[ Parent | on HN ]
Re:Ask HN: What scientific phenomenon do you wish someone wo... by gnu-nobody on Monday April 27, 2020 @04:28AM (#22993997)
> 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).

[ Parent | on HN ]
Re:Ask HN: What scientific phenomenon do you wish someone wo... by infogulch on Monday April 27, 2020 @05:09AM (#22994209)
Ah yes, we may as well add NP-completeness to this thread.
[ Parent | on HN ]