Prototype-Based Classifiers and Vector Quantization on a Quantum Computer—Implementing Integer Arithmetic Oracles for Nearest Prototype Search

The superposition principle in quantum mechanics enables the encoding of an entire solution space within a single quantum state. By employing quantum routines such as amplitude amplification or the Quantum Approximate Optimization Algorithm (QAOA), this solution space can be explored in a computationally efficient manner to identify optimal or near-optimal solutions. In this article, we propose quantum circuits that operate on binary data representations to address a central task in prototype-based classification and representation learning, namely the so-called winner determination, which realizes the nearest prototype principle. We investigate quantum search algorithms to identify the closest prototype during prediction, as well as quantum optimization schemes for prototype selection in the training phase. For these algorithms, we design oracles based on arithmetic circuits that leverage quantum parallelism to apply mathematical operations simultaneously to multiple inputs. Furthermore, we introduce an oracle for prototype selection, integrated into a learning routine, which obviates the need for formulating the task as a binary optimization problem and thereby reduces the number of required auxiliary variables. All proposed oracles are implemented using the Python 3-based quantum machine learning framework PennyLane and empirically validated on synthetic benchmark datasets.