Code example: Quantum classification

This example will only work on the emulator backend

What does it do?

Classification is the act of assigning labels to data, often with respect to other data. For instance, we can classify between animals having 22 or 44 legs or a different number. Often we classify new data based on already classified (learned) data. We classify this new data point by representing all data points by features or characteristics and compute the distance between the features of the new data point and the features of the learned data points. The new data point is assigned the label to which it has the shortest distance.

This is a typical example of kk-nearest neighbor classification, which classically has a complexity of O(NM)\mathcal{O}(NM), with NN the number of data points and MM the number of features. A quantum version of this classifier was proposed by Schuld et al. , see ref.1, and has a constant complexity O(1)\mathcal{O}(1).

What is it used for?

Classification has wide-spread use in everyday life and we often classify objects without fully realizing we do it. Classically, naively we would have to compute the distance between the new data point and all other data points separately, after which we combine the results. This approach can be approved upon, but we are still left with a complexity of O(NM)\mathcal{O}(NM).

With a quantum-based approach, we do the same computations, but now only requiring one single-qubit operation and two measurements. Hence, the quantum-based approach is in theory better than the classical one. A caveat is however that the result is probabilistic, hence, multiple measurement rounds must be needed. Furthermore, a specific quantum state is assumed to begin with. Without something like a quantum RAM or a quantum process that produces the input state efficiently, we are left with the same complexity as the classical approach.

How does it work?

Let our data points be given by (xi,yi)i=0N1{(x_i, y_i)}_{i=0}^{N-1}, with xix_i the data point and yiy_i the corresponding label and let (x,y)(x^, y^) be the unlabeled new data point. Furthermore, there are only two labels yi=±1y_i=\pm 1. The new label is then given by evaluating

y=sgn(i=0N1yi[114Nxxi2])y^* = {\rm sgn}\left(\sum_{i=0}^{N-1} y_i \left[1-\frac{1}{4N}{\vert{x^*}-x_i\vert}^2\right]\right)

If both classes have the same number of data points, we can simplify the above function to

y=sgn(i=0N1yix+xi2)y^* = {\rm sgn}\left(\sum_{i=0}^{N-1} y_i {\vert{x^*} + x_i\vert}^2\right)

We can create a quantum state that will produce precisely this probability distribution, if we start with

12Ni=0N1i(0x+1xi)yi\frac{1}{\sqrt{2N}} \sum_{i=0}^{N-1} \vert i \rangle ( \vert 0 \rangle \vert x^* \rangle + \vert 1 \rangle \vert x_i \rangle) \vert y_i \rangle

Here x=m=0M1xmm\vert x \rangle = \sum_{m=0}^{M-1}x^m\vert m \rangle encodes the data points and yi=syi=2s1y_i = s \leftrightarrow \vert y_i \rangle = \vert 2s-1 \rangle. Furthermore, i\vert i \rangle is the ii-th computational basis state to keep track of the ii-th training point and the second register is an ancilla qubit.

Given this initial state, the quantum algorithm consists of only three operations. First, we apply a Hadamard on the second register. This gives

12Ni=0N1i(0(x+xi)+1(xxi))yi\frac{1}{2\sqrt{N}} \sum_{i=0}^{N-1} \vert i \rangle (\vert 0 \rangle (\vert x^* \rangle + \vert x_i \rangle) + \vert 1 \rangle (\vert x^* \rangle - \vert x_i \rangle))\vert y_i \rangle

We then measure the second register and only conditionally continue if we measured the 00-state. This gives

12Np0i=0N1i0(x+xi)yi=12Np0i=0N1m=0M1i0(xm+xi,mm)yi\frac{1}{2\sqrt{Np_{0}}} \sum_{i=0}^{N-1} \vert i \rangle \vert 0 \rangle(\vert x^* \rangle + \vert x_i \rangle) \vert y_i \rangle = \frac{1}{2\sqrt{Np_{0}}} \sum_{i=0}^{N-1} \sum_{m=0}^{M-1}\vert i \rangle\vert 0 \rangle(x^*m + x{i,m}\vert m \rangle)\vert y_i \rangle

with p0p_{0} the probability of obtaining 00 after measuring the second register and xi,mx_{i,m} the mm-th feature of the ii-th data point.

Now measuring the last register which encodes the label gives the probability of each class

P(y=1)=14Np0iyi=1x+xi2P(y^* = 1) = \frac{1}{4Np_{0}}\sum_{i\vert y_i \rangle =1}{\vert{x^*+x\vert}_i}^2

Note that the two measurement rounds can be combined by classically post-processing the results.

Examination of the code

Let us consider a simple implementation of the above quantum distance-based classifier. As we have to quantum RAM, we will explicitly prepare the quantum state. Furthermore, we will consider only two data points, each with two features.

For normalized and standardized data, we can assume without loss of generality that

x0=cos(θ/2)0sin(θ/2)1\vert x_0 \rangle = \cos(\theta/2)\vert 0 \rangle - \sin(\theta/2)\vert 1 \rangle, y0=1y_0 = -1
x1=cos(ϕ/2)0sin(ϕ/2)1\vert x_1 \rangle = \cos(\phi/2)\vert 0 \rangle - \sin(\phi/2)\vert 1 \rangle, y1=1y_1 = 1
x=cos(ω/2)0sin(ω/2)1\vert x^* \rangle = \cos(\omega/2)\vert 0 \rangle - \sin(\omega/2)\vert 1 \rangle

for specific angles θ\theta, ϕ\phi and ω\omega.

The code is then given by

        
          version 1.0
qubits 4

prep_z q[0:3]
H q[0:1]

#e ncode the new data point, this implements a cRy(omega)
CNOT q[0], q[2]
Ry q[2], -omega/2
CNOT q[0], q[2]
Ry q[2], omega/2
X q[0]

# encode the first data point, this implements a ccRy(theta)
toffoli q[0],q[1],q[2]
CNOT q[1],q[2]
Ry q[2], theta/4
CNOT q[1],q[2]
Ry q[2], -theta/4
toffoli q[0],q[1],q[2]
CNOT q[1],q[2]
Ry q[2], -theta/4
CNOT q[1],q[2]
Ry q[2], theta/4
X q[1]

# encode the second data point, this implements a ccRy(phi)
toffoli q[0],q[1],q[2]
CNOT q[1],q[2]
Ry q[2], phi/4
CNOT q[1],q[2]
Ry q[2], -phi/4
toffoli q[0],q[1],q[2]
CNOT q[1],q[2]
Ry q[2], -phi/4
CNOT q[1],q[2]
Ry q[2], phi/4

# encode the labels
CNOT q[0], q[3]

# The actual algorithm
H q[1]
measure_z q[1,3]

        
      

Here we see the results of the execution for angles θ=\theta=, ϕ=\phi= and ω=\omega=. Note that we must discard the measurement results where the measurement of the second qubit gives 11. Hence, we see that P(y=1)>P(y=1)P(y^=1) > P(y^=-1), as we would expect.

Want to know more?

For more information see the article by Schuld et al., the notebooks on this algorithm on our GitHub or this article [2], where the practicalities of the state preparation are given.

[1] Implementing a distance-based classifier with a quantum interference circuit, M. Schuld, M. Fingerhuth, and F. Petruccione, EPL (Europhysics Letters), Volume 119, Number 6, 2017

[2]: R. Wezeman, N. Neumann, and F. Phillipson. “Distance-based classifier on the Quantum Inspire”. In: Digitale Welt4.1 (Jan. 2020), pp. 85–91