DOI: 10.1002/qute.202300221 ISSN: 2511-9044

Quantum K‐Nearest Neighbor Classification Algorithm via a Divide‐and‐Conquer Strategy

Li‐Hua Gong, Wei Ding, Zi Li, Yuan‐Zhi Wang, Nan‐Run Zhou
  • Electrical and Electronic Engineering
  • Computational Theory and Mathematics
  • Condensed Matter Physics
  • Mathematical Physics
  • Nuclear and High Energy Physics
  • Electronic, Optical and Magnetic Materials
  • Statistical and Nonlinear Physics


The K‐nearest neighbor algorithm is one of the most frequently applied supervised machine learning algorithms. Similarity computing is considered to be the most crucial and time‐consuming step among the classical K‐nearest neighbor algorithm. A quantum K‐nearest neighbor algorithm is proposed based on the divide‐and‐conquer strategy. A quantum circuit is designed to calculate the fidelity between the test sample and each feature vector of the training dataset. The quantum K‐nearest neighbor algorithm has higher classification efficiency in high‐dimensional data processing. The classification accuracy of the proposed algorithm is equivalent to that of the classical K‐nearest neighbor algorithm under the IRIS dataset. In addition, compared with the typical quantum K‐nearest neighbor algorithms, the proposed classification method possesses higher classification accuracy with less calculation time, which has wide applications in the industrial field.

More from our Archive