We introduce a classical-quantum hybrid approach to computation, allowing for a quadratic performance improvement in the decision process of a learning agent. Using the paradigm of quantum accelerators, we introduce a routine that runs on a quantum computer, which allows for the encoding of probability distributions. This quantum routine is then employed, in a reinforcement learning set-up, to encode the distributions that drive action choices. Our routine is well-suited in the case of a large, although finite, number of actions and can be employed in any scenario where a probability distribution with a large support is needed. We describe the routine and assess its performance in terms of computational complexity, needed quantum resource, and accuracy. Finally, we design an algorithm showing how to exploit it in the context of Q-learning.
We introduce a classical-quantum hybrid approach to computation, allowing for a quadratic performance improvement in the decision process of a learning agent. Using the paradigm of quantum accelerators, we introduce a routine that runs on a quantum computer, which allows for the encoding of probability distributions. This quantum routine is then employed, in a reinforcement learning set-up, to encode the distributions that drive action choices. Our routine is well-suited in the case of a large, although finite, number of actions and can be employed in any scenario where a probability distribution with a large support is needed. We describe the routine and assess its performance in terms of computational complexity, needed quantum resource, and accuracy. Finally, we design an algorithm showing how to exploit it in the context of Q-learning.
Combining quantum computing techniques in the form of amplitude amplification with classical reinforcement learning has led to the so-called “hybrid agent for quantum-accessible reinforcement learning”, which achieves a quadratic speedup in sample complexity for certain learning problems. So far, this hybrid agent has only been applied to stationary learning problems, that is, learning problems without any time dependency within components of the Markov decision process. In this work, we investigate the applicability of the hybrid agent to dynamic RL environments and thus to more realistic scenarios. To this end, we enhance the hybrid agent by introducing a dissipation mechanism and, with the resulting learning agent, perform an empirical comparison with a classical RL agent in an RL environment with a time-dependent reward function. Our findings suggest that the modified hybrid agent can adapt its behavior to changes in the environment quickly, leading to a higher average success probability compared to its classical counterpart.
Abstract In the last decade quantum machine learning has provided fascinating and fundamental improvements to supervised, unsupervised and reinforcement learning (RL). In RL, a so-called agent is challenged to solve a task given by some environment. The agent learns to solve the task by exploring the environment and exploiting the rewards it gets from the environment. For some classical task environments, an analogue quantum environment can be constructed which allows to find rewards quadratically faster by applying quantum algorithms. In this paper, we analytically analyze the behavior of a hybrid agent which combines this quadratic speedup in exploration with the policy update of a classical agent. This leads to a faster learning of the hybrid agent compared to the classical agent. We demonstrate that if the classical agent needs on average ⟨J⟩ rewards and ⟨T⟩cl epochs to learn how to solve the task, the hybrid agent will take ⟨ T ⟩ q ⩽ α s α o ⟨ T ⟩ c l ⟨ J ⟩ epochs on average. Here, α s and α o denote constants depending on details of the quantum search and are independent of the problem size. Additionally, we prove that if the environment allows for maximally α o k max sequential coherent interactions, e.g. due to noise effects, an improvement given by ⟨T⟩q ≈ α o ⟨T⟩cl/(4k max) is still possible.
Understanding the power and limitations of quantum access to data in machine learning tasks is primordial to assess the potential of quantum computing in artificial intelligence. Previous works have already shown that speed-ups in learning are possible when given quantum access to reinforcement learning environments. Yet, the applicability of quantum algorithms in this setting remains very limited, notably in environments with large state and action spaces. In this work, we design quantum algorithms to train state-of-the-art reinforcement learning policies by exploiting quantum interactions with an environment. However, these algorithms only offer full quadratic speed-ups in sample complexity over their classical analogs when the trained policies satisfy some regularity conditions. Interestingly, we find that reinforcement learning policies derived from parametrized quantum circuits are well-behaved with respect to these conditions, which showcases the benefit of a fully-quantum reinforcement learning framework.
Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a γ-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy (π∗), the optimal value function (v∗), and the optimal Q-function (q∗), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy (ε) and two main parameters of the MDP: the effective time horizon (1−γ1) and the size of the action space (A). Moreover, we show that our quantum algorithm for computing q∗ is optimal by proving a matching quantum lower bound.
Pairwise sequence alignment is central in bioinformatics for analyzing DNA, RNA, and proteins, revealing similarities that inform evolutionary relationships, gene or protein functions, and disease mechanisms. Classical dynamic programming guarantees optimal alignments but scales poorly, while heuristics reduce runtime at the cost of optimality and still require high resources. Quantum algorithms exploit superposition and entanglement to accelerate optimization or find exact solutions faster. We present a hybrid quantum reinforcement learning (RL) agent based on (Hamann & Wölk, 2022), optimized for NISQ hardware. The agent learns a policy mapping states to action sequences from feedback of an environment. Using a Grover-like subroutine, it evaluates all sequences in parallel, reinforcing those leading to a solution, which reduces environment interactions and can achieve a quadratic speedup over classical RL. To enable execution on current hardware, we introduce a novel Parameterized Quantum Policy embedding entire action sequences, combined with a simplified Grover routine using a black-box oracle. This reduces resource demands but requires prior knowledge and retraining per alignment, limiting generalization. We also outline design ideas for a more general Grover oracle and circuit with broader generalization, which, while not NISQ-compatible, suggest a promising direction for future work.
The recent rise in the number of data-intensive applications has revealed some inherent limitations of traditional machine learning, such as high training costs, slow convergence rates, and the uncapable of scalability of traditional machine learning in high-dimensional spaces. Bottlenecks are caused by the iterative optimization procedure, kernel evaluations, and similarity computations that are not efficiently supported by traditional hardware. Although recent advances in quantum computing, such as the Variational Quantum Algorithm, quantum kernels, and parameterized quantum circuits, hold promise for acceleration, the application of quantum speedup is presently hindered by noisy intermediate-scale quantum computing. This research provides a hybrid quantum-classical acceleration method that integrates quantum methods with selected computationally intensive components of classical machine learning systems rather than attempting to entirely replace them. Carried out a comprehensive analysis of the performance of well-known algorithms like Support Vector Machines, k-means clustering, and gradient-based neural networks in classical and quantum-assisted hybrid scenarios. The quantum resources are greatly beneficial for particular sub-tasks such as optimization, approximation of similarity, and exploration of the feature space, with the remaining learning process performed classically. Our analysis reveals that hybrid methods can offer a tangible acceleration and improved convergence behaviour in particular scenarios without sacrificing accuracy. Moreover, the analysis investigates the trade-offs associated with the utilization of quantum resources, robustness to noise, and orchestration costs.