3 ms·
> There are some basic linear algebra subroutines (Matrix inversion, finding eigenvalues & eigenvectors) that can be performed with an exponential speedup on a
by jlokier 6y ago
> There are some basic linear algebra subroutines (Matrix inversion, finding eigenvalues & eigenvectors) that can be performed with an exponential speedup on a quantum computer in theory
Eh... those particular subroutines have polynomial time algorithms already on a classical computer.
You can't exponentially speed up something that's polynomial time already.
- westurner 6y agohttps://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/ lists algorithms, speedups, and descriptions.
- jlokier 6y agoThat's a great list, thanks! (Though for the benefit of readers here, the list doesn't include any "basic linear algebra subroutines (Matrix inversion, finding eigenvalues & eigenvectors)").
- westurner 6y agoThe "linear systems" and "machine learning" algorithm paragraphs under "Optimization, Numerics, & Machine Learning" reference a number of resources in regards to currently understood limits of and applications for quantum computers and linear optimization.