The Blooming of the \(c^3\) LTC Flowers

by Prahladh Harsha

The last year (2021–22) has seen some amazing new constructions of locally testable codes with constant rate and constant fractional distance and testable with a constant number of queries, sometimes referred to as \(c^3\) LTCs [DELLM22, PK22]. The construction of Panteleev and Kalachev’s LTCs [PK22] is almost identical to that of Dinur, Evra, Livne, Lubotzky, and Mozes [DELLM22]; while Dinur et al.’s main goal was to construct \(c^3\) LTCs, Panteleev and Kalachev were motivated by considerations of constructing quantum LDPC codes. In this short note, I give an informal description of some of the ideas that led to the \(c^3\) LTC construction of Dinur et al., focusing more on the interplay between high-dimensional expanders and codes that led to this construction and less on the technical proofs. The original paper of [DELLM22] is extremely well written, and the reader is encouraged to read either the paper for the technical details or Goldreich’s exposition [Gol21] for a less group-theoretic presentation.

What are locally testable codes (LTCs)?

Let us begin by recalling what a code is. A code \(\mathcal{C}\) with blocklength over the Boolean alphabet refers to a subset of \(\{0,1\}^n\), and the elements of \(\mathcal{C}\) are usually referred to as codewords. The rate of the code \(\mathcal{C}\), denoted by \(R(\mathcal{C})\), is \(\frac{\log_2|\mathcal{C}|}{n}\) while the (fractional) distance, denoted by \(\delta(\mathcal{C})\), is the minimum fractional Hamming distance between any two distinct codewords in \(\mathcal{C}\). In this note, we will restrict our attention to linear codes: where the underlying alphabet \(\{0,1\}\) is identified with the field \(GF(2)\) and the code \(\mathcal{C}\) is a \(GF(2)\)-vector-space. In this case, the distance \(\delta\) is the minimum fractional weight of a nonzero codeword in \(\mathcal{C}\). If a code \(\mathcal{C}\) is linear, it can easily be described by the set of (dual) constraints that describe the vector space \(\mathcal{C}\). These constraints are usually referred to as parity checks. If, furthermore, each of these parity checks has constant arity (i.e., each constraint involves only a constant number of codeword locations), then the code is said to be a low-density parity-check code (LDPC). Given a string \(x \in \{0,1\}^n\) and a subset \(Q \subset [n]\) of the coordinate locations, \(x|_Q\) refers to the projection of the string \(x\) to the coordinates in \(Q\). The projected code \(\mathcal{C}|_Q\) is defined as the set of projected codewords, formally, \[\mathcal{C}|_Q := \{ x \in \{0,1\}^Q \colon \exists y \in \{0,1\}^{[n]\setminus Q} \text{ such that } (x,y) \in \mathcal{C}\}.\]

A linear code \(\mathcal{C}\) is said to be \(q\)-locally testable1 if there exists a distribution \(\mathcal{Q}\) over subsets \(Q \subset [n]\) of size at most \(q\) such that the following is satisfied. \[\text{For every } x \in \{0,1\}^n, \text{ we have } \Pr_{Q \sim \mathcal{Q}}[ x|_Q \not\in \mathcal{C}|_Q] = \Omega(\delta(x,\mathcal{C})).\] Here, \(\delta(x,\mathcal{C})\) refers to \(\min_{c \in \mathcal{C}}\delta(x,c)\), the fractional Hamming distance between \(x\) and the code \(\mathcal{C}\).

In general, we will be interested in constructing a family \(\{\mathcal{C}_n\}_{n=1}^{\infty}\) of codes with increasing blocklengths. The holy grail in this area, which was attained by the recent constructions, was to obtain a family of codes that had constant rate and constant fractional distance and were testable with a constant number of queries. Codes that satisfy the first two properties (constant rate and constant fractional distance) are usually referred to as good codes. We will first take a detour and see how good codes are constructed and then return to the question of \(c^3\) LTCs.

CONTINUE READING

The Blind Men and the Quantum Elephants

by Chinmay Nirkhe (IBM Research and UC Berkeley)

In the parable of the blind men and the elephant, a group of blind men encounters a very large object, unbeknownst to them that it is indeed an elephant. They start exploring the object by touch, with each blind man trying to understand the small fraction of the object in front of him. But each blind man feels a different part of the elephant, such as its trunk, its tusks, its feet, etc. For instance, one feels the elephant’s trunk and remarks, “This feels like a thick snake.” Each develops a different view as to what the object he encounters must be, as each of the blind men is offered only a small perspective on the global object.

Only once the blind men bicker and argue over their different views do they finally agree that they are observing something greater and finally recognize that the object they are observing is an elephant. In other words, only from the union of the small local views — each local view being indistinguishable from other objects (such as the elephant’s trunk and a snake) — are the blind men able to surmise that the global object in front of them is an elephant.

Today, we consider a variation on the parable more suited for our modern understanding of physics. In this parable, instead of one object that the blind men observe, there are two. The blind men approach the first object, and each man goes to his location around the object. The first man feels the front of the object and again remarks, “This feels like a thick snake,” while the other men then proceed to feel the object in front of them and make observations as to what they feel. The men then proceed to the second object and again proceed to make observations as to what they feel. The first man again remarks, “This feels like a thick snake,” and, curiously, each blind man makes the exact same observation for the second object as he did for the first. The blind men confer and note that since each man’s observations were the same for both objects and together they had observed the entirety of both objects, then the two objects must be the same and therefore the same elephant. They must have been presented with the same elephant twice.

But what if the blind men were wrong and they were truly observing two very different objects? Is it possible that the two objects were very different but were the same under every local observation? Well, it is possible if they were quantum elephants! An amazing property of two pure quantum objects is that their local views can be exactly the same and yet globally the states are very different (even orthogonal). We call such quantum objects locally indistinguishable, and they are fundamentally interesting objects in quantum information theory. For one, due to being locally indistinguishable, these quantum states (objects) have the property that their entanglement is nontrivial — in this case, this means that for the state to be expressed as the output of a quantum circuit, the depth of the circuit required is large. If a high-depth quantum circuit is required, then this means that the state is far from all classical states and is fundamentally quantum.

Illustration by Chinmay Nirkhe

Locally indistinguishable quantum states are easy to concoct, but it is far more interesting when locally indistinguishable quantum states are “naturally” occurring. A physicist might phrase this as a local Hamiltonian system (i.e., a quantum energy landscape) with the property that after cooling the system to its minimum energy (temperature), the state of the system is a locally indistinguishable quantum state — i.e., is there any hope that a group of blind physicists go on a trek through the quantum jungle and stumble upon a pair of quantum elephants?

CONTINUE READING