Flip It: A Game with QECC

Weilei Zeng

January 19, 2020

Figure 1: The game ”Flip it”. play it here http://www.4399.com/flash/8366_2.htm

“Flip it” is a small math game. It was played on a board with many units on it. Each units

has two colors/sides, white and black. One can ﬂip the unit and all units next to it by clicking on

this unit. Each time the game starts with certain pattern of ﬂipped units, and then try to make all

units in white.

I can imagine there are smart solutions to it. Since I am working on error correction, I will solve

it in my way. If you know error correction, then the idea is straightforward. Otherwise, you have

to ﬁnd clue in the linear algebra of the equations in the following context, which is also not that

hard to understand.

First, what is an error correction code? let us start with a code deﬁned on a rectangular lattice

(e.g. the playing board) with parity check matrix G. The columns of G represents bits (units on the

board). Each row of G represents a parity check, which measures the bits that have nonzero entry.

When some unknown error e occurs, one measures the parity checks and get the corresponding

syndromes s

T

= Ge

T

( some pattern of ﬂipped units). Then determine an error e

0

which given

the same syndrome and the apply e

0

such that overall e + e

0

reaches zero syndrome. In the game

1

“Flip it” The error we try to determine is the units we need to click such that all units (syndromes)

become white (zero). Then “Flip it” is exactly an error correcting codes. We just need to know

which code it is.

To solve the problem, ﬁrst write check matrix G for given size a × b. The parity checks are

just the bit itself plus its neighboring four bits. The initial state of the lattice in the game is the

measured syndrome s. Our goal is to ﬁgure out e which satisﬁes Ge

T

= s

T

. If G is full rank, then

e

T

= G

−1

s

T

. There is a unique solution.

For some lattice size, G is not full rank. That is, the solution of this game is not unique. There

are conﬁgurations of e which has no eﬀect on the lattice at all. Those are the solutions to the

homogeneous equation Gx = 0. In this case, there is no well deﬁned G

−1

, so I solve it by rewriting

Ge = s as Ge + s = 0. Then deﬁne H = (G, s), and q = (e, 1), and solve Hq

T

= 0.

Now we have solve the problem by applying techniques of error correction or linear algebra.

Then I have some interesting ﬁndings.

First, in any solution, when one of the four edges in the lattice is given, then the row/column

next to the edge can be derived and thus the whole lattice is determined. This implied that, this

problem is not in the complexity of 2

ab

, but 2

min(a,b)

, where a, b are the dimension of the lattice.

Consequently, the input and output of the problem can be simpliﬁed to just one line/edge instead

of the whole lattice. One can push the nonzero entries in the board to an edge. Then solve for the

error. Here only the error on that edge need to be extracted, instead of the whole lattice.

Second, the error correction mentioned here is classical, what about quantum error correction?

Can we make a quantum version of the game? To do that, and to avoid confusion, ﬁrst I need

to point out that the code mapping to “Flip it” is very unique that its parity check matrix is the

same as the adjacent matrix of its graph. Its parity checks happened to measure the bit itself and

all bits connected to it. Then a similar quantum version would be ideally to target on the surface

code. (here we choose the surface code on a square lattice with smooth boundaries in both x and

y direction. It encode zero logical qubit and it is okay to make this game). Similar to surface code,

we will let the qubits sit on bonds. The X and Z errors can be mapped to clicking on the bonds

using left and right mouse button, respectively. Each vertex represents a vertex operator and each

square represents a plaquette operator.

At this point, it is clear that this quantum game has been played and drawed in many research

papers involving decoding surface codes. But if we can still publish this quantum game online, it

would be interesting that what algorithm people will be using, minimum path matching or neural

network?

2