2014/06/30 by Jennifer Barry, Daniel T. Barry, Scott Aaronson · 1 citation
Computer Science · Physics and Astronomy · #cs.AI #quant-ph
paper · pdf · doi:10.1103/physreva.90.032311
published as Phys. Rev. A 90, 032311, 2014 · 13 pages, 3 figures, revised version (fixes several errors, discusses related work)
arxiv created 2014/10/01 · arxiv updated 2015/06/19
We present quantum observable Markov decision processes (QOMDPs), the quantum analogues of partially observable Markov decision processes (POMDPs). In a QOMDP, an agent's state is represented as a quantum state and the agent can choose a superoperator to apply. This is similar to the POMDP belief state, which is a probability distribution over world states and evolves via a stochastic matrix. We show that the existence of a policy of at least a certain value has the same complexity for QOMDPs and POMDPs in the polynomial and infinite horizon cases. However, we also prove that the existence of a policy that can reach a goal state is decidable for goal POMDPs and undecidable for goal QOMDPs.