
N.B. These questions are provided to give you
something concrete to think about to exercise
your understanding of the concepts introduced in lectures.
Which of them you work is your choice, as is collaboration.
 June 18

 June 19

 June 20


Show how to compile a TM into a CA.

Show how to compile a BCA into a CA, and visa versa.

Sketch how an Nbit circuit can be compiled into an initial configuration
for the following 2D BCA, where input and output are provided and read
out, respectively, from chosen sites in the BCA. (adapted from Margolus,
p 136)

it has four states: { . , o, *, G } meaning {empty, wire, signal, gate}.

2 x 2 blocks remain unchanged, unless the set of states in the block is
exactly

o and *: diagonal cells exchange contents

., o, and *: in each cell o becomes * and * becomes o

G and anything: * becomes o in all cells, and in a cell diagonal from a
G, o becomes * if there is no other * present.
(Hint: construct wires, show they can cross, construct a NOT gate and a
NOR gate.)

Can the above BCA simulate a Turing Machine, if a finite input region is
specified? How about for a finite input region within a periodic
patterned background?
 Estimate area bounds for a 1024 node network:
 supporting completely random interconnect
 Tree or Mesh supporting c=4, p=0.67 designs
 June 21

 June 24

 July 10

 July 11

 July 12


Hint: Apply the hybrid argument that we used to show a lower
bound for the search problem.
 Show that a quantum error correcting code that is resilient
against both a bit and a phaseflip on one qubit is also resilient
against any linear error on one qubit. Verify this for the
9qubit Shor code.
What about linear errors on more qubits?
Hint: Can you express any linear operation on one qubit in
terms of the identity (no error), a bitflip, a phaseflip, and
a simultaneous bit and phase flip?

