On Quantum Methods for Machine Learning Problems Part I: Quantum Tools

Farid Ablayev; Marat Ablayev; Joshua Zhexue Huang; Kamil Khadiev; Nailya Salikhova; Dingming Wu

doi:10.26599/BDMA.2019.9020016

Big Data Mining and Analytics 2020, 3(1): 41-55 https://doi.org/10.26599/BDMA.2019.9020016

Open Access | Issue | Published: 19 December 2019

On Quantum Methods for Machine Learning Problems Part I: Quantum Tools

Show Author's Information Hide Author's Information Farid Ablayev, Marat Ablayev, Joshua Zhexue Huang, Kamil Khadiev, Nailya Salikhova, Dingming Wu(

)

∙ College of Computer Science & Software Engineering, Shenzhen University, Shenzhen 518000, China.

∙ Kazan Federal University, Kazan 42008, Russia.

Keywords:

machine learning, quantum algorithm, quantum programming

Cite this article:

Ablayev F, Ablayev M, Huang JZ, et al. On Quantum Methods for Machine Learning Problems Part I: Quantum Tools. Big Data Mining and Analytics, 2020, 3(1): 41-55. https://doi.org/10.26599/BDMA.2019.9020016

Download citation

EndNote(RIS)

BibTeX

1018

Views

Downloads

Citations

Crossref

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

This is a review of quantum methods for machine learning problems that consists of two parts. The first part, "quantum tools", presents the fundamentals of qubits, quantum registers, and quantum states, introduces important quantum tools based on known quantum search algorithms and SWAP-test, and discusses the basic quantum procedures used for quantum search methods. The second part, "quantum classification algorithms", introduces several classification problems that can be accelerated by using quantum subroutines and discusses the quantum methods used for classification.

Full text

Abstract

Full text

Outline

About this article

On Quantum Methods for Machine Learning Problems Part I: Quantum Tools

Show Author's information Hide Author's Information Farid Ablayev, Marat Ablayev, Joshua Zhexue Huang, Kamil Khadiev, Nailya Salikhova, Dingming Wu(

)

∙ College of Computer Science & Software Engineering, Shenzhen University, Shenzhen 518000, China.

∙ Kazan Federal University, Kazan 42008, Russia.

Abstract

Keywords: machine learning, quantum algorithm, quantum programming

References(32)

[1]

S. Arunachalam and R. de Wolf, Guest column: A survey of quantum learning theory, ACM SIGACT News, vol. 48, no. 2, pp. 41-67, 2017.

DOI Google Scholar

[2]

D. Kopczyk, Quantum machine learning for data scientists, arXiv preprint arXiv: 1804.10068, 2018.

Google Scholar

[3]

M. Schuld, I. Sinayskiy, and F. Petruccione, An introduction to quantum machine learning, Contemporary Physics, vol. 56, no. 2, pp. 172-185, 2015.

DOI Google Scholar

[4]

M. Schuld, I. Sinayskiy, and F. Petruccione, The quest for a quantum neural network, Quantum Information Processing, vol. 13, no. 11, pp. 2567-2586, 2014.

DOI Google Scholar

[5]

M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge, UK: Cambridge University Press, 2000.

[6]

R. Jozsa. Quantum computation prerequisite material, https://www.semanticscholar.org/paper/QUANTUM-COMPUTATION-PREREQUISITE-MATERIAL-Jozsa/6dc618f0041a20d8c722ed2cdd8c4057d6e92a0b, 2013.

[7]

A. Eremenko, Spectral theorems for hermitian and unitary matrices, Technical report, Purdue University, USA, 2017.

[8]

I. Wegener, Branching Programs and Binary Decision Diagrams: Theory and Applications. Philadelphia, PA, USA: SIAM, 2000.

DOI

[9]

F. Ablayev, A. Gainutdinova, and M. Karpinski, On computational power of quantum branching programs, in Fundamentals of Computation Theory. FCT 2001, R. Freivalds, ed. Berlin, Germany: Springer, 2001, pp. 59-70.

DOI

[10]

F. M. Ablayev and A. V. Vasilyev, On quantum realisation of Boolean functions by the fingerprinting technique, Discrete Mathematics and Applications, vol. 19, no. 6, pp. 555-572, 2009.

DOI Google Scholar

[11]

F. Ablayev, M. Ablayev, K. Khadiev, and A. Vasiliev, Classical and quantum computations with restricted memory, in Adventures Between Lower Bounds and Higher Altitudes, 2018, pp. 129-155.

DOI

[12]

C. A. Trugenberger, Probabilistic quantum memories, Physical Review Letters, vol. 87, no. 6, p. 067901, 2001.

DOI Google Scholar

[13]

P. Kaye, Reversible addition circuit using one ancillary bit with application to quantum computing, arXiv preprint arXiv: quant-ph/0408173, 2004.

Google Scholar

[14]

L. K. Grover, A fast quantum mechanical algorithm for database search, in ACM Symp. on Theory of Computing, Philadelphia, PA, USA, 1996, pp. 212-219.

DOI

[15]

G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Contemporary Mathematics, vol. 305, pp. 53-74, 2002.

DOI Google Scholar

[16]

L. K. Grover and J. Radhakrishnan, Is partial quantum search of a database any easier, in ACM Symp. on Parallelism in Algorithms and Architectures, Las Vegas, NV, USA, 2005, pp. 186-194.

DOI

[17]

M. Boyer, G. Brassard, P. Høyer, and A. Tapp, Tight bounds on quantum searching, Fortschritte der Physik, vol. 46, nos. 4&5, pp. 493-505, 1998.

DOI

[18]

G. Brassard, P. Høyer, and A. Tapp, Quantum counting, in International Colloquium on Automata, Languages, and Programming, K. G. Larsen, S. Skyum, and G. Winskel, eds. Berlin, Germany: Springer, 1998, pp. 820-831.

DOI

[19]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, vol. 26, no. 5, pp. 1484-1509, 1997.

DOI Google Scholar

[20]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, vol. 41, no. 2, pp. 303-332, 1999.

DOI Google Scholar

[21]

A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem, arXiv preprint arXiv: quant-ph/ 9511026, 1995.

Google Scholar

[22]

R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Quantum algorithms revisited, in Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, vol. 454, no. 1969, pp. 339-354, 1998.

DOI

[23]

M. Mosca, Counting by quantum eigenvalue estimation, Theoretical Computer Science, vol. 264, no. 1, pp. 139-153, 2001.

DOI Google Scholar

[24]

N. Wiebe, A. Kapoor, and K. M. Svore, Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning, Quantum Information & Computation, vol. 15, nos. 3&4, pp. 316-356, 2015.

DOI Google Scholar

[25]

C. Durr and P. Høyer, A quantum algorithm for finding the minimum, arXiv preprint arXiv: quant-ph/9607014, 1996.

Google Scholar

[26]

D. Gottesman and I. Chuang, Quantum digital signatures, arXiv preprint arXiv: quant-ph/0105032, 2001.

Google Scholar

[27]

F. M. Ablayev and A. V. Vasiliev, Cryptographic quantum hashing, Laser Physics Letters, vol. 11, no. 2, p. 025202, 2014.

DOI Google Scholar

[28]

Project Q, https://projectq.ch/, 2019.

[29]

Qiskit, https://qiskit.org/, 2019.

[30]

Rigetti forest sdk, https://pyquil.readthedocs.io/en/stable/start.html, 2019.

[31]

Microsoft Q#, https://docs.microsoft.com/enus/quantum/?view=qsharp-preview, 2019.

[32]

The quipper language, https://www.mathstat.dal.ca/selinger/quipper/, 2019.

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 10 September 2019

Accepted: 25 September 2019

Published: 19 December 2019

Issue date: March 2020

Copyright

Acknowledgements

This work was supported in part by the Russian Science Foundation (No. 19-19-00656) and Natural Science Foundation of Guangdong Province, China (No. 2019A1515011721).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).