On Quantum Methods for Machine Learning Problems Part II: Quantum Classification Algorithms

The SVM is a well-known algorithm for the classification problem^{[ 1 ]}. For function $F$ , we can write the following:

(2) $$F(x)=\text{sign}\left(\underset{i=1}{\overset{n}{\sum }}{x}_i{w}_i+w_0\right)=\text{sign}((x\cdot w)+w_0)$$

where $x=(x_1,\mathrm{\dots },x_n)\in {ℝ}^n$ , the coefficients $w=(w_1,\mathrm{\dots },w_n)\in {ℝ}^n$ and $w_0\in ℝ$ are parameters of the algorithm, $(x\cdot w)$ is the inner product of the vectors, and the hyperplane $(x\cdot w)+w_0$ separates two classes.

As a plane, we choose the farthest one of the nearest vectors. The closest vectors to the plane are called "support vectors" and should be such that $(x^i\cdot w)+w_0=y^i$ or, equivalently, $y^i((x^i\cdot w)+w_0)=1$ . For finding the parameters of the plane, we should maximize the distance between different classes with $2/||w||$ or, equivalently, minimize $0.5{||w||}^2$ . The minimization problem can be solved with the following conditions:

(3) $$y^i((x^i\cdot w)+w_0)⩾1,i\in \{1,\mathrm{\dots },m\}$$

Based on the Kuhn-Tucker theorem, we can replace the problem by the dual formulation of the Lagrange function:

(4) $$ℒ(w,w_0,\lambda )=0.5(w\cdot w)-{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\lambda }_i(y^i((w\cdot x^i)-w_0)-1)$$ $$\to \underset{w\in {ℝ}^n,w_0\in ℝ}{\min }\underset{\lambda \in {ℝ}^m}{\max }$$

with the following conditions for $i\in \{1,\mathrm{\dots },m\}$ :

• ${\lambda }_i⩾0$ ;

• ${\lambda }_i=0$ , or $(x^i\cdot w)-w_0=y_i$ .

At the same time, we have the following conditions:

(5) $$\{\begin{array}{c}\frac{\partial ℒ}{\partial w}=w-\underset{i=1}{\overset{m}{\sum }}{\lambda }_i{y}^i{x}^i=0;\hfill \\ \frac{\partial ℒ}{\partial w_0}=-\underset{i=1}{\overset{m}{\sum }}{\lambda }_i{y}^i=0\hfill \end{array}$$

Therefore, we obtain the next relation between $\lambda$ and $w$ :

(6) $$\{\begin{array}{c}w=\underset{i=1}{\overset{m}{\sum }}{\lambda }_i{y}^i{x}^i;\hfill \\ \underset{i=1}{\overset{m}{\sum }}{\lambda }_i{y}^i=0\hfill \end{array}$$

Finally, we obtain the following optimization problem on the $\lambda$ variables:

(7) $$ℒ(\lambda )=\underset{i=1}{\overset{m}{\sum }}{\lambda }_i+0.5\underset{i=1}{\overset{m}{\sum }}\underset{j=1}{\overset{m}{\sum }}{\lambda }_i{\lambda }_j{y}^i{y}^j(x^i\cdot x^j)\to \underset{\lambda }{\max }$$

with the following conditions for $i\in \{1,\mathrm{\dots },m\}$ :

• ${\lambda }_i⩾0$ ;

• ${\sum }_{i=1}^m{\lambda }_i{y}^i=0$ .

In a case of a non-linear separation between classes, we can add errors ${\xi }_i$ ; in that case $y^i((w\cdot x^i)+w_0)⩾1-{\xi }_i$ . The minimization function is replaced by $0.5{||w||}^2+C{\sum }_{i=1}^m{\xi }_i$ , where $C$ is a constant that is a parameter of the algorithm. The Lagrange function in Eq. ( 4 ) is replaced by

(8) $$\begin{array}{c}ℒ(w,w_0,\sigma ,\lambda ,\beta )=0.5{||w||}^2+C\underset{i=1}{\overset{m}{\sum }}{\xi }_i-\hfill \\ \hfill \underset{i=1}{\overset{m}{\sum }}{\lambda }_i\left\{{\lambda }_i\left[(w\cdot x^i)-w_0\right]-1+{\xi }_i\right\}-\underset{i=1}{\overset{m}{\sum }}{\beta }_i{\xi }_i\end{array}$$

with ${\lambda }_i$ and ${\beta }_i⩾0$ . The relation between $\lambda ,\beta$ and $w,\xi$ can be obtained using an equation similar to Eq. ( 6 ). At the same time, we obtain the additional equality $C-{\beta }_i-{\lambda }_i=0$ . Because ${\beta }_i⩾0$ , we get ${\lambda }_i⩽C$ . The final minimization problem is

(9) $$ℒ(\lambda )=\underset{i=1}{\overset{m}{\sum }}{\lambda }_i+0.5\underset{i=1}{\overset{m}{\sum }}\underset{j=1}{\overset{m}{\sum }}{\lambda }_i{\lambda }_j{y}^i{y}^j(x^i\cdot x^j)\to \underset{\lambda }{\max }$$

with the following conditions for $i\in \{1,\mathrm{\dots },m\}$ :

• $C⩾{\lambda }_i⩾0$ ;

• ${\sum }_{i=1}^m{\lambda }_i{y}^i=0$ .

If the input data is not linearly separable, then we can replace the inner product $(x^i\cdot x^j)$ by another function $k(x^i,x^j)$ , which is called the kernel of the SVM algorithm. Typically, researchers choose the following functions as possible kernels: ${(x^i\cdot x^j)}^d$ and ${(x^i\cdot x^j+1)}^d$ for some constant $d$ ; or ${\text{e}}^{-\gamma {||x^i-x^j||}^2}$ for some constant $\gamma >0$ .

In the general case, $ℒ(\lambda )$ can have several local minimums, and gradient-based methods are unhelpful. In that case, the problem is NP-hard. We can apply discretization and then use brute force or analog algorithms. We can also apply the Grover’s search to this problem and obtain a quadratic speed-up. A description of the algorithm follows.

Supposing that $\epsilon >0$ is a given precision for our solution, then we can split the segment $[0;C]$ to points with interval $\epsilon$ ; these points will be possible solutions. There are $d=1+{\displaystyle \frac{C}{\epsilon }}$ points for one ${\lambda }_i$ , so the $j$ -th point is ${\lambda }_i=\epsilon \cdot j$ , for $j\in \{0,\mathrm{\dots },m\}$ . Enumerating all possible solutions $({\lambda }_1,\mathrm{\dots },{\lambda }_m)$ with precision $\epsilon$ , the solution number $q={\sum }_{i=1}^m{j}_i\cdot$ ${(d+1)}^{i-1}$ is $({\lambda }_1^q,\mathrm{\dots },{\lambda }_m^q)=(\epsilon \cdot j_1,\mathrm{\dots },\epsilon \cdot j_m)$ for $j_i\in$ $\{0,\mathrm{\dots },d\}$ and $i\in \{1,\mathrm{\dots },m\}$ . We can obtain $q$ by $(j_1,$ $\mathrm{\dots },j_m)$ and vice versa.

With the function $f:\{0,\mathrm{\dots },{(d+1)}^m-1\}\to ℝ$ as $f(q)=ℒ({\lambda }_1^q,\mathrm{\dots },{\lambda }_m^q)$ , the problem is a maximum search for the function $f$ . The quantum version of the algorithm is presented as Algorithm 1 (QSVM represents Quantum Supporting Vector Machine).

The complexity of the quantum algorithm is presented in Property 1 and can be compared with the complexities given in the subsequent properties.

Property 1.  The expected quantum query complexity of the quantum version of the learning phase for the SVM algorithm is $\text{height}(\text{QSVM})=$ $O\left({\left({\displaystyle \frac{C}{\epsilon }}\right)}^{m/2}{m}^2+m^{2}n\right)$ .

Proof. $O(m^{2}n)$ is required for precomputing all of the inner products. The maximum search algorithm then computes the function $f$ . The complexity of computing $f$ is $O(m^2)$ and the size of the search space is ${\left({\displaystyle \frac{C}{\epsilon }}\right)}^m$ . Hence, the complexity of the maximum search is $O\left({\left({\displaystyle \frac{C}{\epsilon }}\right)}^{m/2}{m}^2\right)$ and the total complexity is $O\left({\left({\displaystyle \frac{C}{\epsilon }}\right)}^{m/2}{m}^2+m^{2}n\right)$ .

For comparison, the classical algorithm has the following complexity.

Property 2. The query complexity of the learning phase for the SVM algorithm is $\text{height}(\text{SVM})=$ $O\left({\left({\displaystyle \frac{C}{\epsilon }}\right)}^m{m}^2+m^{2}n\right)$ .

Note that the different approach to the solution given in Ref. [ 14 ] achieves an exponential speed-up.

The perceptron is a simple Artificial Neural Network (ANN). It can also be considered as a building block for ANNs^{[ 2 ]} and as a modification of the SVM algorithm^{[ 3 ]}. Wiebe et al.^{[ 7 , 8 ]} suggested a quantum algorithm for training a classical perceptron that shows a quadratic speed-up. The algorithm is based on Grover’s search algorithm^{[ 6 ]}.

In the classical model, the function $F$ can be written as follows:

(10) $$F(x)=\text{sign}\left(\underset{i=1}{\overset{n}{\sum }}{x}_i{w}_i+w_0\right)=\text{sign}(x\cdot w+w_0)$$

where $x=(x_1,\mathrm{\dots },x_n)\in {ℝ}^n$ is the input, $w=(w_1,$ $\mathrm{\dots },w_n)\in ℝ{}^n$ and $w_0\in ℝ$ are parameters of the algorithm; $x\cdot w$ is the inner product of the vectors, the hyperplane $x\cdot w+w_0$ separates two classes, and $w$ and $w_0$ should be chosen such that $y^i(w\cdot x^i+w_0)>0$ . There is an assumption that all training vectors are separated by a margin of $\gamma$ in the feature space.

The idea of the classical algorithm is to invoke random sampling of $(w,w_0)$ and check whether the hydroplane classifies the training set correctly. The classical algorithm requires $O(mn)$ to search for the existence of a pair $(x^i,y^i)$ that is misclassified; that is, $y^i(w\cdot x^i+w_0)<0$ . $O\left(\log {\displaystyle \frac{1}{\epsilon {\gamma }^2}}\right)$ samples need to be checked to get the correct one with error probability $\epsilon {\gamma }^2$ for some constant $\epsilon >0$ .

Property 3. The query complexity of sampling algorithm A for perceptron is $\text{height}(\text{A})=$ $O\left(nm\log {\displaystyle \frac{1}{\epsilon {\gamma }^2}}\right)$ , where $\epsilon >0$ is a constant and the training vectors are separated by a margin of $\gamma$ in the feature space.

Quantum algorithm for perceptron training. The quantum algorithm operates with a quantum register $|\psi ⟩$ of $\lceil {\log }_{2}m\rceil$ qubits. As a function for oracle, we use $f_w(i)={ℱ}_w(x^i,y^i)$ , where ${ℱ}_w(x^i,y^i)$ is a Boolean-value function that is $1$ if and only if the vector $x^i$ is misclassified. We use the amplitude amplification version of the Grover’s search algorithm to find misclassified vectors. The query complexity of the procedure is $O(\sqrt{m}n)$ . As in the classical case, we invoke random sampling of $(w,w_0)$ for $K=$ $O\left(\log {\displaystyle \frac{1}{\epsilon {\gamma }^2}}\right)$ times. The algorithm is presented as Algorithm 2.

As was proven in Ref. [ 11 ], if $K={\log }_{3/4}\epsilon$ for some $\epsilon >0$ , then the algorithm returns the result with error probability $\epsilon {\gamma }^2$ . The complexity of the algorithm is presented in the following property.

Property 4. The query complexity of Algorithm 3.2 is $\text{height}(\text{QPerceptron}\mathrm{\_}\text{Trnning})=O\left(n\sqrt{m}\log {\displaystyle \frac{1}{\epsilon {\gamma }^2}}\right)$ , where $\epsilon >0$ is a constant and the training vectors are separated by a margin of $\gamma$ in the feature space.

A utility procedure will be used in the quantum algorithms of this section. The procedure is an algorithm in the quantum branching program model, and it is required to store a superposition of training vectors in a single quantum state of $n$ qubits; that is, it needs to get the following quantum state:

(11) $$|T⟩=\frac{1}{\sqrt{m}}\underset{j=1}{\overset{m}{\sum }}|x^j⟩$$

Trugenberger^{[ 15 ]} introduced an algorithm for generating this state unitarily from a simple initial state of $n$ qubits.

Property 5. If $n$ is an input vector size and $m$ is the number of input vectors in a training set, then there is an algorithm A for constructing the quantum state $|T\rangle$ . The algorithm has the following complexity properties:

• $\text{size}(\text{A})=2n+2;$

• $\text{height}(\text{A})=m;$

• $\text{time}(\text{A})=O(mn)$ .

Let us construct the algorithm A as the proof of the property.

We use three registers. The first is a register $|\phi \rangle$ of $n$ qubits for storing input vectors $x^j$ ; the second register is a utility register $|u\rangle =|u_1\rangle |u_2\rangle$ of two qubits; and the third is a register $|v\rangle$ of $n$ qubits that is holding memory. The full initial state is

(12) $$|{\psi }_0^1\rangle =|\phi \rangle |u\rangle |v\rangle =|0,\text{…},0;01;0,\text{…},0\rangle$$

This state is split into two terms: one corresponding to the already stored input vectors and another ready to process a new input vector from the training set. These two parts are distinguished by the state of the second utility qubit $|u_2\rangle$ . The $|0\rangle$ state is for the stored input vectors, and $|1\rangle$ is readiness for processing.

Before processing the vector $x^j$ , the algorithm reads it and stores it to the $|\phi \rangle$ register. This can be done using the CNOT operator. The controlling bit is an input bit $x_s^j$ and the target bit is the $s$ -th qubit of $|\phi \rangle$ , where $s\in \{1,\mathrm{\dots },n\}$ . If $|\phi \rangle =|0,\text{…},$ $0⟩$ before the procedure, then after the procedure $|\phi \rangle =|x_1^j,\text{…},x_n^j\rangle$ . If $|\phi \rangle =|x_1^j,\text{…},x_n^j\rangle$ before the procedure, then after the procedure $|\phi \rangle =|0,\text{…},0\rangle$ . Therefore, we can use the same procedure for erasing the $|\phi \rangle$ register. That is why we consider an input with the duplication of each vector $x^j$ ; that is, the input is $x^1,x^1,x^2,x^2,\mathrm{\dots },x^m,x^m$ . For the next part of the procedure, we assume that $|\phi \rangle =|x_1^j,\text{…},x_n^j\rangle$ .

For each input vector $x^j$ to be stored, the operations described below are performed:

(13) $$|{\psi }_1^j⟩=\underset{s=1}{\overset{n}{\prod }}2\mathrm{CNOT}(x_s^j,u_2,v_s)|{\psi }_0^j⟩$$

where $x_s^j$ and $u_2$ are the control qubits, and $v_s$ is the target qubit.

This operation simply copies the input vector $x^j$ into the memory register of the processing term, identified by $|u_2\rangle =|1\rangle$ .

The next operation works as follows. If the contents of the input vector and the memory register are identical, then all of the qubits of the memory register are set to $|1\rangle$ (this will be exactly the case only for the processing term):

(14) $$|{\psi }_2^j⟩=\underset{s=1}{\overset{n}{\prod }}\mathrm{NOT}(v_s)\mathrm{CNOT}(x_s^j,v_s)|{\psi }_1^j⟩$$

where in the CNOT operator, $x_s^j$ is the control qubit and $v_s$ is the target qubit.

The next operation changes the first utility qubit $u_1$ of the processing term to a $|1\rangle$ , while keeping it unchanged for the stored input vectors term:

(15) $$|{\psi }_3^j⟩=\mathrm{nCNOT}(v_1,\mathrm{\dots },v_n,u_1)|{\psi }_2^j⟩$$

where $v_1,\mathrm{\dots },v_n$ are control qubits and $u_1$ is the target qubit.

This is followed by the controlled normalization operator:

(16) $$\{\begin{array}{l}C{S}^j=|0\rangle \langle 0|\otimes 1+|1\rangle \langle 1|\otimes S^j;\\ S^j=\left(\begin{array}{cc}\sqrt{\frac{j-1}{j}}& \frac{1}{\sqrt{j}}\\ \frac{-1}{\sqrt{j}}& \sqrt{\frac{j-1}{j}}\end{array}\right)\end{array}$$

for $j=1,\mathrm{\dots },m$

(17) $$|{\psi }_4^j⟩={\mathrm{CS}}^{m+1-j}(u_1,u_2)|{\psi }_3^j⟩$$

This operation separates out the new input vector to be stored with the already correct normalization factor.

The utility qubit $u_1$ is then restored to its original value:

(18) $$|{\psi }_5^j⟩=\mathrm{nCNOT}(v_1,\mathrm{\dots },v_n,u_1)|{\psi }_4^j⟩$$

where $v_1,\mathrm{\dots },v_n$ are control qubits and $u_1$ is the target qubit.

The next operation restores the memory register $v$ to its original state:

(19) $$|{\psi }_6^j⟩=\underset{s=n}{\overset{1}{\prod }}\mathrm{CNOT}(x_s^j,v_s)\mathrm{NOT}(v_s)|{\psi }_5^j⟩$$

where in the CNOT operator, $x_s^j$ is the control qubit and $v_s$ is the target qubit.

When these operations are complete,

(20) $$|{\psi }_6^j⟩=\frac{1}{\sqrt{m}}\underset{k=1}{\overset{j}{\sum }}|x^j;00;x^k⟩+\sqrt{\frac{m-j}{m}}|x^j;01;x^j⟩$$

The third register $v$ of the processing term and the second term in the equation above are then restored to the initial value $|0_1,\mathrm{\dots },0_n⟩$ :

(21) $$|{\psi }_7^j⟩=\underset{s=n}{\overset{1}{\prod }}2\mathrm{CNOT}(x_s^j,u_2,v_s)|{\psi }_6^j⟩$$

where $x_s^j$ and $u_2$ are control qubits, and $v_s$ is the target qubit.

At this point, a new input vector can be loaded into register $|\phi \rangle$ and the sequence of operations reiterated. At the end of the whole process, the $v$ -register is exactly in the state $|T\rangle$ .

The time complexity of the algorithm is $O(mn)$ .

The algorithm is presented as Algorithm 4.1, where $X$ is a training set, $m$ is the length of the training set, and $n$ is the length of each input vector in the training set. The algorithm constructs a superposition of input vectors of the training set $X$ .

In the next two subsections, we describe two quantum $k$ -NN algorithms. The first is from Ref. [ 9 ] and the second is from Ref. [ 10 ]. Both algorithms can be split into two stages: the preliminary stage and the main stage.

The similarity of these two algorithms lies in the preliminary stage that prepares a superposition of the training data using Algorithm 4.1. Their differences are as follows:

•They have different mechanisms for computing the distance between vectors;

•The first algorithm changes the superposition of the training data in the main stage, while the second algorithm does not change it until the measurement.

Since the preliminary stage of both algorithms has the time complexity $O(mn)$ , these two algorithms have the same time complexity as their classic counterparts. If a more efficient way to construct the superposition in $O(n)$ , or to receive the superposition from a quantum memory device, were to be found, the performance of these quantum algorithms would be independent of the number of training vectors. It is impossible to achieve such an effect with the classical algorithm.

Additionally, if a method of training vectors storage uses a smaller number of qubits, without affecting the proportions between the features of the vectors, then it would be possible to reduce the memory size for these algorithms.

The algorithm, presented in Ref. [ 9 ], is a quantum version of the classical weighted nearest neighbor algorithm. The idea of the quantum version of the algorithm is as follows. Firstly, we prepare a superposition of all vectors from the training set as one quantum state, using the procedure from Section 4.1. Second, we compute the Hamming distance between each training vector and the test vector, and store this into the amplitude of each training vector in the superposition. Having done that, if we measure the class qubit, we will get the appropriate class with high probability. If we repeat the algorithm enough times, then we can get the probability distribution, which will carry information about the average closeness of members of each class to the test vector ( " $k\leftarrow \text{all}$ " ).

Only the preliminary stage of the algorithm (the procedure in Section 4.1) reads input variables; the main stage is a quantum circuit that does not read input data.

Property 6. If $n$ is the size of an input vector, $m$ is the number of input vectors in a training set, and $D$ is a number of classes, then the algorithm SSP-kNN for classifying a test vector has the following complexity properties:

$$\bullet \text{size}(\text{SSP-}k\text{NN})=2n+\log D+1;$$ $$\bullet \text{time}(\text{SSP-}k\text{NN preliminary stage})=O(mn);$$ $$\bullet \text{time}(\text{SSP-}k\text{NN main stage})=O(n).$$

The SSP algorithm can be described as follows.

The first step of the algorithm is preparing a superposition of all of the training vectors into one quantum state using the construction of a training set superposition algorithm from Section 4.1.

(22) $$|T\rangle =\frac{1}{\sqrt{m}}{\displaystyle \underset{j=1}{\overset{m}{\sum }}|x_1^j,\text{…},x_n^j,y^j\rangle }$$

The algorithm for constructing the superposition of vectors of the training set has $O(mn)$ time complexity. The test vector is represented as $|x\rangle =|x_1,\text{…},x_n\rangle$ .

The second step is to prepare the following initial state:

(23) $$|{\psi }_0\rangle =\frac{1}{\sqrt{m}}{\displaystyle \underset{j=1}{\overset{m}{\sum }}|x_1,\text{…},x_n;x_1^j,\text{…},x_n^j,y^j;0\rangle }$$

This state is made up of three registers: The first contains the test vector ( $n$ qubits), the second contains the superposition of the training vectors ( $n+\lceil \log D\rceil$ qubits), and the third contains a utility qubit. The part of the second register that stores $y^j$ and contains $\lceil \log D\rceil$ qubits will be called the "class register". Initially, we assign $|0\rangle$ to the last utility qubit.

The third step of the algorithm is to apply the Hadamard gate to the utility qubit:

(24) $$|{\psi }_1\rangle =\frac{1}{\sqrt{m}}{\displaystyle \underset{j=1}{\overset{m}{\sum }}|x_1,\text{…},x_n;x_1^j,\text{…},x_n^j,y^j\rangle }\otimes$$ $$\frac{1}{\sqrt{2}}(|0\rangle +|1\rangle )$$

The fourth step is to prepare a state for obtaining the Hamming distance. We apply the CNOT gate to $|x_1,\mathrm{\dots },x_n;x_1^j,\mathrm{\dots },x_n^j⟩$ with $|x_1,\mathrm{\dots },x_n⟩$ as the control register and $|x_1^j,\mathrm{\dots },x_n^j⟩$ as a target register, and then apply the NOT gate to reverse the states in the second register:

(25) $$|{\psi }_2\rangle ={\displaystyle \underset{s=1}{\overset{n}{\prod }}NOT}(x_s^j)CNOT(x_s,x_s^j)|{\psi }_1\rangle =$$ $${\displaystyle \frac{1}{\sqrt{m}}}{\displaystyle \underset{j=1}{\overset{m}{\sum }}}|x_1,\mathrm{\dots },x_n;d_1^j,\mathrm{\dots },d_n^j,y^j⟩\otimes$$ $$\frac{1}{\sqrt{2}}(|0\rangle +|1\rangle )$$

where

$$d_s^j=\{\begin{array}{cc}1,\text{if}|x_s^j⟩=|x_s⟩;\hfill & \\ 0,\text{otherwise.}\hfill & \end{array}$$

The fifth step is to apply the unitary operator $U$ , where

$$U={\text{e}}^{\text{i}\frac{\text{π}}{2n}\eta },\eta =I\otimes D_{\text{Ham}}^j\otimes I\otimes {\sigma }_z,$$ $$D_{\text{Ham}}^j=\underset{s=1}{\overset{n}{\sum }}\left(\frac{{\sigma }_z+I}{2}\right),$$

in which ${\sigma }_z$ is a Pauli-Z matrix. The operator $\eta$ assigns the number of zeros in the second register as a phase in the case of a $|0\rangle$ value of the utility qubit. In the case of a $|1\rangle$ value of the utility qubit, the operator assigns the same value, but as a negative. Note that the number of zeros is the number of unequal bits for $|x\rangle$ and $|x^j\rangle$ ; that is, the Hamming distance between these vectors. Denoting this as $d_{\text{Ham}}(x,x^j)$ , the state after applying $\eta$ is

(26) $$\left|{\psi }_3\rangle =U\right|{\psi }_2\rangle =\frac{1}{\sqrt{2m}}{\displaystyle \underset{j=1}{\overset{m}{\sum }}}$$ $$({\text{e}}^{\text{i}\frac{\text{π}}{2n}{d}_{\text{Ham}}(x,x^j)}|x_1,\mathrm{\dots },x_n;d_1^j,\mathrm{\dots },d_n^j,y^j;0⟩+\mathit{\hspace{1em}\hspace{0.25em}}$$ $${\text{e}}^{-\text{i}\frac{\text{π}}{2n}{d}_{\text{Ham}}(x,x^j)}|x_1,\mathrm{\dots },x_n;d_1^j,\mathrm{\dots },d_n^j,y^j;1⟩)$$

The sixth step is to apply a Hadamard gate on the utility qubit, and write the phase information of the $j$ -th state into amplitudes:

(27) $$\{\begin{array}{l}{U}_2=I\otimes I\otimes I\otimes H;\hfill \\ |{\psi }_4\rangle =U_2\text{|}{\psi }_3\rangle =\frac{1}{\sqrt{m}}{\displaystyle \underset{j=1}{\overset{m}{\sum }}}\hfill \\ (\cos \frac{\text{π}}{2n}{d}_{\text{Ham}}(x,x^j)|x_1,\text{…},x_n;d_1^j,\text{…},d_n^j,y^j;0\rangle +\hfill \\ \sin \frac{\text{π}}{2n}{d}_{\text{Ham}}(x,x^j)|x_1,\text{…},x_n;d_1^j,\text{…},d_n^j,y^j;1)\hfill \end{array}$$

The seventh step is to measure the utility qubit. If the test vector is close to the training vector, then the probability of a $|0\rangle$ result is high; otherwise, the probability of a $|1\rangle$ result is high. The probability of getting $|0\rangle$ is

(28) $${\mathrm{Pr}}_0=\frac{1}{\sqrt{m}}\underset{j=1}{\overset{m}{\sum }}{\cos }^2\left[\frac{\text{π}}{2n}{d}_{\text{Ham}}(x,x^j)\right]$$

In other words, if there are many training vectors for which the Hamming distance between them and the test vector is small, then ${\mathrm{Pr}}_0$ is high.

If we obtain a $|0\rangle$ result, then the next step is to measure the "class register". We have a higher probability of getting a class $c\in \{0,1,\mathrm{\dots },D-1\}$ for classes that have training vectors with smaller Hamming distances from the test vector. After obtaining a $|0\rangle$ result from the utility qubit measurement, we have the following state:

(29) $$\begin{array}{l}|{\psi }_5\rangle =\frac{1}{\sqrt{m\cdot P{r}_0}}{\displaystyle \underset{y=0}{\overset{D-1}{\sum }}|y\rangle \otimes {\displaystyle \underset{l:y^l=y}{\sum }}}\\ \cos \frac{\text{π}}{2n}{d}_{\text{Ham}}(x,x^l)|x_1,\dots ,x_n;d_1^l,\dots ,d_n^l,y^l;0\rangle \end{array}$$

The probability of obtaining $c$ -result from the "class register" measurement is

(30) $$\mathrm{Pr}(c)=\frac{1}{m\cdot {\mathrm{Pr}}_0}\underset{l:y^l=c}{\sum }{\cos }^2\left[\frac{\text{π}}{2n}{d}_{\text{Ham}}(x,x^l)\right]$$

The class $c$ has a higher probability where more training vectors of this class have a small Hamming distance from the test vector.

Since for small angles $\theta$ $\left(\theta <{\displaystyle \frac{\text{π}}{12}}\right)$ , $\sin \theta \approx \theta$ , and $\cos \theta \approx 1-{\theta }^2$ , the following statement is true.

(1) If for $b$ vectors among $m$ vectors of the training set

$$d_{\text{Ham}}<\frac{n}{6},$$

then the following double inequality for the probability ${\mathrm{Pr}}_0$ is true:

$$\frac{b}{m}\left[1-{\left(\frac{\text{π}}{12}\right)}^2\right]<{\mathrm{Pr}}_0⩽1.$$

(2) If $b_c$ vectors among above $b$ vectors belong to $c$ class, then the following double inequality for probability $\mathrm{Pr}(c)$ , conditioned on the probability ${\mathrm{Pr}}_0$ , is true:

$$\frac{b_c}{b}<\mathrm{Pr}(c)⩽1.$$

For computing the time complexity of the algorithm, there are $n$ NOT gates and $n$ CNOT gates in the fourth step, while the fifth step requires $2n$ gates for the unitary operator $U$ implementation due to Ref. [ 16 ], and there are two Hadamard gates in Steps 3 and 6. The total time complexity of the main stage of the algorithm is therefore $4n+2$ .

The algorithm is presented as Algorithm 4.2 and is labelled as $\text{SSP}\text{-}k\text{NN}(X,m,n,x)$ , where $X$ is a training set, $m$ is the length of the training set, $n$ is the length of each vector in the training set, and $x$ is the test vector. If we obtain a $1$ -result from the utility qubit measurement, then we are unable to obtain a class, and the algorithm returns $-1$ to represent "unknown" .

This algorithm is run enough times as necessary to obtain a precise picture from the measurement results.

In this section, we present a classification method that is developed for non-binary classification problems. Wiebe et al.^{[ 11 ]} suggested a quantum version of the NN algorithm with a quadratic speed-up. This quantum algorithm uses the minimum search algorithm^{[ 5 ]} and subroutines for computing distances between vectors^{[ 11 ]}.

In the classical algorithm, the function $F$ can be written as the $k$ -NN algorithm for $k=1$ :

(38) $$F(x)=y_j\text{, for}j={\arg \min }_{i\in \{1,\mathrm{\dots },m\}}||x^i-x||$$

The classical algorithm is a linear search among vectors $x_1,\mathrm{\dots },x_m$ for the minimum of $||x^i-x||$ . The procedure for computing the distance between two vectors has complexity $O(n)$ , so the algorithm has the following complexity.

Property 8. The classical query complexity of the $k$ -NN algorithm is $\text{height(1NN)}=O(nm)$ .

Quantum version of the nearest neighbor algorithm. First, the maximum search algorithm^{[ 5 ]} is used; second, distance computing algorithms are used for computing the distance between vectors $x^i$ and $x$ . Both of these methods were described in the first part of the paper.

The assumptions are follows:

(1) The input vectors $x^1,\mathrm{\dots },x^m$ and $x$ are $d$ -sparse for some $1⩽d⩽n$ . In other words, each vector $x^i$ has only $d$ non-zero elements.

(2) Quantum oracles are provided in the form

$$𝒪|i⟩|j⟩|0⟩\to |i⟩|j⟩|x_j^i⟩,$$ $$ℱ|i⟩|l⟩\to |i⟩|\text{pos}(i,l)⟩,$$

where $\text{pos}(i,l)$ is the position of the $l$ -th non-zero element of $x^i$ .

(3) There is an $r_{\max }$ such that $0⩽x_j^i⩽r_{\max }$ for any $i\in \{1,\mathrm{\dots },m\},j\in \{1,\mathrm{\dots },n\}$ .

(4) Each vector is normalized to 1, for convenience.

It is known that for any two vectors $a$ and $b$ , the following equality holds:

(39) $${\Vert a-b\Vert }^2={\Vert a\Vert }^2+{\Vert b\Vert }^2-2(a\cdot b)$$

where $a\cdot b$ is the inner product of $a$ and $b$ . Therefore, the following property holds:

(40) $$\begin{array}{c}F(x)=y_j\text{, for}j={\arg \min }_{i\in \{1,\mathrm{\dots },m\}}||x^i-x||=\hfill \\ \hfill {\arg \max }_{i\in \{1,\mathrm{\dots },m\}}{(x^i\cdot x)}^2\end{array}$$

The quantum algorithm is presented as Algorithm 6.

The algorithm has the complexity given in the following property.

Property 9. The quantum query complexity of the quantum version of the nearest neighbor algorithm is $O(\sqrt{m}\log m\cdot d^2{r}_{\max }^4)$ .

Comments. As already discussed, the algorithm works for $d$ -sparse vectors, where $1⩽d⩽n$ . This means that in the general case, we realize the speed-up if $\sqrt{m}>n$ . This setup is reasonable for a range of problems, as problems with $d$ -sparse vectors in training and testing sets are not unusual.

Another restriction of the algorithm is $r_{\max }$ . Typically, a prepossessing procedure can be performed that normalizes data and changes $r_{\max }$ . The complexity of this procedure is $O(mn)$ , but it will be performed only once, so we do not take account of the complexity of the peprocessing procedure in the case of a large test set.

This paper surveys quantum algorithms for binary classification and discusses the quantum nearest neighbor algorithms. It further analyzes the quantum nearest neighbor algorithms and reveals their quadratic speed-up over classical algorithms.