Hi Andreas Wichert , I hope you are well. I'll be the first to put a toe in the water :) ...

The question is excellent and invokes a lot of discussion, I think maybe the short answer is yes, but so few understand it the lack of information is deafening - the caveat to that is "finding any way to make it useful is the most difficult task".

Quantum computing (general purpose) is IMO a different kettle of fish than Quantum Machine Learning in so far as algorithmic approaches go.

The biggest hurdle for classical students coming to this field is utter misinformation regarding the quantum approach. The simple idea that quantum computers process all and every permutation simultaneously and find the correct answer is very common and very wrong. Trying not to think classically is almost impossible and requires a lot of mental resolve for many IMHO.

For the benefit of those entering the field and pondering the question, it is worth noting that often quantum advantages are specific to one tiny fraction of a much wider explicit methodology, for example Shor's factoring algorithm which enjoys the most widespread misunderstanding ever! Here we try to find 2 primes p and m such that pm=N. Peters algorithm only uses a quantum process in one of the several steps required. That process is to find the period of r of a function f(x). Quantum does this surprisingly faster than any brute force method. Once the period is found it is then back to fully classical number theory to do the rest. Shor's algorithm DOES NOT multiply every number by every number simultaneously and magically find the factors of a large prime (but you would be surprised how many think that).

In fact QC actually only does a handful of things faster than any other method available and from a machine learning perspective that means rethinking the way something like a neural network functions fully to try and put the burden of computational roadblocks into a faster quantum version... the rest - is classical.

As a lot of machine learning is rooted in efficient search, matching and classification, improvements in search efficiency through such things as a Grovers algorithm etc has direct implications.

If the foregoing is rudimentary to those following the question, I apologise but feel the discussion needs to start somewhere.

As Feynman himself said .. if you think you know quantum, you don't know quantum. Therefore I have tried to bring the question into a more compartmentalised state so that I can get ripped to shreds :)

Warm regards

Scot

Dear Scot, thank you for the answer. QC has advantaged to classical computation. But many Quantum Machine Learning algorithms assume that the data is represented in quantum states as a kind of superposition vector. I did not find any information (maybe it is my mistake) of how to build such a superposition vector from real data efficiently. Basically to read N data points you need N steps. A quantum machine learning algorithm can be logarithmic faster in the size of N, but this does not help since we spend already N steps on reading the data. And you can not reuse the superposition vector since neither you can copy it (it is forbidden) and it gets destroyed during the measurement process. For example you could use Grover algorithm for N points to speed up the search quadratically, but why do you care to do it, since you already spend N steps to read the data..

Can anybody give me a hint, or a link to a paper that deals with this problem.

I know the paper of S. Aaronson. Quantum Machine Learning Algorithms: Read the Fine Print , Nature Physics 11:291-293, 2015., but despite it there is a lot of papers that deal with quantum machine learning ignoring the problem. Is the problem not noticed, and if so why? Or is it already solved?

Hiya Andreas Wichert , the Grover search is case in point of what I was implying. In such a search you are NOT tasked with entering an entire phone book into a database and then searching through it (thats the classical way), rather you are looking to develop a quantum function that will produce an answer that matches your search. e.g : if a simple hash produces a 64 bit value, and you are given a hashed value - how do you find the input I?, the task is to create a search function that exploits some quantum mechanism to produce the input I (or range of inputs) that produce the hash. That is "the speed up", because you simply have searched through 2^64 inputs in quadratic time rather than O(N).. although rather more to the point you "haven't at all", the quantum phenomena did it without needing to have a disk full of phone numbers. .. I would add to search a phone book, it would be better to use SQL .. I was just paraphrasing ;-) It really is about selecting your problem and choosing your battles with quantum, many of which are just as well solved using classical methods.

Best, Scot.

I have spoken to a friend and he suggested that having N data points quantum machine learning guarantees you that the if classical complexity is bigger then O(N) like a O(f(N)), for example O(N^2) , quantum complexity O(quantum(N)) reduce it to O(N)