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

SIAM Journal on ComputingJan 1, 200217 citations

A decision procedure for unitary linear quantum cellular automata

Christoph Dürr, Miklós Sántha

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

arXiv:quant-ph/9604007Apr 9, 199624 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(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

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

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

From Quantum Cellular Automata To Quantum Lattice Gases

DAVID A. MEYER, From Qca, Qlga David +1 more

A natural architecture for nanoscale quantum computation is that of a quantum cellular automaton. Motivated by this observation, in this paper we begin an investigation of exactly unitary cellular automata. After proving that there can be no nontrivial, homogeneous, local, unitary, scalar cellular automaton in one dimension, we weaken the homogeneity condition and show that there are nontrivial, exactly unitary, partitioning cellular automata. We find a one parameter family of evolution rules which are best interpreted as those for a one particle quantum automaton. This model is naturally reformulated as a two component cellular automaton which we demonstrate to limit to the Dirac equation. We describe two generalizations of this automaton, the second of which, to multiple interacting particles, is the correct definition of a quantum lattice gas. KEY WORDS: quantum cellular automaton; quantum lattice gas; quantum computation. to appear in J. Stat. Phys.A natural architecture for nanoscale quantum computation is that of a quantum cellular automaton. Motivated by this observation, in this paper we begin an investigation of exactly unitary cellular automata. After proving that there can be no nontrivial, homogeneous, local, unitary, scalar cellular automaton in one dimension, we weaken the homogeneity condition and show that there are nontrivial, exactly unitary, partitioning cellular automata. We find a one parameter family of evolution rules which are best interpreted as those for a one particle quantum automaton. This model is naturally reformulated as a two component cellular automaton which we demonstrate to limit to the Dirac equation. We describe two generalizations of this automaton, the second of which, to multiple interacting particles, is the correct definition of a quantum lattice gas. KEY WORDS: quantum cellular automaton; quantum lattice gas; quantum computation. to appear in J. Stat. Phys.

Jan 1, 1996458 citations

n

is the size of the input.

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.