A decision procedure for unitary linear quantum cellular automata
| dc.creator | Durr, Christoph | |
| dc.creator | Santha, Miklos | |
| dc.date | 1996-04-09 | |
| dc.date | 1999-06-21 | |
| dc.date.accessioned | 2026-07-07T09:05:09Z | |
| dc.date.available | 2026-07-07T09:05:09Z | |
| dc.description | Linear quantum cellular automata were introduced recently as one of the models of quantum computing. A basic postulate of quantum mechanics imposes a strong constraint on any quantum machine: it has to be unitary, that is its time evolution operator has to be a unitary transformation. In this paper we give an efficient algorithm to decide if a linear quantum cellular automaton is unitary. The complexity of the algorithm is O(n^((3r-1)/(r+1))) = O(n^3) in the algebraic computational model if the automaton has a continuous neighborhood of size r, where $n$ is the size of the input. | |
| dc.description | Updated for submission to SIAM Journal on Computing. Improved slightly the algorithm | |
| dc.identifier | https://arxiv.org/abs/quant-ph/9604007 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/9604007 | |
| dc.identifier | Proceeding of the 37th IEEE Symposium on Foundations of Computer Science, 38--45, 1996 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/149623 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | A decision procedure for unitary linear quantum cellular automata | |
| dc.type | text |