# Meeting notes 11 04 14

Kamil: Quantum cellular automata (CAs), and Deutsch's model of a quantum Turing machine.

- Classical 1-D CAs

Given a bit string, e.g. 00110101, apply an *update rule*, in which each bit is replaced by some function of a neighborhood of that bit.

- Turing Machine

Now there's a bit string, say, 00110101, but with a duck in the middle, named Robert, or R for short. Say 001R10101. Robert is a cross-dressing duck, and sometimes also goes by Lucy, or L.

Update rules can be of the form: <math>xR0\rightarrow x0R'</math>, in which Robert changes state to <math>R'</math> or <math>xR1\rightarrow xL0</math>, in which he changes direction (and gender).

- Quantum Cellular Automata (
*a la*Watrous)

There is an infinite sequences of qubits. Each qubit interacts with its neighbors at every time step. So, upon input <math>\cdots |x_{-1}\rangle \otimes |x_0\rangle \otimes |x_1\rangle\cdots</math>, we replace the middle qubit with <math>M_{x_{-1},x_0,x_1}|x_0\rangle</math>, where each <math>M_{x_{-1},x_0,x_1}</math> is a (not necessarily unitary) matrix.

This formalism is pretty general, and it's not obvious what conditions to impose on the <math>M_{x_{i-1},x_i,x_{i+1}}</math> matrices to make the overall evolution unitary. But you can go in the other direction, and turn a global unitary evolution into a quantum CA, if your original evolution was sufficiently local. To see how to do this, we turn to.

- Quantum Turing Machines (
*a la*Deutsch)

States are of the form <math>|x:{D}:\vec{T}\rangle</math>, where <math>x</math> labels position, <math>D</math> is the internal state of the TM (aka duck) and <math>\vec{T}</math> is the tape.

The state is initially <math>|0,0,\vec T\rangle</math> and is repeated acted on by <math>U</math>, where <math>U</math> is some translationally invariant unitary, like <math>\sum_x |x+1\rangle\langle x|\otimes V_{R,x} + |x\rangle\langle x+1| \otimes V_{L,x}</math>, where <math>V_{L,x}, V_{R,x}</math> act on <math>D</math> and the qubit at position <math>x</math> in a way that otherwise doesn't depend on <math>x</math>.

- Idea for a universal QCA

Use the path-integral formulation of quantum computing: see (quant-ph/0408129, this paper on algebraic circuits and the instantaneous quantum computing work (0809.0847 and 1005.1407).

The QCA would alternate Hadamards on every qubits with a controlled phase on adjacent triples of qubits (i.e. flip the phase if all three are 1).

### Status Updates

- Paul

Turning his quals project into a paper.

Working with Austin Fowler on FTQC with the surface code.

Thinking about copyability of quantum states, vaguely inspired by quantum money.