Termination of nondeterministic quantum programs

Li, Y; Yu, N; Ying, M

Termination of nondeterministic quantum programs

Li, Y Yu, N

Ying, M

Permalink

Publisher:: Springer
Publication Type:: Journal Article
Citation:: Acta Informatica, 2014, 51, (1), pp. 1-24
Issue Date:: 2014-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted versionAdobe PDF (246.22 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Li, Y
dc.contributor.author	Yu, N https://orcid.org/0000-0003-1188-3032
dc.contributor.author	Ying, M https://orcid.org/0000-0003-4847-702X
dc.date.accessioned	2023-03-14T01:44:52Z
dc.date.available	2023-03-14T01:44:52Z
dc.date.issued	2014-01
dc.identifier.citation	Acta Informatica, 2014, 51, (1), pp. 1-24
dc.identifier.issn	0001-5903
dc.identifier.issn	1432-0525
dc.identifier.uri	http://hdl.handle.net/10453/167291
dc.description.abstract	We define a language-independent model of nondeterministic quantum programs in which a quantum program consists of a finite set of quantum processes. These processes are represented by quantum Markov chains over the common state space, which formalize the quantum mechanical behaviors of the machine. An execution of a nondeterministic quantum program is modeled by a sequence of actions of individual processes, and at each step of an execution a process is chosen nondeterministically to perform the next action. This execution model formalize the users behavior of calling the processes in the classical world. Applying the model to a quantum walk as an instance of physically realizable systems, we describe an execution step by step. A characterization of reachable space and a characterization of diverging states of a nondeterministic quantum program are presented. We establish a zero-one law for termination probability of the states in the reachable space. A combination of these results leads to a necessary and sufficient condition for termination of nondeterministic quantum programs. Based on this condition, an algorithm is found for checking termination of nondeterministic quantum programs within a fixed finite-dimensional state space.
dc.language	English
dc.publisher	Springer
dc.relation	http://purl.org/au-research/grants/arc/DP110103473
dc.relation	National Natural Science Foundation of China60736011
dc.relation.ispartof	Acta Informatica
dc.relation.isbasedon	10.1007/s00236-013-0185-3
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s00236-013-0185-3
dc.subject	0802 Computation Theory and Mathematics, 0803 Computer Software, 0804 Data Format
dc.subject.classification	Computation Theory & Mathematics
dc.title	Termination of nondeterministic quantum programs
dc.type	Journal Article
utslib.citation.volume	51
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0803 Computer Software
utslib.for	0804 Data Format
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.consider-herdc	true
dc.date.updated	2023-03-14T01:44:51Z
pubs.issue	1
pubs.publication-status	Published
pubs.volume	51
utslib.citation.issue	1

Abstract:

We define a language-independent model of nondeterministic quantum programs in which a quantum program consists of a finite set of quantum processes. These processes are represented by quantum Markov chains over the common state space, which formalize the quantum mechanical behaviors of the machine. An execution of a nondeterministic quantum program is modeled by a sequence of actions of individual processes, and at each step of an execution a process is chosen nondeterministically to perform the next action. This execution model formalize the users behavior of calling the processes in the classical world. Applying the model to a quantum walk as an instance of physically realizable systems, we describe an execution step by step. A characterization of reachable space and a characterization of diverging states of a nondeterministic quantum program are presented. We establish a zero-one law for termination probability of the states in the reachable space. A combination of these results leads to a necessary and sufficient condition for termination of nondeterministic quantum programs. Based on this condition, an algorithm is found for checking termination of nondeterministic quantum programs within a fixed finite-dimensional state space.

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

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