# User:Luca Innocenti/sandbox

Quantum machine learning is a newly emerging interdisciplinary research area between quantum physics and computer science that summarises efforts to combine quantum mechanics with methods of machine learning.[1][2][3] Quantum machine learning models or algorithms intend to use the advantages of quantum information in order to improve classical methods of machine learning, for example by developing efficient implementations of expensive classical algorithms on a quantum computer.[4][5][6] However, quantum machine learning also includes the vice versa approach, namely applying classical methods of machine learning to quantum information theory.

Although yet in its infancy, quantum machine learning is met with high expectations of providing a solution for big data analysis using the ‘parallel’ power of quantum computation.[7] This trend is underlined by recent investments of companies such as Google and Microsoft into quantum computing hardware and research. However, quantum machine learning is still in its infancy and requires more theoretical foundations as well as solid scientific results in order to mature to a full academic discipline.

## Quantum methods for Machine Learning

A number of proposals suggest ideas of how to adapt classical methods of machine learning to quantum information processing.[8]

### Quantum Support Vector Machines

A support vector machine can be implemented on a quantum computer using a combination of known quantum algorithms.[9] In order to construct the hyperplane separating the dataset for classification tasks, the linear equation from the dual form or least squares formulation is solved using a quantum algorithm to solve linear equations [10] An important trick is thereby a routine to construct a density matrix whose entries correspond to those of the kernel matrix.

Extracting information from the final state can be done through quantum principal component analysis.[11] The classification of a new input is accomplished through a so-called swap test, in which the overlap between two quantum states is calculated. The quantum support vector machine can be implemented in time that depends logarithmically on the dimension of the feature space and the number of training vectors, while the classical solution requires a polynomial dependence.[12] First experiments on a quantum support vector machine have been realised.[13]

### Quantum Clustering and k-nearest neighbour methods

Machine learning algorithms such as k-means clustering or classification with k-nearest neighbours are based on calculating distances between feature vectors and selecting the closest one (either to identify the nearest cluster centroid or the nearest neighbours to a certain feature vector). Implementing such distance-based methods on a quantum computer means in the first place to find a way of calculating classical distances with quantum algorithms. A frequent idea is to employ the overlap of two carefully prepared wavefunctions ${\displaystyle \langle \psi |\varphi \rangle }$ as a distance measure between quantum states.

The minimum distance can be found based on an iterative Grover search.[14][15]

Distance-based machine learning algorithms such as unsupervised clustering can also be implemented through adiabatic quantum computing which improves the classical computation time of ${\displaystyle O(Mlog(MN))}$ for Lloyd’s algorithm to ${\displaystyle O(k\;log(MN))}$ (where M is the number of N-dimensional data vectors, and k is the given number of clusters).[16]

First experiment on distance-based quantum machine learning algorithms has been implemented on a photonic quantum computer up to eight dimensions, demonstrating supervised nearest-neighbor algorithm and unsupervised k-means algorithm.[17]

### Quantum neural networks

Quantum neural networks were initially discussed from a different perspective, namely the question of whether and how quantum effects could play a role in the brain’s biological neural networks.[18] However, the debate quickly shifted towards a purely computational focus on quantum versions of artificial neural networks, which play an important role in machine learning. A number of ideas for quantum neural network models have been published since.[19][20][21][22][23][24] An interesting approach for quantum machine learning is the quantum associative memory model based on Grover’s search algorithm.[25] However, finding a convincing method to train a quantum neural network is still an open task.[26]

The term quantum machine learning can also be used for approaches that apply classical methods of machine learning to problems of quantum information theory. For example, when experimentalists have to deal with incomplete information on a quantum system or source, Bayesian methods and concepts of algorithmic learning can be fruitfully applied. This includes machine learning approaches to quantum state classification,[27] Hamiltonian learning,[28] and learning an unknown unitary transformation.[29][30]

### Classical machine learning algorithms to learn about quantum systems

A variety of classical machine learning algorithms have been proposed to tackle problems in quantum information and technologies. This becomes particularly relevant with the increasing ability to experimentally control and prepare larger quantum systems.

In this context, many machine learning techniques can be used to more efficiently address experimentally relevant problems. Indeed, the problem of turning huge and noisy data sets into meaningful information is by no means unique to the quantum laboratory. This results in many machine learning techniques being naturally adapted to tackle these problems. Notable examples are those of extracting information on a given quantum state,[31][32][33] or on a given quantum process.[34][35][36][37][38] A partial list of problems that have been addressed with machine learning techniques includes:

1. The problem of identifying an accurate model for the dynamics of a quantum system, through the reconstruction of it Hamiltonian.[35][36][37]
2. Extracting information from unknown states.[31][39][40][41]
3. Learning unknown unitaries and measurements.[34]
4. Engineering of quantum gates from qubit networks with pairwise interactions, using time dependent[42] or independent[38] Hamiltonians.
5. Generation of new quantum experiments by finding the combination of quantum operations that allow for the generation of a quantum state with a certain desired property.[43]

### Machine-learning-inspired data extraction methods

The process of data extraction from quantum algorithms can be meaningfully influenced by ideas from machine learning.

## Corporate investmen ts into quantum machine learning research

Not only academia but also leading IT companies show interest in the potential of quantum machine learning for future technological implementations. Google Research launched its Quantum Artificial Intelligence Lab in 2013.[44] which is run as a joint initiative together with NASA and the Universities Space Research Association. An important hardware asset is the controversially debated D-Wave quantum computer.[45] Also Microsoft seems to become interested in the topic, and Microsoft’s Head of Research Peter Lee announced to “dramatically” increase the companies’ activity in quantum computing.[46]

## References

1. ^ Maria Schuld, Ilya Sinayiskiy, and Francesco Petruccione (2014) An introduction to quantum machine learning, Contemporary Physics, doi:10.1080/00107514.2014.964942 (preprint available at arXiv:1409.3097)
2. ^ Wittek, Peter (2014). Quantum Machine Learning: What Quantum Computing Means to Data Mining. Academic Press. ISBN 978-0-12-800953-6.
3. ^ Jeremy Adcock, Euan Allen, Matt Day, Stefan Frick, Janna Hinchliff, Mack Johnson, Sam Morley-Short, Sam Pallister, Alasdair Price and Stasja Stanisic (2015) Advances in Quantum Machine Learning, arXiv:1512.02900
4. ^ see for example, Nathan Wiebe, Ashish Kapoor, and Krysta M. Svorey (2014) Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning, arXiv:1401.2142v2
5. ^ Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost (2014) Quantum algorithms for supervised and unsupervised machine learning, arXiv:1307.0411v2
6. ^ Seokwon Yoo, Jeongho Bang, Changhyoup Lee, and Jinhyoung Lee, A quantum speedup in machine learning: finding an N-bit Boolean function for a classification, New Journal of Physics 16 (2014) 103014, arXiv:1303.6055
7. ^ "How Quantum Computers and Machine Learning Will Revolutionize Big Data". WIRED. Retrieved 26 November 2014.
8. ^ For a review, see Maria Schuld, Ilya Sinayiskiy, and Francesco Petruccione (2014) An introduction to quantum machine learning, Contemporary Physics, doi:10.1080/00107514.2014.964942 (upcoming, preprint available at arXiv:1409.3097)
9. ^ Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd (2014) Quantum support vector machine for big data classification, Physical Review Letters 113 130501
10. ^ Aram W. Harrow, Avinatan Hassidim and Seth Lloyd (2009) Quantum Algorithm for Linear Systems of Equations, Physical Review Letters 103 150502, arXiv:0811.3171
11. ^ Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost (2014) Quantum principal component analysis, Nature Physics 10 pp. 631-633
12. ^ Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd (2014) Quantum support vector machine for big data classification], Physical Review Letters 113 130501, arXiv:1307.0471v3
13. ^ Zhaokai Li, Xiaomei Liu, Nanyang Xu, and Jiangfeng Du (2014) Experimental Realization of Quantum Artificial Intelligence, arXiv preprint arXiv:1410.1054v1
14. ^ C. Duerr and P. Hoyer (1996), A quantum algorithm for finding the minimum, arXiv preprint quantph/ 9607014
15. ^ Esma Aïmeur, Gilles Brassard, Sébastien Gambs (2013) Quantum speed-up for unsupervised learning, Machine Learning 90, pp. 261-287
16. ^ Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost Quantum algorithms for supervised and unsupervised machine learning, arXiv preprint arXiv:1307.0411v2
17. ^ Cai, X.-D.; Wu, D.; Su, Z.-E.; Chen, M.-C.; Wang, X.-L.; Li, Li; Liu, N.-L.; Lu, C.-Y.; Pan, J.-W. (2015). "Entanglement-Based Machine Learning on a Quantum Computer". Physical Review Letters. 114: 110504. arXiv:1409.7770. Bibcode:2015PhRvL.114k0504C. doi:10.1103/physrevlett.114.110504.
18. ^ Kak (1995). "Quantum neural computing, Advances in Imaging and Electron Physics 94". Advances in Imaging and Electron Physics: 259–313. doi:10.1016/S1076-5670(08)70147-2. Retrieved 26 November 2014.
19. ^ for example, Menneer, T., Narayanan, A. (1995) Quantum-inspired neural networks. Department of Computer Science, University of Exeter, UK, Technical Report 32
20. ^ Altaisky, M.V. (2001) Quantum neural network. arXiv:quant-ph/0107012
21. ^ Zak, M., Williams, C.P. (1998) Quantum neural nets. International Journal of Theoretical Physics 37(2), pp. 651–684
22. ^ Behrman, E.C., Steck, J.E., Skinner, S.R. (1999) A spatial quantum neural computer. In: International Joint Conference on Neural Networks, IEEE IJCNN’99, Vol. 2, pp. 874–877
23. ^ Purushothaman, G., Karayiannis, N.B. (1997) Quantum neural networks (qnns): inherently fuzzy feedforward neural networks. IEEE Trans. Neural Netw. 8(3), pp. 679–693
24. ^ da Silva, Adenilton J.; Ludermir, Teresa B.; de Oliveira, Wilson R. "Quantum perceptron over a field and neural network architecture selection in a quantum computer". Neural Networks. 76: 55–64. doi:10.1016/j.neunet.2016.01.002.
25. ^ Dan Ventura, and Tony Martinez (2000) Quantum associative memory, Information Sciences 124 pp. 273-296
26. ^ Maria Schuld, Ilya Sinayskiy, Francesco Petruccione (2014) The quest for a Quantum Neural Network, Quantum Information Processing, doi:10.1007/s11128-014-0809-8
27. ^ Sentıs, G.; Calsamiglia, J.; Munoz-Tapia, R.; Bagan, E. (2012). "Quantum learning without quantum memory". Scientific Reports. 2: 708. arXiv:1106.2742. Bibcode:2012NatSR...2E.708S. doi:10.1038/srep00708.
28. ^ Wiebe, Nathan; Granade, Christopher; Ferrie, Christopher; Cory, David (2014). "Quantum Hamiltonian learning using imperfect quantum resources". Physical Review A. 89: 042314. arXiv:1311.5269. Bibcode:2014PhRvA..89d2314W. doi:10.1103/physreva.89.042314.
29. ^ Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D’Ariano, Stefano Facchini, and Paolo Perinotti (2010) Optimal quantum learning of a unitary transformation, Physical Review A 81, 032324, arXiv:arXiv:0903.0543
30. ^ Jeongho; Junghee Ryu, Bang; Yoo, Seokwon; Pawłowski, Marcin; Lee, Jinhyoung (2014). "A strategy for quantum algorithm design assisted by machine learning". New Journal of Physics. 16: 073017. arXiv:1304.2169. Bibcode:2014NJPh...16a3017K. doi:10.1088/1367-2630/16/1/013017.
31. ^ a b Sasaki, M.; Carlini, A.; Jozsa, R. (2001-07-17). "Quantum Template Matching". Physical Review A. 64 (2). doi:10.1103/PhysRevA.64.022317. ISSN 1050-2947.
32. ^ Sasaki, Masahide (2002-01-01). "Quantum learning and universal quantum matching machine". Physical Review A. 66 (2). doi:10.1103/PhysRevA.66.022303.
33. ^ Sentís, G.; Calsamiglia, J.; Munoz-Tapia, R.; Bagan, E. (2011-06-14). "Quantum learning without quantum memory". arXiv:1106.2742 [quant-ph].
34. ^ a b Bisio, A.; Chiribella, G.; D'Ariano, G. M.; Facchini, S.; Perinotti, P. (2010-03-25). "Optimal quantum learning of a unitary transformation". Physical Review A. 81 (3). doi:10.1103/PhysRevA.81.032324. ISSN 1050-2947.
35. ^ a b Granade, Christopher E.; Ferrie, Christopher; Wiebe, Nathan; Cory, D. G. (2012-10-03). "Robust Online Hamiltonian Learning". New Journal of Physics. 14 (10): 103013. doi:10.1088/1367-2630/14/10/103013. ISSN 1367-2630.
36. ^ a b Wiebe, Nathan; Granade, Christopher; Ferrie, Christopher; Cory, D. G. (2014-05-14). "Hamiltonian Learning and Certification Using Quantum Resources". Physical Review Letters. 112 (19). doi:10.1103/PhysRevLett.112.190501. ISSN 0031-9007.
37. ^ a b Wiebe, Nathan; Granade, Christopher; Ferrie, Christopher; Cory, David G. (2014-04-17). "Quantum Hamiltonian Learning Using Imperfect Quantum Resources". Physical Review A. 89 (4). doi:10.1103/PhysRevA.89.042314. ISSN 1050-2947.
38. ^ a b Banchi, Leonardo; Pancotti, Nicola; Bose, Sougato (2016-07-19). "Quantum gate learning in qubit networks: Toffoli gate without time-dependent control". npj Quantum Information. 2. doi:10.1038/npjqi.2016.19. ISSN 2056-6387.
39. ^ Sasaki, Masahide (2002-01-01). "Quantum learning and universal quantum matching machine". Physical Review A. 66 (2). doi:10.1103/PhysRevA.66.022303.
40. ^ Sentís, Gael; Guţă, Mădălin; Adesso, Gerardo (2015-07-09). "Quantum learning of coherent states". EPJ Quantum Technology. 2 (1): 17. doi:10.1140/epjqt/s40507-015-0030-4. ISSN 2196-0763.
41. ^ Sentís, G.; Calsamiglia, J.; Muñoz-Tapia, R.; Bagan, E. (2012-10-05). "Quantum learning without quantum memory". Scientific Reports. 2. doi:10.1038/srep00708. ISSN 2045-2322. PMC 3464493. PMID 23050092.
42. ^ Zahedinejad, Ehsan; Ghosh, Joydip; Sanders, Barry C. (2016-11-16). "Designing High-Fidelity Single-Shot Three-Qubit Gates: A Machine Learning Approach". Physical Review Applied. 6 (5). doi:10.1103/PhysRevApplied.6.054005. ISSN 2331-7019.
43. ^ Krenn, Mario (2016-01-01). "Automated Search for new Quantum Experiments". Physical Review Letters. 116 (9). doi:10.1103/PhysRevLett.116.090405.