Quantum Algorithms for Similarity Measurement Based on Euclidean Distance
- PDF / 635,451 Bytes
- 11 Pages / 439.642 x 666.49 pts Page_size
- 20 Downloads / 206 Views
Quantum Algorithms for Similarity Measurement Based on Euclidean Distance Kai Yu1 · Gong-De Guo1 · Jing Li1 · Song Lin1 Received: 26 February 2020 / Accepted: 4 August 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Similarity measurement is a fundamental problem that arise both on its own and as a key subroutine in more complex tasks, such as machine learning. However, in classical algorithms, the time used to similarity measurement usually increases exponentially as the amount of data and the number of data dimensions increase. In this paper, we presented three quantum algorithms based on Euclidean distance to measure the similarity between data sets. In the proposed algorithms, some special unitary operations are utilized to construct imperative quantum states from quantum random access memory. Then, a badly needed result for estimating the similarity between data sets, can be got by performing projective measurements. Furthermore, it is shown that these algorithms can achieve the exponential acceleration of the classical algorithm in the quantity or the dimension of data. Keywords Quantum algorithm · Quantum machine learning · Similarity measurement · Euclidean distance
1 Introduction Dating from the 80’s of last century, it is shown that quantum computing allows for more efficient solutions of some problems than classical computing. The prime-factorization problem is one of this. In 1994, by exploiting quantum mechanical properties, Shor proposed the famous Shor algorithm [1], which is exponentially faster than the best-known classical factoring algorithm. The other one is Grover algorithm for solving unsorted database search problem [2], which makes quadratic speedup over the classical search algorithm. Inspired by these algorithms, people try to exploit quantum computing to solve other problems in the field of information technology [3–20], e.g., machine learning. The most representative one is HHL algorithm [3]. In this algorithm, Harrow et al. utilized Hamiltonian simulation [4] and phase estimation technology to solve linear equations. Furthermore, it has exponential speedup compared with classical counterpart, and can be widely applied in machine learning numerical calculation or other scenarios. After that, more and Song Lin
[email protected] 1
College of Mathematics and Informatics, Fujian Normal University, Fuzhou, 350007, China
International Journal of Theoretical Physics
more attention has been paid to this new multi-knowledge crossed research field, quantum machine learning. As for now, some subtle quantum machine learning algorithms have been proposed for various machine learning tasks, such as quantum principal component analysis [5], quantum supervised learning [6–10], quantum unsupervised learning [7, 11], quantum regression [12–14], quantum search engine ranking [15–18], quantum neural network [19], and so on. More excitingly, all these algorithms achieve desirable speedup effect. Similarity measurement is a primitive machine learning task, which pl
Data Loading...
