A Note on Quantum Markov Models
This provides a rare example of tractability in quantum control theory, which is significant for researchers in quantum computing and machine learning, though it is incremental as it builds on prior undecidability results.
The paper addresses the decidability of approximating optimal policies in quantum Markov decision processes, showing that this problem remains decidable in the quantum setting, unlike many classical counterparts that are undecidable.
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.