Quantum Speedup for Active Learning Agents

Can quantum mechanics help us build intelligent learning agents? A defining signature of intelligent behavior is the capacity to learn from experience. However, a major bottleneck for agents to learn in real-life situations is the size and complexity of the corresponding task environment. Even in a moderately realistic environment, it may simply take too long to rationally respond to a given situation. If the environment is impatient, allowing only a certain time for a response, an agent may then be unable to cope with the situation and to learn at all. Here, we show that quantum physics can help and provide a quadratic speedup for active learning as a genuine problem of artificial intelligence. This result will be particularly relevant for applications involving complex task environments.

Popular Summary

Quantum mechanics has been previously exploited in the contexts of computer science and communication, but whether it can offer provable enhancements in the task of designing autonomous learning agents such as robots has, thus far, hardly been explored. The increasing need for an autonomous workforce capable of handling involved tasks in conditions unsuitable for humans necessitates the design of artificial intelligence that is capable of quickly responding to, and learning from, a variety of complex environmental stimuli. We show that quantum physics can help provide a provable quadratic speedup for a broad family of autonomous active learning agents that operate in unknown and dynamic environments.

Learning from experience is a hallmark of intelligence—real-life situations are often complex and characterized by many variables. We consider the reinforcement-learning model of artificial intelligence where a reward is offered when a correct action is executed. The time required for the autonomous learning agent to evaluate its action must be taken into account, particularly when repeated actions are necessary. We employ the theory of a quantum random walk to show how an agent can explore its episodic memory in superposition to dramatically speed up its active learning time. Utilizing quantum physics to promote artificial intelligence learning has the ability to provide a quadratic increase in speed in active learning—critical when the environment changes on time scales of the “thinking” time of the autonomous learning agent.

The design of intelligent agents that outperform their classical counterparts will be advantageous for addressing environmental stimuli that change rapidly. Using quantum physics to create active learning agents will furthermore shed light on both the possibilities and limitations of engineering agents.

Figure 1

An agent is always situated in an environment. It is equipped with sensors, through which it receives percepts from the environment, and with actuators, through which it can act on the environment. Based on perceptual input, the agent will after some internal processing engage its actuators and output an action. This figure is adapted and modified from Refs. [20, 22].

Figure 2

Both the classical and the quantum RPS are characterized by their internal Markov chains over the clip space. The procedures the quantum agent performs in order to choose the desired actions are listed. The values $t_{\text{mix}}^q$ and $t_{\text{check}}^q$ are chosen in $\tilde{O}(1/\sqrt{{\delta }_s})$ and uniformly at random in $[0,\tilde{O}(1/\sqrt{{\epsilon }_s})]$, respectively; see the text for details.

Figure 3

(a) The simple PS model with flags. The transition from percept to action occurs in one step. Flags are percept dependent. (b) Intermediary step: The graph of (a) can be broken up into two graphs, by duplication of actions. (c) The straightforward analog of the simple PS in the reflecting-agent model. To each percept, a MC over the actions only is assigned, such that the stationary distribution recovers the initial output probabilities. The flags are trivially inherited.