"Before answering this question, let me preface by stating that the
following is simply MY answer as a Machine Learning Researcher and
"Hobbyist" Theoretical Physicist, although I have strong feelings that
my answer will most certainly be proven as true, I am more than sure
that others will have differing opinions as with everything else in
this world!" ~ Me
That being said, I would say that the answer to your question, is unequivocally YES! I could write a short book on the subject (that might be a good idea actually) but I will keep this response brief, although I am happy to answer any further questions your may have to which I possess the answers in the comments!
The primary reasons that I believe the newly blossoming field of Quantum Computation will have a massive impact on the field of Machine Learning in general, are as follows:
The most simple reason for my belief is that the primary goal of Machine Learning, is to create an entity which is capable of coherent, self-aware thought much like we exhibit as human beings. We know that the brain is what allows us to be capable of such feats, and thus I view the field something like brain counterfeiting. Without going into esoteric detail, there are many subtleties of the brain's workings which are thought to be quantum mechanical in operation, and thus would suggest that the path of least resistance to replicating the system would require a quantum mechanical computational medium.
The second primary rationale which solidifies my position, is the point which you briefly touched upon by stating that,
"We know that according to Shor's Algorithm Quantum Computing can reduce the complexity > of breaking an encryption from O(2n) to O(2n2) (not sure)."
This is primarily due to the quantum phenomena referred to as Super Position, which allows for a multiple qubit gate to not only work with the options of 00, 01, 10 and 11 (assuming a two qubit gate) but to also work with any combination in-between, during the computation. Although when the result is obtained (this is what is referred to as collapsing the wave function) you will only still have a resulting state space with 2^n possibilities, where n is the number of qubits. This being said, there are very clever ways, by which one can design their algorithms to make full use of this technically infinite computational space before observing the final results.
I hope that my answer is helpful to you in some way, although I am aware that it is not a very in-depth answer, I feel that it hits the primary reasons why my personal belief is that there will be a wall which is hit, in the pursuit of a general AI, while we are limited to classical computation faculties; and thus will require quantum based computation before we are able to truly mimic the brain's most well kept secrets! The next couple decades should be VERY interesting in the fields, keep a close eye on the latest happenings!