• Editors' Suggestion

Quantum partially observable Markov decision processes

Jennifer Barry, Daniel T. Barry, and Scott Aaronson
Phys. Rev. A 90, 032311 – Published 9 September 2014

Abstract

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.

  • Figure
  • Figure
  • Figure
  • Received 12 June 2014

DOI:https://doi.org/10.1103/PhysRevA.90.032311

©2014 American Physical Society

Authors & Affiliations

Jennifer Barry1,*, Daniel T. Barry2,†, and Scott Aaronson3,‡

  • 1Rethink Robotics, Boston, Massachusetts 02210, USA
  • 2Denbar Robotics, Sunnyvale, California 94085, USA
  • 3Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA

  • *jbarry@csail.mit.edu
  • dbarry@denbarrobotics.com
  • aaronson@csail.mit.edu

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 90, Iss. 3 — September 2014

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×