Nearest Centroid Classification on a Trapped Ion Quantum Computer

We start by a procedure that given access to a classical data point $x=(x_{1},x_{2},\ldots,x_{d})\in\mathbb{R}^{d}$, pre-processes the classical data efficiently, i.e. spending only $\widetilde{O}(d)$ total time, in order to create a set of parameters $\theta=(\theta_{1},\theta_{2},\ldots,\theta_{d-1})\in\mathbb{R}^{d-1}$, that will be the parameters of the $(d-1)$ two-qubit gates we will use in our quantum circuit. In the pre-processing, we also keep track of the norms of the vectors.

It is important here to notice that the classical memory is accessed once (we use read-once access to $x$) and the parameters $\theta$ are “stored inside the quantum circuit” (as the parameters of the quantum gates), which means that if we need to perform many operations with the specific data point (which is the case here and, for example, in training neural networks), we do not need to access the classical memory again, we just need to re-run the quantum circuit that already has the parameters in place.

Let us now describe how to find and store these parameters $\theta$. The data structure for storing $\theta$ is in fact the one used in kerenidis2016quantum , but note that there we assumed that we have quantum access to these parameters (in the sense of being able to query these parameters in superposition) while here we will compute and store these parameters classically and also encode them as the parameters of the gates used in the quantum circuit.

At a high level, we think of the coordinates $x_{i}$ as the leaves of a binary tree of depth $\log d$. The parameters $\theta$ correspond to the values of the internal tree nodes, starting form the root and going towards the leaves.

We first consider the parameter series $(r_{1},r_{2},\ldots,r_{d-1})$. For the last $d/2$ values $(r_{d/2},\ldots,r_{d-1})$, we define an index $j$ that takes values in the interval $[1,d/2]$ and define the values as

For the first $d/2-1$ values, namely the values of $(r_{1},r_{2},\ldots,r_{d/2-1})$, and for $j$ in $[1,d/2]$, we define

We can now define the set of angles $\theta=(\theta_{1},\theta_{2},\ldots,\theta_{d-1})$ in the following way. We start by defining the last $d/2$ values $(\theta_{d/2},\ldots,\theta_{d-1})$. To do so, we define an index $j$ that takes values in the interval $[1,d/2]$ and define the values as

For the first $d/2-1$ values, namely the values for $j\in[1,d/2]$, we define

Note that we can easily perform these calculations in a read-once way, where for every $x_{i}$ we update the values that are on the path from the $i$-th leaf to the root. This also implies that when one coordinate of the data is updated, then the time to update the $\theta$ parameters is only logarithmic, since only $\log d$ values of $r$ and of $\theta$ need to be updated.

Now that we have found the parameters that we need for our parametrized quantum circuit, we can define the architecture of our quantum circuit. It will use $d$ qubits, $d-1$ two-qubit gates, $\log d$ depth, and will resemble a binary tree architecture. For convenience, we assume that $d$ is a power of 2.

We will use a gate that has appeared with small variants with different names as partial SWAP, or fSIM, or Reconfigurable BeamSplitter, etc. We call this two-qubit parametrized gate $RBS(\theta)$ and we define it as

One can define the above gate with imaginary off-diagonal elements and in fact we will use that definition when we implement this on the hardware but we keep this definition here for ease of exposition. We can think of this gate as a simple rotation by an angle $\theta$ on the two-dimensional subspace spanned by the vectors $\{\mathinner{|{10}\rangle},\mathinner{|{01}\rangle}\}$ and an identity in the other subspace spanned by $\{\mathinner{|{00}\rangle},\mathinner{|{11}\rangle}\}$. A different way would be to think of a single photon entering one of the two input modes of a reconfigurable beam-splitter and getting split into the two output spatial modes with a ratio depending on the parameter $\theta$. We denote by $RBS^{\dagger}(\theta)$ the adjoint gate for which we have $RBS^{\dagger}(\theta)=RBS(-\theta)$.

We can now describe the circuit itself. We start by putting the first qubit in state $\mathinner{|{1}\rangle}$, while the remaining $d-1$ qubits remain in state $\mathinner{|{0}\rangle}$. Then, we use the first parameter $\theta_{1}$ in an $RBS$ gate in order to “split” this ‘1’ between the first and the $d/2$-th qubit. Then, we use the next two parameters $\theta_{2},\theta_{3}$ for the next layer of two $RBS$ gates, where again in superposition we “split” the ‘1’ into the four qubits with indices $(1,d/4,d/2,3d/4)$ and this continues for exactly $\log d$ layers until at the end of the circuit we have created exactly the state

where the states $\mathinner{|{e_{i}}\rangle}$ are a unary representations of the numbers $1$ to $d$, using $d$ qubits. The circuit appears in Fig. 1.

An interesting extension of our loader is that we can trade off qubits with depth and keep the number of overall gates $d-1$ (in this case, both $RBS$ and controlled-$RBS$ gates). For example, we can use $2\sqrt{d}$ qubits and $O(\sqrt{d}\log d)$ depth Ker2020 . The circuit is quite simple, if one thinks of the $d$ dimensional vector as a $\sqrt{d}\times\sqrt{d}$ matrix. Then, we can index the coordinates of the vector using two registers (one each for the row and column) and create the state

For this circuit, we find, in the same way as for the parallel loader, the values $\theta$ and then create the following circuit in Figure 2. We start with a parallel loader for a $\sqrt{d}$-dimensional vector using the first $\sqrt{d}$ angles $\theta$ (which corresponds to a vector of the norms of the rows of the matrix) and then, controlled on each of the $\sqrt{d}$ qubits we perform a controlled parallel loader corresponding to each row of the matrix.

Notice that naively the depth of the circuit is $O(d\log d)$, but it is easy to see that one can interleave the gates of the controlled-parallel loaders to an overall depth of $O(\sqrt{d}\log d)$. We will not use this circuit here but such circuits can be useful both for loading vectors and in particular matrices for linear algebraic computations.

Let us make some remarks about the data loader circuits. First, we will see in the following sections that the circuits are quite robust to noise and amenable to efficient error mitigation techniques. Second, we use a single type of two-qubit gate that is native or quasi-native to different hardware platforms. Third, we note that the connectivity of the circuit is quite local, where most of the qubits interact with very few qubits (for example $7/8$ of the qubits need at most 4 neighboring connections) while the maximum number of interacting neighbors for any qubit is $\log d$. Here, we take advantage of the full connectivity of the ionQ hardware platform, so we can apply all gates directly. On a grid architecture one would need to embed the circuit on the grid which asymptotically requires no more than doubling the number of qubits.

Given two vectors ${x}$ and ${y}$ corresponding to classical data points, the Euclidean distance, namely $l_{xy}=\left\lVert{x}-{y}\right\rVert$ Ker2020 is given by

where $c_{xy}=\langle x|y\rangle$ is the inner product of the two normalised vectors. Here we describe a circuit to estimate $c_{xy}$ which is combined with the classically calculated vector norms to obtain $l_{xy}$.

The power of the data loaders comes from the operations that one can do once the data is loaded into such “amplitude encoding” quantum states. In this work, we show how to use the data loader circuits to perform a fundamental operation at the core of supervised and unsupervised similarity-based learning, which is the estimation of the distance between data points.

In fact, here we will only discuss one of the variants of the distance estimation circuits which works for the case where the inner product between the data points is positive, which is usually the case for image classification where the data points have all non negative coordinates. It is not hard to extend the circuit with one extra qubit to deal with the case of also non-positive inner products.

The distance estimation circuit for two data points of dimension $d$ uses $d$ qubits, $2(d-1)$ two-qubit parametrized gates, $2\log d$ depth, and will allow us to measure at the end of the circuit a qubit whose probability of giving the outcome $\mathinner{|{1}\rangle}$ is exactly the square of the inner product between the two normalized data points. From this, one can easily estimate the inner product and the distance between the original data points. When the hardware allows deeper quantum operations, then an amplitude estimation procedure can be used to decrease the number of samples one needs to perform this estimation. For our experiments, we directly repeatedly measured the output state between 500-1000 times in order to get an estimate of the inner product.

The distance estimation circuit is shown in Fig. 3, and it consists of two parts, the first is the data loader circuit for the first data point, and the second part is the adjoint data loader circuit for the second data point (without the $X$ gate), where we recall that for the adjoint $RBS^{\dagger}(\theta)=RBS(-\theta)$. We can easily see that the probability the first qubit is measured in state $\mathinner{|{1}\rangle}$ is exactly the square of the inner product of the two data points.

After the first part, the state of the circuit is $\mathinner{|{x}\rangle}$, as in Eq. 2. One can rewrite this state in the basis $\{\mathinner{|{y}\rangle},\mathinner{|{y^{\bot}}\rangle}\}$ as

Once the state goes through the inverse loader circuit for $y$ the first part of the superposition gets transformed into the state $\mathinner{|{e_{1}}\rangle}$ (which would go to the state $\mathinner{|{0}\rangle}$ after an $X$ gate on the first qubit), and the second part of the superposition goes to a superposition of states $\mathinner{|{e_{j}}\rangle}$ orthogonal to $\mathinner{|{e_{1}}\rangle}$

It is easy to see that after measuring the circuit (either all qubits or just the first qubit), the probability of getting $\mathinner{|{1}\rangle}$ in the first qubit is exactly the square of the inner product of the two data points.

We can also notice a simplification we can make in the circuit that will reduce the number of gates and depth. In the middle of the circuit, there are pairs of $RBS$ gates that are applied to the same consecutive qubits. Each such pair of two gates can be combined to one gate whose parameter $\theta$ is just equal to $\theta_{1}+\theta_{2}$, where $\theta_{1}$ is the parameter of the first gate and $\theta_{2}$ is the parameter of the second gate.

This reduces the number of gates of the circuit to $3d/2-2$ and reduces the depth by one. The final circuit used in our application is in Fig. 4.

For the synthetic data, we create datasets with $k$ clusters (for $k$ equal to 2 and 4) of $d$-dimensional data points (for $d$ equal to 4 and 8). This begins with generating $k$ random points that serve as the “centroids” of a cluster, followed by generating $n=10$ data points per centroid by adding Gaussian noise to the “centroid” point. The distance between the centroids was set to be a minimum of 0.3, the variance of the Gaussians was set to be 0.05 and the points were distributed within a sphere of radius 1. Therefore, there is appreciable probability of the points generated from one centroid lying closer to the centroid of another cluster. This can be seen as mimicking noise in real life data.

In Tables 1 and 2 we present, as an example, the data points and the labels assigned to them by the classical and quantum Nearest Centroid for the case of four classes in the 4- and 8-dimensional case. The first line shows how the points were sampled, namely the first quarter of points were sampled starting from the centroid labelled 0, the second quarter were sampled from the centroid labelled 1, etc. The second row shows the labels assigned by the classical Nearest Centroid algorithm. These are the labels that we will benchmark against. The third and fourth line presents the results of the quantum Nearest Centroid algorithm without and with error mitigation. We see in these examples, and in fact this is the behaviour overall, that our quantum Nearest Centroid algorithm with error mitigation provides the correct labels for 39 out of 40 4-dimensional points and for 36 out of the 40 8-dimensional points, or an accuracy of $97.5\%$ and $90\%$ respectively. The quantum classification is affected by the noise in the operations and can shift the assignment non-trivially based on the accuracy in the measured distance, as can be seen in cluster 1 in Table 2. This will be discussed in more detail in Section E.

For the synthetic data, our goal was to see whether the quantum Nearest Centroid algorithm can assign the same labels as the classical one, even though the points are quite close to each other. Thus our classical benchmark for the synthetic data is $0\%$ classification error. The baseline which corresponds to the accuracy of just randomly guessing the labels is $1/k$ for $k$ classes.

In Fig. 8 (b), we first show the error of the quantum Nearest Centroid algorithm averaged over a data set of 20 or 40 data points. Here, $N_{c}$ is the number of classes, $N_{s}$ is the number of shots and $N_{q}=d$ is the dimension and number of qubits used in the experiment. For each case, there are two values (left-blue, right-red) that correspond to the results without and with error mitigation. For 2 classes, we see that for the case of 4-dimensional data, we achieve $100\%$ percent accuracy even with as little as 100 shots per circuit and even without error-mitigation. For the case of 8-dimensional data, we also achieve $100\%$ accuracy with error mitigation and 1000 shots. We also performed experiments with 4 classes, and the accuracies were $97.5\%$ for the 4-dimensional case and $90\%$ for the 8-dimensional case with error-mitigation. The number of shots used is more for the higher dimensional case as suggested by the analysis in Section E.

While trying to estimate meaningful error bars for classification accuracy would require an impractical number of experiments (each experiment consists of running up to 160 different circuits a 1000 times each), Fig. 8 (a) shows the average ratio between the distance estimation from experiment and simulation along with its error bars. We see that the experimentally estimated distance may actually be off by a significant factor from the theoretical distance. However, since the error bars in the distance estimation are quite small, and what matters for classification is that the ratio of the distances remains accurate, it is reasonable that we have high classification accuracy. In section E, we will show a way to reduce the error in the distance itself based on knowledge of the noise model of the quantum system.

The IRIS data set consists of three classes of flowers (Iris setosa, Iris virginica and Iris versicolor) and 50 samples from each of three classes. Each data point has four dimensions that correspond to the length and the width of the sepals and petals, in centimeters. This data set has been used extensively for benchmarking classification techniques in machine learning, in particular because classifying the set is non trivial. In fact, the data points can be clustered easily in two clusters, one of the clusters contains Iris setosa, while the other cluster contains both Iris virginica and Iris versicolor. Thus classification techniques like Nearest Centroid do not work exceptionally well without preprocessing (for example linear discriminant analysis) and hence it is a good data set to benchmark our quantum Nearest Centroid algorithm as it is not tailor-made for the method to work well.

Fig. 9 shows the classification error for the IRIS data set of 150 4-dimensional data points. The classical Nearest Centroid classifies around $92.7\%$ of the points while our experiments with 500 shots and error mitigation reaches $84\%$ accuracy. Increasing the number of shots beyond 500 does not increase the accuracy because at this point the experiment is dominated by systematic noise which changes each time the system is calibrated. In the particular run, going from 500 to 1000 shots, the number of wrong classifications slightly increases, which just reflects the variability in the calibration of the system. We also provide the ratio of the experimental vs simulated distance estimation for these experiments.

Fig. 10 compares the classification visually before and after error mitigation. Before error mitigation, many of the points that lie close to midway between centroids are mis-classified, whereas applying the mitigation moves them to the right class.

The MNIST database contains 60,000 training images and 10,000 test images of handwritten digits and it is widely used as a benchmark for classification. Each image is a $28\times 28$ image i.e. a 784-dimensional point. To work with this data set we preprocessed the images with PCA to project them into 8 dimensions. This reduces the accuracy of the algorithms, both the classical and the quantum, but it allows us to objectively benchmark the quantum algorithms and hardware on different types of data.

For our experiments with the 8-dimensional MNIST database, we created four different data sets. The first one has 40 samples of 0 and 1 digits only. The second one has 40 samples of the 2 and 7 digits. The third one has 80 samples of four different digits 0-3. The fourth one has 200 samples of all possible digits 0-9.

In Figure 11 we see that for the first data set the quantum algorithm with error mitigation gets accuracy $100\%$, matching well the classical accuracy of $97.5\%$. For the case of 2 vs. 7, we achieve accuracy of around $87.5\%$ similar to the classical algorithm. For the 4-class classification, we also get similar accuracy to the classical algorithm of around $83.75\%$. Most impressively, for the last data set with all 10 different digits, we practically match the classical accuracy of around $77.5\%$ with error mitigation and 1000 shots. We also provide the ratio of the experimental vs simulated distance estimation for these experiments which shows high accuracy for the distance estimation as well.

Note that this is the first time classification with 10 classes has been performed on a quantum computer with remarkably encouraging accuracy. A quantum computer of eight qubits was able to recognise eight out of ten handwritten digits on average, same as the classical algorithm, and with a time scaling which with the advent of more qubits and faster quantum clocks may become competitive with classical computers.

In Figure 12 we provide the confusion graph for the classical and quantum nearest centroid algorithm, showing how our quantum algorithm matches the accuracy of the classical one.