Quantum cellular automata
Friday, August 27th, 2004Date: 27 August, 2004
Who: Charles Hill (UQ)
Seminar type: Journal Club
Abstract:
There are many models of quantum computing. Familiar models include the quantum circuit model, the quantum Turing machine, and the cluster state with measurements. There is another model: the Quantum Cellular Automata. Watrous’ paper shows that Quantum Cellular Automata can simulate a quantum Turing machine with a constant slowdown. Conversely, he shows that a restricted class of cellular automata can be simulated efficiently by a quantum Turing machine.
Background:
Watrous, J., “On One Dimensional Quantum Cellular Automata”, In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995, 528-537