A decision procedure for unitary linear quantum cellular automata

Abstract

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.

Updated for submission to SIAM Journal on Computing. Improved slightly the algorithm

Cited by in corpus (10)

• On the absence of homogeneous scalar unitary cellular automata
• Quantum mechanics of lattice gas automata. II. Boundary conditions and other inhomogeneities
• Unitarity in one dimensional nonlinear quantum cellular automata
• The Measurement Calculus
• Quantum field theory from a quantum cellular automaton in one spatial dimension and a no-go theorem in higher dimensions
• Generalized Cayley Graphs and Cellular Automata over them
• Causal graph dynamics
• An overview of Quantum Cellular Automata
• Quantum Pushdown Automata
• Quantum Automata and Quantum Grammars