The Logic Seminar will meet again this Friday. The speaker will be Bjørn Kjos-Hanssen.

Title:
Superposition as memory: unlocking quantum automatic complexity

Time:
Friday March 17, 2:30-3:20

Place: Keller 404 (Note: this might change)

Abstract:
Imagine a lock with two states, “locked” and “unlocked”, which may be manipulated using two operations, called 0 and 1. Moreover, the only way to (with certainty) unlock using four operations is to do them in the sequence 0011, i.e., $0^n1^n$ where $n=2$. In this scenario one might think that the lock needs to be in certain further states after each operation, so that there is some memory of what has been done so far. Here we show that this memory can be entirely encoded in superpositions of the two basic states “locked” and “unlocked”, where, as dictated by quantum mechanics, the operations are given by unitary matrices. Moreover, we show using the Jordan–Schur lemma that a similar lock is not possible for $n=60$.