Quantum Machine Learning: An Overview
kdnuggets.com
kdnuggets.com
Like Shor's factoring and Grover's algorithm, machine learning problems like solving systems of linear equations have been mathematically proven to have a quantum speedup. The problem is engineering quantum computers well enough that they can outperform classical computers on these tasks. We are currently working on that and it will take a couple of decades at least.
Hope is not lost. There are also a couple of theories that hybrid classical/quantum computers of the next decade or so will perform some tasks like quantum chemistry and approximate optimization (which can be used in machine learning) better than classical computers. Only time will tell.
I'm not an expert, so please correct me if I'm wrong, but my understanding from Aaronson's paper is that this is not really true in general.
Unlike Shor's algorithm, which can be used to actually find the factors of some integer, HHL (the quantum algorithm that "solves" systems of linear equations) is best compared to quantum Fourier transform. That is: it can only be used to prepare a state |x> that contains the solution you want. But that's still a quantum state -- if you naively try to measure it, you'll get garbage. That doesn't mean HHL or quantum Fourier transform are useless (indeed, quantum Fourier transform is used by Shor's algorithm), it just means that they're not drop-in replacements for their classical counterparts (like Shor's algorithm is for classical factoring).
It's rare for quantum algorithms to be drop-in replacements for classical problems. Take Grover's algorithm. Using it to search a classical database kills the speedup due to the number of calls to memory. Therefore, it will probably be used to attack NP-complete problems instead.
I stopped reading here. Can anyone who read beyond this tell me if the article is worth reading?