We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Termination of nondeterministic quantum programs.
- Authors
Li, Yangjia; Yu, Nengkun; Ying, Mingsheng
- 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.
- Subjects
QUANTUM mechanics; MARKOV processes; MACHINERY; DETERMINISTIC processes; INFORMATION technology; SET theory
- Publication
Acta Informatica, 2014, Vol 51, Issue 1, p1
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-013-0185-3