Quantum partially observable Markov decision processes
We present quantum observable Markov decision processes (QOMDPs), the quantum analogs of partially observable Markov decision processes (POMDPs). In a QOMDP, an agent is acting in a world where the state is represented as a quantum state and the agent can choose a superoperator to apply. This is sim...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2014
|
| Online Access: | http://hdl.handle.net/1721.1/89468 https://orcid.org/0000-0003-1333-4045 |
| _version_ | 1811083436108021760 |
|---|---|
| author | Barry, Jennifer Barry, Daniel T. Aaronson, Scott |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Barry, Jennifer Barry, Daniel T. Aaronson, Scott |
| author_sort | Barry, Jennifer |
| collection | MIT |
| description | We present quantum observable Markov decision processes (QOMDPs), the quantum analogs of partially observable Markov decision processes (POMDPs). In a QOMDP, an agent is acting in a world where the 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. |
| first_indexed | 2024-09-23T12:33:02Z |
| format | Article |
| id | mit-1721.1/89468 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:33:02Z |
| publishDate | 2014 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/894682022-10-01T09:42:24Z Quantum partially observable Markov decision processes Barry, Jennifer Barry, Daniel T. Aaronson, Scott Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott We present quantum observable Markov decision processes (QOMDPs), the quantum analogs of partially observable Markov decision processes (POMDPs). In a QOMDP, an agent is acting in a world where the 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. National Science Foundation (U.S.) (Grant 0844626) National Science Foundation (U.S.) (Grant 1122374) National Science Foundation (U.S.) (Waterman Award) 2014-09-12T17:39:21Z 2014-09-12T17:39:21Z 2014-09 2014-06 2014-09-09T22:00:24Z Article http://purl.org/eprint/type/JournalArticle 1050-2947 1094-1622 http://hdl.handle.net/1721.1/89468 Barry, Jennifer, Daniel T. Barry, and Scott Aaronson. "Quantum partially observable Markov decision processes." Phys. Rev. A 90, 032311 (September 2014). © 2014 American Physical Society https://orcid.org/0000-0003-1333-4045 en http://dx.doi.org/10.1103/PhysRevA.90.032311 Physical Review A Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. American Physical Society application/pdf American Physical Society American Physical Society |
| spellingShingle | Barry, Jennifer Barry, Daniel T. Aaronson, Scott Quantum partially observable Markov decision processes |
| title | Quantum partially observable Markov decision processes |
| title_full | Quantum partially observable Markov decision processes |
| title_fullStr | Quantum partially observable Markov decision processes |
| title_full_unstemmed | Quantum partially observable Markov decision processes |
| title_short | Quantum partially observable Markov decision processes |
| title_sort | quantum partially observable markov decision processes |
| url | http://hdl.handle.net/1721.1/89468 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT barryjennifer quantumpartiallyobservablemarkovdecisionprocesses AT barrydanielt quantumpartiallyobservablemarkovdecisionprocesses AT aaronsonscott quantumpartiallyobservablemarkovdecisionprocesses |