Is there any potential application of quantum computers in machine learning or AI?

Much of the work done so far with quantum computers has been focused on solving combinatorial optimization problems. Both D-Wave style Quantum Annealers and the more recent Gate Model machines from Rigetti, IBM, and Google have been solving combinatorial optimization problems. One promising approach to connecting machine learning and quantum computing involves finding optimization problems within standard machine learning tasks.

For example the recent Rigetti paper Unsupervised Machine Learning on a Hybrid Quantum Computer essentially recasts the unsupervised machine learning problem of clustering data into two groups, also known as 2-means clustering, into the combinatorial optimization problem of MaxCut. The folks at Rigetti then solve the MaxCut problem with the Quantum Approximate Optimization Algorithm (QAOA).

I would expect to see more of this style of work in the future, especially given the natural connections between optimization and machine learning.

I will only answer to the part of the question regarding how quantum mechanics can be useful to analyse classical data with machine-learning-like techniques. There are also works related to "quantum AI", but that is a much more speculative (and less defined) kind of thing, which I do not want to go into.

So, can quantum computers be used to speed-up data analysis via machine learning algorithms? Quoting Scott Aaronson's Read the fine print paper, that’s a simple question with a complicated answer.

It should first of all be noted that trying to answer this kind of question is a big part of what the research area of Quantum Machine Learning is about (the terms quantum-enhanced machine learning and quantum assisted machine learning are also often used to refer to this merger of QM and ML, to distinguish it from the use of ML to help solve problems in QM, which is an entirely different subject). As you can see from the Wikipedia page, there are many things going on in the field, and it would be pointless to try and give a comprehensive list of relevant papers here.

Quoting from Schuld et al. 2014, the idea behind Quantum-Assisted Machine Learning (QAML) is the following:

Since the volume of globally stored data is growing by around 20% every year (currently ranging in the order of several hundred exabytes [1]), the pressure to find innovative approaches to machine learning is rising. A promising idea that is currently investigated by academia as well as in the research labs of leading IT companies exploits the potential of quantum computing in order to optimise classical machine learning algorithms.

Going back to your question, a first seemingly positive answer was provided by Harrow et al. 2009, which gave an efficient quantum algorithm to invert linear system of equations (under a number of conditions over the system), working when the data is stored in quantum states. Being this a fundamental linear algebra operation, the discovery led to many proposed quantum algorithms to solve machine learning problems by some of the same authors (1307.0401, 1307.0411, 1307.0471), as well as by many others. There are now many reviews that you can have a look at to get more comprehensive lists of references, like 1409.3097, 1512.02900, 1611.09347, 1707.08561, 1708.09757, Peter Wittek's book, and likely more.

However, it is far from established how this would work in practice. Some of the reasons are well explained in Aaronson's paper: Read the fine print (see also published version: nphys3272). Very roughly speaking, the problem is that quantum algorithms generally handle "data" as stored in quantum states, often encoding vectors into the amplitudes of the state. This is, for example, the case for the QFT, and it is still the case for HHL09 and derived works.

The big problem (or one of the big problems) with this is that it is far from obvious how you can efficiently load the "big" classical data into this quantum state for processing. The typical answer to this is "we just have to use a qRAM", but that also comes with many caveats, as this process needs to be very fast to maintain the exponential speed-up that we now can be achieved once the data is in quantum form. Again, further details can be found in Aaronson's paper.

There are arguments that our brains are quantum mechanical, and arguments against, so that's a hotly debated topic. Fisher at UCSB has some speculative thinking about how brains might still use quantum effects even though they aren't quantum mechanical in nature. While there's no direct experimental evidence there are two references you might want to read:

• Quantum Cognition: The possibility of processing with nuclear spins in the brain

• Are we quantum computers, or merely clever robots?

Now, on the subject of using quantum computing and machine learning, Rigetti Computing has demonstrated a clustering algorithm using their prototype quantum chips (19 qubits). They published their findings in a white paper on arXiv.org here:

• Unsupervised Machine Learning on a Hybrid Quantum Computer

So there's clearly an opportunity to advance machine learning, and eventually, AI using quantum computing imho.