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

Abstract

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.

Keywords: prototype-based learning; quantum machine learning; vector quantization.

Figure 1

Circuit of the threshold oracle. The red dottet lines seperate forward pass and uncomputation from the phase shift.

Figure 2

Absolute Difference Operator.

Figure 3

Circuit that implements the Best Selection Oracle for two prototypes per class and a data width of four. The vertical lines seperate the steps: data loading, distance calculation, distance comparison and uncomputation.