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.

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

arXiv:cs/9906024Jun 23, 19991 citation

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.

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(4r-3)/(r+1))=O(n/sup 4/) if the automaton has a continuous neighborhood of size r.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(4r-3)/(r+1))=O(n/sup 4/) if the automaton has a continuous neighborhood of size r.

Annual Symposium on Foundations of Computer ScienceDec 23, 200216 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

On one-dimensional quantum cellular automata

John Watrous

Since Richard Feynman introduced the notion of quantum computation in 1982, various models of "quantum computers" have been proposed (R. Feynman, 1992). These models include quantum Turing machines and quantum circuits. We define another quantum computational model, one dimensional quantum cellular automata, and demonstrate that any quantum Turing machine can be efficiently simulated by a one dimensional quantum cellular automaton with constant slowdown. This can be accomplished by consideration of a restricted class of one dimensional quantum cellular automata called one dimensional partitioned quantum cellular automata. We also show that any one dimensional partitioned quantum cellular automaton can be simulated by a quantum Turing machine with linear slowdown, but the problem of efficiently simulating an arbitrary one dimensional quantum cellular automaton with a quantum Turing machine is left open. From this discussion, some interesting facts concerning these models are easily deduced.Since Richard Feynman introduced the notion of quantum computation in 1982, various models of "quantum computers" have been proposed (R. Feynman, 1992). These models include quantum Turing machines and quantum circuits. We define another quantum computational model, one dimensional quantum cellular automata, and demonstrate that any quantum Turing machine can be efficiently simulated by a one dimensional quantum cellular automaton with constant slowdown. This can be accomplished by consideration of a restricted class of one dimensional quantum cellular automata called one dimensional partitioned quantum cellular automata. We also show that any one dimensional partitioned quantum cellular automaton can be simulated by a quantum Turing machine with linear slowdown, but the problem of efficiently simulating an arbitrary one dimensional quantum cellular automaton with a quantum Turing machine is left open. From this discussion, some interesting facts concerning these models are easily deduced.

Annual Symposium on Foundations of Computer ScienceNov 19, 2002156 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.

n

is the size of the input.