Machine learning & artificial intelligence in the quantum domain: a review of recent progress

Stemming from the traditions of pattern recognition, such as recognizing handwritten text, and statistical learning theory (which places ML ideas in a rigorous mathematical framework), ML, broadly speaking, explores the construction of algorithms that can learn from and make predictions about data. Traditionally, ML deals with two main learning settings: supervised and unsupervised learning, which are closely related to data analysis and data mining-type tasks (Shalev-Shwartz and Ben-David 2014), see figure 4. A broader perspective (Alpaydin 2010) on the field also includes reinforcement learning (Sutton and Barto 1998), which is closely related to learning as is realized by biological intelligent entities. We shall discuss reinforcement learning separately.

Zoom In Zoom Out Reset image size

In broad terms, supervised learning deals with learning-by-example: given a certain number of labeled points (so-called training set) $\{(x_i, y_i) \}_i$ where x_i denote data points, e.g. N  −  dimensional vectors, and y_i denote labels (e.g. binary variables, or real values), the task is to infer a 'labeling rule' $x_i \mapsto y_i$ which allows us to guess the labels of previously unseen data, that is, beyond the training set. Formally speaking, we deal with the task of inferring the conditional probability distribution $P(Y=y | X=x)$ (more specifically, generating a labeling function which, perhaps probabilistically, assigns labels to points) based on a certain number of samples from the joint distribution $P(X, Y)$. For example, we could be inferring whether a particular DNA sequence belongs to an individual who is likely to develop diabetes. Such an inference can be based on the datasets of patients whose DNA sequences had been recorded, along with the information on whether they actually developed diabetes. In this example, the variable Y (diabetes status) is binary and the assignment of labels is not deterministic, as diabetes also depends on environmental factors. Another example could include two real variables, where x is the height from which an object is dropped and y the duration of the fall. In this example, both variables are real-valued and (in vacuum) the labeling relation will be essentially deterministic. In unsupervised learning, the algorithm is provided just with the data points without labels. Broadly speaking, the goal here is to identify the underlying distribution, or structure, and other informative features in the dataset. In other words, the task is to infer properties of the distribution $P(X=x),$ based on a certain number of samples, relative to a user-specified guideline or rule. Standard examples of unsupervised learning are clustering tasks, where data-points are supposed to be grouped in a manner which minimizes within-group mean-distance, while maximizing the distance between the groups. Note that the group membership can be thought of as a label, and so this also corresponds to a labeling task, but lacks 'supervision': examples of correct labelings. In basic examples of such tasks the number of expected clusters is given by the user, but this too can be automatically optimized.

Another class of unsupervised learning tasks includes feature extraction and dimensionality reduction, critical in combating the so-called curse of dimensionality. The curse of dimensionality refers to problems which stem from the fact that the raw representations of real-life data often occupy very high dimensional spaces. For instance, a standard resolution one-second video-clip at standard refresh frequency, capturing events which are extended in time, maps to a vector in  ∼10⁸ dimensional space¹⁴, even though the relevant information it carries (say a license-plate number of a speeding car filmed) may be significantly smaller. More generally, intuitively it is clear that, since geometric volume scales exponentially with the dimension of the space it is in, the number of points needed to capture (or learn) general features of an n  −  dimensional object will also scale exponentially. In other words, learning in high dimensional spaces is exponentially difficult. However, very often, the data-points which we can observe in reality (i.e. the effective support of the distribution $P(X)$) lie in a sub-manifold of a substantially lower dimension. Hence, a means of dimensionality reduction from raw representation space (e.g. moving car clips) to the relevant feature space (e.g. license-plate numbers) is a necessity in any real-life scenario.

These approaches map the data-points to a space of significantly reduced dimension, while attempting to maintain the main features—the relevant information—of the structure of the data. Feature extraction can also be understood as a labeling process, where the points in the reduced space correspond to labels¹⁵. A typical example of a linear dimensionality example technique is, e.g., principal component analysis. In practice, such algorithms also constitute an important step in data pre-processing for other types of learning and analysis.

Furthermore, unsupervised learning also includes generative models. In this flavor of learning, the effective task is to specify a model, in this case a specification of a probability distribution, which best matches the observed data-points drawn from $P(X)$. Ideally, such a model well-approximates $P(X)$ itself and can be used to generate new samples. As a comment on the nomenclature, it should be pointed out that the relationship between various flavors of learning is often a matter of perspective. For instance, generative models stand in contrast to discriminative models, which, as the name suggests, discriminate, i.e. they associate labels to points. From this perspective, most of supervised learning neatly fits in the discriminative paradigm, whereas unsupervised learning contains both discriminative (clustering) and generative aspects. On the other hand, both supervised discriminative and unsupervised generative models can be understood as data-fitting problems: in supervised settings, the goal is to identify the best classifying function with respect to how the labels in Y are correlated to the data-points in X, in the labeled training set (or the distribution $P(X, Y)$). Thus, the problem is to identify the best approximation of the conditional distribution $P(Y|X)$. Generative models aim to capture the whole distribution (which may be multivariate or not). In both approaches, the actual task, in operational terms, boils down to identifying which element from the model set best fits the observed data. The model set is known as the set of hypotheses, and may consist of functions (e.g. neural networks, or hyperplanes in support vector machines) or parametrizations of distributions (e.g. Boltzmann machines, or more general graphical models), depending on whether the setting is discriminative or generative, respectively. For more details on the various models for ML, see section 2.1.

ML provides a plethora of methods which help us to understand data better, and in an automated fashion. As humanity is amassing data at an exponential rate (insideBIGDATA 2017) such methods may offer the only sustainable route to gaining new knowledge about the world we live in—as long as we can provide the computing power to match the growth of the datasets.

Reinforcement learning (RL) (Sutton and Barto 1998, Russell and Norvig 2009) is, traditionally, the third canonical category of ML. Partially due to the relatively recent prevalence of (un)supervised methods in the contexts of the pervasive data mining and big data analysis topics, many modern textbooks on ML focus on these methods. RL strategies have mostly remained reserved to the robotics and AI communities. Lately, however, the surge of interest in adaptive and autonomous devices, robotics and AI have increased the prominence of RL methods.

One recent celebrated result which relies on the extensive use of standard ML and RL techniques in conjunction is that of AlphaGo (Silver et al 2016), a learning system which mastered the game of Go, and achieved, arguably, superhuman performance, easily defeating the best human players. This result is notable for multiple reasons, including the fact that it illustrates the potential of learning machines over special-purpose solvers in the context of AI problems: while specialized devices which relied on programming over learning (such as Deep Blue) could surpass human performance in chess, they failed to do the same for the more complicated game of Go, which has a notably larger space of strategies. The learning system AlphaGo achieved this many years ahead of typical predictions.

In subsequent recent works, it was further demonstrated that superhuman performance in Go can be achieved without relying on human-generated data, or supervised learning. In particular, the system relied on self-play and predominantly on RL methods (Silver et al 2017b). Such a more general RL approach lead to high flexibility and resulted in a system which simultaneously plays Go, chess and shogi (also known as Japanese chess) (Silver et al 2017a) at superhuman level. Such recent results have prompted a noticeable increase of interest in RL techniques, e.g. RL was listed as one of the ten breakthrough technologies of 2017 by MIT technology review (Review 2017).

The distinction between RL and other data-learning ML methods is particularly relevant from a quantum information perspective, which will be addressed in more detail in section 7.2.

RL constitutes a broad learning setting, formulated within the general agent–environment paradigm (AE paradigm) of AI (Russell and Norvig 2009). Here, we do not deal with a static database, but rather an interactive task environment. The learning agent (or, a learning algorithm) learns through the interaction with the task environment.

As an illustration, one can imagine a robot acting on its environment and perceiving it via its sensors—the percepts being, say, snapshots made by its visual system and actions being, say, movements of the robot—as depicted in figure 5. The AE formalism is, however, more general and abstract. It is also unrestrictive as it can also express supervised and unsupervised settings.

Zoom In Zoom Out Reset image size

In RL, it is typically assumed that the goal of the process is manifest in a reward function, which, roughly speaking, rewards the agent whenever the agent's behavior is correct (in which case we are dealing with positive reinforcement, but other variants of operant conditioning are also used¹⁶). This model of learning seems to cover pretty well how most biological agents (i.e. animals) learn: one can illustrate this through the process of training a dog to do a trick by giving it treats whenever it performs well. As mentioned earlier, RL is all about learning how to perform the 'correct' sequence of actions given the received percepts, which is an aspect of planning, in a setting which is fully on-line: the only way to learn about the environment is by interacting with it.

While supervised, unsupervised and RL constitute the three broad categories of learning, there are many variations and intermediary settings. For instance, semi-supervised learning interpolates between unsupervised and supervised settings, where the number of labeled instances is very small compared to the total available training set. Nonetheless, even a small number of labeled examples have been shown to improve the bare unsupervised performance (Chapelle et al 2010), or, from an opposite perspective, unlabeled data can help with classification when facing a small quantity of labeled examples. In active supervised learning, the learning algorithm can further query the human user, or supervisor, for the labels of particular points which would improve the algorithm's performance. This setting can only be realized when it is operatively possible for the user to correctly label all the points and may yield advantages when this exact labeling process is expensive. Further, in supervised settings, one can consider so-called inductive learning algorithms which output a classifier function, based on the training data, which can be used to label all possible points. A classifier is simply a function which assigns labels to the points in the domain of the data. In contrast, in transductive learning (Chapelle et al 2010) settings, the points that need to be labeled later are known beforehand—in other words, the classifier function is only required to be defined on a priori known points. Next, a supervised algorithm can perform lazy learning, meaning that the whole labeled dataset is kept in memory in order to label unknown points (which can then be added), or eager learning, in which case, the (total) classifier function is output (and the training set is no longer explicitly required) (Alpaydin 2010). Typical examples of eager learning are linear classifiers, such as basic support vector machines, described in the next section, whereas lazy learning is exemplified by, e.g., nearest-neighbor methods¹⁷. Our last example, online learning (Alpaydin 2010), can be understood as either an extension of eager supervised learning, or a special case of RL. Online learning generalizes standard supervised learning, in the sense that the training data is provided sequentially to the learner and used to incrementally update the classifying function. In some variants, the algorithm is asked to classify each point and is given the correct response afterward, and the performance is based on the guesses. The match/mismatch of the guess and the actual label can also be understood as a reward, in which case online learning becomes a restricted case of RL.

The aforementioned specialized learning scenarios can be phrased in a unifying language, which also enables us to discuss how specialized tasks fit in the objective of realizing true AI. In the modern take on AI (Russell and Norvig 2009), the central concept of the theory is that of an agent. An agent is an entity which is defined relative to its environment and which has the capacity to act, that is, do something.

In computer science terminology the requirements for something to be an agent (or for something to act) are minimal and essentially everything can be considered an agent—for instance, all non-trivial computer programs are also agents.

AI concerns itself with agents which do more—for instance they also perceive their environment, interact with it and learn from experience. AI is nowadays defined¹⁸ as the field which is aimed at designing intelligent agents (Russell and Norvig 2009), which are autonomous, perceive their world using sensors, act on it using actuators and choose their activities so as to achieve certain goals—a property which is also called rationality in literature.

Agents only exist relative to an environment (more specifically a task environment) with which they interact, constituting the overall AE paradigm, illustrated in figure 6. While it is convenient to picture robots when thinking about agents, they can also be more abstract and virtual, as is the case with computer programs 'living' in the internet¹⁹. In this sense, any learning algorithm for any of the more specialized learning settings can also be viewed as a restricted learning agent, operating in a special type of environment, e.g. a supervised learning environment may be defined by a training phase, where the environment produces examples for the learning agent, followed by a testing phase, where the environment evaluates the agent, and finally the application phase, where the trained and verified model is actually used. The same also obviously holds for more interactive learning scenarios such as the reinforcement-driven mode of learning—RL, we briefly illustrated in section 1.2.2, is natively phrased in the AE paradigm. In other words, all ML models and settings can be phrased within the broad AE paradigm.

Zoom In Zoom Out Reset image size

Although the field of AI is fragmented into research branches with focus on isolated, specific goals, the ultimate motivation of the field remains the same: the design of true, general AI, sometimes referred to as artificial general intelligence (AGI)²⁰, that is, the design of a 'truly intelligent' agent (Russell and Norvig 2009).

The topic of what ingredients are needed to build AGI is difficult, and there is no consensus.

One perspective focuses on the behavioral aspects of agents. In literature, many features of intelligent behavior are captured by characterizing more specific types of agents: simple reflex agents, model-based reflex agents, goal-based agents, utility-based agents, etc. Each type captures an aspect of intelligent behavior, much like the fragments of the field of ML, understood as a subfield of AI, capture specific types of problems intelligent agents should handle. For our purposes, the most important, overarching aspect of intelligent agents is the capacity to learn²¹ and we will emphasize learning agents in particular.

The AE paradigm is particularly well suited for such an operational perspective, as it abstracts from the internal structure of agents and focuses on behavior and input–output relations.

More precisely, the perspective on AI presented in this review is relatively simple: (a) AI pertains to agents which behave intelligently in their environments and (b) the central aspect of intelligent behavior is that of learning. While we, unsurprisingly, do not more precisely specify what intelligent behavior entails, this simple perspective on AI already has non-trivial consequences. The first is that intelligence can be ascertained from the interaction history between the agent and its environment alone. Such a viewpoint on AI is also closely related to behavior-based AI and the ideas behind the Turing test (Turing 1950); it is in line with an embodied viewpoint on AI (see embodied AI in section 1.2) and it has influenced certain approaches towards quantum AI, touched on in section 7.3. The second is that the development of better ML and other types of relevant algorithms does constitute genuine progress towards AI, conditioned only on the fact that such algorithms can be coherently combined into a whole agent. It is, however, important to note that actually achieving this integration may be far from trivial. In contrast to such strictly behavioral and operational points of view, an alternative approach towards whole agents (or complete intelligent agents) focuses on agent architectures and cognitive architectures (Russell and Norvig 2009). In this approach to AI the emphasis is equally placed not only on intelligent behavior, but also on forming a theory about the structure of the (human) mind. One of the main goals of a cognitive architecture is to design a comprehensive computational model which encapsulates various results stemming from research in cognitive psychology. The aspects which are predominantly focused on understanding human cognition are, however, not central for our take on AI. We discuss this further in section 7.3.

Throughout this review paper, we have striven to use the notation specified in the reviewed works. To avoid notational chaos, however, we keep the notation consistent within subsections—this means that, within one subsection, we adhere to the notation used in the majority of works if inconsistencies arise.

Artificial neural networks (ANNs, or just NNs) are a biologically inspired approach to tackling learning problems. Originating in 1943 (McCulloch and Pitts 1943), the basic component of NNs is the artificial neuron (AN), which is, abstractly speaking, a real-valued function $AN: \mathbb{R}^k \rightarrow \mathbb{R}$ parametrized by a vector of real, non-negative weights $(w_i)_i = {\bf w} \in\mathbb{R}^k$ and the activation function $\phi: \mathbb{R} \rightarrow \mathbb{R},$ given by

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle AN({\bf x}) = \phi \left( \sum_{i} x_i w_i \right), {\rm ~ with\ } {\bf x} = (x_i)_i \in \mathbb{R}^k. \nonumber \end{align} \tag{ 1 }$$

For the particular choice when the activation function is the threshold function, given by $\phi_{\theta} (x) = 1$ if $x>\theta \in \mathbb{R}^+$ and $\phi_{\theta} (x) = 0$ otherwise, the AN is called a perceptron (Rosenblatt 1957), and has been studied extensively. Already such simple perceptrons perform classification into subspaces specified by the hyperplane with the normal vector ${\bf w}$ and offset θ (see support vector machines later in this section).

Note that in ML terminology a distinction should be made between artificial neurons (ANs) and perceptrons—perceptrons are special cases of ANs, with a fixed activation function, the step function, and a specified update or training rule. ANs in modern times use various activation functions (often the differentiable sigmoid functions) and can use different learning rules. For our purposes, this distinction will not matter. The training of such a classifier or AN for supervised learning purposes consists in optimizing the parameters ${\bf w}$ and θ so as to correctly label the training set—there are various figures of merit particular approaches care about and various algorithms that perform such an optimization, which are not relevant at this point. By combining ANs in a network we obtain NNs (if ANs are perceptrons, we usually talk about multi-layered perceptrons). While single perceptrons, or single-layered perceptrons, can realize only linear classification, a three-layered network already suffices to approximate any continuous real-valued function (with precision depending on the number of neurons in the inner, so-called hidden, layer). Cybenko (1989) was the first to prove this for sigmoid activation functions, whereas Hornik generalized this to show that the same holds for all non-constant, monotonically increasing and bounded activation functions (Hornik 1991) soon thereafter. This shows that if sufficiently many neurons are available, a three-layered ANN can be trained to learn any dataset, in principle²². Although this result seems very positive, it comes with the price of a large model complexity, which we discuss in section 2.2.2²³.

In recent years, it has become apparent that using multiple, sequential, hidden feed-forward layers (instead of one large layer), i.e. deep NNs, may have additional benefits. In particular, convolutional NNs (CNNs) have achieved stellar successes, especially in the fields of vision and pattern recognition. CNNs are, in essence, deep NNs of a particular structure (e.g. the connections between neighboring layers maintain a notion of locality), which is inspired by the biological visual cortex of certain animals (see e.g. Rawat and Wang (2017) and references therein for more information). CNNs have a reduced number of parameters (Poggio et al 2017) compared to unrestricted deep NNs. Furthermore, the sequential nature of processing of information from layer to layer can be understood as a feature abstraction mechanism (the layers process the data sequentially, highlighting relevant features at each step) and the analyses of the outputs of the trained layers of the CNN can shed light on the relevant features of the task at hand.

While deep NNs are extremely successful in practice, they also suffer from short-comings. Perhaps the central issue of deep networks follows from the complex nature of the functions they can realize and the convoluted relationship between the network parameters and the realized functions. The high expressivity—their capacity to represent many involved functions—is responsible for their outstanding performance, but also limits what can theoretically be said about generalization performance. Indeed, our lack of understanding of why such networks generalize well is a matter of ongoing debate (Zhang et al 2017a). Further, the complex structure of functions realized by deep networks (even CNNs) dramatically limits the interpretability of the model, which is, intuitively, the possibility for high level explanations of the model's outputs. The relevance of interpretability of learning models is becoming more important as we delegate ever more important decisions to automated systems. For this reason, NNs are often not considered as the go-to approaches in critical systems, where failures may have catastrophic consequences (e.g. automated cars), or when it is simply required to produce a qualified explanation for any given decision. However, the question of what interpretability should entail, and how it can be enforced, is still a matter of cutting-edge research (Lipton 2016, Zhang et al 2017b).

One of the main practical disadvantages of such deep networks is the computational cost and computational instabilities in training (see the vanishing gradient problem (Hochreiter et al 2001)) and also the size of the dataset, which has to be large (Larochelle et al 2009). With modern technology and datasets, both obstacles are becoming less prohibitive, which has lead to a minor revolution in the field of ML.

Not all ANNs are feed-forward: recurrent NNs allow for the backpropagation of signals. Particular examples of such networks are so-called Hopfield networks (HNs), Boltzmann machines (BMs) and long short-term memory (LSTM) networks, which are often used for different purposes than feed-forward networks.

In HNs, we deal with one layer, where the outputs of all the neurons serve as inputs to the same layer. The network is initialized by assigning binary values (traditionally  −1 and 1 are used, for reasons of convenience) to the neurons (more precisely, some neurons are set to fire, and some not), which are then processed by the network, leading to a new configuration. This update can be synchronous (the output values are 'frozen' and all the second-round values are computed simultaneously) or asynchronous (the update is done one neuron at a time in a random order). The connections in the network are represented by a matrix of weights $(w_{ij})_{ij},$ specifying the connection strength between the ith and the jth neuron. The neurons are perceptrons, with a threshold activation function, given by the local threshold vector $(\theta_i)_i$. Such a dynamical system, under a few mild assumptions (Hopfield 1982), converges to a configuration (i.e. a bit-string) which (locally) minimizes the energy functional

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle E({\bf s}) = -\frac{1}{2} \sum_{ij} w_{ij} s_i s_j + \sum_{i} \theta_i s_i, \label{ising} \nonumber \end{align} \tag{ 2 }$$

with $\ {\bf s} = (s_i)_i, \ s_i \in \{-1, 1 \}$, that is, the Ising model. In general, this model has many local minima, which depend on the weights w_ij and the thresholds, which are often set to zero. Hopfield provided a simple algorithm (called Hebbian learning, after D. Hebb for historical reasons (Hopfield 1982)), which enables one to 'program' the minima—in other words, given a set of bit-strings S (more precisely, strings of signs  +1/−1), one can find the matrix w_ij such that exactly those strings S are local minima of the resulting functional E. Such programmed minima are then called stored patterns. Furthermore, Hopfield's algorithm achieved this in a manner which is local (the weights w_ij depend only on the ith and jth bits of the targeted strings, allowing parallelizability), incremental (one can modify the matrix w_ij to add a new string without having to keep the old strings in memory) and immediate. Immediateness means that the computation of the weight matrix is not a limiting, but finite process. Violating incrementality would lead to a lazy algorithm (see section 1.2.3), which can be sub-optimal in terms of memory requirements, but often also computational complexity²⁴. It was shown that the minima of such a trained network are also attractive fixed-points, with a finite basin of attraction. This means that if a trained network is fed a new string and let run, it will (eventually) converge to a pattern which is closest to it (the distance measure that is used depends on the learning rule, but typically it is the Hamming distance, i.e. the number of entries where the strings disagree). Such a system then forms an associative memory, also called a content-addressable memory (CAM). CAMs can be used for supervised learning (the 'labels' are the stored patterns) and, conversely, supervised learning machinery can be used for CAM²⁵. An important feature of HNs is their capacity: how many distinct patterns it can store²⁶. For the Hebbian update rule this number scales as $O(n/\log(n))$, where n is the number of neurons, which Storkey (1997) improved to $O(n/\sqrt{\log(n)})$. In the meantime, more efficient learning algorithms have been invented (Hillar and Tran 2014). Aside from applications as CAMs, due to the representation in terms of the energy functional in equation (2) and the fact that the running of HNs minimize it, early on they were also considered for tasks of optimization (Hopfield and Tank 1985). The operative isomorphism between HNs and the Ising model, technically, holds only in the case of a zero-temperature system. BMs generalize this. Here, the value of the ith neuron is set to  −1 or 1 (called 'off' and 'on' in literature, respectively) with probability

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle p(i=-1) = \left(1+\exp \left(-\beta \Delta E_i \right) \right)^{-1},\ {\rm with~ }\Delta E_{i}=\sum _{j}w_{ij}\,s_{j}+\theta _{i}, \label{boltz} \nonumber \end{align} \tag{ 3 }$$

where $\Delta E_{i}$ is the energy difference between the configurations with the ith neuron being on or off, assuming the connections ${\bf w}$ are symmetric and β is the inverse temperature of the system. In the limit of infinite running time, the network's configuration is given by the (input-state invariant) Boltzmann distribution over the configurations, which depends on the weights ${\bf w}$, local thresholds (weights) $\bf{\theta}$ and the temperature. BMs are typically used in a generative fashion, to model and sample from (conditional) probability distributions. In the simplest variant, the training of the network attempts to ensure that the limiting distribution of the network matches the observed frequencies in the dataset. This is achieved by the tuning of the parameters ${\bf w}$ and $\bf{\theta}$. The structure of the network dictates how complicated a distribution can be represented. To capture more complicated distributions, over, say, k-dimensional data, the BMs have N  >  k neurons. k of them will be denoted as visible units and the remainder are called hidden units, and they capture latent, not directly observable, variables of the system which generated the dataset and which we are in fact modeling. Training such networks consists in a gradient ascent of the log-likelihood of observing the training data in the parameter space. While this seems conceptually simple, it is computationally intractable, in part because it requires accurate estimates of probabilities of equilibrium distributions, which are hard to obtain. In practice, this is mitigated by using restricted BMs, where the hidden and visible units form the partition of a bipartite graph (so only connections between hidden and visible units exist). (Restricted) BMs have a large spectrum of applications including providing generative models, producing new samples from the estimated distribution; as classifiers, via conditioned generation; as feature extractors, a form of unsupervised clustering; and as building blocks of deep architectures (Larochelle et al 2009). BMs can be 'stacked' in multiple layers, in analogy to deep NNs to form deep BMs²⁷.

The utility of BM-based architectures is mostly limited by the cost of training—for instance, the cost of obtaining equilibrium Gibbs distributions, or by the errors stemming from heuristic training methods such as contrastive divergence (Larochelle et al 2009, Bengio and Delalleau 2009, Wiebe et al 2014c).

The back-propagating nature of information flow in recurrent NNs can also be used as a means to affect the action of the network on the current data input, depending on the previous input(s). This memory effect was shown to be useful in the processing of time-series, such as natural language processing. For a review of recurrent NNs applied to the learning of sequential data we refer the reader to Lipton et al (2015). Arguably the most successful models in this domain comprise LSTM networks (Hochreiter and Schmidhuber 1997). The simplest recurrent networks already have short-term memory capacities: e.g. an 'identity' neuron with a back-propagating connection can forward information from a previous step to the subsequent step, as part of input to another neuron (or itself). However, LSTMs are constructed so that the network can be trained to preserve signals (i.e. data points at a given instance in time) for arbitrarily long intervals. Similar results have recently also been obtained by a slightly simpler model of gated recurrent units (Chung et al 2014). LSTM and closely related models are currently the go-to methods behind many cutting edge technologies, specifically those pertaining to speech recognition (Wired 2017) and machine translation (Wu et al 2016).

Modern advances in NN approaches to ML also involve various combined architectures which are targeted to various shortcomings of the more standard methods. We will just briefly mention a few such approaches relevant for this review. In domain-adversarial NN training (Ganin et al 2016), one performs supervised learning, while ensuring that the resulting classifier will also perform well on similar domains. This is achieved by using two datasets, called the source domain (a labeled set) and the target domain (which may be unlabeled), and by training a feature extracting NN such that two competing properties are maintained: from the extracted features, distinction between the domains should be impossible, while correct prediction of the data labelings from the source set should be possible. This is achieved by using two NNs (a domain predictor, which should ultimately fail; and a label classifier, which should not fail). Conceptually related pairings of unsupervised and supervised methods also occur in generative scenarios. In the highly successful generative adversarial nets (Goodfellow et al 2014) approach, a generative model is trained to generate new samples based on a input dataset. The generative model is put in opposition to a discriminative model (often a convolutional network), which is trained to distinguish between true examples from the input dataset and the outputs of the generative model. Finally, we mention variational autoencoders (VAs) as one of the most successful approaches for generative models (Kingma and Welling 2013, Doersch 2016). In VAs, very roughly, one combines a compressing encoder (e.g. a feed-forward NN with significantly fewer output than input neurons) with a decoding network, which aims to recover the whole input. Such a structure is often called an autoencoder. In VAs, it is additionally enforced that the distribution output by the encoder (given the dataset), approximately follows the standard normal distribution. If the network is trained to decode correctly while the distribution of the 'bottleneck layer' (connecting the encoder and decoder) approximately follows a known easy-to-generate distribution P, this offers a direct means of using the VA as a generative model—one simply samples from P and applies the decoder. The performance of VAs is often compared to that of (restricted) BMs. Often mentioned advantages of the VA approach include the fact that they are applicable to models beyond NNs and that the training may be more efficient. For instance, if a VA is built from feed-forward NNs, it can be trained essentially using just the standard and efficient NN machinery.

Novel NN-based architectures have been emerging at an accelerated rate in recent years, in part motivated by the available computing power which allows such complex models to be trained. However, while such more complex models may offer record-setting performances, they certainly lead us further away from interpretable scenarios, where we can understand how and why the system works, in a clean formal way²⁸. One model which does allow such a clean treatment is the support vector machine, which we describe next.

Support vector machines (SVMs) form a family of perhaps best understood approaches for solving classification problems. The basic idea behind SVMs is that a natural way to classify points based on a dataset $\{{\bf x}_i, y_i \}_i,$ for binary labels $y_i \in \{-1, 1\},$ is to generate a hyperplane separating the negative instances from the positive ones. Such observations are not new and, indeed, perceptrons, briefly discussed in the previous section, perform the same function.

Such a hyperplane can then be used to classify all points. Naturally, not all sets of points allow this (those that do are called linearly separable), but SVMs are further generalized to deal with sets which are not linearly separable using so-called kernels. Kernels, effectively, realize non-linear mappings of the original dataset to higher dimensions where they may become separable, depending on a few technical conditions²⁹, and by allowing a certain degree of misclassification, which leads to so-called 'soft-margin' SVMs.

Even in the case where the dataset is linearly separable, there will still be many hyperplanes doing the job. This leads to various variants of SVMs, but the basic variant identifies a hyperplane which: (a) correctly splits the training points and (b) maximizes the so-called margin: the distance of the hyperplane to the nearest point (see figure 7).

Zoom In Zoom Out Reset image size

The distance of choice is most often the geometric Euclidean distance, which leads to so-called maximum margin classifiers. In high-dimensional spaces, in general the maximization of the margin ends in a situation where there are multiple  +1 and  −1 instances of training data points which are equally far from the hyperplane. These points are called support vectors. The finding of a maximum margin classifier corresponds to finding a normal vector ${\bf w}$ and offset b of the separating hyperplane, which corresponds to the optimization problem

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\bf w}^\ast= {\rm argmin}_{{\bf w}, b} \frac{1}{2}\| {\bf w} \|^2 \nonumber \end{align} \tag{ 4 }$$

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm such ~that}\ y_i ({\bf w} \cdot {\bf x}_i+b) \geqslant 1. \nonumber \end{align} \tag{ 5 }$$

The formulation above is actually derived from the basic problem by noting that we may arbitrarily and simultaneously scale the pair $({\bf w}, b)$ without changing the hyperplane. Therefore, we may always choose a scaling such that the realized margin is 1, in which case, the margin corresponds to $\|{\bf w} \|^{-1}$, which simply maps a maximization problem to a minimization problem as above. The square ensures the problem is stated as a standard quadratic programming problem. This problem is often expressed in its Lagrange dual form, which reduces to

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle (\alpha^\ast_1 ,\ldots \alpha^\ast_N) = {\rm argmin}_{\alpha_1 \ldots \alpha_N} \left( \sum_{i} \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j{\bf x}_i \cdot {\bf x}_j \right) \label{inner} \nonumber \end{align} \tag{ 6 }$$

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm such ~that}\ \alpha_i\geqslant 0\ {\rm and}\ \sum_{i}\alpha_iy_i =0 \label{alphas}, \nonumber \end{align} \tag{ 7 }$$

where the solution of the original problem is given by

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\bf w}^\ast = \sum_{i}y_i\alpha_i {\bf x}_i. \nonumber \end{align} \tag{ 8 }$$

In other words, we have expressed ${\bf w}^\ast$ in the basis of the data vectors, and the data vectors ${\bf x}_i$ for which the corresponding coefficient $\alpha_i$ is non-zero are precisely the support vectors. The offset $b^\ast$ is easily computed having access to one support vector of, say, an instance  +1, denoted ${\bf x}^{+}$, by solving ${\bf w}^{\ast}\cdot {\bf x}^{+}+b^{\ast} = 1$.

The class of a new point ${\bf z}$ can also be computed directly using the support vectors via the following expression

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\bf z} \mapsto ~{\rm sign}~ \left( \sum_{i}y_i\alpha_i {\bf x}_i\cdot {\bf z} + b^\ast \right). \nonumber \end{align} \tag{ 9 }$$

The dual representation of the optimization problem is convenient when dealing with kernels. As mentioned, a way of dealing with data which is not linearly separable is to first map all the points into a higher-dimensional space via a non-linear function $\phi: \mathbb{R}^{m} \rightarrow \mathbb{R}^{n}$, where m  <  n is the dimensionality of the data points. As we can see, in the dual formulation, the data points only appear in terms of inner products ${\bf x}_i \cdot {\bf x}_j$. This leads to the notion of the kernel function k which, intuitively, measures the similarity of the points in the larger space, typically defined by $k({\bf x}_i, {\bf x}_j) = \phi({\bf x}_i){}^{\tau} \phi({\bf x}_j)$. In other words, to train the SVM according to a non-trivial kernel k, induced by the non-linear mapping ϕ, the optimization line in equation (6) will be replaced with ${\rm argmin}_{\alpha_1 \ldots \alpha_N} \left( \sum_{i} \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j k({\bf x}_i,{\bf x}_j) \right).$ The offset is computed analogously, using just one application of ϕ. The evaluation of a new point is given in the same way with ${\bf z} \mapsto {\rm ~sign~} \left( \sum_{i}y_i\alpha_i k({\bf x}_i, {\bf z}) + b^\ast \right)$. In other words, the data points need not be explicitly mapped via ϕ, as long as the map-inducing inner product $k(\cdot, \cdot)$ can be computed more effectively. The choice of the kernel is critical in the performance of the classifier, and the finding of good kernels is non-trivial and often solved by trial and error.

While increasing the dimension of the extended space (co-domain of ϕ) may make data points more linearly separable (i.e. fewer mismatches for the optimal classifier), in practice they will not be fully separable (and furthermore, increasing the kernel dimension comes with a cost which we elaborate on later). To resolve this, SVMs allow for misclassification, with various options for measuring the 'amount' of misclassification, inducing a penalty function. A typical approach to this is to introduce so-called 'slack variables' $\newcommand{\x}{X} \xi_i \geqslant 0$ to the original optimization task, so:

$$\begin{align} \newcommand{\e}{{\rm e}} \newcommand{\x}{X} \displaystyle {\bf w}^\ast= {\rm argmin}_{{\bf w}, b} \left( \frac{1}{2}\| {\bf w} \|^2 + C \sum_{i} \xi_i \right) \nonumber \end{align} \tag{ 10 }$$

$$\begin{align} \newcommand{\e}{{\rm e}} \newcommand{\x}{X} \displaystyle {\rm such~ that}\ y_i ({\bf w} \cdot {\bf x}_i+b) \geqslant 1 - \xi_i. \nonumber \end{align} \tag{ 11 }$$

If the value $\newcommand{\x}{X} \xi_i$ of the optimal solution is between 0 and 1, the point i is correctly classified, but is within the margin, and $\newcommand{\x}{X} \xi_i>1$ denotes a misclassification. The (hyper)parameter C controls the relative importance we place on minimizing the margin norm, versus the importance we place on misclassification. Interestingly, the dual formulation of the above problem is near identical to the hard-margin setting discussed thus far, with the small difference that the parameters $\alpha_i$ are now additionally constrained with $\alpha_i \leqslant C$ in equation (7). SVMs, as described above, have been extensively studied from the perspective of computational learning theory and have been connected to other learning models. In particular, their generalization performance, which, roughly speaking, characterizes how well a trained model³⁰ will perform beyond the training set can be analyzed. This is the most important feature of a classifying algorithm. We will briefly discuss generalization performance in section 2.2.2. We end this short review of SVMs by considering a non-standard variant, which is interesting for our purposes as it has been beneficially quantized. SVMs as described are trained by finding the maximal margin hyperplane. Another model, called least-squares SVM (LS-SVM), takes a regression (i.e. data-fitting) approach to the problem, and finds a hyperplane which, essentially, minimizes the least square distance of the vector of labels, and the vector of distances from the hyperplane, where the ith entry of the vector is given with $({\bf w} \cdot {\bf x}_i+b)$. This is effected by a small modification of the soft-margin formulation:

$$\begin{align} \newcommand{\e}{{\rm e}} \newcommand{\x}{X} \displaystyle {\bf w}^\ast_{\rm LS}= {\rm argmin}_{{\bf w}, b} \frac{1}{2}\| {\bf w} \|^2 + C \sum_{i} \xi_i^2 \nonumber \end{align} \tag{ 12 }$$

$$\begin{align} \newcommand{\e}{{\rm e}} \newcommand{\x}{X} \displaystyle {\rm such ~that}\ y_i ({\bf w} \cdot {\bf x}_i+b) =1 - \xi_i, \nonumber \end{align} \tag{ 13 }$$

where the only two differences are that the constraints are now equalities and the slack variables are squared in the optimization expression. This seemingly innocuous change causes differences in performance, but also in the training. The dual formulation of the latter optimization problem reduces to a linear system of equations:

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \left[\begin{array}{@{}cc@{}}0&1_{}^{T} \nonumber \\1_{N}&\Omega +\gamma ^{-1}I_{}\end{array}\right]\left[\begin{array}{@{}cc@{}}b \nonumber \\ \boldsymbol{\alpha}\end{array}\right]=\left[\begin{array}{@{}cc@{}}0 \nonumber \\Y \end{array}\right], \label{LSSVM:sys} \nonumber \end{align} \tag{ 14 }$$

where 1 is an 'all ones' vector, Y is the vector of labels y_i, b is the offset and γ is a parameter depending on C. $\boldsymbol{\alpha}$ is the vector of the Lagrange multipliers yielding the solution. This vector again stems from the dual problem which we omitted due to space constraints, and which can be found in Suykens and Vandewalle (1999). Finally, Ω is the matrix collecting the (mapped) 'inner products' of the training vectors so $\Omega_{i, j} = k({\bf x}_i, {\bf x}_j),$ where k is a kernel function, in the simplest case, just the inner product. The training of LS-SVMs is thus simpler (and particularly convenient from a quantum algorithms perspective), but the theoretical understanding of the model, and its relationship to the well-understood SVMs, is still a matter of study, with few known results (see e.g. Ye and Xiong (2007)).

While NNs and SVMs constitute two popular approaches for ML tasks (in particular, supervised learning), many other models exist, suitable for a variety of ML problems. Here we very briefly list and describe some such models which have also appeared in the context of quantum ML. While classification typically assigns discrete labels to points, in the case where the labeling function has a continuous domain (say the segment $[0, 1]$) we are dealing with function approximation tasks, often dealt with by using regression techniques. Typical examples here include linear regression, which approximates the relationship of points and labels with a linear function, most often minimizing the least-squares error. More broadly, such techniques are closely related to data-fitting, that is, fitting the parameters of a parametrized function so as to best fit observed (training) data. The k-nearest neighbor algorithm is an intuitive classification algorithm which, given a new point, considers the k nearest training points (with respect to a metric of choice) and assigns the label by a majority vote (if used for classification), or by averaging (in the case of regression, i.e. continuous label values). The mutually related k-means and k-medians algorithms are typically used for clustering: the k specifies the number of clusters, and the algorithm defines them in a manner which minimizes the within-cluster distance to the mean (or median) point.

Another method for classification and regression optimizes decision trees, where each dimension or entry (or more generally a feature³¹) of the new data point influences a move on a decision tree. The depth of the tree is the length of the vector (or number of features) and the degree of each node depends on the possible number of distinct features/levels per entry³². The vertices of the tree specify an arbitrary feature of interest, which can influence the classification result, but most often they consider the overlaps with geometrical regions of the data point space. Decision trees are in principle maximally expressive (can represent any labeling function), but very difficult to train without constraints.

More generally, classification tasks can be treated as the problem of finding a hypothesis $h: \mathrm{Data} \rightarrow \mathrm{Labels}$ (in ML, the term hypothesis is essentially synonymous with the term classifier, also called a learner) which is from some family H, which minimizes error (or loss) under some loss function. For instance, the hypotheses realized by SVMs are given by the hyperplanes (in the kernel space), and in neural nets they are parametrized by the parameters of the nets: geometry, thresholds, activation functions, etc. In addition to loss terms, the minimization of which is called empirical risk minimization, ML applications benefit from adding an additional component to the objective function: the regularization term, the purpose of which is to penalize complex functions which could otherwise lead to poor generalization performance; see section 2.2.2. The choices of loss functions, regularization terms and classes of hypotheses lead to different particular models, and training corresponds to optimization problems given by the choice of the loss function and the hypothesis (function) family. Furthermore, it has been shown that essentially any learning algorithm which requires only convex optimization for training leads to poor performance under noise. Thus non-convex optimization is necessary for optimal learning (see e.g. Long and Servedio (2010) and Manwani and Sastry (2011)).

An important class of meta-algorithms for classification problems are boosting algorithms. The basic idea behind boosting algorithms is the highly non-trivial observation, first proven via the seminal AdaBoost algorithm (Freund and Schapire 1997), that multiple weak classifiers, which perform better than random on distinct parts of the input space, can be combined into an overall better classifier. More precisely, given a set of (weak) hypotheses/classifiers $\{h_j\}, h_j: \mathbb{R}^{n}\rightarrow \{-1, 1\}$, under certain technical conditions, there exists a set of weights $\{w_i\}, w_i \in \mathbb{R}$, such that the composite classifier of the form $hc_{{\bf w}}({\bf x}) = {\rm sign}(\sum_i w_i h_i({\bf x}))$ performs better. Interestingly, a single (weak) learning model can be used to generate the weak hypotheses needed for the construction of a better composite classifier—one which, in principle, can achieve arbitrarily high success probabilities, i.e. a strong learner. The first step of this process is achieved by altering the frequencies at which the training labeled data points appear—one can effectively alter the distributions over the data (in a black-box setting, these can be obtained by, e.g., rejection sampling methods). The training of one and the same model on such differentially distributed datasets can generate distinct weak learners, which emphasize distinct parts of the input space. Once such distinct hypotheses are generated, optimization of the weight w_i of the composite model is performed. In other words, weak learning models can be boosted³³.

Aside from the broad classes of approaches to solve various ML tasks, ML is also often conflated with specific computational tools which are used to solve them. A prominent example of this is the development of algorithms for optimization problems, especially those arising in the training of standard learning models. This includes, e.g., particle swarm optimization, genetic and evolutionary algorithms and even variants of stochastic gradient descent.

ML also relies on other methods including linear algebra tools, e.g. matrix decomposition methods, such as singular value decomposition, QR-, LU- and other decompositions, derived methods such as principal component analysis and various techniques from the field of signal analysis (Fourier, Wavelet, Cosine and other transforms). The latter set of techniques serves to reduce the effective dimension of the dataset and helps combat the curse of dimensionality. The optimization, linear algebra and signal processing techniques and their interplay with quantum information is an independent body of research with enough material to deserve a separate review, and we will only reflect on these methods when needed.

COLT can be understood as a rigorous formalization of supervised learning which stems from a computational complexity theory tradition. The most famous model in COLT is that of probably approximately correct (PAC) learning. We will explain the basic notions of PAC learning on a simple example: optical character recognition. Consider the task of training an algorithm to decide whether a given image (given as a black and white bitmap) of a letter corresponds to the letter 'A', by supplying a set of examples and counterexamples: a collection of images. Each image ${\bf x}$ can be encoded as a binary vector in {0,1}ⁿ (where n  =  height  ×  width of the image).

Assuming that there exists an univocally correct assignment of label 0 (not 'A') and 1 to each image implies there exists a characteristic function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}$ which discerns letters A from other images. Such an underlying characteristic function (or, equivalently, the subset of bit-strings for which it attains value '1') is, in COLT, called a concept. Any (supervised) learning algorithm will first be supplied with a collection of N examples $({\bf x}_i), f(({\bf x}_i))_i$. In some variants of PAC learning, it is assumed that the data points (${\bf x}$) are drawn from some distribution D attaining values in {0,1}ⁿ. Intuitively, this distribution can model the fact that, in practice, the examples that are given to the learner stem from its interaction with the world, which specifies what kinds of 'A's we are more likely to see³⁶. PAC learning typically assumes inductive settings, meaning that the learning algorithm, given a sample set S_N (comprising N identically independently distributed samples from D) outputs a hypothesis $h:\{0, 1\}^{n} \rightarrow \{0, 1\}$ which is, intuitively, the algorithms 'best guess' for the actual concept f. The quality of the guess is measured by the total error (also known as loss, or regret),

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \mathrm{err}_D(h_{S_N}) = \sum_{{\bf x}} P(D = {\bf x}) |h_{S_N}({\bf x}) - f({\bf x})|, \label{errorPAC} \nonumber \end{align} \tag{ 15 }$$

averaged according to the same (training) distribution D, where $h_{S_N}$ is the hypothesis the (deterministic) learning algorithm outputs given the training set S_N. Intuitively, the larger the training set is (N), the smaller the error will be, but this also depends on the actual examples (and thus S_N and D). PAC theory concerns itself with probably (δ), approximately $\newcommand{\e}{{\rm e}} (\epsilon)$ correct learning, i.e. with the following expression:

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle P_{S_{N} \sim D^{N}}\left[ \mathrm{err}_D(h_{S_N}) \leqslant \epsilon \right] \geqslant 1-\delta,\label{PAC} \nonumber \end{align} \tag{ 16 }$$

where $S \sim D$ means S was drawn according to the distribution D. The above expression is a statement certifying that the learning algorithm, having been trained on the dataset sampled from $D,$ will, except with probability δ, have a total error below . We say a concept f is $\newcommand{\e}{{\rm e}} (\epsilon, \delta)$-learnable under distribution D if there exist a learning algorithm and an N such that equation (16) holds, and simply learnable if it is $\newcommand{\e}{{\rm e}} (\epsilon, \delta)$-learnable for all choices of $\newcommand{\e}{{\rm e}} (\epsilon, \delta)$. The functional dependence of N on $\newcommand{\e}{{\rm e}} (\epsilon, \delta)$ (and on the concept and distribution D) is called the sample complexity. In PAC learning, we are predominantly concerned with identifying tractable problems, so a concept/distribution pair $f, D$ is PAC-learnable if there exists an algorithm for which the sample complexity is polynomial in $\newcommand{\e}{{\rm e}} \epsilon^{-1}$ and $\delta^{-1}$. These basic ideas are generalized in many ways. First, in the case where the algorithm cannot output all possible hypotheses, but only a restricted set H (e.g. the hypothesis space is smaller than the total concept space), we can look for the best case solution by substituting the actual concept f with the optimal choice $h^{\ast} \in H$ which minimizes the error in (15) in all the expressions above. Second, we are typically not interested in just distinguishing the letter 'A' from all other letters, but rather recognizing all letters. In this sense, we typically deal with a concept class (e.g. 'letters'), which is a set of concepts, and it is (PAC) learnable if there exists an algorithm for which each of the concepts in the class are (PAC) learnable. If, furthermore, the same algorithm also learns for all distributions D, then the class is said to be (distribution-free) learnable.

COLT contains other models, generalizing PAC. For instance, concepts may be noisy or stochastic. In the agnostic learning model, the labeled examples $({\bf x}, y)$ are sampled from a distribution D over $\{0, 1\}^{n}\times\{0, 1\},$ which also models probabilistic concepts³⁷. Furthermore, in agnostic learning we define a set of concepts $C \subseteq \{c | c: \{0, 1\}^n \rightarrow \{0, 1\} \}$ and, given $D,$ we can identify the best deterministic approximation of D in the set C, given with $\mathrm{opt}_C = \min_{c\in C} \mathrm{err}_D(c)$. The goal of learning is to produce a hypothesis $h \in C$ which performs not much worse than the best approximation $\mathrm{opt}_C,$ in the PAC sense—the algorithm is a $\newcommand{\e}{{\rm e}} (\epsilon, \delta)-$ agnostic learner for D and C if, given access to samples from D, it outputs a hypothesis $h\in C$ such that $\newcommand{\e}{{\rm e}} \mathrm{err}_D(c) \leqslant \epsilon + \mathrm{opt}_C$, except with probability δ.

Another common model in COLT is the exact learning from membership queries model (Angluin 1988), which is, intuitively, related to active supervised learning (see section 1.2.3). Here, we have access to an oracle, a black box, which outputs the concept value $f({x})$ when queried with an example ${x}$. The basic setting is exact, meaning we are required to output a hypothesis which, with a bounded probability (say 3/4), makes no errors whatsoever. In other words, this is PAC learning where $\newcommand{\e}{{\rm e}} \epsilon = 0,$ but we get to choose which examples we are given, adaptively, and δ is bounded away from 1/2. The figure of merit usually considered in this setting is query complexity, which denotes the number of calls to the oracle the learning algorithm uses, and is for most intents and purposes synonymous with sample complexity³⁸. This, in spirit, corresponds to an active supervised learning setting.

Much of PAC learning deals with identifying examples of interesting concept classes which are learnable (or proving that relevant classes are not), but other more general results exist connecting this learning framework. For instance, we can ask whether we can achieve a finite-sampling universal learning algorithm: that is, an algorithm that can learn any concept, under any distribution, using some fixed number of samples N. The No Free Lunch theorems we mentioned previously imply that this is not possible: for each learning algorithm (and $\newcommand{\e}{{\rm e}} \epsilon, \delta$) and any N there is a setting (concept/distribution) which requires more than N samples to achieve $\newcommand{\e}{{\rm e}} (\epsilon, \delta)$-learning.

Typically, the criterion for a problem to be learnable assumes that there exists a classifier whose performance is essentially arbitrarily good—that is, it assumes the classifier is strong. The boosting result in ML, already touched upon in section 2.1.3, shows that settling on weak classifiers, which perform only slightly better than random classification, does not generate a different concept of learnability (Schapire 1990).

Classical COLT has also been generalized to deal with concepts with continuous ranges. In particular, so called p-concepts have range in $[0, 1]$ (Kearns and Schapire 1994). The generalization of the entire COLT to deal with such continuous-valued concepts is not without problems, but nonetheless some of the central results, for instance quantities which are analogs of the VC dimension, and analogous theorems relating this to generalization performance, can still be provided (see Aaronson (2007) for an overview given in the context of the learning of quantum states discussed in section 5.1.1).

COLT is closely related to the statistical learning theory of Vapnik and Chervonenkis (VC theory) which we discuss next.

The statistical learning formalism of Vapnik and Chervonenkis was developed over the course of more than 30 years and in this review we are forced to present just a chosen aspect of the total theory, which deals with generalization performance guarantees. In the previous paragraph on PAC learning, we have introduced the concept of total error, which we will refer to as (total) risk. It is defined as the average over all the data points, which is, for a hypothesis h, given by $R(h) = \mathrm{error}(h) = \sum_{{\bf x}} P(D = {\bf x}) |h({\bf x}) - f({\bf x})|$ (we are switching notation to maintain consistency with the literature of differing communities). However, this quantity cannot be evaluated in practice, as in practice we only have access to the training data. This leads us to the notion of the empirical risk given by

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \hat{R}(h) = \frac{1}{N}\sum_{{\bf {\bf x} \in S_N}} |h({\bf x}) - f({\bf x})|, \nonumber \end{align} \tag{ 17 }$$

where S_N is the training set drawn independently from the underlying distribution D.

The quantity $\hat{R}(h)$ is intuitive and directly measurable. However, the problem of finding learning models which optimize empirical risk alone is not in itself interesting as it is trivially resolved with a look-up table. From a learning perspective, the more interesting and relevant quantity is the performance beyond the training set, which is contained in the unmeasurable $R(h),$ and indeed the task of inductive supervised learning is identifying h which minimizes $R(h)$, given only the finite training set S_N. Intuitively, the hypothesis h which minimizes the empirical risk should also be our best bet for the hypothesis which minimizes $R(h),$ but this can only make sense if our hypothesis family is somehow constrained, at least to a family of total functions: again, a look-up table has zero empirical risk, yet says nothing about what to do beyond. One of the key contributions of VC theory is to establish a rigorous relationship between the observable quantity $\hat{R}(h)$, the empirical risk; the quantity we actually wish to bound $R(h)$, the total risk; and the family of hypotheses our learning algorithm can realize. Intuitively, if the function family is too flexible (as is the case with just look-up tables) a perfect fit on the examples says little. In contrast, having a very restrictive set of hypotheses, say just one (which is independent from the dataset/concept and the generating distribution), suggests that the empirical risk is a fair estimate of the total risk (however bad it may be), as nothing has been tailored for the training set. This brings us to the notion of the model complexity of the learning model, which has a few formalizations, and here we focus on the Vapnik–Chervonenkis dimension of the model (VC dimension)³⁹.

The VC dimension is an integer number assigned to a set of hypotheses $H \subseteq \{h | h: {\bf S} \rightarrow \{0, 1 \} \},$ (e.g. the possible classification functions our learning algorithm can even in principle be trained to realize), where ${\bf S}$ can be, for instance, the set of bit-strings {0,1}ⁿ, or, more generally, say, real vectors in $\mathbb{R}^{n}$. In the context of basic SVMs, the set of hypotheses is 'all hyperplanes'⁴⁰. Consider now a subset C_k of k points in $\mathbb{R}^{n}$ in general position⁴¹. These points can attain binary labels in 2^k different ways. The hypothesis family H is said to shatter the set C if for any labeling $\newcommand{\e}{{\rm e}} \ell$ of the set C_k there exists a hypothesis $h \in H$ which correctly labels the set C_k according to $\newcommand{\e}{{\rm e}} \ell$. In other words, using functions from H we can learn any labeling function on the set C_k of k points in general position perfectly. The VC dimension of H is then the largest k_max such that there exists a set $C_{k_{\rm max}}$ of points in general position which is shattered (perfectly 'labelable' for any labeling) by H. For instance, for n  =  2, 'rays' shatter three points but not 4 (imagine vertices of a square where diagonally opposite vertices share the same label), and in n  =  N, 'hyperplanes' shatter N  +  1 points. While it is beguiling to think that the VC dimension corresponds to the number of free parameters specifying the hypothesis family, this is not the case⁴². The VC theorem (in one of its variants) (Devroye et al 1996) then states that the empirical risk matches total risk up to a deviation which decays in the number of samples, but grows in the VC dimension of the model, more formally:

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle P\left( \hat{R}(h_{S_N}) - R(h_{S_N}) \leqslant \epsilon \right) = 1- \delta \nonumber \end{align} \tag{ 18 }$$

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \epsilon = \sqrt{\frac{d \left( \log(2N/d) +1 \right)}{N} - \frac{\log(\delta/4)}{N} }, \label{VCth} \nonumber \end{align} \tag{ 19 }$$

where d is the VC dimension of the model, N the number of samples and $h_{S_N}$ is the hypothesis output by the model given the training set S_N, which is sampled from the underlying distribution D. The underlying distribution D implicitly appears also in the total risk R. Note that the chosen acceptable probability of incorrectly bounding the true error, δ, contributes only logarithmically to the misestimation bound , whereas the VC dimension and the number of samples contribute (mutually inversely) linearly to the square of .

The VC theorem suggests that the ideal learning algorithm would have a low VC dimension (allowing a good estimate of the relationship between the empirical and total risk), while at the same time performing well on the training set. This leads to a learning principle called structural risk minimization. Consider a parametrized learning model (say parametrized by an integer $l \in \mathbb{l}$) such that each l induces a hypothesis family H^l, each more expressive then the previous, so $H^{l} \subseteq H^{l+1}$. Structural risk minimization (contrasted to empirical risk minimization which just minimizes empirical risk) takes into account that in order to have (a guarantee on) good generalization performance we need to have both good observed performance (i.e. low empirical risk) and low model complexity. High model complexity induces risk stemming from the structure of the problem, manifested in common issues such as data overfitting. In practice, this is achieved by considering (meta-)parametrized models, like {H^l}, where we minimize a combination of l (influencing the VC dimension) and the empirical risk associated to H^l. In practice, this is realized by adding a regularization term to the training optimization, so generically the (unregularized) learning process resulting in ${\rm argmin}_{h \in H} \hat{R}(h)$ is updated to ${\rm argmin}_{h^{l} \in H^{l}} \left(\hat{R}(h) + {\rm reg}(l) \right)$, where ${\rm reg}(\cdot)$ penalizes the complexity of the hypothesis family, or just the given hypothesis.

VC dimension is also a vital concept in PAC learning, connecting the two frameworks. Note first that a concept class $C,$ which is a set of concepts, is also a legitimate set of hypotheses and thus has a well-defined VC dimension d_C. Then the sample complexity of $\newcommand{\e}{{\rm e}} (\epsilon, \delta)-$(PAC)-learning of C is given by $\newcommand{\e}{{\rm e}} O\left( (d_C + \log{1/\delta}) \epsilon^{-1} \right)$.

Some of the approaches developed for supervised learning and discriminative models have, to some extent, been extended to the domain of unsupervised learning as well. Such results are much rarer and more specialized and beyond the scope of this review. However, for an example of the types of results that have been established, we refer the interested reader to the following work of Seldin and Tishby (2010).

Learning efficiency and learnability for reinforcement learning.

The generic scenarios of Hamiltonian estimation, a common instance of metrology in the quantum domain, consider a quantum system governed by a (partially unknown) Hamiltonian within a specified family $H(\boldsymbol{\theta}),$ where $\boldsymbol{\theta} = (\theta_1, \ldots, \theta_n),$ is a set of parameters. Roughly speaking, Hamiltonian estimation deals with the task of identifying the optimal methods (and the performance thereof) for estimating the Hamiltonian parameters.

This amounts to optimizing the choice of initial states (probe states) which will evolve under the Hamiltonian and the choice of the subsequent measurements, which uncover the effect the Hamiltonian had, and thus, indirectly, the parameter values⁵⁹. This prolific research area considers many restrictions, variations and generalizations of this task. For instance, one may assume settings in which we either have control over the Hamiltonian evolution time t or it is fixed so that t  =  t₀, which are typically referred to as frequency and phase estimation, respectively. Further, the efficiency of the process can be measured in multiple ways. In a frequentist approach, one is predominantly interested in estimation strategies which, roughly speaking, allow for the best scaling of precision of the estimate, as a function of the number of measurements. The quantity of interest is the so-called quantum Fisher information, which bounds and quantifies the scaling. Intuitively, in this setting, also called the local regime, many repetitions of measurements are typically assumed. Alternatively, in the Bayesian, or single-shot, regime the prior information, which is given as a distribution over the parameter to be estimated, and its update to the posterior distribution given a measurement strategy and outcome are central objects (Jarzyna and Demkowicz-Dobrzański 2015). The objective here is the identification of preparation/measurement strategies which optimally reduce the average variance of the posterior distribution, which is computed via Bayes' theorem.

One of the key interests in this problem is that the utilization of arguably genuine quantum features such as entanglement, squeezing etc in the structure of the probe states and measurements may lead to provably more efficient estimation than is possible by so-called classical strategies for many natural estimation problems. Such quantum enhancements are potentially of immense practical relevance (Giovannetti et al 2011). The identification of optimal scenarios has been achieved in certain 'clean' theoretical scenarios, which are, however, often unrealistic or impractical. It is in this context that ML-flavored optimization and other ML approaches can help.

Interesting estimation problems, from an ML perspective, can already be found in the simple examples of a phase shift in an optical interferometer, where one of the arms of an otherwise balanced interferometer contains a phase shift of θ. Early on, it was shown that given an optimal probe state with mean photon number N and an optimal (so-called canonical) measurement, the asymptotic phase uncertainty can decay as N⁻¹ (Sanders and Milburn 1995)⁶⁰, known as the Heisenberg limit. In contrast, the restriction to 'simple measurement strategies' (as characterized by the authors), involving only photon number measurements in the two output arms, achieves a quadratically weaker scaling of $\sqrt{N^{-1}},$ referred to as the standard quantum limit. This was proven in more general terms: the optimal measurements cannot be achieved by the classical post-processing of photon number measurements of the output arms but constitute an involved, experimentally unfeasible POVM (Berry and Wiseman 2000). However, in Berry and Wiseman (2000) it was shown how this can be circumvented by using 'simple measurements', provided they can be altered in run-time. Each measurement consists of a photon number measurement of the output arms and is parametrized by an additional controllable phase shift of ϕ in the free arm—equivalently, the unknown phase can be tweaked by a chosen ϕ. The optimal measurement process is an adaptive strategy: an entangled N-photon state is prepared (see e.g. Berry et al (2001)), the photons are sequentially injected into the interferometer and photon numbers are measured. At each step, the measurement performed is modified by choosing a different phase shift ϕ, which depends on previous measurement outcomes. In Berry and Wiseman (2000) and Berry et al (2001), an explicit strategy was given which achieves the Heisenberg scaling of the optimal order $O(1/N)$. However, for N  >  4 it was shown this strategy is not strictly optimal.

This type of planning is hard as it reduces to the solving of non-convex optimization problems⁶¹. The field of ML deals with such planning problems as well, and so many optimization techniques have been developed for this purpose. The applications of such ML techniques, specifically particle swarm optimization, were first suggested in the pioneering works of Hentschel and Sanders (2010, 2011) and later in Sergeevich and Bartlett (2012). In subsequent work, perhaps more well-known methods of differential evolution have been demonstrated to be superior and more computationally efficient (Lovett et al 2013).

ML techniques can also be employed in significantly more general settings of quantum process estimation. More general Hamiltonian estimation settings consider a partially controlled evolution given by $H_C(\boldsymbol{\theta}),$ where C is a collection of control parameters of the system. This is a reasonable setting in e.g. the production of quantum devices, which have controls (C), but whose actual performance (dependent on $\boldsymbol{\theta}$) needs to be confirmed. Further, since production devices are seldom identical, it is beneficial to even further generalize this setting, by allowing the unknown parameters $\boldsymbol{\theta}$ to be only probabilistically characterized. More precisely, they are probabilistically dependent on another set of hyperparameters $\newcommand{\z}{Z} \boldsymbol{\zeta} = (\zeta_1, \ldots, \zeta_k)$, such that the parameters $\boldsymbol{\theta}$ are distributed according to a known conditional probability distribution $\newcommand{\z}{Z} P(\boldsymbol{\theta}|\boldsymbol{\zeta})$. This generalized task of estimating the hyperparameters $\newcommand{\z}{Z} \boldsymbol{\zeta}$ thus allows the treatment of systems with inherent stochastic noise, when the influence of noise is understood (given by $\newcommand{\z}{Z} P(\boldsymbol{\theta}|\boldsymbol{\zeta})$). Such very general scenarios are addressed in Granade et al (2012), relying on classical learning techniques of Bayesian experimental design (BED) (Loredo 2004), combined with Monte Carlo methods. The details of this method are beyond the scope of this review, but, roughly speaking, BED assumes a Bayesian perspective on the experiments of the type described above. The estimation methods of the general problem (ignoring the hyperparameters and noise, for simplicity, although the same techniques apply) realize a conditional probability distribution $P(\boldsymbol{d} | \boldsymbol{\theta} ; C)$ where $\boldsymbol{d}$ corresponds to experimental data, i.e. measurement outcomes collected in the experiment. Assuming some prior distribution over hidden parameters ($P(\boldsymbol{\theta} | C)$), the posterior distribution, given experimental outcomes, is given via Bayes' theorem by

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle P(\boldsymbol{\theta} |\boldsymbol{d} ; C) = \frac{P(\boldsymbol{d} | \boldsymbol{\theta} ; C) P(\boldsymbol{\theta} | C)}{P(\boldsymbol{d} | C)}. \nonumber \end{align} \tag{ 22 }$$

The evaluation of the above is already non-trivial, principally because the normalization factor $P(\boldsymbol{d} | C)$ includes an integration over the parameter space. Further, of particular interest are scenarios where an experiment is iterated many times. In this case, analogously to the adaptive setting for metrology discussed above, it is beneficial to tune the control parameters C dependent on the outcomes.

BED (Loredo 2004) tackles such adaptive settings by selecting the subsequent control parameters C so as to maximize a utility function⁶² for each update step. The Bayes updates consist of the computing of $P(\boldsymbol{\theta} |\boldsymbol{d}_1, \ldots, \boldsymbol{d}_{l-1} \boldsymbol{d}_k) \propto P(\boldsymbol{d_k} | \boldsymbol{\theta}) P (\boldsymbol{\theta} | \boldsymbol{d}_1, \ldots, \boldsymbol{d}_{l-1})$ at each step. The evaluation of the normalization factor $P(\boldsymbol{d} | C){}^{-1}$ is, however, also non-trivial, as it includes an integration over the parameter space. In Granade et al (2012) this integration is tackled via numerical integration techniques, namely sequential Monte Carlo, yielding a novel technique for robust Hamiltonian estimation.

The robust Hamiltonian estimation method was subsequently expanded to use access to trusted quantum simulators, which forms a more powerful and efficient estimation scheme (Wiebe et al 2014b)⁶³, which was also shown to be robust to moderate noise and imperfections in the trusted simulators (Wiebe et al 2014a). A restricted version of the method of estimation with simulators was experimentally realized in Wang et al (2017). More recently, connected to the methods of robust Hamiltonian estimation, Bayesian and sequential Monte Carlo based estimation have further been combined with particle swarm optimization techniques (Stenberg et al 2016). There the goal was to achieve reliable coupling strength and frequency estimation in simple decohering systems, corresponding to realistic physical models. More specifically, the studied problem is the estimation of field–atom coupling terms and the mode frequency term in the Jaynes–Cummings model. The controlled parameters are the local field strength and measurements are done via swap spectroscopy.

Aside from using ML to perform partial process tomography of controlled quantum systems, ML can also help in genuine problems of quantum control, specifically, the design of target quantum gates. This forms the next topic.

The paradigmatic setting in quantum control considers a Hamiltonian with a controllable (c) and a drift part (dr), e.g. $H(C(t)) = H_{\rm dr} + C(t) H_{\rm c}$. The free part is modulated via a (real-valued) control field $C(t)$. The resulting time-integrated operator $\newcommand{\e}{{\rm e}} U = U[C(t)] \propto \exp \left( - {\rm i} \int_{0}^T {\rm d}t H(C(t)) \right)$, over some finite time T, is a function of the chosen field function $C(t)$. The typical goal is to specify the control field $C(t)$ which maximizes the transition probability from some initial state $\newcommand{\ket}[1]{\left| #1 \right\rangle} \ket{0}$ to a final state $\newcommand{\ket}[1]{\left| #1 \right\rangle} \ket{\phi},$ i.e. to find $\newcommand{\ket}[1]{\left| #1 \right\rangle} \newcommand{\bra}[1]{\left\langle #1 \right|} {\rm argmax}_{C} |\bra{\phi} U[C(t)] \ket{0}|$⁶⁴. Generically, the mappings $C(t) \mapsto U[C(t)]$ are highly involved but, nonetheless, empirically it was shown that greedy optimization approaches provide optimal solutions (which is the reason greedy approaches dominate in practice). This empirical observation was later elucidated theoretically (Rabitz et al 2004), suggesting that in generic systems local minima do not exist, which leads to easy optimization (see also Russell and Rabitz (2017) for a more up-to-date account). This is good news for experiments, but also suggests that quantum control has no need for advanced ML techniques. However, as is often the case with claims of such generality, the underlying subtle assumptions are fragile and can often be broken. In particular, greedy algorithms for optimizing the control problem as above can fail, even in the low dimensional case, if we simply place rather reasonable constraints on the control function and parameters. Already for 3-level and 2-qubit systems with constraints on the allowed evolution time t and the precision of the linearization of the time-dependent control parameters⁶⁵, it is possible to construct examples where greedy approaches fail, yet global (derivative-free) approaches, in particular differential evolution, succeed (Zahedinejad et al 2014).

Another example of hard off-line control concerns the design of high fidelity single-shot three-qubit gates⁶⁶, which is in Zahedinejad et al (2015) and Zahedinejad et al (2016) addressed using a specialized novel optimization algorithm the authors called subspace-selective self-adaptive differential evolution (SuSSADE).

An interesting alternative approach to gate design is by utilizing larger systems. Specifically designed larger systems can naturally implement desired evolutions on a subsystem, without the need for time-dependent control (see QC with always-on interaction (Benjamin and Bose 2003)). In other words, local gates are realized despite the fact that the global dynamics is unmodulated. The non-trivial task of constructing such global dynamics for the Toffoli gate is in Banchi et al (2016) tackled by a method which relies upon stochastic gradient descent and draws from supervised learning techniques.

Complementary to off-line methods, here we assume access to an actual quantum experiment and the identification of optimal strategies relies on on-line feedback. In these cases, the quantum experiment need not be fully specified beforehand. Further, the required methodologies lean towards on-line planning and RL, rather than optimization. In the case where optimization is required, the parameters of optimization are different due to experimental constraints; see Shir et al (2012) for an extensive treatment of the topic.

The connections between on-line methods which use feedback from experiments to 'steer' systems to desired evolutions have been connected to ML in early works (Bang et al 2008, Gammelmark and lmer 2009). These exploratory works deal with generic control problems via experimental feedback and have, especially at the time, remained mostly unnoticed by the community. In more recent times, feedback-based learning and optimization has received more attention. For instance, in Chen et al (2014) the authors have explored the applicability of a modified Q-learning algorithm for RL (see section 2.3) on canonical control problems. Further, the potential of RL methods had been discussed in the context of optimal parameter estimation, but also typical optimal control scenarios, in Palittapongarnpim et al (2016). In the latter work, the authors also provide a concise yet extensive overview of related topics and outline a perspective which unifies various aspects of ML and RL in an approach to resolve hard quantum measurement and control problems. In Clausen and Briegel (2016), RL based on PS updates was analyzed in the context of general control-and-feedback problems. Finally, ideas of unified computational platforms for quantum control, albeit without explicit emphasis on ML techniques, had been previously provided in Machnes et al (2011).

In the next section, we further coarse-grain our perspective to consider scenarios where ML techniques control various gates and more complex processes, and even help us learn how to do interesting experiments.

The simplest example of involved ML machinery being used to generate control of slightly more complex systems was done in the context of the problem of dynamical decoupling for quantum memories. In this scenario, a quantum memory is modeled as a system coupled to a bath (with a local Hamiltonian for the system (H_S) and the bath H_B) and decoherence is realized by a coupling term H_SB; the local unitary errors are captured by H_S. The evolution of the total Hamiltonian $H_{\rm noise}= H_{\rm S} + H_{\rm B} + H_{\rm SB}$ would destroy the contents of the memory, but this can be mitigated by adding a controllable local term H_C acting on the system alone⁶⁷. Certain optimal choices of the control Hamiltonian H_C are known. For instance, we can consider the scenario where H_C is modulated so that it implements instantaneous⁶⁸ Pauli-X and Pauli-Y unitary operations, sequentially, at intervals $\Delta t$. As this interval, which is also the time of the decoherence-causing free evolution, approaches zero, so $\Delta t \rightarrow 0$, this process is known to ensure perfect memory. However, the moment the setting is made more realistic, allowing finite $\Delta t$ times, the space of optimal sequences becomes complicated. In particular, optimal sequences start depending on $\Delta t,$ the form of the noise Hamiltonian and total evolution time.

To identify optimal sequences, in August and Ni (2017), the authors employ a recurrent NN, specifically the LSTM (see section 2.1.1 for details), which is trained to generate sequences which minimize final noise. The entire sequences of pulses (Pauli gates) which the networks generated were shown to outperform well-known sequences.

In a substantially different setting, where interaction necessarily arises, the authors studied how AI/ML techniques can be used to make quantum protocols themselves adaptive. Specifically, the authors applied RL methods based on projective simulation (PS) (Briegel and De las Cuevas 2012) (see section 7.1) to the task of protecting QC from local stray fields (Tiersch et al 2015). In MBQC (Raussendorf and Briegel 2001, Briegel et al 2009), the computation is driven by performing adaptive single-qubit projective measurements on a large entangled resource state, such as the cluster state (Briegel and Raussendorf 2001, Raussendorf and Briegel 2001). In a scenario where the resource state is exposed to a stray field, each qubit undergoes a local rotation. To mitigate this, in Tiersch et al (2015), the authors introduce a learning agent which 'plays' with a local probe qubit, initialized in, say, the  +1 eigenstate of $\sigma_x$, denoted by $\newcommand{\ket}[1]{\left| #1 \right\rangle} \ket{+}$, learning how to compensate for the unknown field. In essence, given a measurement (preparation), the agent chooses the next measurement direction (effectively guessing its evolution), obtaining a reward whenever a  +1 outcome is observed. The agent is thus trained to compensate for the unknown field, and serves as an 'interpreter' between desired measurements and the measurements which should be performed in the given setting (i.e. in the given field with given frequency of measurements $(\Delta t)$); see figure 11. The problem of mitigating such fixed stray fields could naturally be solved with non-adaptive methods where we use knowledge about the system to solve our problem, by e.g. measuring the field and adapting accordingly, or by using fault-tolerant constructions. From a learning perspective, such direct methods have a few shortcomings which may be worth presenting for didactic purposes. Fault tolerant methods are clearly wasteful, as they fail to gain or utilize any knowledge about the noise processes. In contrast, field estimation methods learn too much, and assume a model of the world. In particular, to compensate for the measured field we need to use quantum mechanics, specifically the Born rule. In contrast, the RL approach is model-free: the Born rule plays no part, and 'correct behavior' is learned and established exclusively based on experience. This is conceptually different, but also operatively critical, as model-free approaches allow for more autonomy and flexibility (i.e. the same machinery can be used in more settings without intervention)⁶⁹. Regarding learning too much, one of the basic principles of statistical learning posits that 'when solving a problem of interest, one should not solve a more general problem as an intermediate step' (Vapnik 1995), which is intuitive. The problem of the presented setting is 'how to adapt the measurement settings', not 'characterize the stray fields'. While in the present context the information-theoretic content of the two questions may be the same, it should be easy to imagine that if more complex fields are considered full process characterization contains a lot more information than needed to optimally adapt the local measurements. The approaches of Tiersch et al (2015) can further be generalized to utilize information from stabilizer measurements (Orsucci et al 2016) or, similarly, outcomes of syndrome measurements when codes are utilized (Combes et al 2014) (instead of probe states) to similar ends. Addressing somewhat related problems, but using supervised learning methods, the authors in Mavadia et al (2017) have also shown how to compensate for qubit decoherence (stochastic evolution) in experiments. Related to the topics of automated optimization of (complex) quantum protocols, in recent works generic optimization algorithms have been exploited to optimize and analyze QKD-type cryptographic protocols in the presence of noise (Krawec 2016, Krawec et al 2017). Further, in Wigley et al (2016), the authors demonstrated how on-line ML optimization can be used to find optimal evaporation ramps for Bose–Einstein condensates production.

Zoom In Zoom Out Reset image size

Finally, we point out that one of the most exciting applications of ML in the context of quantum experiments is the possibility that advanced ML techniques could significantly mitigate the major obstacles preventing the building of scalable quantum computers. This question can be addressed at various levels. For instance, the aforementioned control problems, relying on adaptive methods for the robust implementations of unitary gates, comprise a 'lower-level' aspect. The results of Tiersch et al (2015) and August and Ni (2017) also contribute to the overall goal of building large-scale robust quantum computers, but at a higher level—the action space of the agent already assumes access to unitary gates and measurements as primitives. In line with the same program, ML techniques can also help on an even further abstracted level, in helping with hard classical post-processing which may occur in the run-time of a quantum computer. Prominent examples here include ML efforts to optimize the decoders for quantum error correction codes. In this vital area, researchers have explored various ML techniques for a spectrum of issues. For instance, in the pioneering work in Torlai and Melko (2017), the potential of using restricted Boltzmann machines (BMs) (see section 2.1.1) to output near-optimal decoding/correcting strategies based on syndrome outcomes was explored. In follow up works, Varsamopoulos et al (2018) and Krastanov and Jiang (2017), feed-forward shallow and deep NN architectures were employed to speed up the decoding process or to achieve performance-beating standard decoding algorithms, respectively. In Baireuther et al (2017), the authors proposed an adaptive decoder based on LSTMs (see section 2.1.1). The proposed architecture accounted not only for temporally correlated errors, but allowed the training to be performed based on experimental data alone, i.e. without a reference to an error model. Similar problems have also been considered in the settings of restricted devices. For instance, in Johnson et al (2017), the authors have explored device-specific error-correcting encoding and decoding circuits in a variational setting. Here, parametrized circuits of a fixed structure are optimized to perform error correction, with no reference to a particular error correcting code. Such approaches are particularly appealing for near-term devices which can handle only a modest number of qubits and operations of only a limited computational depth. Such variational approaches are similar to how various ML techniques are employed (in particular, they are conceptually close to classical autoencoders; see section 2.1.1). Further, in this setting, the correct solutions may involve very hard optimization steps which form yet another class of entry points for ML methodology to be employed⁷⁰. As the field advances, we are expecting to see a significant increase in the number of applications of ML for the purpose of building large-scale quantum devices.

One of the first examples of applications of RL in QIP appears in the context of experimental photonics, where one of the current challenges lies in the generation of highly entangled, high dimensional, multi-party states. Such states are generated on optical tables, the systematic configuration of which, to generate complex quantum states, is still not fully understood. The search for configurations which are interesting can be mapped to an RL problem, where a learning agent is rewarded whenever it generates an interesting state (in a simulation). In a precursor work by Krenn et al (2016), the authors used a feedback-assisted search algorithm to identify previously unknown configurations which generate novel highly entangled states. This demonstrated that the design of novel quantum experiments can also be automatized, which can significantly aid in research. This idea, given in the context of optical tables, has subsequently been combined with earlier proposals to employ AI agents in quantum information protocols and as 'lab robots' in future quantum laboratories (Briegel 2013). This led to the application of more advanced RL techniques, based on the PS framework, for the tasks of understanding the Hilbert space accessible with optical tables and the autonomous machine-discovery of useful optical gadgets (Melnikov et al 2017). Related to the topic of learning new insight from experimenting machines, in Bukov et al (2017) the authors consider the problem of preparing target states by means of chosen pulses implementing (a restricted set) of rotations. This is a standard control task, and the authors show that RL achieves respectable and sometimes near-optimal results. However, for our purposes, the most relevant aspects of this work pertain to the fact that the authors also illustrate how ML/RL techniques can be used to obtain new insights in quantum experiments and non-equilibrium physics by circumventing human intuition, which can be flawed. Interestingly, the authors also demonstrate the reverse, i.e. how physics insights can help elucidate learning problems⁷¹.

Learning phases.

Representational capacities of generative models.

State discrimination.

Quantum template matching—classical templates.

Quantum template matching—quantum templates.

Other known optimality results for (restricted) template matching.

Quantum generalizations of (un)supervised learning.

Quantum inductive learning.

The previous subsections addressed the topics of classification of quantum states, based on quantum database examples. The overall theory, however, relies on the assumption that there exists a labeling rule which generates such examples and the labeling rule is what is learned. This rule is also known as a concept in COLT (e.g. PAC learning; see section 2.2.1 for details). A reasonable sufficient criterion is whether one can predict the probabilities of the outcomes of any two-outcome measurements on this state, as this already suffices for a full tomographic reconstruction. What would 'the learning of quantum states' mean, from this perspective? What does it mean to 'know a quantum state'? A natural criterion is that one 'knows' a quantum state if one can predict the measurement outcome probabilities of any given measurement. In Aaronson (2007), the author addressed the question of the learnability of quantum states in the sense above, where the role of a concept is played by a given quantum state, and 'knowing' the concept then equates to the possibility of predicting the outcome probability of a given measurement and its outcome. One immediate distinction from conventional COLT, discussed in section 2.2.1, is that the concept range is no longer binary. However, as we clarified, classical COLT has generalizations with continuous ranges. In particular, so called p-concepts have range in $[0, 1]$ (Kearns and Schapire 1994), and quantities which are analogs of the VC dimension and analogous theorems relating this to generalization performance exist for the p-concept case as well (see Aaronson (2007)). Explicitly, the basic elements of such a generalized theory are: domain of concepts ${\bf X},$ a sample ${\bf x} \in {\bf X}$ and the p-concept $f: {\bf X} \rightarrow [0, 1]$. These abstract objects are mapped to central objects of quantum information theory (Aaronson 2007) as follows: the domain of concepts is the set of two-outcome quantum measurements, a sample is a POVM element Π⁸⁷ (in short: ${\bf x} \leftrightarrow \Pi$) and the p-concept to be learned is a quantum state ψ. The evaluation of the concept/hypothesis on the sample corresponds to the probability ${\rm Tr}[\Pi \psi]\in [0, 1]$ of observing the measurement outcome associated with Π when the state ψ is measured.

It may be useful to further clarify the connection between the standard data-classification perspectives of supervised learning and the COLT perspective above. In the language of supervised learning we typically talk about classifiers, which partition their domain — or rather, they label the data points. In the setting of learning of quantum states, the classifier is the concept — in this case the quantum state. The quantum state 'classifies' the set of quantum POVM elements, according to the probability of observing the corresponding outcome. Specifically, a quantum state r (concept/hypothesis/classifier) assigns the label Tr [r P] ∈ [0,1] to the POVM element (data point) P. The training set elements for this model are of the form $(\Pi, {\rm Tr}(\rho \Pi)),$ with $0 \leqslant \Pi \leqslant \mathbb{1}$.

In the spirit of COLT, the concept class 'quantum states', is said to be learnable under some distribution $\mathcal{D}$ over two-outcome generalized measurement elements $(\Pi)$ if, for every concept—quantum state ρ—there exists an algorithm with access to examples of the form $(\Pi, {\rm Tr}(\rho \Pi))$, where Π is drawn according to $\mathcal{D}$, which outputs a hypothesis h which (approximately) correctly predicts the label ${\rm Tr}(\rho \Pi')$ with high probability when $\Pi'$ is drawn from $\mathcal{D}$. Note that the role of a hypothesis here can simply be played by a 'best guess' classical description of the quantum state ρ. The key result of Aaronson (2007) is that quantum states are learnable with sample complexity scaling only linearly in the number of qubits⁸⁸, that is, logarithmically in the dimension of the density matrix. In operative terms, if Alice wishes to send an n qubit quantum state to Bob who will perform on it a two-outcome measurement (and Alice does not know which), she can achieve near-ideal performance by sending ($O(n)$) classical bits⁸⁹, which has clear practical but also theoretical importance. In some sense, these results can also be thought of as a generalized variant of Holevo bound theorems (Holevo 1982), limiting how much information can be stored and retrieved in the case of quantum systems. This latter result has thus far been more influential in the contexts of tomography than quantum ML, despite being quite a fundamental result in quantum learning theory. However, for fully practical purposes, the results above come with a caveat. The learning of quantum states is efficient in sample complexity (e.g. number of measurements one needs to perform) but the computational complexity of the reconstruction of the hypothesis is, in fact, likely exponential in the qubit number. Very recently, the efficiency of the reconstruction algorithms for the learning of stabilizer states was also shown in Rocchetto (2017).

Learning of quantum processes.

Learning unitaries.

Learning measurements.

Foundations of quantum-generalized RL.

The first quantum generalization of PAC learning was presented in Bshouty and Jackson (1998), where the quantum example oracle was defined to output coherent superpositions

$$\begin{align} \newcommand{\e}{{\rm e}} \newcommand{\ket}[1]{\left| #1 \right\rangle} \displaystyle \sum_{\bf x} \sqrt{p_D({\bf x})} \ket{x, c(x)} , \nonumber \end{align} \tag{ 23 }$$

for a given distribution D over the data points x for a concept c. Recall that classical PAC oracles output a sample pair $(x, c(x))$, where x is drawn from D, which can be understood as copies of the mixed state $\newcommand{\dm}[1]{\left|#1 \right\rangle \left\langle #1 \right|} \sum_{\bf x} p_D({\bf x}) \dm{x, c(x)}$, with $p_D({\bf x}) = P(D={\bf x})$. The quantum oracle reduces to the standard oracle if the quantum example is measured in the standard (computational) basis. This first pioneering work showed that quantum algorithms with access to such a quantum-generalized oracle can provide more efficient learning of certain concept classes. The authors have considered the concept class of DNF formulas under the uniform distribution: here the concepts are s-term formulas in disjunctive normal form. In other words, each concept c is of the form $\newcommand{\bi}{\boldsymbol}c({\bf x})= \bigvee_I \bigwedge_j ({x}_I)'_j,$ where x_I is a substring of $\textbf x$ associated to I, which is a subset of the indices of cardinality at most s, and $({x}_I)'_j$ is a variable or its negation (a literal). An example of a DNF is of the form $(x_1 \wedge x_3 \wedge \neg x_6) \vee (x_4 \wedge \neg x_8 \wedge x_1) \cdots$, where parentheses (terms) only contain variables or their negations in conjunction (ANDs, $\wedge$), whereas all the parentheses are in disjunction (ORs, $\vee$).

The uniform DNF learning problem (for n variables and ${\rm poly}(n)$ terms) is not known to be efficiently PAC learnable, but in Bshouty and Jackson (1998) it was proven to be efficiently quantum PAC learnable. The choice of this learning problem was not accidental: DNF learning is known to be learnable in the membership query model, which is described in detail in the next section. The corresponding classical algorithm which learns DNF in the membership query model directly inspired the quantum variant in the PAC case⁹⁷. If the underlying distribution over the concept domain is uniform, other concept classes can be learned with a quantum speed-up as well, specifically, so called k-juntas: n-bit binary functions which depend only on k  <  n bits. In Atıcı and Servedio (2007), Atıcı and Servedio have shown that there exists a quantum algorithm for learning k-juntas using $\newcommand{\e}{{\rm e}} O(k \log(k)/\epsilon)$ uniform quantum examples, O(2^k) uniform classical examples and $\newcommand{\e}{{\rm e}} O(n\ k \log(k)/\epsilon + 2^k \log(1/\epsilon))$ time. Note that the improvement in this case is not in query complexity but rather in the classical processing, which, for the best known classical algorithm, has complexity at least O(n^2k/3) (see Atıcı and Servedio (2007) and Arunachalam and de Wolf (2017) for further details).

Diverging from perfect PAC settings, in Cross et al (2015), the authors considered the learning of linear boolean functions⁹⁸ under the uniform distribution over the examples. The twist in this work is the assumption of noise⁹⁹ which allows for evidence of a classical quantum learnability separation.

In more recent times, it was also shown that learning with errors¹⁰⁰, an important topic in COLT with critical applications in post-quantum cryptography, has been shown to be efficiently learnable given quantum examples (Grilo and Kerenidis 2017).

Distribution-free PAC.

Quantum predictive PAC learning.

In the model of exact learning from membership queries, the learner can choose the elements from the concept domain it wishes to be labeled (similar to active learning); however, the task is to identify the concept exactly (no error) except with probability $\delta<1/3$¹⁰³. Learning from membership queries has, in the quantum domain, usually been called oracle identification. While quantum improvements in this context are possible, in Servedio and Gortler (2004), the authors show that they are at most low-degree polynomial improvements in the most general cases. More precisely, if a concept class C over n-bits has classical and quantum membership query complexities $D(C)$ and $Q(C)$, respectively, then D(C)  =  O(nQ(C)³)¹⁰⁴—in other words, improvements in sample complexity can be at most polynomial. Polynomial relationships have also been established for worst-case exact learning sample complexities (so-called $(N, M)$-query complexity); see Kothari (2013) and Arunachalam and de Wolf (2017). The above result is in spirit similar to earlier results in Beals et al (2001), where it was shown that quantum query complexity cannot provide a better-than-polynomial improvement over classical results, unless structural requirements on the oracle are imposed.

The results so far considered are standard, comparatively simple generalizations of classical learning settings, leading to somewhat restricted improvements in sample complexity. More dramatic improvements are possible if computational (time) complexity is taken into account, or if slightly non-standard generalizations of the learning model are considered. Note that we are not explicitly bringing computational complexity separations into the picture. Rather, under the assumption that certain computation problems are hard for the learner, we obtain a sample complexity separation.

In particular, already in Kearns and Valiant (1994) the authors constructed several classes of Boolean functions in the distribution-free model whose efficient learning (in the sample complexity sense) implies the capacity of factoring so-called Blum integers—a task not known to be solvable classically, but solvable on a quantum computer¹⁰⁵. Using this observations, Servedio and Gortler have demonstrated classes which are efficiently quantum PAC learnable and classes which are efficiently learnable in the quantum membership query model, but which are not efficiently learnable in the corresponding classical models, unless Blum integers¹⁰⁶ can be efficiently factored on a classical computer (Servedio and Gortler 2004).

In some of the first works (Ventura and Martinez 2000 and Trugenberger 2001) it was suggested that the proverbial 'exponential-sized' Hilbert space describing systems of qubits may allow exponential improvements: intuitively even exponentially nume-rous pattern sets P can be 'stored' in a quantum state of only n qubits: $\newcommand{\ket}[1]{\left| #1 \right\rangle} \ket{\psi_{P}} = |P|^{-\frac{1}{2}} \sum_{{\bf x}\in P} \ket{x}$. These early works suggested creative ideas on how such a memory could be used to recover patterns (e.g. via modified amplitude amplification), though these often suffered from a lack of scalability and other quite fundamental issues, preventing them from yielding complete proposals¹⁰⁷, and thus we will not dig into the details. We will, however, point out that these works may be interpreted to propose some of the first examples of 'amplitude encoding' of classical data, which is heavily used in modern approaches to quantum ML. In particular, the stored memory of a CAM can always be represented as a single bit-string $(b_{(0\cdots 0)}, b_{(0\cdots 1)}, \ldots, b_{(1\ldots1)})$ of length 2ⁿ (each bit in the bit-string is indexed by a pattern, and its value encodes whether it is stored or not). This data vector (in this case binary, but this is not critical) is thus encoded into amplitudes of a quantum state of an exponentially smaller number of qubits: $\newcommand{\ket}[1]{\left| #1 \right\rangle} {\bf b} = (b_{(0\cdots 0)}, b_{(0\cdots 1)}, \ldots, b_{(1\ldots1)}) \rightarrow \sum_{{\bf x}\in \{0, 1 \}^n} b_{{\bf x}} \ket{{\bf x}}$ (up to normalization).

A different approach to increasing the capacities of CAMs arises from the 'quantization' of different aspects of classical HNs, which constitute well-understood classical CAM systems.

Hopfield networks as content-addressable memories.

Recall that an HN is a recurrent NN characterized by a set of n neurons, whose connectivity is given by a (typically symmetric) real matrix of weights $W = (w_{ij})_{ij}$ and a vector of (real) local thresholds $\{\theta_i \}_{i=1}^n$. In the context of CAMs, the matrix W encodes the stored patterns, which are in this setting best represented as sequences of signs, so ${\bf x} \in \{1, -1\}^{n}$. The retrieval, given an input pattern ${\bf y} \in \{1, -1\}^{n}$, is realized by setting the kth neuron s_k to the kth value of the input pattern y_k followed by the 'running of the network' according to standard perceptron rules: each neuron k computes its subsequent value by checking if its inbound weighted sum is above the local threshold: $s_k \leftarrow {\rm sign}(\sum_{l} w_{kl} s_l - \theta_k)$ (assuming ${\rm sign}(0)=+1$)¹⁰⁸. As discussed previously, under moderate assumptions the described dynamical system converges to local attractive points, which also correspond to the energy minima of the Ising functional

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle E({\bf s}) = -\frac{1}{2} \sum_{ij} w_{ij} s_i s_j + \sum_{i} \theta_i s_i. \nonumber \end{align} \tag{ 24 }$$

Such a system still allows significant freedom in the rule specifying the matrix $W,$ given a set of patterns to be stored: intuitively, we need to 'program' the minima of E (choosing the appropriate W will suffice, as the local thresholds can be set to zero) to be the target patterns, ideally without storing too many unwanted, so-called spurious, patterns. This and other properties of a useful storing rule, that is, a rule which specifies W given the patterns, are given as follows (Storkey 1997): (a) locality: an update of a particular connection should depend only on the information available to the neurons on either side of the connection¹⁰⁹; (b) incrementality: the rule should allow the updating of the matrix W to store an additional pattern based only on the new pattern and W itself¹¹⁰; (c) immediateness: the rule should not require a limiting computational process for the evaluation of the weight matrix (rather, it should be a simple computation of few steps). The most critical property of a useful rule is that it (d) results in a CAM with a non-trivial capacity: it should be capable of storing and retrieving some number of patterns with controllable error (which includes few spurious patterns, for instance).

The first rule, historically speaking, the Hebbian rule, satisfies all the conditions above and is given by a simple recurrence relation: for the set of patterns $\{{\bf x}^k\}_k$ the weight matrix is given by $w_{ij} = \sum_{k}{\bf x}_i^k {\bf x}_j^k / M$ (where ${\bf x}_j^k$ is the jth sign of the kth pattern, and M is the number of patterns). The capacity of HNs under standard recall and Hebbian updates has been investigated from various perspectives and, in the context of absolute capacity (the asymptotic ratio of the number of patterns that can be stored without error to the number of neurons, as the network size tends to infinity), it is known to scale as $O(\frac{n} {2 \log(n)})$. A well known result in the field improves on this to the capacity of $O(\frac{n} {\sqrt{2 \log(n)}})$, and is achieved by a different rule introduced by Storkey (1997), while maintaining all the desired properties. Here, we should emphasize that, in broad terms, the capacity is typically (sub)-linear in n. Better results, however, can be achieved in the classical settings if some of the assumptions (a)–(c) are dropped, but this is undesirable.

Quantization of Hopfield-based content-addressable memories.

Quantum optimization techniques play an increasingly important role in quantum ML. Here, we can roughly distinguish two flavors of approaches, which differ in what computationally difficult aspect of training of a classical model is tackled by adiabatic methods. In the (historically) first approach, we deal with clear-cut optimization in the context of binary classifiers and, more specifically, boosting (see section 2.1.3). Since then, it has been shown that annealers can also help by generating samples from hard-to-simulate distributions. We will mostly focus on the earlier approaches, and only briefly mention the other more recent results.

Optimization for boosting.

The representative line of research, which also initiated the development of this topic of quantum-enhanced ML based on adiabatic QC, focuses on a particular family of optimization problems called quadratic unconstrained binary optimization (QUBO) problems of the form

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\bf x}^\ast = (x_1^\ast,\ldots,x_n^\ast) = {\rm argmin}_{(x_1,\ldots,x_n)}\sum_{i<j} J_{ij} x_i x_j,\ x_k \in\{0,1 \} \nonumber \end{align} \tag{ 25 }$$

specified by a real matrix J. QUBO problems are equivalent to the problem of identifying lowest energy states of the Ising functional¹¹⁴ $E({\bf s}) = -\frac{1}{2} \sum_{ij} J_{ij} s_i s_j + \sum_{i} \theta_i s_i$, provided we make no assumptions on the underlying lattice. Modern annealing architectures provide means for tackling the problem of finding such ground states using adiabatic QC. Typically we are dealing with systems which can implement the tunable Hamiltonian of the form

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle H(t) = -A(t)\underbrace{\sum_{i} \sigma^x}_{H_{\rm initial}} + B(t)\underbrace{\sum_{ij} J_{ij} \sigma^z_i \sigma^z_j}_{H_{\rm target}}, \nonumber \end{align} \tag{ 26 }$$

where $A, B$ are smooth positive functions such that $A(0)\gg B(0)$ and $B(1)\gg A(1),$ that is, by tuning t sufficiently slowly we can perform adiabatic preparation of the ground state of the Ising Hamiltonian H_target, thereby solving the optimization problem. In practice, the parameters J_ij cannot be chosen fully freely (e.g. the connectivity is restricted to the so-called Chimera graph (Hen et al 2015) in D-Wave architectures), and also the realized interaction strength values have a limited precision and accuracy (Neven et al 2009b, Bian et al 2010), but we will ignore this for the moment. In general, finding ground states of the Ising model is functional NP-hard¹¹⁵, which is likely beyond the reach of quantum computers. However, annealing architectures still may have many advantages; for instance it is believed that they may still provide speed-ups in all, or at least average, instances and/or that they may provide good heuristic methods and hopefully near optimal solutions¹¹⁶.

In other words, any aspect of optimization occurring in ML algorithms which has an efficient mapping to (non-trivial) instances of QUBO problems, specifically those which can be realized by experimental set-ups, is a valid candidate for quantum improvements. Such optimization problems have been identified in a number of contexts, mostly dealing with training binary classifiers, and so belong to the class of supervised learning problems. The first setting considers the problem of building optimal classifiers from linear combinations of simple hypothesis functions, which minimize empirical error, while controlling the model complexity through a so-called regularization term. This is the common optimization setting of boosting (see section 2.1.3) and, with appropriate mathematical gymnastics and few assumptions, it can be reduced to a QUBO problem.

The overarching setting of this line of work can be expressed in the context of training a binary classifier by combining weaker hypotheses. For this setting, consider a dataset $D=\{{\bf x}_i, y_i \}_{i=1}^{M}$, ${\bf x}_i \in \mathbb{R}^{n}$, $y_i \in\{-1, 1 \}$, and a set of hypotheses $\{h_j\}_{j=1}^{K}, h_j: \mathbb{R}^{n}\rightarrow \{-1, 1\}$. For a given weight vector ${\bf w} \in \mathbb{R}^{n}$ we define the composite classifier of the form $hc_{{{\bf w}}}({\bf x}) = {\rm sign}(\sum_k {w}_k h_k({\bf x}))$.

The training of the composite classifier is achieved by the optimization of the vector ${\bf w}$ so as to minimize misclassification on the training set, and so as to decrease the risk of overtraining. The misclassification cost is specified via a loss function L, which depends on the dataset and the hypothesis set in the boosting context. The overtraining risk, which tames the complexity of the model, is controlled by a so-called regularization term R. Formally we are solving

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm argmin}_{{\bf w}}\ L({\bf w}; D) + R({\bf w}). \nonumber \end{align} \tag{ 27 }$$

This constitutes the standard boosting frameworks exactly, but is also closely related to the training of certain SVMs, i.e. hyperplane classifiers¹¹⁷. In other words, quantum optimization techniques which work for the boosting setting can also help for hyperplane classification.

There are a few well-justified choices for L and R, leading to classifiers with different properties. Often, best choices (the definition of which depends on the context) lead to hard optimization (Long and Servedio 2010), and some of those can be reduced to QUBOs, but not straightforwardly.

In the pioneering paper on the topic (Neven et al 2008), Neven and co-authors consider the boosting setting. The regularization term is chosen to be proportional to the 0-norm, which counts the number of non-zero entries, that is, $R({\bf w}, \lambda) = \lambda \| {\bf w}\|_0$. The parameter λ controls the relative importance of regularization in the overall optimization task. A common choice for the loss function would be the 0–1 loss function L₀₋₁, optimal in some settings, given by $\newcommand{\T}{\mathcal{T}} L_{0-1}({\bf w}) = \sum_{j=1}^{M} \Theta \left(-y_j \sum_k {w}_k h_k({\bf x}_j) \right)$ (where Θ is the step function), which simply counts the number of misclassifications. This choice is reasonably well motivated in terms of performance and is likely to be computationally hard. With appropriate discretization of the weights ${\bf w}$, which the authors argue likely does not hurt performance, the above forms a solid candidate for a general adiabatic approach. However, it does not fit the QUBO structure (which has only quadratic terms) and hence cannot be tackled using existing architectures. To achieve the desired QUBO structure the authors impose two modifications: they opt for a quadratic loss function $L_{2}({\bf w}) = \sum_{j=1}^{M} |y_j - \sum_k {w}_k h_k({\bf x}_j) |^2$ and restrict the weights to binary (although this can be circumvented to an extent). Such a system is also tested using numerical experiments. In a follow-up paper (Neven et al 2009b), the same team has generalized the initial proposal to accommodate another practical issue: problem size. Available architectures allow optimization over a few thousand variables, whereas in practice the number of hypotheses one optimizes over (K) may be significantly larger. To resolve this, the authors show how to break a large optimization problem into more manageable chunks while maintaining (experimentally verified) good performance. These ideas were also tested in an actual physical architecture (Neven et al 2009a), and combined and refined in a more general, iterative algorithm in Neven et al (2012), tested also using actual quantum architectures.

While L₀₋₁ loss functions were known to be good choices, they were not the norm in practice as they lead to non-convex optimization—so convex functions were preferred. However, in 2010 it became increasingly clear that convex functions are provably bad choices. For instance, in the seminal paper (Long and Servedio 2010) Long and Servedio¹¹⁸ showed that boosting with convex optimization completely fails in noisy settings. Motivated by this, in Denchev et al (2012), the authors re-investigate D-Wave type architectures and identify a reduction which allows a non-convex optimization. Expressed in the hyperplane classification setting (as explained, this is equivalent to the boosting setting in structure), they identify a reduction which (indirectly) implements a non-convex function $l_{q}(x) = \min\{(1-q){}^2, (\max (0, 1-x)){}^2 \}$. This function is called the q-loss function, where q is a real parameter. The implementation of the q-loss function allows for the realization of optimization relative to the total loss of the form $L_{q}({\bf w}, b ; D) =\sum_j l_{q}(y_j({\bf w}^\tau {\bf x} + b))$. The resulting regularization term is in this case proportional to the 2-norm of ${\bf w},$ instead of the 0-norm as in the previous examples, which may be sub-optimal. Nonetheless, the above forms a prime example where quantum architectures lead to ML settings which would not have been explored in the classical case (the loss L_q is unlikely to appear naturally in many settings) yet are well motivated, as (a) the function is non-convex and thus has the potential to circumvent all the no-go results for convex functions and (b) the optimization process can be realized in a physical system. The authors perform a number of numerical experiments demonstrating the advantages of this choice of a non-convex loss function when analyzing noisy data, which is certainly promising. In later work (Denchev et al 2015), it was also suggested that combinations of loss-regularization which are realizable in quantum architectures can also be used for so-called totally corrective boosting with cardinality penalization, which is believed to be classically intractable.

The details of this go beyond the scope of this review, but we can at least provide a flavor of the problem. In corrective boosting, the algorithm updates the weights ${\bf w}$ essentially one step at a time. In totally corrective boosting, at the tth step of the boosting algorithm optimization, t entries of ${\bf w}$ are updated simultaneously. This is known to lead to better regularized solutions, but the optimization is harder. Cardinality penalization pertains to using explicitly the 0-norm for the regularization (discussed earlier), rather than the more common 1-norm. This, too, leads to harder optimization which may be treated using an annealing architecture. In Babbush et al (2014), the authors significantly generalized the scope of loss functions which can be embedded into quantum architectures by observing that any polynomial unconstrained binary optimization can, with small overhead, be mapped onto a (slightly larger) QUBO problem. In particular, this opens up the possibility of implementing odd-degree polynomials which are non-convex and can approximate the 0–1 loss function. This approach introduced new classes of unusual yet promising loss functions.

Applications of quantum boosting.

Beyond boosting.

One of the most important applications of ML in recent times has been in the context of data mining and analyzing so-called big data. The most impressive improvements in this context have been achieved by proposing specialized quantum algorithms which solve particular ML problems. Such algorithms assume the availability of full-blown quantum computers and have been tentatively probed since the early 2000s. In recent times, however, we have witnessed a large influx of ideas. Unlike the situation we have seen in the context of quantum annealing, where an optimization subroutine alone was run on a quantum system, in most of the approaches of this section the entire algorithm, and even the dataset, may be quantized.

The ideas for quantum-enhancements for ML can roughly be classified into two groups: (a) approaches which rely on Grover's search and amplitude amplification to obtain up-to-quadratic speed-ups and (b) approaches which encode relevant information into quantum amplitudes and which have a potential for even exponential improvements. The second group of approaches forms perhaps the most developed research line in quantum ML, and collects a plethora of quantum tools—most notably quantum linear algebra, utilized in quantum ML proposals.

Speed-ups by amplitude amplification.

Precursors of amplitude encoding.

Amplitude encoding: linear algebra tools.

Tool 1: inner product evaluation.

Tool 2: quantum linear system solving.

Tool 3: density matrix exponentiation.

Density matrix exponentiation (DME) is a remarkably simple idea, with few subtleties and arguably profound consequences. Consider an N-dimensional density matrix ρ. Now, from a mathematical perspective, ρ is nothing but a semidefinite positive matrix, although it is also commonly used to denote the quantum state of a quantum system—and these two are subtly different concepts. In the first reading, where ρ is a matrix (we will denote it $[\rho]$ to avoid confusion), $[\rho]$ is also a valid description of a physical Hamiltonian, with time-integrated unitary evolution $\newcommand{\e}{{\rm e}} \exp(-{\rm i} [\rho] t)$. Could one approximate $\newcommand{\e}{{\rm e}} \exp(-{\rm i}[\rho] t)$, having access to quantum systems prepared in the state ρ? Given sufficiently many copies ($\rho^{\otimes n}$), the obvious answer is yes—one could use full state tomography to reconstruct $[\rho],$ to arbitrary precision, and then execute the unitary using, say, Hamiltonian simulation (efficiency notwithstanding). In Lloyd et al (2014), the authors show a significantly simpler method: given any input state σ and one copy of ρ, the quantum state

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \sigma' = {\rm Tr}_{B}[ \exp(-{\rm i} \Delta t S) ( \sigma_{A} \otimes \rho_B) \exp({\rm i} \Delta t S)], \nonumber \end{align} \tag{ 28 }$$

where S is the Hermitian operator corresponding to the quantum SWAP gate, approximates the desired time evolution to first order, for small $\Delta t$: $\sigma' = \sigma - {\rm i} \Delta t [\rho, \sigma ] + O(\Delta t^2)$. If this process is iterated, by using fresh copies of ρ, we obtain that the target state $\newcommand{\e}{{\rm e}} \sigma_\rho = \exp(-{\rm i} \rho t) \sigma \exp({\rm i} \rho t)$ can be approximated to precision $\newcommand{\e}{{\rm e}} \epsilon,$ by setting $\Delta t$ to $\newcommand{\e}{{\rm e}} O(\epsilon/t)$ and using $\newcommand{\e}{{\rm e}} O(t^2/\epsilon)$ copies of the state ρ. DME is, in some sense, a generalization of the process of using SWAP tests between two quantum states, to simulate aspects of a measurement specified by one of the quantum states. One immediate consequence of this result is in the context of Hamiltonian simulation, which can now be efficiently realized (with no dependency on the sparsity of the Hamiltonian) whenever one can prepare quantum systems in a state which is represented by the matrix of the Hamiltonian. In particular, this can be realized using qRAM stored descriptions of the Hamiltonian whenever the Hamiltonian itself is of low rank. More generally, this also implies e.g. that QLS algorithms can also be efficiently executed when the system matrix is not sparse, but rather dominated by few principal components, i.e. close to a low rank matrix¹²⁷.

Remark. Algorithms for QLS, inner product evaluation, quantum PCA and, consequently, almost all quantum algorithms listed in the remainder of this section also assume 'pre-loaded databases', which allow accessing of information in quantum parallel, and/or the accessing or efficient preparation of amplitude encoded states. The problem of parallel access, or even the storing of quantum states, has been addressed and mostly resolved using so-called quantum random access memory (qRAM) architectures (Giovannetti et al 2008)¹²⁸. The same qRAM structures can also be used to realize oracles utilized in the approaches based on quantum search. However, having access to quantum databases pre-filled with classical data does not a priori imply that quantum-amplitude-encoded states can also be generated efficiently, which is, at least implicitly, assumed in most works below. For a separate discussion on the cost of some similar assumptions, we refer the reader to Aaronson (2015).

Amplitude encoding: algorithms.

Regression algorithms.

One of the first proposals for quantum enhancements tackled linear regression problems, specifically, least-squares fitting, and relied on QLS. In least-squares fitting, we are given N M-dimensional real data points paired with real labels, so $({\bf x}_i, y_i)_{i =1}^{N},$ ${\bf x}_i = (x^{\,j}_i)_j \in \mathbb{R}^{M}, {\bf y} = (y_i)_i \in \mathbb{R}^N$. In regression y is called the response variable (also regressand or dependent variable), whereas the data points ${\bf x}_i$ are called predictors (or regressors or explanatory variables), and the goal of least-squares linear regression is to establish the best linear model, that is $\boldsymbol{\beta} = (\beta_j)_{j} \in \mathbb{R}^{M}$ given by

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle {\rm argmin}_{\boldsymbol{\beta}} \| {\bf X} \boldsymbol{\beta} - {\bf y} \|^2, \nonumber \end{align} \tag{ 29 }$$

where the data matrix ${\bf X}$ collects the data points ${\bf x}_i$ as rows. In other words, linear regression assumes a linear relationship between the predictors and the response variables. It is well-established that the solution to the above least-squares problem is given by $\boldsymbol{\beta} = {\bf X}^+ {\bf y}$, where ${\bf X}^+$ is the Moore–Penrose pseudoinverse of the data matrix, which is, in the case that ${\bf X}^\dagger {\bf X}$ is invertible, given by ${\bf X}^+ = ({\bf X}^\dagger {\bf X}){}^{-1} {\bf X}^\dagger$. The basic idea in Wiebe et al (2012) is to apply ${\bf X}^\dagger$ onto the initial vector $\newcommand{\ket}[1]{\left| #1 \right\rangle} \ket{{\bf y}}$ which amplitude-encodes the response variables, obtaining a state proportional to $\newcommand{\ket}[1]{\left| #1 \right\rangle} {\bf X}^\dagger \ket{{\bf y}}$. This can be done e.g. by modifying the original QLS algorithm (Harrow et al 2009) to imprint not the inverses of eigenvalues but the eigenvalues themselves. Following this, the task of applying $({\bf X}^\dagger {\bf X}){}^{-1}$ (onto the generated state proportional to $\newcommand{\ket}[1]{\left| #1 \right\rangle} {\bf X}^\dagger \ket{{\bf y}}$) is interpreted as an equation-solving problem for the system $({\bf X}^\dagger {\bf X}) \boldsymbol{\beta} = {\bf X}^\dagger {\bf y}$.

The end result is a quantum state $\newcommand{\ket}[1]{\left| #1 \right\rangle} \ket{\boldsymbol{\beta}}$ proportional to the solution vector $\boldsymbol{\beta},$ in time $\newcommand{\e}{{\rm e}} O(\kappa^4 d^3 \log(N)/\epsilon),$ where $\kappa, d$ and are the condition number, the sparsity of the 'symmetrized' data matrix ${\bf X}^\dagger {\bf X}$ and the error, respectively. Again, we have in general few guarantees on the behavior of κ and an obvious restriction on the sparsity d of the data matrix. However, whenever both are $O({\rm polylog}(N))$, we have a potential¹²⁹ for exponential improvements. This algorithm is not obviously useful for actually finding the solution vector $\boldsymbol{\beta},$ as it is encoded in a quantum state. Nonetheless, it is useful for estimating the quality of fit: essentially by applying ${\bf X}$ onto $\newcommand{\ket}[1]{\left| #1 \right\rangle} \ket{\boldsymbol{\beta}}$ we obtain the resulting prediction of ${\bf y},$ which can be efficiently compared to the actual response variable vector via a swap test¹³⁰.

These basic ideas for quantum linear regression have since been extended in a few works. In an extensive and complementary work (Wang 2014), the authors rely on the powerful technique of 'qubitization' (Low and Chuang 2016) and optimize the goal of actually producing the best-fit parameters $\boldsymbol{\beta}$. By necessity, the complexity of their algorithm is proportional to the number of data points M, but is logarithmic in the data dimension N, and quite efficient in other relevant parameters. In Schuld et al (2016), the authors follow the ideas of Wiebe et al (2012) more closely and achieve the same results as in the original work when the data matrix, rather than being sparse, is low-rank. Further, they improve on the complexities by using other state-of-the-art methods. This latter work critically relies on the technique of DME.

Clustering algorithms.

Quantum principal component analysis.

Quantum support vector machines.

One of the most influential papers in quantum-enhanced ML relies on QLS and DME for for the task of quantizing SVM algorithms. For the basic ideas behind SVMs see section 2.1.2.

We focus our attention to the problem of training SVMs, as given by the optimization task in its dual form, in equation (6), repeated here for convenience:

$$\begin{align*} \newcommand{\e}{{\rm e}} \displaystyle & (\alpha^\ast_1 ,\ldots \alpha^\ast_N) = {\rm argmin}_{\alpha_1 \ldots \alpha_N} \sum_{i} \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j{\bf x}_i \cdot {\bf x}_j , \nonumber \\ & \ {\rm such\ that}\ \alpha_i\geqslant 0\ {\rm and}\ \sum_{i}\alpha_iy_i =0.\ \nonumber \end{align*}$$

The solution of the desired SVM is then easily computed by ${\bf w}^\ast = \sum_{i}y_i\alpha_i {\bf x}_i$.

As a warm-up result, in Rebentrost et al (2014) the authors point out that using quantum evaluation of inner products, appearing in equation (30), can already lead to exponential speed-ups with respect to the data-vector dimension N. The quantum algorithm complexity is, however, still polynomial in the number of data points M and the error dependence is now linear (as the error of the inner product estimation is linear). The authors proceed to show that full exponential improvements can be possible (with respect to both N and M), however, for the special case of least-squares SVMs. Given the background discussions we have already laid out with respect to DME and QLS, the basic idea is here easy to explain. Recall that the problem of training least-squares SVMs reduces to a linear program, specifically a least-squares minimization. As we have seen previously, such minimization reduces to equation solving, which was given by the system in equation (14) which we repeat here:

$$\begin{align} \newcommand{\e}{{\rm e}} \displaystyle \label{inner2} \left[\begin{array}{@{}cc@{}}0&1_{}^{T} \nonumber \\1_{N}&\Omega +\gamma ^{-1}I_{}\end{array}\right]\left[\begin{array}{@{}cc@{}}\,b \nonumber \\ \boldsymbol{\alpha} \end{array}\right]=\left[\begin{array}{@{}cc@{}}\,0 \nonumber \\Y \end{array}\right]. \nonumber \end{align} \tag{ 30 }$$

Here, 1 is an 'all ones' vector, Y is the vector of labels y_i, $\boldsymbol{\alpha}$ is the vector of the Lagrange multipliers yielding the solution, b is the offset, γ is a parameter depending on the hyperparameter C and Ω is the matrix collecting the (mapped) inner products of the training vectors so $\Omega_{i, j} = {\bf x}_i \cdot {\bf x}_j$. The key technical aspects of Rebentrost et al (2014) demonstrate how the system above is realized in a manner suitable for QLS. To give a flavor of the approach, we will simply point out that the system sub-matrix Ω is proportional to the reduced density matrix of the quantum state $\newcommand{\ket}[1]{\left| #1 \right\rangle} \sum_i |{\bf x}_i| \ket{i}_{1}\ket{{\bf x}_i}_{2},$ obtained after tracing out the subsystem 2. This state can, under some constraints, be efficiently realized with access to qRAM encoding the data points. Following this, DME enables the application of QLS where the system matrix has a block proportional to Ω, up to technical details which we omit for brevity. The overall quantum algorithm generates the quantum state proportional to $\newcommand{\ket}[1]{\left| #1 \right\rangle} \ket{\psi_{\rm out}} \propto b\ket{0} + \sum_{i=1}^M \alpha_i \ket{i},$ encoding the offset and the multipliers. The multipliers need not be extracted from this state by sampling. Instead any new point can be classified by (1) generating an amplitude-encoded state of the input and (2) estimating the inner product between this state and $\newcommand{\ket}[1]{\left| #1 \right\rangle} \ket{\psi_{\rm out}'} \propto b\ket{0}\ket{0} + \sum_{i=1}^M \alpha_i |{\bf x}_i| \ket{i}\ket{{\bf x}_i},$ which is obtained by calling the quantum data oracle using $\newcommand{\ket}[1]{\left| #1 \right\rangle} \ket{\psi_{\rm out}}$. This process has an overall complexity of $\newcommand{\e}{{\rm e}} O(\kappa_{\rm eff}^3 \epsilon^{-3} \log (MN))$, where $\kappa_{\rm eff}$ depends on the eigenstructure of the data matrix. Whenever this term is polylogarithmic in data size, we have a potential for exponential improvements.

Gaussian process regression.

Geometric and topological data analysis.

Quantum agent–environment paradigm.

The (abstract) AE paradigm, roughly illustrated in figure 6, can be understood as a two-party communication scenario, the quantum descriptions of which are well-understood in QIP. In particular, the two players—here the agent and the environment—are modeled as (infinite) sequences of unitary maps $\{\mathcal{E}_A^i\}_i$ and $\{\mathcal{E}_E^i\}_i$, respectively. They both have private memory registers R_A and R_E, with matching Hilbert spaces H_A and H_E, and to enable precise specification of how they communicate (and to cleanly delineate the two players), the register of the communication channel, R_C, is introduced, and it is the register alone which is accessible to both players—that is, the maps of the agent act on $H_A\otimes H_C$ and of the environment on $H_E\otimes H_C$¹⁴⁰. The two players then interact by sequentially applying their respective maps in turn (see figure 15).

Zoom In Zoom Out Reset image size

To further tailor this fully general setting for the purposes of the AE paradigm, the percept and action sets are promoted to sets of orthonormal vectors $\newcommand{\ket}[1]{\left| #1 \right\rangle} \{\ket{s} | s \in {\bf S}\}$ and $\newcommand{\ket}[1]{\left| #1 \right\rangle} \{\ket{a} | a \in {\bf A} \}$, which are also mutually orthogonal. These are referred to as classical states. The Hilbert space of the channel is isomorphic to a space spanned by these two sets, so $\newcommand{\ket}[1]{\left| #1 \right\rangle} H_C = {\rm span} \{\ket{x} |\ x \in {\bf S} \cup {\bf A}\}$.

This also captures the notion that the agent/environment only performs one action, or issues one percept, per turn. Without loss of generality, we assume that the reward status is encoded in the percept space. It should be mentioned that the quantum AE paradigm also includes all other quantum ML settings as a special case. For instance, most quantum-enhanced ML algorithms assume access to quantum database—a quantum memory—and this setting is illustrated in figure 15, part DL. The 'environment' of the agent here is the database (or whatever the mechanism generating the data may be), the actions are the queries and percepts the data points. Since the quantum database is, without loss of generality, a unitary map (see e.g. qRAM described in section 6.3.2), it requires no additional memory of its own nor does it change over interaction steps¹⁴¹.

At this point, the classical AE paradigm can be recovered when the maps of the agent and environment are restricted to 'classical maps', which, roughly speaking, do not generate superpositions of classical states nor entanglement when applied to classical states.

Further, we now obtain a natural classification of generalized AE settings: CC, CQ, QC and QQ, depending on whether the agent or the environment are classical (C) or quantum (Q). We will come back to this classification in section 7.2.1.

The performance of a learning agent, beyond internal processing time, is a function of the realized history of interaction, which is the percept-action sequence (of a given finite length) which has occurred between a given agent and environment¹⁴². Any genuine learning-related figure of merit, for instance, the probability of a reward at a given time-step (efficiency) or number of steps needed before the efficiency is above a threshold (learning speed), is a function of the interaction history. In the classical case, the history can simply be read out by a classical-basis measurement of the register H_C, as the local state of the communication register is diagonal in this basis and not entangled to the other systems—meaning the measurement does not perturb, i.e. commutes with, the interaction. In the quantum case this is not, in general, the case. To recover a robust notion of a history (needed to gauge the learning), a more detailed description of measurement is used, which captures weaker measurements as well: an additional system, a tester, is added, which interchangeably couples to the H_C register and can copy full or partial information to a separate register. Formally, this is a sequence of controlled maps, relative to the classical basis, controlled by the states on H_C and acting on a separate register, as illustrated in figure 15. The tester can copy the full information when the maps are generalized controlled-NOT gates—in which case it is called a classical tester—or even do nothing, in which case the interaction is untested. The restriction of the tester to maps which are controlled with respect to the classical basis guarantees that a classical interaction will never be perturbed by its presence. With this basic framework in place, the authors show a couple of basic theorems characterizing when any quantum separations in learning-related figures of merit can be expected at all. The notion of a quantum-classical separation here is essentially the same as in the context of oracular computation, or quantum PAC theory: a separation means no classical agent could achieve the same performance. The authors prove basic expected theorems: quantum improvements (separations) require a genuine quantum interaction and, further, full classical testing prohibits this. Further, they show that, for any specification of a classical environment, there exists a 'quantum implementation'—a sequence of maps $\{\mathcal{E}_E^i\}_i$—which is consistent with the classical specification and prohibits any quantum improvements.

Provable quantum improvements in reinforcement learning.

However, if the above no-go scenarios are relaxed, much can be achieved. The authors provide a structure of task environments (roughly speaking, maze-type problems), specification of quantum-accessible realizations of these environments and a sporadic tester (which leaves a part of the interaction untested), for which classical learning agents can often be quantum-enhanced.

The idea has a few steps, which we only very briefly sketch out. As a first step, the environments considered are deterministic and strictly episodic—this means the task is reset after some M steps. Since the environments are deterministic, whether or not rewards are given depends only on the sequence of actions, as the interlacing percepts are uniquely specified. Since everything is reset after M steps there are no correlations in the memory of the environment between the blocks, i.e. episodes. This allows for the specification of a quantum version of the same environment, which can be accessed in superpositions and which takes blocks of actions and returns the same sequence plus a reward status—moreover, it can be realized such that it is self-inverse¹⁴³. With access to such an object, a quantum agent can actually Grover-search for an example of a winning sequence.

To convert this exploration advantage to a learning advantage, the set of agents and environments is restricted to pairs which are 'luck-favoring', i.e. those where better performance in the past implies improved performance in the future, relative to a desired figure of merit. Under these conditions, any learning agent which is luck-favoring relative to a given environment can be quantum enhanced by first using quantum access to quadratically faster find the first winning instance, which is then used to 'pre-train' the agent in question. The overall quantum-enhanced agent provably outperforms the basic classical agent.

The construction is illustrated in figure 16. These results can be generalized to a broader class of environments. In more recent work, the authors have also applied a similar approach to provide improvements in the context of meta-learning (Dunjko et al 2017). Further, by showing how to embed oracular identification problems into Markov decision processes, in Dunjko et al (2017) the authors have provided constructions of RL task environments which satisfy certain criteria for genuine RL problems, while still allowing for a provable super-polynomial and exponential separation between quantum agents and optimal classical agents. These results showed that even in genuine RL problems, better-than-quadratic improvements are possible.

Zoom In Zoom Out Reset image size

Although these results form the first examples of quantum improvements in learning figures of merit in RL contexts, the assumptions of having access to 'quantized' environments of the type used—in essence, the amount of quantum control the agent is assumed to have—are quite restrictive from a practical perspective. The questions of minimal requirements and the questions of the scope of improvements possible are still unresolved.

At this point, it should be highlighted that the most probable application of results where quantum environments are assumed is in the contexts of model-based learning, learning with off-line pre-training and learning in simulations. In all these settings, the learning interaction is performed with a virtual, rather than a real, environment, which opens doors for the techniques described in this section. In model-based learning, the agent builds up an internal representation of the environment, which allows, e.g., planning. Since this representation is internal to the agent, it certainly can be quantized (provided sufficiently large quantum devices are available). An example of off-line pre-training is the AlphaGo system, in particular, the AlphaGo zero variant (Silver et al 2017a, 2017b). The AlphaGo system learns via self-play: an instance of the model plays against itself. Only after an extensive training phase is the system confronted with a human (or software) adversary. Such pre-training is again internal to the agent and can in principle be quantized. Similarly, beyond self-play, training can be performed using a simulation: for instance, in the precursor to the AlphaGo system, a learning machine was trained to play many Atari games at superhuman level (Mnih et al 2015). Although, once trained, the machine could in principle be used to build a robot to play on an actual computer, all the training and evaluation is performed relative to an emulation of the Atari system. Again, such emulations or simulations can be quantized, as they can be realized internal to the agent.

The AE paradigm is typically encountered in the contexts of RL, robotics and more general AI settings, while it is less common in ML communities. Nonetheless, conventional ML scenarios can naturally be embedded in this paradigm, since it is, ultimately, mostly unrestrictive. For instance, supervised learning can be thought of as an interaction with an environment which is, for a certain number of steps, an effective database (or the underlying process, generating the data) providing training examples. After a certain number of steps, the environment starts providing unlabeled data points and the agent responds with the labels. If we further assume the environment additionally responds with the correct label to whatever the agent sent, when the data point/percept was from the training set, we can straightforwardly read out the empirical risk (training set error) from the history. Since the quantization of the AE paradigm naturally leads to four settings—CC, CQ, QC and QQ—depending on whether the agent, or environment, or both are fully quantum systems, we can classify all of the results in quantum ML into one of the four groups. Such coarse-grained division places standard ML in CC, results on using ML to control quantum systems in CQ, quantum speed-ups in ML algorithms (without a quantum database, as is the case in annealing approaches) in QC and quantum ML/RL where the environments, databases or oracles are quantum-accessible are QQ. This classification is closely related to the classification introduced in Aïmeur et al (2006), which uses the $L^{\rm context}_{\rm goal}$ notation, where 'context' may denote whether we are dealing with classical or quantum data and/or learner and 'goal' specifies the learning task (see section 5.1.1 for more details).

The quantum-AE-based separation is not, however, identical to the $L^{\rm context}_{\rm goal}$ systematics. For instance, classical learning tasks may require quantum access or classical access, depending on the details of the setting. Quantum access is required in most quantum ML algorithms which rely on a quantum database. Thus, in the quantum AE paradigm, even when we deal with a classical ML problem, we may be facing a QQ scenario. However, if one considers the bigger picture, the database itself must be pre-filled at some point using classical interfaces. If this is included in the description of the same quantum ML algorithm, we obtain a QC setting (which now may fail to be as efficient). Both viewpoints make sense depending on the scenario which we choose to consider, which may not be obvious in the classification of Aïmeur et al (2006). On the other hand, the $L^{\rm context}_{\rm goal}$ systematics does a nice job separating classical ML from quantum generalizations of ML, discussed in section 5.

This mismatch between these two classifications also illustrates the difficulties one encounters if a sufficiently coarse-grained classification of the quantum ML field is required. The classification criteria of this field, and also aspects of QAI, in this review have been inspired by both the AE-induced criteria (perhaps natural from a physics perspective) and the $L^{\rm context}_{\rm goal}$ classification (which is more objective driven, and natural from a computer science perspective).