This portal has been archived. Explore the next generation of this technology.
A Note on Quantum Markov Models
lib:e74e2d8461c05a8f (v1.0.0)
Authors: Christino Tamon,Weichen Xie
ArXiv: 1911.01953
Document: PDF DOI
Abstract URL: https://arxiv.org/abs/1911.01953v1
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.
ArXiv: 1911.01953
Document: PDF DOI
Abstract URL: https://arxiv.org/abs/1911.01953v1
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.
Relevant initiatives
Related knowledge about this paper
Reproduced results (crowd-benchmarking and competitions)
Artifact and reproducibility checklists
- ACM/cTuning artifact appendix and reproducibility checklist
- NeurIPS reproducibility checklist
- SIGPLAN's checklist for empirical evaluation
- Collective Knowledge (organizing research projects based on FAIR principles)