## 2 The Learning Algorithm
### DBSCAN Algorithm for Determining the Support Vector  
The training algorithm is designed by applying the DBSCAN clustering algorithm to a Deutsch-Jozsa decision problem on the training data. The idea is depicted in Figure 2. Let us consider the hypersphere \(B_{\epsilon}(\vec{x}_{i})\) of radius \(\epsilon\) centered in the data point \(\vec{x}_{i}\). Near the classification boundary, it is more likely that the data in the sphere have two different classification labels. On the other hand, for the data in the interior of each cluster, it is more likely that all the data points in the sphere have the same label. Hence, the classification boundary can be identified by a DBSCAN scanning through all the data points. For each data point, we query a decision problem, namely, whether the data inside the sphere is constant or not. If the number of non-constant spheres around is large for a given data point, we then select this point as a support vector for the prediction algorithm. This decision problem takes the form of a Deutsch-Jozsa problem and the potential use of the quantum DJ algorithm to enhance the training is discussed in Section 2.4.  
After selecting the support vectors from the training data, we compute a kernel matrix \((J_{sv})_{i,j}=J(\vec{x}_{i},\vec{x}_{j})\) for \(\vec{x}_{i},\vec{x}_{j}\in\{\text{support vectors}\}\). This kernel matrix will be used in the prediction algorithm. The matrix elements are, in general, some functions of data positions. We choose \(J\) to be the inverse of some power-law function of distances between data points:  
\[J(\vec{x}_{i},\vec{x}_{j})=\frac{1}{||\vec{x}_{i}-\vec{x}_{j}||^{\beta}}. \tag{4}\]  
The training algorithm can be described as the pseudo-code Algorithm 1.  
Figure 1: Outline of the proposed algorithm. The training data set is fed into the support vector selection algorithm. The support vectors are then used in the Ising predictor for prediction. The support vector selection algorithm is described in Algorithm 1 and the Ising predictor is described in Section 2.5.  
```
Input: Training dataset \(\{(\vec{x}_{i},y_{i})|i=1,\ldots,l\}\), \(\epsilon\), \(\alpha\), \(\beta\) Output: Support vectors \(\{(\vec{x}_{i},y_{i})|i=1,\ldots,n_{sv}\}\), \((I_{sv})_{i,j}\)
1 Allocate an integer array \(c[i]\), \(i\in\{1,\ldots,l\}\) where \(l\) is the number of training data
2 for each data point \(\vec{x}_{i}\) in the training dataset : do
3 Making a query:
4 Examine the class label \(y_{j}\) of all the training data points \(\vec{x}_{j}\in B_{\epsilon}(\vec{x}_{i})\)
5 Determine whether the training data in the sphere including the central data point are all the same class (constant) or mixed with other classes (mixed)
6 ifmixedthen
7\(c[j]\gets c[j]+1\) for all \(\vec{x}_{j}\in B_{\epsilon}(\vec{x}_{i})\)
8 end if
9
10 end for
11 Rank \(c[i]\)
12 The top \(1/\alpha\) data points in the ranking are the support vectors
13 Compute matrix \((J_{sv})_{i,j}\) for \(\vec{x}_{i}\), \(\vec{x}_{j}\in\{\text{support vectors}\}\) according to Equation (4)
```  
Figure 2: The training process. The red dots and blue dots are training data with two different classification labels. (**a**) For each data point \(\vec{x}_{i}\), we consider the hypersphere \(B_{\epsilon}(\vec{x}_{i})\) of radius \(\epsilon\) centered in the data point \(\vec{x}_{i}\). We ask the question of whether all the data points in the sphere have the same label or not. (**b**) If the data within the sphere are mixed (not constant), then all the data within the sphere receive one count by \(c[j]=c[j]+1\). (**c**) After scanning through all the data, we rank the data according to \(c[i]\). (**d**) The data points with the highest \(c[i]\) are selected as support vectors. The blue and yellow dots are support vectors for two different classes.