Reachability analysis of quantum Markov decision processes

Ying, S; Ying, M

Reachability analysis of quantum Markov decision processes

Ying, S Ying, M

Permalink

Publication Type:: Journal Article
Citation:: Information and Computation, 2018, 263 pp. 31 - 51
Issue Date:: 2018-12-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Submitted VersionAdobe PDF (319.55 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Ying, S	en_US
dc.contributor.author	Ying, M https://orcid.org/0000-0003-4847-702X	en_US
dc.date.issued	2018-12-01	en_US
dc.identifier.citation	Information and Computation, 2018, 263 pp. 31 - 51	en_US
dc.identifier.issn	0890-5401	en_US
dc.identifier.uri	http://hdl.handle.net/10453/117698
dc.description.abstract	© 2018 Elsevier Inc. We introduce the notion of quantum Markov decision process (qMDP) as a semantic model of nondeterministic and concurrent quantum programs. It is shown by examples that qMDPs can be used in analysis of quantum algorithms and protocols. We study various reachability problems of qMDPs both for the finite-horizon and for the infinite-horizon. The (un)decidability and complexity of these problems are settled, and the relationship between one of them and the joint spectral radius problem, a long-standing open problem in matrix analysis and control theory, is clarified. Some of these results show a certain separation between the MDP and qMDP models. We also develop an algorithm for finding an optimal scheduler for a large class of qMDPs. Finally, the results of reachability problems are applied in the analysis of the safety problem for qMDPs.	en_US
dc.relation.ispartof	Information and Computation	en_US
dc.relation.isbasedon	10.1016/j.ic.2018.09.001	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	Reachability analysis of quantum Markov decision processes	en_US
dc.type	Journal Article
utslib.citation.volume	263	en_US
utslib.for	020603 Quantum Information, Computation and Communication	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
utslib.for	08 Information and Computing Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US
pubs.volume	263	en_US

Abstract:

© 2018 Elsevier Inc. We introduce the notion of quantum Markov decision process (qMDP) as a semantic model of nondeterministic and concurrent quantum programs. It is shown by examples that qMDPs can be used in analysis of quantum algorithms and protocols. We study various reachability problems of qMDPs both for the finite-horizon and for the infinite-horizon. The (un)decidability and complexity of these problems are settled, and the relationship between one of them and the joint spectral radius problem, a long-standing open problem in matrix analysis and control theory, is clarified. Some of these results show a certain separation between the MDP and qMDP models. We also develop an algorithm for finding an optimal scheduler for a large class of qMDPs. Finally, the results of reachability problems are applied in the analysis of the safety problem for qMDPs.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/117698