Termination of Nondeterministic Quantum Programs

Details Termination of Nondeterministic Quantum Programs Termination of Nondeterministic Quantum Programs

2012-01-04

arxiv.org/abs/1201.0891v1

Computer Science

Logic in Computer Science

Scientific paper

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. An execution of a nondeterministic quantum program is modeled by a sequence of actions of individual processes. These actions are described by super-operators on the state Hilbert space. At each step of an execution, a process is chosen nondeterministically to perform the next action. 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 of a nondeterministic quantum program. 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. A striking difference between nondeterministic classical and quantum programs is shown by example: it is possible that each of several quantum programs simulates the same classical program which terminates with probability 1, but the nondeterministic program consisting of them terminates with probability 0 due to the interference carried in the execution of them.

Affiliated with

Also associated with

No associations

Rating

Termination of Nondeterministic Quantum Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Termination of Nondeterministic Quantum Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Termination of Nondeterministic Quantum Programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-156504