Quantum Cellular Automata: Theory and Applications

I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. iii This thesis presents a model of Quantum Cellular Automata (QCA). The presented formalism is a natural quantization of the classical Cellular Automata (CA). It is based on a lattice of qudits, and an update rule consisting of local unitary opera-tors that commute with their own lattice translations. One purpose of this model is to act as a theoretical model of quantum computation, similar to the quantum circuit model. The main advantage that QCA have over quantum circuits is that QCA make considerably fewer demands on the underlying hardware. In particu-lar, as opposed to direct implementations of quantum circuits, the global evolution of the lattice in the QCA model does not assume independent control over indi-vidual qudits. Rather, all qudits are to be addressed collectively in parallel. Th