Quantum Computing Methods for Supervised Learning

Qubits are a scarce and expensive resource. The restricted physical implementations of quantum computers available today have very few qubits⁵⁵5The recent quantum supremacy experiment conducted by Google used only 54 qubits [37].. An important question therefore that has implications for performance and feasibility is how to represent classical data in quantum states. Suppose we have a dataset $D$ of $N$ instances:

where each $x_{i}$ is a real number. In basis encoding, each instance $x_{i}$ is encoded as $\ket{b_{i}}$ where $b_{i}$ is the binary representation of $x_{i}$. The dataset $D$ can then be represented as a superposition of all computational basis states:

In amplitude encoding, data is encoded in the amplitudes of quantum states. The above dataset $D$ can be encoded as:

Besides basis and amplitude encoding, many other methods of encoding exist such as Qsample encoding, dynamic encoding, squeezing embedding, displacement embedding, Hamiltonian encoding etc. [38][39].

Grover’s algorithm [20] is a quantum search algorithm that offers a quadratic speed-up over classical algorithms when performing a search over an unstructured search space. Suppose we are given a set of $N$ elements $X=\{x_{1},...,x_{i},...,x_{N}\}$ where $x_{i}\in\{0,1\}^{m}$ and a boolean function $f:\{0,1\}^{m}\rightarrow\{0,1\}$ such that:

Any classical algorithm that performs a search for $x^{*}$ in $X$ is $O(N)$ in time. Grover’s algorithm can perform such a search in $O(\sqrt{N})$. The algorithm has three steps to it.

In the first step, a quantum state is set up in an equal superposition of basis states using the Hadamard transform. As an example, consider $N=8$. We set up the state using 3 qubits as:

The second step referred to as phase inversion deals with flipping the amplitude of each $\ket{x}$ if $f(x)=1$ and leaving it unchanged if $f(x)=0$. To do this, we define a unitary quantum oracle $O\ket{x}=(-1)^{f(x)}\ket{x}$. Suppose, in our example, $x^{*}$ is present at the fourth position. Applying gate $O$ on $\ket{\psi_{1}}$ gives us:

The third step referred to as inversion around the mean involves flipping all amplitudes around their collective mean $\mu=\frac{1}{N}\sum_{x}{\alpha_{x}}$. This is performed by the Grover diffusion operator $G$:

Applying $G$ to $\ket{\psi_{2}}$ gives us:

Thus, after one iteration, the amplitude of the target element $x^{*}$ is higher than the amplitudes of other elements. If we were to measure the system at this point, we would get the target element as outcome with a probability of $(\frac{5}{4\sqrt{2}})^{2}=78\%$. The second and third steps are repeated $\sqrt{N}$ times to maximize this probability. After the second iteration, we get the below state which will find the target element with a probability of $95\%$:

The same algorithm can also find $k$ matching entries instead of a single entry. Several modifications have been proposed that extend this work. Durr and Hoyer [40] propose a quantum algorithm to find the index of the minimum value from a list of $N$ values in time $O(c\sqrt{N})$ with a probability of at least $(1-\frac{1}{2^{c}})$. These methods generalize Grover’s search and are collectively referred to as amplitude amplification techniques [41].

The swap test [42] is a simple subroutine used to compute the overlap between two quantum states $\ket{\phi}$ and $\ket{\psi}$. Quantum procedures can be easily described using circuit diagrams. The circuit diagram of the swap test is shown in figure 1.

The system is initially prepared in the state $\ket{0,\phi,\psi}$. The Hadamard gate applied on the first ancilla qubit⁶⁶6Input qubits that do not hold any input data but are added to satisfy other conditions (most often reversibility of the transformation) are called auxiliary or ancillary qubits. transforms the state to $\frac{1}{\sqrt{2}}(\ket{0,\phi,\psi}+\ket{1,\phi,\psi})$. The CSWAP further transforms it to $\frac{1}{\sqrt{2}}(\ket{0,\phi,\psi}+\ket{1,\psi,\phi})$. After the application of the second Hadamard gate to the first qubit, the state can be written as $\frac{1}{2}\ket{0}(\ket{\phi,\psi}+\ket{\psi,\phi})+\frac{1}{2}\ket{1}(\ket{\phi,\psi}-\ket{\psi,\phi})$. The probability of measuring the first qubit as $\ket{0}$ is given by $p=\frac{1}{2}+\frac{1}{2}{|\braket{\psi}{\phi}|}^{2}$. If $\ket{\phi}$ and $\ket{\psi}$ are equal, ${|\braket{\psi}{\phi}|}^{2}=1$, and the observed value of $p$ is 1. If $\ket{\phi}$ and $\ket{\psi}$ are orthogonal, ${|\braket{\psi}{\phi}|}^{2}=0$, and the observed value of $p$ is $\frac{1}{2}$. The degree of overlap given by the inner product of the two states can be estimated with this method to precision $\epsilon$ using $O(1/\epsilon)$ copies [32].

Solving a system of linear equations is an important problem ubiquitous throughout science and engineering. A seminal result in quantum computation is the HHL algorithm [23] that solves the following problem: given a Hermitian matrix $A\in\mathbb{R}^{N\times N}$ and a unit vector $\overrightarrow{b}\in\mathbb{R}^{N}$, find a solution vector $\overrightarrow{x}\in\mathbb{R}^{N}$ that satisfies the equation $A\overrightarrow{x}=\overrightarrow{b}$.

We present here a condensed outline of the algorithm. The solution we are interested in is $\ket{x}=A^{-1}\ket{b}$. Let $\{v_{1},...,v_{N}\}$ be the eigenvectors of $A$ with corresponding eigenvalues $\{\lambda_{1},...,\lambda_{N}\}$. The vector $\overrightarrow{b}$ is encoded using amplitude encoding (section 3.1.1) as $\ket{b}=\sum_{i=1}^{N}{\beta_{i}\ket{v_{i}}}$. Hamiltonian simulation is used to transform the matrix $A$ into a unitary operator, and quantum phase estimation⁷⁷7The quantum phase estimation algorithm can estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. is used to carry out eigendecomposition to get the state $\sum_{i=1}^{N}{\beta_{i}\ket{v_{i}}\ket{\lambda_{i}}}$. An ancilla qubit is added, rotation conditioned on $\ket{\lambda_{i}}$ is carried out, and the eigenvalue register $\ket{\lambda_{i}}$ is uncomputed to yield a state proportional to $\sum_{i=1}^{N}{\beta_{i}\lambda_{i}^{-1}\ket{v_{i}}}=A^{-1}\ket{b}=\ket{x}$.

It is important to note that while a classical algorithm finds all coefficients $x_{i}$ for $x$, the HHL algorithm finds the quantum state $\ket{x}=\sum_{i=1}^{N}{x_{i}\ket{i}}$. Obtaining values for all $x_{i}$ takes $O(N)$ repetitions; this observation nullifies the speed-up the quantum algorithm has over the classical counterparts. Hence, the HHL algorithm is most useful when used as a subroutine carrying out an intermediate step in a larger process where the quantum state $\ket{x}$ is consumed by the next subroutine in the process.

Most quantum algorithms assume parallel access to amplitude encoded states; this is performed using a quantum random access memory or QRAM [43]. The classical RAM takes a memory address as input and returns the data stored at that address. A QRAM performs a similar operation using qubit registers. The input register contains a superposition of addresses $\sum_{a}c_{a}\ket{a}$ and the output register contains a superposition of the data at those addresses $\sum_{a}c_{a}\ket{a}\ket{D_{a}}$. While a classical RAM queries $N$ addresses in $O(N)$, QRAM performs the operation in $O(\log N)$.

The k-nearest neighbors (KNN) is one of the simplest supervised learning algorithms. To predict the label of a new unseen instance $x_{test}$, the algorithm looks at $k$ instances in the training set that are closest to $x_{test}$ and chooses the class that appears most often in the labels of these k-nearest neighbors as the predicted label (for regression, the algorithm assigns the mean value of the k-nearest neighbors as the label). An advantage of KNN is that, unlike many other supervised algorithms, it is non-parametric and makes no assumptions about the data distribution. However, since all computation is deferred, inference can become prohibitively expensive for large training sets. During inference, the distance of the test instance from all other training instances is calculated; this is the most computationally intensive step in the process. Hence, quantum versions of KNN focus on faster evaluation of the distance between two instances.

Aïmeur et al. [48] propose using the overlap $|\braket{a}{b}|$ as computed by the swap test (section 3.1.3) as a measure of similarity between $\ket{a}$ and $\ket{b}$. Llyod et al. [49] develop a technique based on the swap test to compute the distance between $\overrightarrow{a}$ and $\overrightarrow{b}$. A state $\ket{\psi}=\frac{1}{\sqrt{2}}(\ket{0,a}+\ket{1,b})$ is constructed by setting up an ancilla. A second state given by $\ket{\phi}=\frac{1}{\sqrt{Z}}(|\overrightarrow{a}|\ket{0}-|\overrightarrow{b}|\ket{1})$ is constructed where $Z=|\overrightarrow{a}|^{2}+|\overrightarrow{b}|^{2}$. Using $\braket{x}{x}=|\overrightarrow{x}|^{-1}|\overrightarrow{x}|$, the authors make the observation that $|\overrightarrow{a}-\overrightarrow{b}|^{2}=Z|\braket{\phi}{\psi}|^{2}$. With this, the distance between $\overrightarrow{a}$ and $\overrightarrow{b}$ can be retrieved using a swap test [26]. The authors use the above technique to implement the nearest-centroid classification algorithm in which the centroids of all training instances belonging to each class are precomputed; during inference, a class label is assigned to the test instance by calculating its distance from all centroids. Given a training set of $M$ instances, this procedure solves the problem of classifying an $N$-dimensional test vector into one of several classes in $O(log(MN))$ compared to $O(MN)$ required by classical algorithms.

Wiebe et al. [50] argue that the nearest-centroid classification presented above can perform poorly in practice since training instances are often embedded in complicated manifolds, and the centroids may lie outside these manifolds. They propose two fast methods for computing the distance between vectors based on an alternative representation of classical information in quantum states, amplitude amplification, and Durr-Hoyer minimum finding [40].

Support vector machines (SVM) [51] is a popular classification algorithm that determines the optimal hyperplane that separates instances of two classes in the training data and classifies test instances based on which side of the separating hyperplane they lie on. Given training instances $\{(x_{1},y_{1}),...,(x_{i},y_{i}),...,(x_{M},y_{M})\}$ where $x_{i}\in\mathbb{R}^{N}$ and $y_{i}\in\{-1,+1\}$, the algorithm learns an $N$-dimensional hyperplane given by $w=[\beta_{1},\beta_{2},...,\beta_{N}]^{T}$ that separates the instances of the two classes with maximum margin. Classification of a test instance $x_{t}$ is performed as:

Since the instances may not be strictly separable, slack variables are introduced that provide a soft margin by allowing some data points to violate the margin criterion. This formulation is known as the maximum margin classifier or support vector classifier; this however still requires the data points to be linearly separable. SVMs overcome this limitation of linear separability by what is known as the kernel trick which transforms the feature space into a new, higher-dimensional feature space. Instances that were not linearly separable in the original feature space may be linearly separable in the new feature space. Mathematically, the kernel trick generalizes the dot product between two feature vectors $\braket{x_{i},x_{j}}$ by a kernel function $k(x_{i},x_{j})$. Different kernels can be chosen depending on the data distribution. Training an SVM involves solving the quadratic programming problem [52]:

where $\alpha_{n}\in\mathbb{R}$, $C$ is the regularization parameter, and $k(\cdot,\cdot)$ is the kernel function.

Anguita et al. [53] observe that training support vector machines may be a hard problem and propose a quantum variant that uses Durr and Hoyer’s minimum finding [40] based on Grover’s algorithm to solve the optimization problem. Rebentrost et al. [54] suggest computing inner products using a quantum method based on an approach similar to the one discussed in section 3.3.1 which leads to an exponential speed-up with respect to the dimension of the feature vector $N$. They also describe a least-squares reformulation of the SVM algorithm with slack variables $e_{j}$ that converts the quadratic optimization problem into a problem of solving a system of linear equations which leads to an additional exponential speed-up in terms of the number of training instances $M$:

As shown in section 3.2, quantum annealing is particularly well-suited for solving optimization problems. Willsch et al. [55] demonstrate a practical implementation of training SVMs on the commercially available D-Wave DW2000Q quantum annealer by formulating it as a QUBO problem.

Artificial neural networks or simply neural networks were originally inspired from biological neural networks that model the activity of neurons in human brains. The basic building block of a neural network is the neuron, also called node or perceptron, that maps the input $x\in\mathbb{R}^{N}$ to the output $y\in\mathbb{R}$ as follows⁸⁸8This is the general form used in modern feedforward neural networks. The original perceptron used a step activation function and produced only binary outputs 0 and 1.:

where $w_{i}\in\mathbb{R}$, $b\in\mathbb{R}$, and $g:\mathbb{R}\rightarrow\mathbb{R}$ is the activation function. The outputs of some neurons can be fed as inputs to other neurons thus creating layers within the network.

Even though neural networks were amongst the first machine learning algorithms to be proposed, their research stagnated for several decades from 1940s to 1980s due to the inherent difficulty and large computational power required to train them. They returned to popularity after the introduction of backpropagation [56] which eased these problems by offering a faster method for training. In the last decade, with GPUs and cloud computing providing cheaper access to massive computational power, neural networks have dwarfed other learning algorithms⁹⁹9Many informal texts now relegate all other learning algorithms to the category conventional machine learning. to become one of the biggest success stories of modern computers finding applications in various industries including healthcare, manufacturing, finance, analytics etc. to solve problems in image processing, computer vision, natural language processing, predictive modeling, and many other areas. However, even today, significant resources are required to train neural networks, and training times for research and industrial problems can run into weeks or even months.

An obvious difficulty arises in considering quantum computation as a means for implementing neural networks. Quantum computation (and indeed quantum mechanics itself) is a theory fundamentally based on linear transformations, while an important practical advantage neural networks enjoy over many other learning algorithms is that they can model non-linear data distributions. Bringing non-linearity into quantum algorithms is a non-trivial task [57]. However, classical neural networks do make heavy use of linear algebra, and the inherent randomness of quantum mechanical effects can be leveraged to automatically introduce noise in the training process to improve model robustness - something that needs to be done purposefully in classical training [58]. Numerous neural network architectures have emerged in recent times to tackle problems belonging to a wide range of supervised, unsupervised, and reinforcement learning tasks [59]. Research in this field has been scattered with different proposals addressing narrow problems in piecemeal style. We present here a select subset of these proposals.

Most early work on quantizing¹⁰¹⁰10Developing a quantum alternative to a classical computation technique is often referred to as quantizing it although we prefer this term is used sparingly. neural networks focussed on Hopfield networks [60] which differ from the neural networks presently used in practice. In a Hopfield network, all neurons have undirected connections with all other neurons as opposed to feed-forward networks that are organized as layers; also, each neuron outputs a binary 0 or 1 instead of a real number. Hopfield networks are used to model associative memories which allow retrieval of data based on content rather than addresses. Kak [61] introduces the idea of quantum neural computation and Perus [62] describes a quantum associative network by drawing analogies between Hopfield networks and quantum information processing. Behrman et al. [63] present a quantum realization of neural networks by showing that a single quantum dot¹¹¹¹11Quantum dots are nanometre-scale semiconductor particles. molecule can act as a recurrent quantum neural network. More recently, Rebentrost et al. [64] present a technique based on quantum Hebbian learning and fast quantum matrix inversion to train Hopfield networks.

Boltzmann machines [65], closely related to Hopfield networks, are stochastic generative networks that can learn a probability distribution over a set of inputs. They are trained by adjusting the interconnection weights between the neurons so that the thermal statistics of the system as described by the Boltzmann-Gibbs distribution reproduces the statistics of the data [28]. Boltzmann machines can be conveniently represented by an Ising model whose spins encode features and interactions encode statistical dependencies between the features. In a restricted Boltzmann machine, connections exist only between neurons belonging to different layers; this makes them easier to train than fully-connected Boltzmann machines. Restricted Boltzmann machines can be stacked together to form deep belief networks that can be used to learn internal representations or can be trained under supervision to perform classification. Training Boltzmann machines is exponentially hard and is performed using approximation techniques like contrastive divergence [66][67] that rely on Gibbs sampling. Wiebe et al. [50] propose quantum methods to efficiently train full Boltzmann machines by preparing a coherent analog of the Gibbs state from which samples can be drawn. Adachi et al. [68] investigate an alternative approach of performing the sampling on a D-Wave quantum annealer instead of classical Gibbs sampling.

A different line of research involves developing quantum analogs for classical perceptrons. Schuld et al. [69] introduce a quantum perceptron model with a step activation function that can be used to develop superposition-based learning schemes in which a superposition of training vectors can be processed in parallel. Kapoor et al. [70] develop two quantum techniques for modeling perceptrons; the first provides quadratic speed-up with respect to the number of training instances, and the second provides a quadratic reduction in the scaling of the training time with the margin between the two classes.

Feedforward networks are one of the simplest neural network architectures in which the connections between neurons do not form any loops or cycles. They are usually trained using backpropagation, and the optimization is performed using some variant of gradient descent. Most machine learning architectures used in practice today are based on feedforward networks or their derivatives such as convolutional neural networks or recurrent neural networks [59]. Allcock et al. [58] define an efficient quantum subroutine for robust inner product estimation using QRAM [43] and use it to demonstrate quadratic speed-ups in the size of the network over classical counterparts; they additionally claim that the proposed quantum method naturally imitates regularization techniques like drop-out leading to more robust networks. Farhi et al. [36] present a general framework for binary classification specifically designed for near-term quantum processors in which the input strings are mapped to computational basis states, and the predicted label is given by the outcome of a Pauli operator measured on a readout qubit. This framework extends to a full quantum neural network that can classify both classical and quantum data. Convolutional neural networks (CNNs) [71] have achieved great success [72] in image classification tasks in recent times. They, however, suffer from the fact that the operation of convolution is computationally expensive. Kerenidis et al. [73] design a quantum CNN based on quantum computation of the convolution product between two tensors. They also propose a quantum tomography¹²¹²12Quantum tomography is the process by which a quantum state is reconstructed using measurements on an ensemble of identical quantum states. sampling approach to recover classical information from the network output and a quantum backpropagation algorithm for efficient training of the quantum CNN.

It is important to distinguish between quantum-enhanced machine learning that focuses on techniques to implement learning on classical data using quantum computers from quantum-generalisation of machine learning algorithms that deals with developing fully quantum algorithms that work with quantum data. This is especially true for neural networks for which active research is underway on both fronts. We restrict this paper to quantum-enhanced techniques and refer the reader to [57][74][75][76][77] for work on quantum generalisations. The principles of quantum computing have inspired development of new classical randomized algorithms that show exponential speed-ups over conventional algorithms [25]. With these quantum-inspired algorithms, the gap between certain classical and quantum algorithms is no longer exponential but polynomial. Arrazola et al. [78] provide a study of these algorithms and observe that they work well only under stringent conditions which occur rarely in practice. We do not cover these in this paper.