This is a puzzle about computations in a (generally nonabelian) group \(G\). Let \(a,b,c \in G\). You must compute \(abcb^{-1}a^{-1}c^{-1}\). You are permitted only to multiply elements and take inverses; no additional knowledge of the nature of \(G\) is allowed beyong the group structure itself.

This is not hard, so of course there’s a constraint. You have a computer with very little memory. In fact, you have only enough memory to store three elements of \(G\).

So: you begin with \(a,b,c\) in your three registers. By multiplying registers, or taking the inverse of any register, as many times as you like, can you arrange for one of the registers to contain \(abcb^{-1}a^{-1}c^{-1}\)? It does not matter what junk ends up in the rest of the registers.

As an example, to get \(abcb^{-1}a^{-1}\) (missing only the last factor) into the first register, we need two multiplications (putting \(abc\) into the register), followed by two inversions (to obtain \(b^{-1}\) and \(c^{-1}\)) and two more multiplications. All that’s needed is one last \(c^{-1}\) tacked onto the end.

Give it a shot.

This puzzle comes from the desire to compute the \(2\times 1\) plaquette shown in Figure 2 here as efficiently as possible. The answer is that it’s not possible.

To see this, note first that all permitted operations are reversible. (In the context of quantum computing, all available gates are unitary — but the puzzle doesn’t use the fact that we’re on a quantum processor.) If we want a non-reversible transformation, it’s not going to be possible! I claim that any transformation that dumps \(abcb^{-1}a^{-1}c^{-1}\) into one of the registers is fated to be irreversible.

Consider the case where \(G\) is abelian — or better yet, take \(G = \mathbb Z_2\). The desired quantity is always the identity for an abelian group. We start with three unknown group elements. When we end, one of the registers contains the identity, so we have only two unknown group elements. We lost information! In the case of \(\mathbb Z_2\), we start with three bits, and end up with two. There’s no way that’s reversible.

It’s much harder to see that the desired operation is irreversible for a general nonabelian group. In fact, for all I know, there may be nontrivial groups for which it is reversible. Nevertheless, the case of abelian groups shows that no general circuit can exist.

(Thanks to Henry Lamm for showing me this puzzle.)