## 1 Introduction  
Quantum machine learning [1; 2; 3] is an emerging field using quantum information processing for machine learning applications. Various quantum machine learning algorithms have been proposed, such as quantum Boltzmann machines [4], supervised quantum autoencoders [5], reinforcement learning using quantum Boltzmann machines [6], quantum circuit learning [7; 8] and some quantum methods for linear algebra [9; 10; 11]. Even though the exponentially large Hilbert space is expected to help tackling the \"curse of dimensionality\" in machine learning, loading large classical data sets into a small quantum memory is a bottleneck [12; 13]. Even though this problem can be circumvented in some settings [14], the available quantum information processors are restricted by the small number of qubits and high operational noise in the current noisy intermediate-scale quantum [15] era. On the other hand, these quantum algorithms have inspired various new classical efficient methods [16; 17; 18; 19]. The dequantizing of quantum algorithms is not only for practical concerns, but also for theoretical interests in complexity theory [20].  
The support-vector machine (SVM) is a widely used classification algorithm [21; 22; 23; 24]. There are also newly developed variants of the SVM [25; 26] and several quantum versions of the SVM have been proposed [27; 28; 29]. One proposal is to use the HHL algorithm [9] to invert the kernel matrix [27]. [PERSON] et al. [28] proposed a QSVM algorithm in which the distance for the kernel classifier is evaluated by single qubit gate circuits. Recently, [PERSON] et al. [29] implemented the quantum circuit learning classification and a quantum kernel estimator for the SVM. However, due to the requirements of quantum coherence, the applications of these algorithms to large-scale data sets has not been demonstrated yet.  
In this work, we propose a new quantum-inspired algorithm for classification tasks. The support vectors are selected from the data by a principle inspired by the classical clustering algorithm density-based spatial clustering of applications with noise (DBSCAN) [30] and the quantum algorithm Deutsch-Jozsa (DJ) [31]. DBSCAN is a commonly used classical clustering algorithm that determines clusters by considering numbers of data points within some distance parameter \(\epsilon\). DBSCAN is efficient, noise-resilient and does not require the input of the number of clusters. DJ is a deterministic quantum algorithm that determines a specific property of a given Boolean function \(f:\{0,1\}^{n}\rightarrow\{0,1\}\) with a single oracle call to the function \(f\). The classical deterministic algorithm to solve the DJ problem requires \(O(2^{n})\) calls. We combine DBSCAN and DJ to identify support vectors that are close to the classification boundary. The support vectors are then used for prediction based on an Ising model classifier. The prediction labels are identified as spins in an Ising model and the prediction label is aligned with nearby support vectors through spin-spin interactions. The training time complexity of the proposed algorithm scales according to \(O(l^{2}d)\), where \(l\) is the number of training data and \(d\) is the feature dimension. This is favorable comparing to \(O(l^{3}d)\) standard kernel support-vector machines, such as LIBSVM, used in scikit-learn [21; 22; 23; 24]. The proposed algorithm can be executed on classical computers, while quantum devices could be used to accelerate several subroutines in the algorithm. The numerical verification is presented. We also provide theoretical evidences for the learnability of the algorithm. We show that the training algorithm is described by an integer linear programming problem. We also derive upper bounds for the VC dimension of the Ising classifier in two special lattices.