dorsal/arxiv
View SchemaComputation in Finitary Stochastic and Quantum Processes
| Authors | Karoline Wiesner, James P. Crutchfield |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0608206 |
| URL | https://arxiv.org/abs/quant-ph/0608206 |
Abstract
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's 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.
{
"annotation_id": "6c92bd19-748c-4349-9116-634cef7fd42d",
"date_created": "2026-03-02T18:02:31.150000Z",
"date_modified": "2026-03-02T18:02:31.150000Z",
"file_hash": "62e9ffc5b25313aee170ef566ed910d6d4b1359340e1ec0b4dbdabc83840e3eb",
"private": false,
"record": {
"abstract": "We introduce stochastic and quantum finite-state transducers as\ncomputation-theoretic models of classical stochastic and quantum finitary\nprocesses. Formal process languages, representing the distribution over a\nprocess\u0027s behaviors, are recognized and generated by suitable specializations.\nWe characterize and compare deterministic and nondeterministic versions,\nsummarizing their relative computational power in a hierarchy of finitary\nprocess languages. Quantum finite-state transducers and generators are a first\nstep toward a computation-theoretic analysis of individual, repeatedly measured\nquantum dynamical systems. They are explored via several physical systems,\nincluding an iterated beam splitter, an atom in a magnetic field, and atoms in\nan ion trap--a special case of which implements the Deutsch quantum algorithm.\nWe show that these systems\u0027 behaviors, and so their information processing\ncapacity, depends sensitively on the measurement protocol.",
"arxiv_id": "quant-ph/0608206",
"authors": [
"Karoline Wiesner",
"James P. Crutchfield"
],
"categories": [
"quant-ph"
],
"title": "Computation in Finitary Stochastic and Quantum Processes",
"url": "https://arxiv.org/abs/quant-ph/0608206"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "ad1bb9ef-cd48-40ea-bdb2-8d9149c774da",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}