  The study of Markov models is central to control theory and machine learning.
A quantum analogue of partially observable Markov decision process was studied
in (Barry, Barry, and Aaronson, Phys. Rev. A, 90, 2014). It was proved that
goal-state reachability is undecidable in the quantum setting, whereas it is
decidable classically. In contrast to this classical-to-quantum transition from
decidable to undecidable, we observe that the problem of approximating the
optimal policy which maximizes the average discounted reward over an infinite
horizon remains decidable in the quantum setting. Given that most relevant
problems related to Markov decision process are undecidable classically (which
immediately implies undecidability in the quantum case), this provides one of
the few examples where the quantum problem is tractable.
