Computation in finitary stochastic and quantum processes

K Wiesner, JP Crutchfield

Research output: Contribution to journalArticle (Academic Journal)peer-review

15 Citations (Scopus)


We introduce stochastic and quantum finite-state transducers as computation-theoretic models of classical stochastic and quantum finitary processes. Formal process languages, representing the distribution over a process’ behaviors, are recognized and generated by suitable specializations. We characterize and compare deterministic and nondeterministic versions, summarizing their relative computational power in a hierarchy of finitary process languages. Quantum finite-state transducers and generators are a first step toward a computation-theoretic analysis of individual, repeatedly measured quantum dynamical systems. They are explored via several physical systems, including an iterated-beam-splitter, an atom in a magnetic field, and atoms in an ion trap—a special case of which implements the Deutsch quantum algorithm. We show that these systems’ behaviors, and so their information processing capacity, depends sensitively on the measurement protocol.
Translated title of the contributionComputation in finitary stochastic and quantum processes
Original languageEnglish
Pages (from-to)1173 - 1195
Number of pages23
JournalPhysica D: Nonlinear Phenomena
Issue number9
Publication statusPublished - 1 Jul 2008

Bibliographical note

Publisher: Elsevier


Dive into the research topics of 'Computation in finitary stochastic and quantum processes'. Together they form a unique fingerprint.

Cite this