Complexity Explorer Santa Few Institute

1. Say the creature at the beginning of the lecture is started off in state [321]; you then hit it with C, C, C, S, and then C. What state is it in now?
A. 231
B. 123
C. 321
D. 213

Answer (A): [321]-C->[132]-C->[213]-C->[321]-S->[312]-C->[231]. Note that the order of the operations matters! C, C, C, S, then C is not the same as C, S, C, C, then C (convince yourself it’s true). Unfortunately, different fields have different traditions for the order in which they write them down. In this module, we “read” from left to right, so would write CCCSC. Physicists, however, often think of the operations as being “done” to a creature sitting on the right-hand side of the page, and so they would “read” the order of operations from right to left. When order matters, we say that the operations “don’t commute”; groups with non-commuting operations are called “non-abelian”.

2. Which of these operations is an identity operation? (i.e., takes every state back to itself)

A. CSC
B. CSCS
C. CCC
D. Both (B) and (C)

Answer (D). CSC cycles down, swaps, and cycles: 123->312->321->132. You'll notice that another swap will take you back to 123. A little thinking should convince you that it's the case for every single initial state (which you need for the CSCS operation to be the identity). CCC is an easier one; taking the bottom card and putting it on top three times in a row will necessarily get you back to where you started with a stack of three cards.

3. What does it mean that the creature is "reversible"?
A. for every state that the creature begins in, and every sequence of moves I do to it, I can find a sequence of moves that gets me back to the original state.
B. for every sequence of moves I do to the creature, I can find a sequences that restores it to its original state, and that sequence doesn't depend on the initial state of the creature.
C. for every sequence of moves I do to the creature, most of them leave it unchanged.
D. there is a sequence of moves I can do to the creature that invariably take it back to a unique "reset" state.

Answer (B). (A) is too restrictive; if the creature is reversible, you're guaranteed the ability to undo all your damage, even if you don't know what the original state is. (C) is a funny way of saying that many of the moves are "identity" moves (i.e., trivially undo-able); but this doesn't say anything about the ability to undo all moves. (D) is actually the exact opposite of reversible: if there's a move, or sequence of moves, that resets the creature, putting it in a unique starting state, this means that if I do those moves, I'll never be able to recover the original creature state with another set of moves in the manner of (B).