Some recent advances in quantum machine learning

Update: A paper on the quantum learning of coherent states came out just a day after writing this up. I added a paragraph on it.

Since I submitted the manuscript of the book on quantum machine learning to the publisher, quite a bit of progress has been made on the topic. In this post, I quickly go through the new papers that came to my attention recently.

To start with, a South African group at the University of KwaZulu-Natal published an introduction to quantum machine learning (Schuld et al, 2014a). The paper is easy to read, and, apart from supervised and unsupervised learning, it also mentions reinforcement learning, albeit there is no mentioning of a quantum flavour of this kind of problems. Apart from the usual suspects, the authors pay special attention to methods closer to classical statistics, such as Bayesian inference and Markov models, which I find refreshing. Furthermore, they mention quantum decision tree classifiers, pointing out that key steps of the algorithms remain obscure.

While writing the book, I struggled the most with quantum neural networks. This was not because the subject matter is difficult to comprehend: it is fairly light. The problem was the vast number of papers published, not all of which was truly quantum: some were quantum-like learning methods, presenting a classical algorithm that was inspired by quantum mechanics. Even if we filter out those, the numbers were still intimidating. The same South African group as above published a good review on quantum neural networks recently (Schuld et al, 2014c). I wish I had this when I was writing the chapter on this subject. They highlight the usual problem of closed quantum systems having a neat unitary evolution, whereas neural networks work with a nonlinear activation. They enumerate the potential solutions explored so far in the literature. They also did original research on the topic in an earlier paper, which I regrettably missed before, linking Hopfield networks to quantum random walks (Schuld et al, 2014b).

Talking about random walks and reinforcement learning, I missed a paper that was published two years ago, connecting these two in a model based on intelligent agents who constantly search a memory space and also generate new possible solutions (Briegel & De las Cuevas, 2014). Moreover, the authors extended the method to quantum random walks in an open quantum system. To my knowledge, this is the first link between reinforcement learning and quantum information theory.

From Seth Lloyd's collection of three papers last year, the one on quantum principle component analysis was published in Nature Physics. He and a new batch of co-authors posted a new manuscript on arXiv with 'big data' in the title, again. The paper is curious: it deals with the quantum variant of topological methods in machine learning (Lloyd et al., 2014). A workshop was recently organized on topological methods at ICML-14, but it is still far from being mainstream. It is a more algebraic view on manifold learning, and we already have a quantum variant of it.

One last bit of Seth Lloyd-related news: a group implemented his k-means clustering algorithm using a photonic quantum computer up to eight dimensions (Cai et al., 2014).

Moving on to a more combinatorial approach to machine learning, identifying an n-bit parity function is equivalent to a binary classification problem with an n-dimensional binary feature space. If we talk about learning parity with noise, then not all the binary labels are correct. A new paper proves that without noise, the computational complexity of learning with classical and quantum methods is the same, but the noise turns the complexity of classical methods to superpolynomial, whereas the increase with quantum algorithms is only logarithmic (Cross et al., 2014). This is certainly an exciting take on the problem of separating classical and quantum learning algorithms. Working with the same n-bit parity functions without noise, Yoo et al. (2014) prove a large, but constant-factor speedup for quantum algorithms.

Quantum learning of unitary transformations is similar to transduction: we have a limited number of future targets on which we want to apply the function -- the unitary in the quantum case. A new paper proves super-replication of unitaries: given n copies, we can get \(n^2\) almost perfect copies, with exponentially decreasing probability of success (Dür et al., 2014). The result holds for unitaries of the form \(U(\theta) = exp(-\imath\theta H)\), where the Hamiltonian H is known, but the interaction strength \(\theta\) is unknown. Generalization of this result would be exciting.

It is also interesting to see how learning methods enhance problems in quantum information theory. A new paper investigates the optimal strategy to distinguish two states: a signal (a quantum state) of unknown amplitude is beamed at a classical bit (Sentís et al., 2014). The signal either goes through a transparent medium if the stored bit is zero, or it is perfectly reflected and captured by a detector. The detector is also supplied n copies of the quantum state. Now the question is whether it is better to estimate the amplitude first and then do a measurement on the reflection, or do a collective measurement. The result is similar in broad outlines to the quantum learning of unitaries, although for only small amplitudes: a collective measurement is optimal.

References

Briegel, H. J. & De las Cuevas, G. Projective Simulation for Artificial Intelligence. Scientific Reports, 2012, 2, 1--16.

Cai, X.-D.; Wu, D.; Su, Z.-E.; Chen, M.-C.; Wang, X.-L.; Li, L.; Liu, N.-L.; Lu, C.-Y. & Pan, J.-W. Entanglement-Based Quantum Machine Learning. arXiv:1409.7770, 2014.

Cross, A. W.; Smith, G. & Smolin, J. A. Quantum Learning Robust to Noise. arXiv:1407.5088, 2014.

Dür, W.; Sekatski, P. & Skotiniotis, M. Deterministic Super-Replication of Unitary Operations. arXiv:1410.6008, 2014.

Lloyd, S.; Garnerone, S. & Zanardi, P. Quantum Algorithms for Topological and Geometric Analysis of Big Data. arXiv:1408.3106, 2014.

Schuld, M.; Sinayskiy, I. & Petruccione, F. An Introduction to Quantum Machine Learning. Contemporary Physics, 2014, 0, 1--14.

Schuld, M.; Sinayskiy, I. & Petruccione, F. Quantum Walks on Graphs Representing the Firing Patterns of a Quantum Neural Network. Physics Review A, American Physical Society, 2014, 89, 032333.

Schuld, M.; Sinayskiy, I. & Petruccione, F. The Quest for a Quantum Neural Network. Quantum Information Processing, Springer US, 2014, 13, 2567--2586.

Sentís, G.; Guţă, M. & Adesso, G. Quantum Learning of Coherent States. arXiv:1410.8700, 2014.

Yoo, S.; Bang, J.; Lee, C. & Lee, J. A Quantum Speedup in Machine Learning: Finding an N-bit Boolean Function for a Classification. New Journal of Physics, 2014, 16, 103014.