Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Machine Intelligence Research

Optimal Policies for Quantum Markov Decision Processes

Mingsheng Ying, Yuan Feng, Shenggang Ying

Published Mar 19, 2021• 15 citations
Publisher

Abstract

Abstract Markov decision process (MDP) offers a general framework for modelling sequential decision making where outcomes are random. In particular, it serves as a mathematical framework for reinforcement learning. This paper introduces an extension of MDP, namely quantum MDP (qMDP), that can serve as a mathematical model of decision making about quantum systems. We develop dynamic programming algorithms for policy evaluation and finding optimal policies for qMDPs in the case of finite-horizon. The results obtained in this paper provide some useful mathematical tools for reinforcement learning techniques applied to the quantum world.

DOI
10.1007/s11633-021-1278-z

Related papers

Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

Joao F. Doriguello

Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard approach to study such interaction is through Markov Decision Processes (MDPs) and the task of choosing an optimal policy --- a function that tells the agent which action to take. In this work, we study two types of MDPs --- finite-horizon and infinite-horizon discounted --- and propose new quantum algorithms for computing approximate optimal policies. Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, overall enhanced with techniques from sample-optimal classical algorithms. Our resulting query complexities improve upon previous works, thus approaching already established quantum lower bounds.

quant-pharXiv:2608.02826•Aug 5, 2026•0 citations

Quantum Markov Decision Processes: General Theory, Approximations, and Classes of Policies

Naci Saldı, Sina Sanjari, Serdar Yüksel

Abstract. In this paper, the aim is to develop a quantum counterpart to classical Markov decision processes (MDPs). First, we provide a very general formulation of quantum MDPs with state and action spaces in the quantum domain, quantum transitions, and cost functions. Once we formulate the quantum MDP (q-MDP), our focus shifts to establishing the verification theorem that proves the sufficiency of Markovian quantum control policies and provides a dynamic programming principle. Subsequently, a comparison is drawn between our q-MDP model and previously established quantum MDP models (referred to as QOMDPs) found in the literature. Furthermore, approximations of q-MDPs are obtained via finite-action models, which can be formulated as QOMDPs. Finally, classes of open-loop and classical-state-preserving closed-loop policies for q-MDPs are introduced, along with structural results for these policies. In summary, we present a novel quantum MDP model aiming to introduce a new framework, algorithms, and future research avenues. We hope that our approach will pave the way for a new research direction in discrete-time quantum control.

arXiv:2402.14649•SIAM Journal on Control and Optimization•Apr 11, 2025•2 citations

Quantum Algorithms for Reinforcement Learning with a Generative Model

Daochen Wang, Aarthi Sundaram, Robin Kothari +2 more

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 ($\frac{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.

arXiv:2112.08451•Dec 15, 2021•14 citations

Quantum logic gate synthesis as a Markov decision process

M. Sohaib Alam, Noah Berthusen, Peter P. Orth

Abstract Reinforcement learning has witnessed recent applications to a variety of tasks in quantum programming. The underlying assumption is that those tasks could be modeled as Markov decision processes (MDPs). Here, we investigate the feasibility of this assumption by exploring its consequences for single-qubit quantum state preparation and gate compilation. By forming discrete MDPs, we solve for the optimal policy exactly through policy iteration. We find optimal paths that correspond to the shortest possible sequence of gates to prepare a state or compile a gate, up to some target accuracy. Our method works in both the absence and presence of noise and compares favorably to other quantum compilation methods, such as the Ross–Selinger algorithm. This work provides theoretical insight into why reinforcement learning may be successfully used to find optimally short gate sequences in quantum programming.

arXiv:1912.12002•npj Quantum Information•Oct 25, 2023•14 citations

Adaptive Quantum Control Policies via Reinforcement Learning

Jincheng Zhang

This paper presents a novel approach to designing adaptive quantum control policies using reinforcement learning (RL). Traditional methods for quantum control often rely on hand-designed pulse shapes or iterative optimization techniques, which can be computationally expensive and may not generalize well to different systems or desired operations. We propose a framework where an RL agent learns to dynamically adjust quantum control parameters in real-time, based on the system's state and the objective of achieving a specific quantum gate with high fidelity. The core of our approach lies in formulating the quantum control problem as a Markov Decision Process (MDP) and utilizing an RL algorithm to train a policy that maps system states to control parameters. We demonstrate the feasibility and effectiveness of this method through a theoretical analysis and a simplified numerical simulation. The resulting adaptive control policies offer a significant advantage over traditional methods, particularly for complex quantum systems and demanding fidelity requirements. The key contributions are the integration of RL for adaptive control and the formalization of the problem as an MDP.

•Sep 3, 2026•0 citations

Quantum Markov Decision Processes

Naci Saldı, Sina Sanjari, Serdar Yüksel

In this paper, we aim to develop a quantum counterpart to classical Markov decision processes (MDPs), referred to as q-MDPs. We first present a comprehensive formulation of quantum MDPs with state and action spaces in the quantum domain, quantum transitions, and cost functions. The focus then shifts to establishing a verification theorem for Markovian quantum control policies. Subsequently, we introduce classes of open-loop and classical-state-preserving closed-loop policies and present their structural results. Finally, we develop algorithms for computing optimal policies and value functions for both open-loop and classical-state-preserving closed-loop policies using the duality between dynamic programming and semi-definite programming formulations.

IEEE Conference on Decision and Control (CDC)•Dec 16, 2024•0 citations
Abstract Markov decision process (MDP) offers a general framework for modelling sequential decision making where outcomes are random. In particular, it serves as a mathematical framework for reinforcement learning. This paper introduces an extension of MDP, namely quantum MDP (qMDP), that can serve as a mathematical model of decision making about quantum systems. We develop dynamic programming algorithms for policy evaluation and finding optimal policies for qMDPs in the case of finite-horizon. The results obtained in this paper provide some useful mathematical tools for reinforcement learning techniques applied to the quantum world.
Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard approach to study such interaction is through Markov Decision Processes (MDPs) and the task of choosing an optimal policy --- a function that tells the agent which action to take. In this work, we study two types of MDPs --- finite-horizon and infinite-horizon discounted --- and propose new quantum algorithms for computing approximate optimal policies. Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, overall enhanced with techniques from sample-optimal classical algorithms. Our resulting query complexities improve upon previous works, thus approaching already established quantum lower bounds.
Abstract. In this paper, the aim is to develop a quantum counterpart to classical Markov decision processes (MDPs). First, we provide a very general formulation of quantum MDPs with state and action spaces in the quantum domain, quantum transitions, and cost functions. Once we formulate the quantum MDP (q-MDP), our focus shifts to establishing the verification theorem that proves the sufficiency of Markovian quantum control policies and provides a dynamic programming principle. Subsequently, a comparison is drawn between our q-MDP model and previously established quantum MDP models (referred to as QOMDPs) found in the literature. Furthermore, approximations of q-MDPs are obtained via finite-action models, which can be formulated as QOMDPs. Finally, classes of open-loop and classical-state-preserving closed-loop policies for q-MDPs are introduced, along with structural results for these policies. In summary, we present a novel quantum MDP model aiming to introduce a new framework, algorithms, and future research avenues. We hope that our approach will pave the way for a new research direction in discrete-time quantum control.
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∗v^*v∗), and the optimal QQQ-function (q∗q^*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 (11−γ\frac{1}{1-γ}1−γ1​) and the size of the action space (AAA). Moreover, we show that our quantum algorithm for computing q∗q^*q∗ is optimal by proving a matching quantum lower bound.
Abstract Reinforcement learning has witnessed recent applications to a variety of tasks in quantum programming. The underlying assumption is that those tasks could be modeled as Markov decision processes (MDPs). Here, we investigate the feasibility of this assumption by exploring its consequences for single-qubit quantum state preparation and gate compilation. By forming discrete MDPs, we solve for the optimal policy exactly through policy iteration. We find optimal paths that correspond to the shortest possible sequence of gates to prepare a state or compile a gate, up to some target accuracy. Our method works in both the absence and presence of noise and compares favorably to other quantum compilation methods, such as the Ross–Selinger algorithm. This work provides theoretical insight into why reinforcement learning may be successfully used to find optimally short gate sequences in quantum programming.
This paper presents a novel approach to designing adaptive quantum control policies using reinforcement learning (RL). Traditional methods for quantum control often rely on hand-designed pulse shapes or iterative optimization techniques, which can be computationally expensive and may not generalize well to different systems or desired operations. We propose a framework where an RL agent learns to dynamically adjust quantum control parameters in real-time, based on the system's state and the objective of achieving a specific quantum gate with high fidelity. The core of our approach lies in formulating the quantum control problem as a Markov Decision Process (MDP) and utilizing an RL algorithm to train a policy that maps system states to control parameters. We demonstrate the feasibility and effectiveness of this method through a theoretical analysis and a simplified numerical simulation. The resulting adaptive control policies offer a significant advantage over traditional methods, particularly for complex quantum systems and demanding fidelity requirements. The key contributions are the integration of RL for adaptive control and the formalization of the problem as an MDP.
In this paper, we aim to develop a quantum counterpart to classical Markov decision processes (MDPs), referred to as q-MDPs. We first present a comprehensive formulation of quantum MDPs with state and action spaces in the quantum domain, quantum transitions, and cost functions. The focus then shifts to establishing a verification theorem for Markovian quantum control policies. Subsequently, we introduce classes of open-loop and classical-state-preserving closed-loop policies and present their structural results. Finally, we develop algorithms for computing optimal policies and value functions for both open-loop and classical-state-preserving closed-loop policies using the duality between dynamic programming and semi-definite programming formulations.