Quantum POMDPs

Abstract

We present quantum observable Markov decision processes (QOMDPs), the quantum\nanalogues of partially observable Markov decision processes (POMDPs). In a\nQOMDP, an agent's state is represented as a quantum state and the agent can\nchoose a superoperator to apply. This is similar to the POMDP belief state,\nwhich is a probability distribution over world states and evolves via a\nstochastic matrix. We show that the existence of a policy of at least a certain\nvalue has the same complexity for QOMDPs and POMDPs in the polynomial and\ninfinite horizon cases. However, we also prove that the existence of a policy\nthat can reach a goal state is decidable for goal POMDPs and undecidable for\ngoal QOMDPs.\n