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 flip the unit and all units next to it by clicking on
this unit. Each time the game starts with certain pattern of flipped 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 find 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 defined 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
= Ge
( some pattern of flipped units). Then determine an error e
which given
the same syndrome and the apply e
such that overall e + e
reaches zero syndrome. In the game
“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, first 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 figure out e which satisfies Ge
= s
. If G is full rank, then
= G
. 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 configurations of e which has no effect on the lattice at all. Those are the solutions to the
homogeneous equation Gx = 0. In this case, there is no well defined G
, so I solve it by rewriting
Ge = s as Ge + s = 0. Then define H = (G, s), and q = (e, 1), and solve Hq
= 0.
Now we have solve the problem by applying techniques of error correction or linear algebra.
Then I have some interesting findings.
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
, but 2
, where a, b are the dimension of the lattice.
Consequently, the input and output of the problem can be simplified 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, first 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