Quantum Machine Learning
Education Quantum Machine Learning Quantum Tutorial

Quantum Machine Learning, an Introduction

May 24, 2020

The Hello World of QML

We’ll start at the beginning and show the Quantum analog of the some of the typical algorithms. Starting with the perhaps one of the most simple but useful algorithms: The Dot Product. We’ll refresh the classical version before introducing the the Quantum Equivalent.

Dot Product in the classical World

Perhaps one of the most useful operations in mathematics. The dot product or inner product can be useful for understand how similar two vectors are. Crucially important in Machine Learning or in fact many processes. Techniques such as cosine similarity use the dot product to determine how similar two vectors are. Each of the vectors could represent a multitude of things. For example in TFIDF – the vectors can represent documents in which each vector encodes the normalized frequencies of word count, with each element of the Vector a normalized word count. Without cover the specific details, but assuming that we have two vectors, we can use the dot product given in the equation below to highlight whether our vectors are different or similar.

A \cdot B = |A||B| \cos(\theta)

We can now write this in a Vector form

A \cdot B = \begin{bmatrix}a & b & c \end{bmatrix} \begin{bmatrix}d \\ e \\ f \end{bmatrix}

The actual computation is as follows and the result is a scalar.

A \cdot B = ad + be + cf

You can easily see that if you take the normalized vectors A and B to be equal the result will be 1 but an example might be the following toy example where A and B are normalized, it is easily to show that the result is 0 or that the two vectors are orthogonal.

A \cdot B = \begin{bmatrix}1 & 0 & 0\end{bmatrix} \begin{bmatrix}0 \\ 1 \\ 0 \end{bmatrix} = 0

Translating to Dirac notation which is useful in Quantum Information, the dot product can be written as the row vector and column vector as follows, where A and B are the state vectors.

\left< A | B \right>

Another way at looking at these expressions is as an overlap function which measures how much of state A and B overlap. Outputting 1 means that A and B are identical, but output values can range from 0 to 1 with zero meaning there are no overlaps at all. Turning now to the Quantum analogue.

Overlap in the Quantum World

How do we achieve this overlap in the Quantum world? Computing the product with a Quantum Circuit is relatively easy. Using a swap test, we can pick up a squared probability of the overlap.

Where can it be used?

Useful in many routines, when distances need to be examined we can use a swap test. We use a Hadamard function on three qubits. One ancillary qubit and the two qubits of our states. Applying the Hadamard to the ancillary qubit we get the following

\left | S_{0} \right> = \left | 0, \psi, \phi \right>

This comes from taking the outer product of our states

\left | S_{0} \right> = \left | 0 \right> \otimes \left | \psi \right> \otimes \left | \phi \right>

Now let us apply the Hadamard Gate (H) to the first qubit in the 0 state

\left | S_{1} \right> = \frac{1}{\sqrt{2}} \left( \left | 0, \psi, \phi \right> + \left | 1, \psi, \phi \right> \right)

Now we can apply the Swap Gate to the quantum states which is controlled on the ancillary qubit – which is 1 on the right hand side of the equation. This will give us the following state.

\left | S_{2} \right> = \frac{1}{\sqrt{2}} \left( \left | 0, \psi, \phi \right> + \left | 1, \phi, \psi \right> \right)

Now let us apply another Hadamard on the left most qubit which gives the following

\left | S_{3} \right> = \frac{1}{\sqrt{2}} \left( \left | \frac{1}{\sqrt{2}} \left( \left | 0 \right> + \left | 1 \right> \right), \psi, \phi \right> + \left | \frac{1}{\sqrt{2}} \left( \left | 0 \right> + \left | 1 \right> \right), \phi, \psi \right> \right)

Expanding this out in terms of our left most qubit, we get the following

\left | S_{3} \right> = \frac{1}{2} \left | 0 \right> \left( \left | \psi, \phi \right> + \left | \phi, \psi \right> \right) + \frac{1}{2} \left | 1 \right>\left( \left | \psi, \phi \right> - \left | \phi, \psi \right> \right)

Interestingly what we have here is now an expression that looks at the sum of our swapped terms and the difference between these swapped terms. We can immediately see properties of this system. Looking at the first term we have term that will be maximal or twice the original state if equal. Looking at the second term, this will be lowest then the states are the same. Lets compute the probabilities more explicitly.

P(\left | 0 \right>) = \frac{1}{4}{ \bigg| \left( \left | \psi, \phi \right> + \left | \phi, \psi \right> \right) \bigg|}^2

With some re-arrangement we can see this becomes

P(\left | 0 \right>) = \frac{1}{2} + \frac{1}{2} {\bigg| \left< \psi | \phi \right> \bigg|}^2

This shows that we can test for orthogonality on \psi and \phi if we see the state 0 with a probability of half. If we were to see the state 0 with a probability of one then we can conclude the \psi and \phi are the same. Similarly we can look at the probability of return a state 1 on the ancillary.

P(\left | 1 \right>) = \frac{1}{2} - \frac{1}{2} {\bigg| \left< \psi | \phi \right> \bigg|}^2

This is consistent with what we found before, if you measure a 0 with certainty then you know that there is maximal overlap between the states \psi and \phi. If orthogonal, then we expect to see the state 1 with a probability of \frac{1}{2}. Basically we have found a way that we can check using just a few gates the level of overlap of our two original states.

Swap Routines

As was mentioned, we need to examine how we can create a swap process. It requires just two gates, a NOT and one of the favorite gates: the Hadamard. If we have two qubits, we can show the following matrix.

SWAP = X \otimes H = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}

Summary

Here we have shown how one the overlap or effectively the inner product or dot product can be created from a relatively simple quantum circuit. These techniques can be used in a variety of different circuits such as Quantum K-means clustering.

For more details, please see one of the Quantum Machine Learning books on your journey towards Quantum Machine Learning from Peter Wittek, and Maria Schuld.