4 ms·
There are some basic linear algebra subroutines (Matrix inversion, finding eigenvalues & eigenvectors) that can be performed with an exponential speedup on a qu
by virattara 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, that's why there is so much interest in Quantum Machine Learning. If you are asking about the current hardware level, then no, current quantum computers can not solve any practical problem faster than a classical computer.
In theory classical computers are also not limited to have better solutions to problems where quantum computers claim superiority like prime factorisation or like Tang's quantum inspired classical algorithm that beats HHL for low rank matrices.
- 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.