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,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,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 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,7,8,9,10], quantum unsupervised learning [7, 11], quantum regression [12,13,14], quantum search engine ranking [15,16,17,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 plays an indispensable role in data clustering [21, 22] and classification [23, 24]. It is a method to evaluate the degree of similarity between individuals. There exist many ways to depict similarity, the most common of which is to use Euclidean distance. That is, the closer the Euclidean distance between two data points (data vectors) is, the more similar they are; and vice versa. With the advent of the era of big data, the number of the data set and the dimension of the data points grow larger. As noted by Aaronson [25], sampling and estimating distances and inner products between post-processed vectors on a classical computer is apparently exponentially hard. Therefore, how to effectively similarity measurement has become a new challenge. Quantum computing may be a good solution to this problem. In 2014, Lloyd exploited quantum parallelism to accelerate the estimation of Euclidean distance from a training data vector to a sample cluster [7]. However, there are many other similarity measurements based on Euclidean distance in classical machine learning algorithms, such as group average distance [26]. Hence, in this work, we examine the issue further and propose three quantum algorithms based on Euclidean distance similarity measurement. In these algorithms, we use the characteristic of quantum random access memory (QRAM) to access data in parallel [27] and the amplitude estimation technology [28] to estimate the Euclidean distance between data sets. And the analysis shows that these algorithms are more efficient than the corresponding classical algorithms.

The remainder of this paper is organized as follows. In Section 2, we briefly introduce the essential preliminaries. Then, the quantum algorithms of three distance measurement methods respectively are described in Section 3. A brief analysis of three proposed quantum algorithms is presented in Section 4. Finally, a short conclusion is provided in Section 5.

2 Preliminaries

2.1 Similarity Measurement Based on Euclidean Distance

As the key of clustering algorithm, similarity measurement can be expressed in many ways. The most common way is Euclidean distance. Given two N-dimensional data vectors u and v, the similarity of them expressed in squared Euclidean distance is \(d^{2}(\mathbf {u},\mathbf {v})={{\sum }_{k=1}^{N}(u_{k}-v_{k})^{2}}\). However, we need not only to estimate the similarity between the points, but also to calculate the distance of two sets in practice. For example, there are three different Euclidean distance measurements in hierarchical clustering, which will lead to different results. Therefore, different methods are needed for different types of data sets. It makes sense to design quantum algorithms for these distances respectively. Before describing quantum algorithms, we review three classical methods, briefly.

Considering the task of similarity measurement for two data sets U and V. And p data points \(\overrightarrow {u_{i}}\in U\) and q data points \(\overrightarrow {v_{j}}\in V\) are given.

  1. i

    Average Linkage (average distance). As shown in Fig. 1a, the squared Euclidean distance between each data point in one set and that in the other set is calculated firstly. Then, by taking the mean as the distance between the two data sets. The average distance between U and V is obtained, which can be written as:

    $$ D(U,V)=\frac{{\sum}_{\overrightarrow{u_{i}}\in U,\overrightarrow{v_{j}}\in V}d^{2}(\overrightarrow{u_{i}},\overrightarrow{v_{j}})}{pq}. $$
    (1)
    Fig. 1
    figure 1

    The illustration of distance

    Full size image
  2. ii

    Complete Linkage (furthest distance). As shown in Fig. 1b, this method is to take the distance between the two furthest data points in the two data sets as the distance between two sets. The furthest distance between U and V can be written as:

    $$ D^{\prime}(U,V)=\underset{\overrightarrow{u_{i}}\in U,\overrightarrow{v_{j}}\in V}{\max}{d^{2}(\overrightarrow{u_{i}},\overrightarrow{v_{j}})}. $$
    (2)
  3. iii

    Single Linkage (nearest distance). As shown in Fig. 1b, the single linkage, contrary to the complete linkage, takes the distance between the nearest data points in the two data sets as the distance between the sets. The nearest distance between U and V can be written as:

    $$ D^{\prime\prime}(U,V)=\underset{\overrightarrow{u_{i}}\in U,\overrightarrow{v_{j}}\in V}{\min}{d^{2}(\overrightarrow{u_{i}},\overrightarrow{v_{j}})}. $$
    (3)

These methods complement each other, satisfying common data types. For example, the average linkage is suitable for ellipsoid data sets, and the single linkage is better for strip data sets [29]. Hence, the three methods could be widely applied to classification and clustering of data sets.

2.2 Data Preparation and Pre-processing

In quantum machine learning, we generally assume that data sets consist of arrays of vectors stored in QRAM. Given a N = 2n dimensional complex vector \(\overrightarrow {u}\), we can express it as the composition of N components of \(\overrightarrow {u}=(u_{1},u_{2},\cdots , u_{N})\), where \(\{{u_{k}}=|u_{k}|e^{\texttt {i}\phi _{k}},\ \texttt {i}=\sqrt {-1}\}\). Moreover, we assume that {|uk|,ϕk} are stored as floating point numbers in quantum random access memory, and stored as “binary trees” data structure that is shown in Fig. 2. The details can be found in its initial proposal for designing quantum recommendation system [30], as well as its successful application in designing the quantum linear system algorithm for dense matrices [31]. In short, N dimensional vector \(\overrightarrow {u}\) can be described by a quantum state \(|u\rangle =|\overrightarrow {u}|^{-1} \overrightarrow {u}\) of n qubits in time \(O\left (\log _{2} N\right )\). Once the exponentially compressed quantum versions of the vectors have been created, we can apply these vectors to the proposed quantum algorithms.

Fig. 2
figure 2

The binary tree storage a data point u, store its \({{u}_{k}^{2}}\) in binary form. Furthermore, this kind of storage structure build N dimensional vector corresponding quantum state simply by \(O\left (\log _{2} N\right )\)

Full size image

3 Quantum Algorithms

In this section, we present quantum algorithms for similarity measurement. It consists of three ways to compute similarity of two data sets based on Euclidean distance: quantum algorithms for estimating the average linkage, the complete linkage and the single linkage.

Suppose that two N dimensional data sets \(U:\left \{\overrightarrow {u_{i}} | i=1,2, \cdots , p\right \}\) and \(V:\left \{\overrightarrow {v_{j}} | j=1,2, \cdots , q\right \}\) are given. From Section 2.2, the corresponding normalization \(\left |\overrightarrow {u_{i}}\right |\) and \(\left |\overrightarrow {v_{j}}\right |\) can be respectively obtained from quantum random access memory. Then, we can read data from QRAM efficiently and build their corresponding form of quantum state \(\left |u_{i}\right \rangle \) and \(\left |v_{j}\right \rangle \) through the following two unitary operations

$$ U_{\mathcal{F}}: \frac{1}{\sqrt{p}} \sum\limits_{i=1}^{p}|i\rangle|0\rangle \mapsto \frac{1}{\sqrt{A}} \sum\limits_{i=1}^{p}|i\rangle \otimes \overrightarrow{u_{i}}=\frac{\left.{\sum}_{i=1}^{p}\left|\overrightarrow{u_{i}} \| i\right\rangle|u_{i}\right\rangle}{\sqrt{{\sum}_{i=1}^{p}\left|\overrightarrow{u_{i}}\right|^{2}}}, $$
(4)
$$ U_{\mathcal{T}}: \frac{1}{\sqrt{q}} \sum\limits_{j=1}^{q}|0\rangle|j\rangle \mapsto \frac{1}{\sqrt{B}} \sum\limits_{j=1}^{q} \overrightarrow{v_{j}} \otimes|j\rangle=\frac{{\sum}_{j=1}^{q}\left|\overrightarrow{v_{j}} \| v_{j}\right\rangle|j\rangle}{\sqrt{{\sum}_{j=1}^{q}\left|\overrightarrow{v_{j}}\right|^{2}}}. $$
(5)

Here, \(A={\sum }_{i=1}^{p}\left |\overrightarrow {u}_{i}\right |^{2}\), \(B={\sum }_{j=1}^{q}\left |\overrightarrow {v_{j}}\right |^{2}\). That is, the operations \(U_{\mathcal {F}}\), \(U_{\mathcal {T}}\) allow preparation of quantum state encoding an original data point of data sets \(\left \{\overrightarrow {u_{i}}\right \}\) and \(\left \{\overrightarrow {v_{j}}\right \}\) respectively. Moreover, based on the conclusions of Ref. [32], two controlled operators \(C(U_{\mathcal {F}})\), \(C(U_{\mathcal {T}})\) may be constructed with the circuits, if the operators \(U_{\mathcal {F}}\) and \(U_{\mathcal {T}}\) are implemented efficiently. In the following, the implementations of quantum algorithms for three computing methods are put forward.

3.1 Algorithm 1: a Quantum Algorithm for Estimating the Average Linkage

From (1), the average distance between two data sets can be expressed as quantum form

$$ \begin{array}{ll} {D(U,V)}&=\frac{{\sum}_{i=1}^{p} {\sum}_{j=1}^{q}{\left|\overrightarrow{u_{i}}-\overrightarrow{v_{j}}\right|}^{2}}{p q}\\ & =\frac{{\sum}_{i=1}^{p} {\sum}_{j=1}^{q}\left( \left|\overrightarrow{u_{i}}\right|^{2}+\left|\overrightarrow{v_{j}}\right|^{2}-2\left|\overrightarrow{u_{i}}\right|\left|\overrightarrow{v_{j}}\right|\left\langle u_{i} | v_{j}\right\rangle\right)}{p q}. \end{array} $$
(6)

Obviously, we are able to use Lloyd algorithm [7] to accomplish this task. Namely, by Lloyd algorithm, the distances between all data points in one data set and the other data set are got, then the average distance is directly derived from the average value of these distances. However, it needs time \(O\left (pq\log N\right )\) and is not efficient. To achieve the internal quantum efficiency, we reexamine this task and propose a new quantum algorithm, which is described as follows.

  1. (A1.1)

    Let us start with constructing a quantum system that consists of four registers, in the initial state, |ϕ〉 = |0〉1|0〉2|0〉3|0〉4, where the subscript indicates the location of register.

  2. (A1.2)

    An operation \(H_{1}\otimes {{F}_{2}^{p}} \otimes I_{3} \otimes {{F}_{4}^{q}}\) is applied on these four registers. Here, \(H=\frac {1}{\sqrt 2} (|0\rangle \langle 0|+|0\rangle \langle 1|+|1\rangle \langle 0|-|1\rangle \langle 1|)\) is a Hadamard operator, and Fp (Fq) is a p(q)-level Fourier transform operator depicted as follows,

    $$ F^{p} = \sum\limits_{i=1}^{p}{\omega}^{il}|i\rangle \langle l|, $$
    (7)

    where, \(\omega =e^{\frac {2\pi \texttt {i}}{p}}\). After this operation, the whole system is in the state,

    $$ \begin{array}{ll} \left|\varphi\right\rangle &=H_{1}\otimes {{F}_{2}^{p}} \otimes I_{3} \otimes {{F}_{4}^{q}}|\phi\rangle_{1234}\\ &=\frac{1}{\sqrt{2 p q}} {\sum}_{i=1}^{p} {\sum}_{j=1}^{q}(|0\rangle|i\rangle|0\rangle|j\rangle+|1\rangle|i\rangle|0\rangle|j\rangle)_{1234}, \end{array} $$
    (8)
  3. (A1.3)

    In this step, a controlled operator \(C(U_{\mathcal {F}})_{123}\) (\(C(U_{\mathcal {T}})_{134}\)) is performed on \(\left |\varphi \right \rangle \), where the first register is the control qubit, and the second and third (second and fourth) registers are the target. That is, if the control qubit is in state |0〉 then apply \(U_{\mathcal {F}}\) to the target registers, otherwise apply \(U_{\mathcal {T}}\), as shown in Fig. 3. After performing the operations \(C(U_{\mathcal {F}})_{123}\) and \(C(U_{\mathcal {T}})_{134}\), the desired state can be obtained,

    $$ \begin{array}{ll} |\psi\rangle &= C(U_{\mathcal{F}})_{123} C(U_{\mathcal{T}})_{134}|\varphi\rangle_{1234}\\ &=\frac{1}{\sqrt{q A+p B}} {\sum}_{i=1}^{p} {\sum}_{j=1}^{q}\left( |0\rangle|i\rangle\left|\overrightarrow{u_{i}}\right|\left|u_{i}\right\rangle|j\rangle+|1\rangle|i\rangle\left|\overrightarrow{v_{j}} \| v_{j}\right\rangle|j\rangle\right)_{1234}, \end{array} $$
    (9)

    where, \(A={\sum }_{i=1}^{p}\left |\overrightarrow {u_{i}}\right |^{2}\) and \(B={\sum }_{j=1}^{q}\left |\overrightarrow {v_{j}}\right |^{2}\).

  4. (A1.4)

    A projective measurement is performed on the first register of state \(\left |\psi \right \rangle \) in the basis \(\{|+\rangle ,|-\rangle \ |\ |\pm \rangle =\frac {1}{\sqrt 2}(|0\rangle \pm |1\rangle )\}\). A direct and simple calculation shows that

    $$ Pr(-)=\frac{\left( q {\sum}_{i=1}^{p}\left|\overrightarrow{u_{i}}\right|^{2}+p {\sum}_{j=1}^{q}\left|\overrightarrow{v_{j}}\right|^{2}-2 {\sum}_{i=1}^{p} {\sum}_{j=1}^{q}\left|\overrightarrow{u_{i}}\right|\left|\overrightarrow{v_{j}}\right|\left\langle u_{i} | v_{j}\right\rangle\right)}{2(q A+p B)}. $$
    (10)

    which is the probability of that the measurement outcome is |−〉.

  5. (A1.5)

    Now, we can straightforward to calculate that square of desired distance,

    $$ \sum\limits_{i=1}^{p} \sum\limits_{j=1}^{q}\left|\overrightarrow{u_{i}}-\overrightarrow{v_{j}}\right|^{2}=2(q A+p B)\times Pr(-). $$
    (11)

    After that, the similarity can be easy to deduce, is equal to \(\frac {{2(q A+p B)\times Pr(-)}}{pq}\).

Fig. 3
figure 3

Schematic diagram of controlled operations \(C\left (U_{\mathcal {F}}\right )\) and \(C\left (U_{\mathcal {T}}\right )\), where \(\left |\tilde {u}_{i}\right \rangle \), \(\left |\tilde {v}_{j}\right \rangle \) represent vectors which may not be normalized

Full size image

Through the above steps, we can obtain the average Euclidean distance between two data sets, which can be used to describe the similarity of these. The schematic quantum circuit of Algorithm 1 is shown in Fig. 4.

Fig. 4
figure 4

Quantum circuit of Algorithm 1

Full size image

3.2 Algorithm 2: a Quantum Algorithm for Estimating the Complete Linkage

In classical machine learning, because of the complexity of the average linkage calculation, the complete linkage is used as the distance between data sets sometimes. From (2), it is evident that the complete linkage is equal to the task of finding the maximum, from the distances between all data points in set \(U=\left \{\overrightarrow {u_{i}}\right \}\) and each data point of set \(V=\left \{\overrightarrow {v_{j}}\right \}\), i.e., \(D^{\prime }(U,V)=\max \limits _{i}{{{d}_{i}^{2}}}=\max \limits _{i}{(\max \limits _{j}{d^{2}(\overrightarrow {u_{i}},\overrightarrow {v_{j}})})}\).

Next, the second quantum algorithm for estimating the complete linkage, Algorithm 2, is presented. In this algorithm, we take the same assumption as that in Section 2, the data points are stored as quantum states in QRAM. So, the quantum counterpart of the distance between two points \(\overrightarrow {u_{i}}\) and \(\overrightarrow {v_{j}}\) is represented as

$$ {d}_{i, j}^{2}={\left|\left| \overrightarrow{u_{i}}\right|\left| u_{i}\right\rangle-\left|\overrightarrow{v_{j}}\right|\left|v_{j}\right\rangle \right|}^{2}={\left|\overrightarrow{u_{i}}\right|^{2}+\left|\overrightarrow{v_{j}}\right|^{2}-2\left|\overrightarrow{u_{i}}\right|\left|\overrightarrow{v_{j}}\right|\left\langle u_{i} | v_{j}\right\rangle}. $$
(12)

Besides, without loss of generality, we can assume p ≤ q. In this case, we reckon the maximum distance between the sample vector \( \overrightarrow {u_{i}}\) (i = 1,2,⋯ ,p) and each data point of data set \(\left \{ \overrightarrow {v_{j}} \right \}\) in turn, and get set \(\left \{{{d}_{1}^{2}},{{d}_{2}^{2}}, \cdots , {{d}_{p}^{2}}\right \}\) (\({{d}_{i}^{2}}=\max \limits _{j}{d^{2}(\overrightarrow {u_{i}},\overrightarrow {v_{j}})}\), i = 1,2,⋯ ,p). Then, the desired distance can be find based on it. The details of the second algorithm are described in the following steps.

  1. (A2.1)

    In a similar way to Algorithm 1, p initial states \(|{\phi }_{i}^{\prime }\rangle \) (i = 1,2,⋯ ,p) are prepared firstly. Each state \(|{\phi }_{i}^{\prime }\rangle \) consists of four registers and in the initial state, \(|{\phi }_{i}^{\prime }\rangle = |0\rangle _{1}|i\rangle _{2}|0\rangle _{3}|0\rangle _{4}\). It will be utilized to calculate distance between the ith data point \( \overrightarrow {u_{i}}\) in data set \(\left \{ \overrightarrow {u_{i}} \right \}\) and each point of data set \(\left \{ \overrightarrow {v_{j}} \right \}\).

  2. (A2.2)

    An operation \(H_{1}\otimes I_{2} \otimes I_{3} \otimes {{F}_{4}^{q}}\) is applied on the state \(|\phi _{i}^{\prime }\rangle \). After this operation, it is in the state,

    $$ \begin{array}{ll} \left|{\varphi}_{i}^{\prime}\right\rangle &=H_{1}\otimes I_{2} \otimes I_{3} \otimes {F^{q}_{4}}|\phi_{i}^{\prime}\rangle_{1234}\\ &=\frac { 1 } { \sqrt { 2q } } {\sum}_{ j=1 }^{ q } (| 0 \rangle | i \rangle | 0 \rangle | j \rangle + | 1 \rangle | i \rangle | 0 \rangle | j \rangle)_{1234}. \end{array} $$
    (13)
  3. (A2.3)

    Two controlled operations \(C(U_{\mathcal {F}})_{123}\), \(C(U_{\mathcal {T}})_{134}\) are performed on the state \(\left |{\varphi }_{i}^{\prime }\right \rangle \). And the details are the same as that in step (A1.3) of Algorithm 1. Then, we obtain the state

    $$ \begin{array}{ll} \left|{\psi}_{i}^{\prime}\right\rangle&=C(U_{\mathcal{F}})_{123}C(U_{\mathcal{T}})_{134}|{\varphi}_{i}^{\prime}\rangle_{1234}\\ &=\frac{{\sum}_{j=1}^{q}\left( |0\rangle|i\rangle\left|\overrightarrow{u_{i}}\right|\left|u_{i}\right\rangle|j\rangle+|1\rangle|i\rangle\left|\overrightarrow{v_{j}}\right|\left|v_{j}\right\rangle|j\rangle\right)_{1234}}{\sqrt{q\left|\overrightarrow{u_{i}}\right|^{2}+{\Sigma}_{j}\left|\overrightarrow{v_{j}}\right|^{2}}}. \end{array} $$
    (14)
  4. (A2.4)

    In this step, we measure these q desired states \(\left |{\psi }_{i}^{\prime }\right \rangle \). Concretely, one projective measurement is performed on the first register of this state in the {|+〉,|−〉} basis. At the same time, the other projective measurement is on the fourth register. This projective measurement is described by an observable, M = Σj|j〉〈j|, a Hermitian operator on the state space of the system being observed. After that, these two registers will project into |−〉〈−| and |j〉〈j| space respectively, with probability

    $$ Pr_{i j}=\frac{\left|\overrightarrow{u_{i}}\right|^{2}+\left|\overrightarrow{v_{j}}\right|^{2}-2\left|\overrightarrow{u_{i}}\right|\left|\overrightarrow{v_{j}}\right|\left\langle u_{i} | v_{j}\right\rangle}{2\left( q\left|\overrightarrow{u_{i}}\right|^{2}+{\sum}_{j=1}^{q}\left|\overrightarrow{v_{j}}\right|^{2}\right)}. $$
    (15)

    Thus, according to (12) and (15), the auxiliary qubit projects to the space spanned by the index \(\left |j\right \rangle \) of set \(\left \{\left |v_{j}\right \rangle \right \}\), that is the farthest from the ith data point in set \(\{\overrightarrow {u_{i}}\}\), with maximum probability mpi. Finally, it is straightforward to calculate the square of maximum distance between the ith sample vector in the data set \(\{\overrightarrow {u_{i}}\}\) and the data point each of data set \(\{\overrightarrow {v_{j}}\}\),

    $$ {{d}_{i}^{2}}=mp_{i} \times 2\left( q\left|\overrightarrow{u_{i}}\right|^{2}+\sum\limits_{j=1}^{q}\left|\overrightarrow{v_{j}}\right|^{2}\right). $$
    (16)
  5. (A2.5)

    Repeating steps (A2.2)-(A2.4) for each \(|\phi _{i}^{\prime }\rangle \) (i = 1,2,⋯ ,p) in turn. It allows us to get the distance set \({\varOmega }=\left \{{{d}_{1}^{2}},{{d}_{2}^{2}}, \cdots , {{d}_{p}^{2}}\right \}\). Then, it costs time O(p) to check every \({{d}_{i}^{2}}\) and find the maximum by using classical methods. Hence, we retrieve the farthest distance \({d}_{\max \limits }^{2}\) of data point in the data sets \(\{\overrightarrow {u_{i}}\}\) and \(\{\overrightarrow {v_{j}}\}\).

Through the above steps, we can obtain the squared Euclidean distance between the furthest data vectors in two sets. Its execution operations are similar to Algorithm 1, so the circuit diagram can refer to Fig. 4.

3.3 Algorithm 3: a Quantum Algorithm for Estimating the Single Linkage

The single linkage method is more suitable for estimating the similarity of s-shaped and strip-shaped data sets in the clustering algorithm [29]. As shown in Section 2, the single linkage is measuring distance of the nearest pair of data vector in data sets \(\{\overrightarrow {u_{i}}\}\) and \(\{\overrightarrow {v_{j}}\}\), i.e., \(D^{\prime \prime }(U,V)=\min \limits {{{d}_{i}^{2}}}=\min \limits _{i}{(\min \limits _{j}{d^{2}(\overrightarrow {u_{i}},\overrightarrow {v_{j}})})}\). Obviously, the method of estimating the complete linkage can be generalized to that of the single linkage. Next, we will describe the third quantum algorithm for estimating the single linkage. Before describing the steps of it, we first assume that the data sets have been processed which makes the different sets are in different spatial quadrants. Then, we introduce two quantum oracles.

Suppose that the following two quantum oracles Ou, Ov exist to obtain the reciprocal of each component of \(\overrightarrow {u_{i}}\) and \(\overrightarrow {v_{j}}\) respectively,

$$ O_{u}:|i\rangle|k\rangle \mapsto \frac{1}{u_{i k}}|i\rangle|k\rangle=|i\rangle\left|\tilde{u}_{i k}^{\prime}\right\rangle, $$
(17)
$$ O_{v}:|k\rangle|j\rangle \mapsto \frac{1}{v_{j k}}|k\rangle|j\rangle=\left|\tilde{v}_{j k}^{\prime}\right\rangle|j\rangle. $$
(18)

Here, the data vectors’ components are stored as floating point numbers in quantum random access memory, and the states \(\left |\tilde {u}_{i k}^{\prime }\right \rangle \) and \(|\tilde {v}_{j k}^{\prime }\rangle \) representing vectors may not be normalized. Meanwhile, the two oracles can be used to efficiently prepare the vector states \(\left |\tilde {u}_{i}^{\prime }\right \rangle \), \(\left |\tilde {v}_{j}^{\prime }\right \rangle \) in time \(O\left (\log N\right )\).

$$ O_{u}: \sum\limits_{k=1}^{N}|i\rangle|k\rangle \mapsto \sum\limits_{k=1}^{N} \frac{1}{u_{i k}}|i\rangle|k\rangle=\sum\limits_{k=1}^{N}\left|\tilde{u}_{i k}^{\prime}\right\rangle|i\rangle \mapsto \overrightarrow{{u}_{i}}^{\prime}=\left|\overrightarrow{u_{i}}^{\prime}\right|\left|{u}_{i}^{\prime}\right\rangle, $$
(19)
$$ O_{v}: \sum\limits_{k=1}^{N}|k\rangle|j\rangle \mapsto \sum\limits_{k=1}^{N} \frac{1}{v_{j k}}|k\rangle|j\rangle=\sum\limits_{k=1}^{N}\left|\tilde{v}_{j k}^{\prime}\right\rangle|j\rangle \mapsto \overrightarrow{{v}_{j}}^{\prime}=\left|\overrightarrow{v_{j}}^{\prime}\right|\left|{v}_{j}^{\prime}\right\rangle. $$
(20)

The essential steps of this algorithm is depicted as follows.

  1. (A3.1)

    At first, we construct p initial states \(|{\phi }_{i}^{\prime \prime }\rangle = |0\rangle _{1}|i\rangle _{2}|0\rangle _{3}|0\rangle _{4}\), and each one consists of four registers. As similar to Algorithm 2, the state \(|{\phi }_{i}^{\prime \prime }\rangle \) means we estimate the distance between the ith vector \( \overrightarrow {{u}_{i}}\) and each point of data set \(\left \{ \overrightarrow {{v}_{j}} \right \}\), in this time.

  2. (A3.2)

    We apply an operation \(H_{1}\otimes I_{2} \otimes {{F}_{3}^{N}} \otimes {{F}_{4}^{q}}\) on the state \(|{\phi }_{i}^{\prime \prime }\rangle \). Here, FN (Fq) is a N(q)-level Fourier transform. In this way, we can obtain state

    $$ \begin{array}{ll} \left|{\varphi}_{i}^{\prime\prime}\right\rangle &=H_{1}\otimes I_{2} \otimes {{F}_{3}^{N}} \otimes {{F}_{4}^{q}}|{\phi}_{i}^{\prime\prime}\rangle_{1234}\\ &=\frac{1}{\sqrt{2q}} {\sum}_{j=1}^{q} {\sum}_{k=1}^{N}(|0\rangle|i\rangle|k\rangle|j\rangle+|1\rangle|i\rangle|k\rangle|j\rangle)_{1234}. \end{array} $$
    (21)
  3. (A3.3)

    Two controlled operations are performed on the state \(\left |{\varphi }_{i}^{\prime \prime }\right \rangle \) based on the oracles. That is, the oracle Ou is applied on the second and the third register if the first qubit of \(\left |{\varphi }_{i}^{\prime \prime }\right \rangle \) is in the state \(\left |0\right \rangle \); otherwise oracle Ov is applied on the third and fourth register. In this way, we will have the specific state

    $$ \begin{array}{ll} \left|{\psi}_{i}^{\prime\prime}\right\rangle&=\frac{1}{\sqrt{2q}} {\sum}_{j=1}^{q} {\sum}_{k=1}^{N}\left( |0\rangle O_{u}|i\rangle|k\rangle|j\rangle+|1\rangle|i\rangle O_{v}|k\rangle|j\rangle\right)_{1234}\\ &=\frac{{\sum}_{j=1}^{q}\left( |0\rangle|i\rangle\left|\overrightarrow{{u}_{i}}^{\prime}\right|\left|{u}_{i}^{\prime}\right\rangle|j\rangle+|1\rangle|i\rangle\left|\overrightarrow{{v}_{j}}^{\prime}\right|\left|{v}_{j}^{\prime}\right\rangle|j\rangle\right)_{1234}}{\sqrt{q\left|\overrightarrow{{u}_{i}}^{\prime}\right|^{2}+{\sum}_{j=1}^{q}\left|\overrightarrow{{v}_{j}}^{\prime}\right|^{2}}}. \end{array} $$
    (22)
  4. (A3.4)

    In this step, the state \(\left |{\psi }_{i}^{\prime \prime }\right \rangle \) instead of state \(\left |{\psi }_{i}^{\prime }\right \rangle \) in the second quantum algorithm. Then, we repeat steps (A2.2)-(A2.4) of Algorithm 2, it can easily adapts to compute the maximum \(d_{i}^{\prime 2}\).

  5. (A3.5)

    We get the distance set \({\varOmega }^{\prime }=\left \{{d}_{1}^{\prime 2},{d}_{2}^{\prime 2}, \cdots , {d}_{p}^{\prime 2}\right \}\) after we repeat steps (A3.2)-(A3.4) for each state \(|{\phi }_{i}^{\prime \prime }\rangle \) (i = 1,2,⋯ ,p). Hence, we retrieve a distance between the farthest pair of data sets (these correspond to the nearest pair of sets in the original data sets) in the way of step (A2.5) from Algorithm 2.

Although the nearest distance between the original data sets is not calculated through the above steps, our algorithm can map the Euclidean distance between the same closest data point pairs. Then, we can depict the similarity between the two sets by it. This result has the same effect on other machine learning tasks, such as hierarchical clustering.

4 Runtime Analysis

In this paper, we proposed three algorithms’ main ideas are similarly, that they all utilize special measurement results to estimate the Euclidean distance between data sets. However, their implementation details are different, so there are some differences in running time. In this section, the performance of them is analyzed briefly.

From Section 3.1, it is known that the time cost is mainly for two main steps in Algorithm 1, i.e., steps (A1.3) and (A1.4). Evidently, what step (A1.3) generates the state of (9) takes time \(O(\log (pq N^{2}))\) [31] based on two controlled operations \(C(U_{\mathcal {F}})\) and \(C(U_{\mathcal {T}})\). In step (A1.4), the time cost is evidently dominated by the amplitude estimation. According to [28], taking \(O\left (\sqrt {\frac {1-Pr(-)}{Pr(-)}} \cdot \frac {1}{\epsilon }\right )= O\left (\sqrt {\frac {1}{Pr(-)}} \cdot \frac {1}{\epsilon }\right )\) times to perform projective measurement ensures that desired result Pr(−) being within relative error 𝜖. Finally, we can be easy to calculate the average distance by the special measure result. Hence, the time cost of the total Algorithm 1 is \(O\left (\frac {1}{\epsilon \cdot \sqrt {Pr(-)}} \log \left (pq N^{2}\right )\right )\). Compared with time O(ploy(pqN)) for the best-known classical algorithm, in this case the exponential speedup can be achieved.

As for Algorithm 2, it is shown that there are two main differences with the last algorithm. One is preparation of state \(\left |{\psi }_{i}^{\prime }\right \rangle \) as shown in step (A2.3). It takes time \(O(\log (N)+\log (q N))\). Another is that Algorithm 2 gets the maximum distance set \({\varOmega }=\left \{{d_{1}^{2}},{d_{2}^{2}}, \cdots , {d_{p}^{2}}\right \}\). It is described in step (A2.5), and each \({{d}_{i}^{2}}\) for i = 1,2,⋯ ,p costs \(O\left (\frac {1-mp_{i}}{mp_{i}} \cdot \frac {1}{\epsilon _{d}}\right )= O\left (\frac {1}{{mp_{i}\cdot {\epsilon _{d}}}} \right )\) times within relative error 𝜖d of mpi. Therefore, getting the distance set Ω takes time \(O\left ({\sum }_{i=1}^{p} \frac {1}{{{mp_{i}} \cdot \epsilon _{d}}} \log (q N^{2})\right )\). Then, we find the maximum of set \(\left \{{{d}_{1}^{2}},{{d}_{2}^{2}}, \cdots , {{d}_{p}^{2}}\right \}\) by using the simple classical method in time O(p). Through above brief analysis, the total time of Algorithm 2 is \(O\left ({\sum }_{i=1}^{p} \frac {1}{{{mp_{i}} \cdot \epsilon _{d}}} \log (q N^{2})+p\right )\). It means that when the number of data space and the dimension of data are large, Algorithm 2 can achieve exponential speedup over the classical similarity measurement algorithms.

In Algorithm 3, the method adopted is the generalization of the second algorithm. The only difference is that in step (A3.3) of the third quantum algorithm, we preprocess the original data and generate a specific state \(\left |\psi _{i}^{\prime \prime }\right \rangle \) with our quantum oracles Ou and Ov. Thus, the nearest distance is converted to the farthest distance to solve the problem. Due to the parallel processing of the quantum algorithm, the time complexity of Algorithm 3 is similar to that of Algorithm 2. Therefore, it is also exponentially accelerated relative to the steps that produce the same effect on the classical algorithm.

Through the brief analysis, we presented algorithms are accelerated to a certain extent compared with the classical algorithm. It is worth emphasizing that the quantum algorithm implementation of the proposed three programs allow us to call different subroutines according to different needs, just like the classical clustering algorithm.

5 Conclusion

In this paper, we made a further study on the quantum similarity measurement. Instead of date points, the distance between data sets is considered, which usually acts as a basic component of some machine learning algorithms. First, we discussed three common kinds of Euclidean distance methods. Then, the characteristics of parallel access data of quantum random access memory and amplitude estimation technology are utilized to propose the corresponding three quantum algorithms. At last, it is shown that the proposed algorithms can achieve exponential speedup over the classical counterparts for data sets with a mass of high-dimensional vector, via a brief complexity analysis. These results demonstrate that measuring the similarity between data sets can implement other interesting tasks with significantly less quantum resource, e.g., document clustering [33, 34], medical analysis [35, 36], and so on.