What is the advantage of quantum machine learning over traditional machine learning?

Question

Why exactly is machine learning on quantum computers different than classical machine learning? Is there a specific difference that allows quantum machine learning to outperform classical machine learning?

Answer 1

Potentially, the same advantage that quantum computing can provide over classical computing. By "quantum machine learning", in the way you seem to be using the term here, people usually refer to quantum algorithms developed to solve tasks usually handled by machine learning, that is, very roughly speaking, pattern recognition tasks (though in the quantum case algorithms aimed at performing linear algebra operations are also included in the category).

Just as there are tasks for which quantum algorithms are known to, or promise to provide enhancement over classical computers, think Grover's or Shor's, one can hope pattern recognition tasks can be similarly sped up. That's pretty much the point of quantum machine learning, also often referred to as "quantum-enhanced machine learning" in this context, to distinguish it from applications of classical machine learning to quantum information tasks, which is an entirely different field of study.

See also this question and links therein.

Answer 2

As so often, and especially in young research areas, the answer depends quite a lot on how you break down the question. Let me try a few examples:

Does quantum mechanics change what is theoretically learnable?

A beautiful paper is this reference which states a few complex results in rather clear words. Again, it depends very much on what you define as "learning". Overall, exponential speedups in the number of data samples seem to not be possible in many settings, but exponential time complexity speedups very well possible.

What asymptotic computational speedups can quantum computing provide for machine learning?

Probably the most studied approach here is to outsource linear algebra subroutines such as matrix inversion or singular value decomposition to quantum computers. These subroutines appear for example in convex optimisation used in linear regression or kernel methods.

Quantum computing research is traditionally very focused on exponential speedups, which have been claimed in many quantum machine learning papers. But they rely on lots of assumptions about how you load your data into a quantum computer, and how to process the results. The assumptions require deep technical knowledge to grasp, and it is not always clear how good classical methods are in this case. For example, the quantum algorithm may require a sparse data matrix for an exponential speedup over the vanilla classical method, but under this assumption there is another classical method that is much faster too. Some quantum algorithms have since been "de-quantised", which is a euphemism for "found to not really provide an exponential speedup if the same assumptions are imposed on classical algorithms".

Standard quantum algorithms can often give you a quadratic speedup for sampling and unstructured search problems. But classical methods are quite fast at heuristic sampling in the first place (think of contrastive divergence), and search problems so vast that a quadratic speedup does not make them tractable either.

Can quantum computations give rise to machine learning models that generalise well?

Most of the work in near-term quantum machine learning, that is QML using small and noisy devices that are the current "prototypes" of quantum computers, are interested in what models quantum computers very naturally give rise to. Do they look like neural networks? Or like anything else? Are they good generalisers? Can they be trained efficiently?

Of course, speedups are important here to - if we find a quantum model that is powerful, but easy to classically simulate, one does not need the quantum computer in the first place (still, a quantum computer may just be the fastest hardware in absolute terms to process those models, and therefore still advantageous). But much more important is to show that the quantum model generalises well.
This type of research, much driven by "variational" or "trainable" or "parametrised" quantum circuits which are optimised with the usual classical techniques of deep learning, has only few answers yet to the question of quantum advantages. There are interesting clues though - quantum models of this type are mathematically speaking linear algebra computations applied to data mapped into the very large Hilbert spaces of quantum systems. They are also modular and trainable like neural networks.

If one accepts that quantum computers are strictly speaking more powerful than classical computers, the quantum model could in principle express a larger class of functions. But how to utilise this potential advantage in a concrete quantum algorithm design is very hard to point out and not "automatically given". For example, one can show that certain ways to encode data into a quantum computer gives quantum models only access to very trivial function classes, and they are unlikely to learn anything interesting.

One reason why this is an extremely challenging (but very interesting) research area is this: if the goal is to build powerful generalisers, but the theoretical foundations of generalisation are poorly understood even in classical machine learning, and our current devices are too small and noisy to run meaningful empirical benchmarks, how can one actually show that the quantum model has an advantage? In other words, a lot of work is needed to even find a satisfying investigation framework for the question "are quantum models better machine learning models?".

So, overall I'd say like every decent research field, the art is to reformulate the question until we can answer it - at which stage the answer is usually hard to understand for non-experts.