The emerging field of quantum machine learning has the potential to substantially aid in the problems and scope of artificial intelligence. This is only enhanced by recent successes in the field of classical machine learning. In this work we propose an approach for the systematic treatment of machine learning, from the perspective of quantum information. Our approach is general and covers all three main branches of machine learning: supervised, unsupervised and reinforcement learning. While quantum improvements in supervised and unsupervised learning have been reported, reinforcement learning has received much less attention. Within our approach, we tackle the problem of quantum enhancements in reinforcement learning as well, and propose a systematic scheme for providing improvements. As an example, we show that quadratic improvements in learning efficiency, and exponential improvements in performance over limited time periods, can be obtained for a broad class of learning problems. PACS numbers: 03.67.-a, 03.67. Ac, 03.65.Aa, 03.67.Hk, 03.67.Lx Introduction.-The field of artificial intelligence (AI) has lately had remarkable successes, especially in the area of machine learning [1, 2] . A recent milestone, until recently believed to be decades away -a computer beating an expert human player in the game of Go [3] -clearly illustrates the potential of learning machines. In parallel, we are witnessing the emergence of a new field: quantum machine learning (QML), which has a further, profound potential to revolutionize the field of AI, much like quantum information processing (QIP) has influenced its classical counterpart [4] . The evidence for this is already substantiated with improvements reported in classification and clustering [5] [6] [7] [8] problems. Such tasks are representative of two of the three main branches of machine learning. The first, supervised learning, considers the problem of learning the conditional distribution P (y|x) (e.g., a function y = f (x)) which assigns labels y to data x (i.e. classifies data), based on correctly-labeled examples, called the training set, provided from a distribution P (x, y). The second, unsupervised learning, uses samples to identify a structure in a distribution P (x), e.g., identifies clusters. The quantum analog of the first task corresponds to a tomography-type problem where conditional states ρ x Y (states of a partition of a system, given a measurement outcome of another partition) should be reconstructed from the measurement statistics of the joint state ρ XY , which encodes the distribution P (x, y). The unsupervised case is similar. The third branch, reinforcement learning (RL) constitutes an interactive mode of learning, and is more gen- * vedran.dunjko@uibk.ac.at † jmtaylor@umd.edu ‡ hans.briegel@uibk.ac.at eral. Here the learning agent (or learning algorithm) learns how to behave correctly through the use of reinforcement signals -rewards, or punishments. RL has been less investigated from a quantum information perspective, although some results have been reported [9, 10] . The key question of how quantum processing can help in learning requires us to clarify what constitutes a good learning model. This can be involved, but two characteristics are typically considered. The first is the computational complexity of the algorithm of the learner. The second, sample complexity, is standard for supervised learning, and quantifies how large the training set has to be, for the algorithm to learn the distribution P (y|x). That is, in a tomography context, it counts the number of copies of ρ XY required until the learning algorithm can reconstruct the states ρ x Y to desired confidence. In RL, sample complexity is usually substituted by learning efficiency -the number of interaction steps needed for the agent to learn to obtain the rewards with high probability. The recent results in QML have focused on improving computational complexity [5] [6] [7] [8] 10] , with only few recent works considering sample complexity aspects [11] or supervised computational learning [12, 13] . However, the broader question of how, and to what extent, AI can ultimately benefit from quantum mechanics, in general learning settings, remains largely open. In this work we address this question, with emphasis on the more general, and less explored, RL setting. We propose a paradigm for considering QML, which allows us to better understand its limits and its power. Using this, we present a schema for identifying settings where quantum effects can help. To illustrate how the schema works, we provide a method for achieving quantum improvements (polynomial in the required number of interaction rounds and exponential improvements in success rate) in many arXiv:1610.08251v1 [quant-ph] 26 Oct 2016 2 RL settings. A paradigm for QML.-All three learning settings fit in the paradigm of so-called learning agents [14] , standard in the field of artificial intelligence. Here we consider a learning agent A (equivalently a learning program A) which interacts with an unknown environment E (the so-called task environment, or problem setting) via the exchange of messages, interchangeably issued by A (called actions A = {a i }) and E (called percepts S = {s j }). In the quantum extension, these sets become Hilbert spaces, H A = span{|a i }, H S = span{|s i }, and form orthonormal bases. The percept and action states, and their mixtures, are referred to as classical states. Any figure of merit Rate(·) of the performance of an agent A in E is a function of the history of interaction H h = (a 1 , s 1 , . . .), collecting the exchanged percepts and actions. The history of interaction is thus the central concept in learning. The correct quantum generalization of the history is not trivial, and we will deal with this momentarily. If either A or E are stochastic, the interaction of A and E is described by a distribution over histories (of length t), denoted by A ↔ t E. Most figures of merit are then extended to such distributions by convex-linearity. To recover, e.g., supervised learning in this paradigm, take E to be characterized by the distribution P (x, y), where the agent is given the training set -n labeled data points (pairs (x, y)) sampled from P (x, y) -as the first n percepts. After this, the agent is to respond with the correct labels as actions (responses) to the presented percepts, which are now the unlabeled data-points x. Reinforcement learning is naturally phrased as such an agentenvironment interaction, where the percept space also contains the reward. We denote the percept space including the reward status asS (e.g., if rewards are binary thenS = S × {0, 1}). Formally, the agent-environment paradigm is a twoparty interactive setting, and thus convenient for a quantum information treatment of QML. All the existing results group into four categories [15] : CC, CQ, QC and QQ, depending on whether the agent (first symbol) or the environment (second symbol) are classical (C) or quantum (Q). This classification is reminiscent to, but should not be confused with, the classification of quantum computational universality [22] where C/Q specify whether the input/outputs of a quantum computation are classical. The CC scenario covers classical machine learning. The CQ setting asks how classical learning techniques may aid in quantum tasks, such as quantum control [16, 17] , quantum metrology [18] , adaptive quantum computing [19] and the design of quantum experiments [20] . Here we deal with, for example, nonconvex or nonlinear optimization problems arising in quantum experiments, tackled by machine learning techniques. QC corresponds to quantum variants of learning algorithms [7, 10, 21 ] facing a classical environment. Figuratively speaking, this studies the potential of a learning robot, enhanced with a "quantum chip". In QQ settings, the focus of this work, both A and E are quantum systems. Here, the interaction can be fully quantum, and even the question of what it means "to learn" becomes problematic as, for instance, the agent and environment may become entangled. Framework.-Since learning constitutes a two-player interaction, standard quantum extensions can be applied: the action and percept sets are represented by the aforementioned Hilbert spaces H A , H S . The agent and the environment act on a common communication register R C (capable of representing both percepts and actions). Thus, the agent (environment) is described as a sequence of completely positive trace-preserving (CPTP) maps {M t A } ({M t E })-one for each time-step -which acts on the register R C , but also a private register R A (R E ) which constitutes the internal memory of the agent (environment). This is illustrated in Fig. 1 above the dashed line. The central object characterizing an interaction, namely its history, is, for the quantum case, generated by performing periodic measurements on R C in the classical (often called computational) basis. The generalization of this process for the quantum case is a tested interaction: we define the tester as a sequence of controlled maps of the form where x ∈ S ∪ A, and {U x t } x are unitary maps acting on the tester register R T , for all steps t. The history, relative to a given tester, is defined to be the state of the register R T . A tested interaction is shown in Fig. 1 . 2 come Hilbert spaces, H A = span{|a i i}, H S = span{|s i i}, and form orthonormal bases. The percept and action states, and their mixtures, are referred to as classical states. Any figure of merit Rate(·) of the performance of an agent A in E is a function of the history of interaction H 3 h = (a 1 , s 1 , . . .), collecting the exchanged percepts and actions. The history of interaction is thus the central concept in learning. The correct quantum generalization of the history is not trivial, and we will deal with this momentarily. If either A or E are stochastic, the interaction of A and E is described by a distribution over histories (of length t), denoted by A $ t E. Most figures of merit are then extended to such distributions by convex-linearity. To recover, e.g., supervised learning in this paradigm, take E to be characterized by the distribution P (x, y), where the agent is given an n sized sample of (x, y) pairs as the first n percepts. After this, the agent is to respond with labels as actions to given percepts, now unlabeled data-points x. This setting is native to RL if the percept space also contains the reinforcement signal -the reward. We denote the percept space including the reward status asS (e.g., if rewards are binary thenS = S ⇥ {0, 1}). The agent-environment paradigm is a two-party interactive setting, and thus convenient for a quantum information treatment of QML. All the existing results group into four categories: CC, CQ, QC and QQ, depending on whether the agent (first symbol) or the environment (second symbol) are classical (C) or quantum (Q) [30] . The CC scenario covers classical machine learning. The CQ setting asks how classical ML techniques may aid in quantum tasks, such as quantum control [14, 15] , quantum metrology [16] , adaptive quantum computing [17] and the design of quantum experiments [18] . Here we, for example, deal with non-convex/non-linear optimization problems arising in quantum experiments, tackeled by ML techniques. QC corresponds to quantum variants of learning algorithms [7, 10, 19 ] facing a classical environment. Figuratively speaking, this studies the potential of a learning robot, enhanced with a with a "quantum chip". In QQ settings, the focus of this work, both A and E are quantum systems. Here, the interaction can be fully quantum, and even the question of what it means "to learn" becomes problematic as, for instance, the agent and environment may become entangled. Framework.-Since learning constitutes a two-player interaction, standard quantum extensions can be applied: the dashed line. The central object characterizing an interaction, namely its history, is, for the classical case, recovered by performing periodic measurements on R C in the classical (often called computational) basis. The generalization of this process for the quantum case is a tested interaction: we define the tester as a sequence of controlled maps of the form and {U x t } x are unitary maps acting on the tester register R T , for all steps t. The history, relative to a given tester, is defined to be the state of the register R T . A tested interaction is shown in Fig. 1 . In general, each map of the tester U T k acts on a fresh subsystem of the register RT , which is not under the control of the agent of the environment. The crossed wires represent multiple systems. The restriction that testers are controlled maps relative to the classical basis guarantees that, for any choice of the local maps U x T , the interaction between classical A and E remains unchanged. A classical tester copies the content of R C relative to the classical basis, which has essentially the same e↵ect as measuring R C and copying the outcome. In other words, the interface between A and E is then classical. It can be shown that, in the latter case, for any quantum agent and/or environment there exist classical A and E which generate the same history under any tester [20] . In other words, classical agents can, in QC settings and, equivalently, in classically tested QQ settings, achieve the same performance as quantum agents, in terms of any history-dependent figure of merit. Thus, the only improvements can then be in terms of computational complexity. Scope and limits of quantum improvements.-What is the ultimate potential of quantum improvements in learning? In the QC and classically tested settings, we are bound to computational complexity improvements, which have been achieved in certain cases. Improvements in learning e ciency require special type of access to the The restriction that testers are controlled maps relative to the classical basis guarantees that, for any choice of the local maps U x T , the interaction between classical A and E remains unchanged. A classical tester copies the content of R C relative to the classical basis, which has essentially the same effect as measuring R C and copying the outcome. In other words, the interface between A and E is then classical. It can be shown that, in the latter case, for any quantum agent and/or environment there exist classical A and E which generate the same history under any tester (see the Appendix for details). In other words, classical agents can, in QC settings and, equivalently, in classically tested QQ settings, achieve the same performance as quantum agents, in terms of any historydependent figure of merit. Thus, the only improvements can then be in terms of computational complexity. Scope and limits of quantum improvements.-What is the ultimate potential of quantum improvements in learning? In the QC and classically tested settings, we are bound to computational complexity improvements, which have been achieved in certain cases. Improvements in learning efficiency require special type of access to the environments, which is not fully tested. Exactly this is done in [6, 8] , for the purpose of improving computational complexity, with great success, as the improvement can be exponential. There, the classical source of samples is substituted by a quantum RAM [25] architecture, which allows for the accessing of many samples in superposition. Such a substitution comes naturally in (un)supervised settings, as the basic interaction comprises only two steps and is memoryless -the agent requests M samples, and the environment provides them. However, in more general settings, environments are illsuited for such quantum parallel approaches: in general, the environment stores all the actions of the agent it in its memory, never to return them again. This effectively breaks the entanglement in the agent's register R A , and prohibits all interference effects. Nonetheless, for many environmental settings, it is still possible to 'dissect' the maps of the environment, and to provide oracular variants, which we can use to help the agent learn. An approach to quantum improvements in reinforcement learning.-This brings us to our schema for improving RL agents. First, given a classical environment E, we define fair unitary oracular equivalents E q . Here, fair is meant in the same sense as quantum oracles of boolean functions are fair analogues of classical boolean functions -E q should not provide more information than E under classical access, which is guaranteed, e.g., when E q is realizable from a reversible version of E. Second, as access to any quantum environment E q cannot generically speed-up all aspects of an interaction (e.g., while quantum walks can find target vertices faster, the price is that the traversed path is undefined), we identify particular environmental properties which can be more efficiently ascertained using E q , and which are relevant for learning. Third, we construct an improved agent which uses the properties from the previous points. We now illustrate our approach on a restricted scenario, for the ease of presentation, and show how the examples generalize later. Application of the framework.-Given any task environment, we can separately consider the map which specifies the next percept the environment will present-in general, a stochastic function f E : H → S, mapping elapsed histories onto the next percept -and the reward function. function. The latter is described as the map Λ : H × S →S which also depends on the history, and complements the percept by setting its reward status. In environments which are simple and strictly epochal (meaning the environment is re-set after M steps and at most one reward is given), although the interaction is turn-based, it can be represented as sequences of M −step maps: where the "bar" on s M highlights that it includes a reward status. Moreover, in deterministic environments, the maps f E and Λ only depend on the actions of the agent, as the percept responses are fixed. For such deterministic, simple strictly epochal environments, the construction of an appropriate oracle is dramatically simplified. The actions can be returned to the agent after each block of M steps, as the next block is independent. Moreover, using phase kick-back, the reward map can be modified (see the Appendix for details) such as to influence just the global phase of returned action states. This leads to the "phase-flip" oracle realizing One use of this environment-specific oracle requires M interaction steps. This constitutes the first step of our proposed schema. Next, we focus on step two: obtaining a useful property of the environment, and identifying settings where it provably helps. The constructed oracle points towards the use of Grover-type search to find rewarding action sequences. This alone suffices for improvements only in special environments where learning reduces to searching. We can do better by combining fast search with a classical learning model. In canonical RL settings, what the agent learns (should learn!) is not a correct sequence of moves per se, but rather the correct association of actions given percepts. To illustrate this, imagine navigating a maze where the percepts encode correct directions of movement. If the correct association is learned, then the agent will perform well, even when the maze changes. Nonetheless, for the agent to learn the correct association, it first must encounter an instance of rewarding sequences, and here quantum access helps. Thus we aim at assisting in the exploration phase of the balancing act between exploration (trying out behaviors to find optima) and exploitation (reaping rewards by using learned information) characteristic for RL [26] . This idea can be made fully precise by considering the class of environments where more successful exploration phases are guaranteed to lead to a better overall learning performance. Whether this is the case, however, also depends also on the learning model of the agent. Thus we identify agent-environment pairs, where such better performance in the past (in exploration) implies better performance in the future (on average), which we call luck-favoring settings. More formally, consider environments E, and agents A, such that if h t and h t are t−length histories, then Rate(h t ) > Rate(h t ) (i.e. h t is a history with a better performance than h t ) implies (3) for some future period T . Here E(h) and A(h) denote the environment and agent, respectively, which have undergone the history h, (note that A(h) and A are, technically, different agents). We will say A(h t ) is luckier than A(h t ). Such environment-agent pairs (A, E), satisfying the formal conditions above, are thus luck-favoring, and we may additionally specify the periods t and T for which the implication (3) holds. This brings us to step three of the schema, given as a Theorem. Theorem 1 Let E be a deterministic, strictly epochal environment. Then there exists an oracular variant E q of E, such that for any classical learning model A which is luck-favoring relative to E, and figure of merit Rate which is monotonically increasing in the number of rewards in the history, we can construct a quantum agent A q such that A q , by interacting with E q , outperforms A in terms of the figure of merit Rate relative to a chosen tester. This Theorem states that, in the restricted settings of determinisic epochal environments, it is possible to generically improve the learning efficiency of all learning agents, provided the environments are luck-favoring for those agents. We note that most reasonable learning models are luck-favoring relative to most typically considered task environments (see the Appendix for a longer discussion). In the statement of Theorem 1, we have omitted additional specifications pertaining to t and T, but it should be understood that if the luck favoring property holds for t and T, then the improved performance holds relative to these periods. To prove Theorem 1 we construct A q , given A. The construction is illustrated step by step in Fig. 2 , where for illustrative purposes, the classical interaction of agent A is contrasted against the quantum interaction of agent A q . Step 1: A q will use the quantum oracle variant of E ( E q oracle ) for time t ∈ O( |A| M ), where M is the epoch length, and |A| is the number of the actions, to find a rewarding action sequence a r , using Grover search. During this period the interaction is untested, and the interaction is fully classically tested thereafter. Step 2: A q will play out one epoch by outputting actions from a r sequentially, now with the classical environment, to obtain the responses of the environment (recall, E q oracle cannot provide these), obtaining the entire rewarding history h r . Thus far, A q used O(M |A| M ) interaction steps. Step 3: A q "trains" an internal simulation of A, simulating the interaction between A and E, and restarting the simulation until the history h r occurs (we assume such an occurrence has a non-zero probability). This may require many internally simulated interactions, but no interaction with the real environment. In Step 4, the internal simulation of A(h r ) corresponds to the luckiest agent possible, and A q relinquishes control to it. Finally, we consider what happens with A during the same time periods. Unless additional information about the environment is given, in O(t) steps A has only an exponentially small (O(exp(−M ln(|A|)/2))) probability of having seen the rewarding sequence. Thus, the quantum agent is luckier than the classical, and in luck-favoring Step 1,2 Step 3 Step 4 Step 1 Step Step 3: A q simulates the agent A, and 'trains' the simulation to produce the rewarding sequence. In Step 4, A q uses A(hr) for the remainder of the now classically tested interaction, with the classical environment E. settings, this implies that A q will continue to outperform A after the t steps. The statement of Theorem 1 is not quantitative, due to the generality of the definition of luck-favoring settings. We can, however, trade off generality for exactness. If an agent A employs a variant of −greedy [26] behavior -that is, it outputs the rewarding sequence (exploits) with probability and explores with probability 1 − , then the ratio of the performances of A q and A will be exponential in M : the constant reward probability of A q versus the exponentially diminishing O(exp(−M ln(|A|)/2))) of A at step t. This exponential gap holds for time-scales T ∈ O(t). However, the improvement in terms of learning efficiency (number of interaction steps) is quadratic. Our results achieve solid improvements using simple techniques, at the cost of restricting the task environments. However, our example can be further generalized in two directions. First, as long as the re-set occurs at step M , multiple and multi-valued rewards can also be handled by defining oracles which reversibly count the rewards. Highly rewarding sequences can then be found through quantum optimization techniques [27] , as worked out in the Appendix. Second, under stronger assumptions on E q , using more involved quantum subroutines, we can deal with stochastic environments. For instance, in the setting with one reward per epoch, the oracle |a |0 where sin 2 θ a is the probability of a reward, given the action sequence a, can be constructed from a reversible implementation of the environment where randomness is represented as a subsystem of an entangled state (see the Appendix for details). From here, by using phase kick-back and phase estimation the agent can realize the mapping |a |0 → |a θ a , whereθ a is an l−bit precision estimate of the reward probability as specified by the angle θ a . Next, amplitude amplification is used to amplitude-amplify all sequences a where the reward probability p r (a) given sequence a, is above a threshold p min . Given N min such sequences (out of N tot := |A| M sequences in total), the overall number of interactions steps multiplies M with the amplitude amplification cost (O((N tot If the minimal relevant success probability is constant for a family of task environments, then this constitutes a quadratic improvement in finding good action sequences. This approach can also be generalized to a wider class of settings (see the Appendix for details). In many settings, e.g., robotics, the classical environments do not allow "oracularization". Nonetheless, the presented constructions can be used in model-based learning [14] , where the agent constructs an internal representation of the environment to facilitate better learning through simulation. Then, the "quantum chip" can help in speeding-up internal processing, which is the most that can be done in QC settings. A tantalizing exception to this may be nano-scale robots (e.g. intelligent versions of in-situ probes in [19] ) in future quantum experiments, as on these scales the environment is manifestly quantum and exquisite control becomes a possibility. Conclusions.-In this work we have extended the general agent-environment framework of artificial intelligence [14] to the quantum domain. Based on this, we have established a schema for quantum improvements in learning, beyond computational complexity. Using this schema, we have given explicit constructions of quantumenhanced reinforcement learning agents, which outperform their classical counterparts quadratically in terms of learning efficiency, or even exponentially in performance over limited periods. This constitutes an important step towards a systematic investigation of the full potential of quantum machine learning, and the first step in the context of reinforcement learning under quantum interaction. ACKNOWLEDGMENTS
A general framework for quantum machine learning is presented in REF .
Quantum-enhanced machine learning
Phys. Rev. Lett. 117, 130501 (2016)
Computer Science Physics Medicine