A decision procedure for well-formed linear quantum cellular automata
| dc.creator | Durr, Christoph | |
| dc.creator | LeThanh, Huong | |
| dc.creator | Santha, Miklos | |
| dc.date | 1999-06-23 | |
| dc.date | 2000-10-27 | |
| dc.date.accessioned | 2026-07-07T03:24:10Z | |
| dc.date.available | 2026-07-07T03:24:10Z | |
| dc.description | In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is $O(n^2)$ in the algebraic model of computation if the input automaton has continuous neighborhood. | |
| dc.identifier | https://arxiv.org/abs/cs/9906024 | |
| dc.identifier | http://arxiv.org/abs/cs/9906024 | |
| dc.identifier | Random Structures and Algorithms 11, 381-394, 1997 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33224 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | Quantum Physics | |
| dc.subject | F.1.1; F.2.1 | |
| dc.title | A decision procedure for well-formed linear quantum cellular automata | |
| dc.type | text |