4 ms·
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
by TJSomething 6y ago
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.
- gnu-nobody 6y ago> 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).
- infogulch 6y agoAh yes, we may as well add NP-completeness to this thread.