Snowflakes and (Quantum) Error Correction- Part 1

#writing #physics #math

Snowflakes

I don't remember much from middle school (thank you selective memory). But one of the things I do distinctly remember is our lesson on snowflakes. Wondering: Why is it that there is snow? Why are there so many different types of snowflakes? And yet, despite the huge variety, how come they still satisfy certain universal properties (in particular, hexagonal symmetry)?

Anyhow, I'd go on, and maybe I will do a deeper dive into snowflakes later. (Now that I think about it, I do wonder if we understand why it is that not only the center of a snowflake is hexagonal, but even the ends of each "arm" are almost perfectly symmetric.)

But their purpose in this article is to serve as an example.

Let's just take for granted some property of snowflakes:

This is kind of nice! Maybe you could do something with it. For instance, let's say I assign a number to each type of snowflake. Then, I can communicate that number to you by sending you a snowflake (or I guess, more realistically, a picture of a snowflake), so that even if some malicious actor were to corrupt some parts of this "codeword," you'd still be able to decode the original codeword (and then map back to the number I'd wanted to send) by fixing the defects in the snowflake.

This seems like it could be a useful notion...

Error Correcting Codes

Let's try to formalize this setup. Alice and Bob (two perennially separated friends) would like to communicate with each other. However, they're only medium for transporting messages is noisy: their messages might have some characters flipped. right-lets-eat-grandma.png|200
For instance, Bob might mistakenly believe Alice wants to eat with her grandma, rather than eat her grandma!

Of course, if the channel can be arbitrarily noisy, then there's no hope of ever conveying any information. So instead, we'll assume that there's a limit to the extent to which the message can be corrupted.

Our goal might then be to be able to encode as many messages as possible while being robust to as large of a corruption as possible.

Like the "space of snowflakes"! (1) There's a lot of them, so we could encode a lot of numbers, and (2) they're all very different, so we can withstand large corruptions!

A simpler example: the Ising model

One way to define a code is to think of it as the ground states of a Hamiltonian, which is just a fancy way of saying, the objects that satisfy all of a particular set of constraints. For instance, for the snowflakes, one set of constraints (among many others that I don't know) is "if you rotate it by a multiple of 60 degrees, it'll look the same."

Another possible set of constraints, this time thinking of our objects as bit strings, is that the parity of any two neighboring bits is the same. In this case, the ground states are the string of all 0s or all 1s. Why? Set any arbitrary bit to 0. Then it's neighbors must also be 0, and their neighbors, and so on... The same applies if you'd set your original bit of choice to 1.

In Hamiltonian terms, we get the 1 dimensional Ising model:

$$H = \sum_{i=1}^n Z_i Z_{i+1}$$

In code terms, we get the repetition code; a simple, and kind of bad, but still non-trivial code. Its rate (log the number of messages) is just 1, but it has a perfect distance (minimum hamming distance between codewords) of $n$.

Better codes, quantum codes

For coding theorists, the holy grail of a code is one which is able to achieve what they call linear rate and linear distance. What this means is that $r=\log_2(\textrm{number messages})\geq \alpha n$ and $d=\min_{x_1,x_2}\mathrm{dist}(x_1,x_2)\geq \beta n$ where $\alpha$ and $\beta$ are constants independent of $n$. Classically, these have been known to exist since forever due to a clever but simple probabilistic argument. Construction was the hard part, coming several decades later via expander graphs (themselves an amazing and ubiquitous tool in theoretical CS).

What I'll be interested in discussing here will be quantum codes. Here, everything goes to sh**. The repetition code that we discussed above? Has distance 1. Probabilistic constructions of quantum codes? Nothing better than trivial.

But amazingly, a recent line of work culminating in a paper of Pantaleev and Kalachev showed that the "holy grail" indeed exists even in the quantum setting!

The goal of the rest of this series will be to try and understand some of this work, especially from a physics point of view. Hoping to draw out this connection that I've hinted at, between materials, which often seem to inherently have some strong robustness properties (this table that I'm sitting at isn't constantly changing properties, despite all the particles and photons and what not bombarding it), and error correcting codes.publish

Now, I don't really know much quantum, and don't really know much about error correction, and don't really know much physics. But hopefully I'll understand a little more of each, and be able to convey a little of each, by the end of this series.

Next to come...

This writeup was motivated by watching (and barely understanding) this series of lectures by Vedika Khemani on the Physics of LDPC Codes. It'll hopefully cover most of the things she talked about.