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.