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.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.

arXiv:cs/9906024Jun 23, 19991 citation

Classification of Quantum Cellular Automata

Michael Freedman, Matthew B. Hastings

arXiv:1902.10285Communications in Mathematical PhysicsApr 6, 202060 citations

A decision procedure for well‐formed linear quantum cellular automata

Christoph Dürr, Huong LêThanh, Miklós Sántha

Random Structures and AlgorithmsDec 1, 19975 citations

Structures in quantum cellular automata

Gerhard Grössing, Anton Zeilinger

Physica B+CJul 1, 198829 citations

A decision procedure for well-formed linear quantum cellular automata

Christoph Dürr, Huong L�Thanh, Miklós Sántha

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(n2) in the algebraic model of computation if the input automaton has continuous neighborhood. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11, 381–394 (1997)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(n2) in the algebraic model of computation if the input automaton has continuous neighborhood. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11, 381–394 (1997)

Random Structures and AlgorithmsDec 1, 199719 citations

O(n^2)

in the algebraic model of computation if the input automaton has continuous neighborhood.

O(n^2)

in the algebraic model of computation if the input automaton has continuous neighborhood.