Quantum Markov Decision Processes

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.