8
$\begingroup$

I am watching this talk about Lifted Product Code (LP). For me, it's quite straightforward to see how to construct a HyperGraph Product Code (HGP) using two separate classical codes. However, I failed to grasp the idea of lifting and how this could help us to further improve the code distance scaling compared with HGP code. Can anyone share their thoughts on the meaning of "lift" here?

$\endgroup$

1 Answer 1

10
$\begingroup$

An $\ell$-lift is just a shorter term for an $\ell$-fold covering graph, a very general idea from graph theory and topology to obtain $\ell$ times larger graph $X^\alpha$ out of a small base graph $X$ (with some fixed edge orientation) by assigning to each edge $e\in E(X)$ a permutation $\alpha_e\in\mathbf{S}_\ell$. Since both classical linear codes and quantum CSS codes can be represented by their Tanner graphs, you can naturally apply this idea to codes as well (please, see the picture below).

enter image description here

In terms of parity-check matrices, this means that from an $m\times n$ matrix of a base code we get an $\ell m\times \ell n$ block matrix of its lift, where $\ell\times\ell$ blocks correspond to permutations from $\mathbf{S}_\ell$, which can also be considered as an $m\times n$ matrix over a group ring $R=\mathbb{F}_2[G]$ when these permutations are actions $x\mapsto gx$ of a group $G$ of size $\ell$ on itself (e.g., look here).

In fact, allmost all classical LDPC codes currently used in practice are constructed as large lifts of small base codes (the Tanner code of the base code is often called a protograph). Since in the lifted Tanner graph we have $\ell$ times more bit and check nodes, then for a base code of rate $\rho$, the rate of all its possible lifts is at least $\rho$. This gives us an infinite family of LDPC codes of rate at least $\rho$ obtained from just one base code. Unfortunately, not every LDPC code in this family has large minimal distance. However, if you take a random lift (e.g., assign random elements from $\mathbf{S}_\ell$), then on average you get a very good minimal distance that grows linearly with the code length. This is an example of a more general phenomenon, first noticed by Shannon, that a random code on average tends to have a very large distance. One can derandomize this (i.e., choose the base code and the permutations from $\mathbf{S}_\ell$ explicitly) using the Sipser-Spielmann construction.

The main idea of lifted product codes is to extend these very powerful methods from classical LDPC to quantum LDPC codes. Ideally, we would like to use any small base quantum CSS code and obtain its random lifts (i.e., lifts of its Tanner graph). Since the obtained quantum LDPC code looks like a random one, it is quite natural to expect that on average its distance is large, as it was in the classical case discussed above.

However, in the quantum case, you also have to check that the obtained large random Tanner graph indeed defines a correct CSS code (i.e., we have $H_X H_Z^\mathrm{T} = \mathbf{0}$). Luckily, if your base quantum code is the hypegraph product code, then there is a way to do this. As you probably know, the Tanner graph of a hypergraph product code is the Cartesian product $X\Box Y$ of the Tanner graphs $X$ and $Y$ of the component classical codes, where $V(X\Box Y) := V(X)\times V(Y)$ and $E(X\Box Y) := E(X)\times V(Y) \sqcup V(X)\times E(Y)$. Now, for given lifts $X^\alpha$ and $Y^\beta$ of $X$ and $Y$, we define the Tanner graph of the lifted product code as the lift $(X\Box Y)^{\alpha\beta}$ of the product $X\Box Y$, where $(\alpha\beta)_{e\times v} = \alpha_e$ and $(\alpha\beta)_{v\times e} = \beta_e$ (please, see the picture below).

enter image description here

If the permutations $(\alpha_e)_{e\in E(X)}$ pairwise commute with the permutations $(\beta_e)_{e\in E(Y)}$ (e.g., they are cyclic shifts), then it is not hard to check that we always have the condition $H_X H_Z^\mathrm{T} = \mathbf{0}$. Hence, if we use random permutations $(\alpha_e)_{e\in E(X)}$ and $(\beta_e)_{e\in E(Y)}$, we get the quantum LDPC code very similar to a random one. This can also be derandomized using Sipser-Spielmann construction, similar to the classical case.

I hope that the above explanations give some intuition why lifted product codes have large distances. However, I should say that the actual proof of this fact is quite involved and contains a lot of additional technical details not discussed here.

$\endgroup$
1
  • $\begingroup$ Fantastic answer! Many thanks for it and welcome to this SE! $\endgroup$
    – Yunzhe
    Commented Dec 4, 2023 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.