Premium
A decision procedure for well‐formed linear quantum cellular automata
Author(s) -
Dürr Christoph,
LêThanh Huong,
Santha Miklos
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199712)11:4<381::aid-rsa6>3.0.co;2-v
Subject(s) - cellular automaton , quantum computer , quantum cellular automaton , computation , quantum , computer science , block cellular automaton , quantum algorithm , automaton , algorithm , theoretical computer science , property (philosophy) , reversible cellular automaton , stochastic cellular automaton , discrete mathematics , mathematics , mobile automaton , automata theory , quantum mechanics , physics , philosophy , epistemology
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. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 11 , 381–394 (1997)