# Lifting decoders for classical codes to decoders for quantum codes

Armanda O. Quintavalle<EMAIL_ADDRESS>Department of Physics & Astronomy,
University of Sheffield, Sheffield, S3 7RH, United Kingdom  Earl T. Campbell
<EMAIL_ADDRESS>Department of Physics & Astronomy, University of
Sheffield, Sheffield, S3 7RH, United Kingdom  AWS Center for Quantum
Computing, Pasadena, CA 91125 USA

###### Abstract

The design of decoding algorithms is a significant technological component in
the development of fault-tolerant quantum computers. Often design of quantum
decoders is inspired by classical decoding algorithms, but there are no
general principles for building quantum decoders from classical decoders.
Given any pair of classical codes, we can build a quantum code using the
hypergraph product, yielding a hypergraph product code. Here we show we can
also lift the decoders for these classical codes. That is, given oracle access
to a minimum weight decoder for the relevant classical codes, the
corresponding $[[n,k,d]]$ quantum code can be efficiently decoded for any
error of weight smaller than $(d-1)/2$. The quantum decoder requires only
$O(k)$ oracle calls to the classical decoder and $O(n^{2})$ classical
resources. The lift and the correctness proof of the decoder have a purely
algebraic nature that draws on the discovery of some novel homological
invariants of the hypergraph product codespace. While the decoder works
perfectly for adversarial errors, it is not suitable for more realistic
stochastic noise models and therefore can not be used to establish an error
correcting threshold.

The construction of quantum codes often takes classical codes as a starting
point. The CSS construction is one method for combining a pair of classical
codes into a quantum code. However, the CSS recipe only works when the pair of
classical codes are dual to each other. Unfortunately, some of the best known
classical code families, such as those based on expander graphs, do not come
in convenient dual pairs. The hypergraph product is a different recipe that
allows a pair of arbitrary classical codes to form the basis of a quantum code
tillich2014quantum . Crucially, when the hypergraph product uses families of
classical low-density parity check (LDPC) codes, it leads to families of
quantum-LDPC codes. The quantum-LDPC property eases the experimental
difficulty of implementation and, combined with suitably growing distance,
ensures the existence of an error correction threshold Kovalevbadcode .

Two of the most widely known quantum codes, the toric and surface codes, are
hypergraph product codes that use the classical repetition code as their seed
classical code. The decoding problem for the surface code can be recast as a
minimum-weight perfect-matching problem, which is efficiently solved by the
blossom algorithm dennis02 ; FowlerRepMeasure  and the union-find algorithm
delfosse2017almost . Another interesting class of hypergraph product codes
uses classical expander codes as their seed, with the resulting offspring
called quantum expander codes leverrier2015quantum , which are quantum-LDPC
codes achieving both constant rate and $\Omega(\sqrt{n})$ distance. The
classical expander codes can be decoded by a very simple bit-flip algorithm
discovered by Spiser and Spielman sipser1996expander . This inspired the
small-set flip decoder for quantum expander codes, which follows a similar
idea but is slightly modified, and has been shown to correct adversarial
errors leverrier2015quantum , stochastic errors fawzi2018  and also to operate
as a single-shot decoder leverrier18 . However, there are a broad range of
hypergraph product codes that are neither surface codes nor quantum expander
codes, for which there is no general propose strategy for decoder design that
is proven to work across the whole code family.

For classical LDPC codes, using a belief propagation decoder (BP) works well
in practice, though it is a heuristic without any rigorously established
performance promises. Furthermore, the classical BP decoder cannot be used out
of the box on quantum-LDPC codes. In fact, whenever a decoding instance has
more than one minimum weight solution, it is degenerate, BP does not converge
and yields a decoding failure. Degeneracy is the quintessential feature of
quantum codes and therefore some workarounds are needed to use BP on quantum-
LDPC codes poulin08 ; babar . The literature offers many examples of BP
inspired decoders for quantum-LDPC codes which show an error correcting
threshold liu2019neural ; rigby ; panteleev2019degenerate ; yoder20 ;
grospellier2020combining ; roffe2020decoding , however, as for the classical
BP, none of them come with a correctness proof. Recently, a union-find like
decoder has been proposed to decode quantum-LDPC codes delfosse2021union_ldpc
. The authors in delfosse2021union_ldpc  prove that their union-find decoder
corrects for all errors of weight up to a polynomial in the distance for three
classes of quantum-LDPC codes: codes with linear confinement (see
bombin2015single ; quintavalle2020single ), $D$-dimensional hyperbolic codes
and $D$-dimensional toric codes for $D\geq 3$. The decoder in
delfosse2021union_ldpc  is therefore provably correct for adversarial noise,
nonetheless a comprehensive investigation of its performance under stochastic
noise is still missing.

Here we introduce the ReShape decoder for generic hypergraph product codes.
Given a hypergraph product built using classical codes with parity matrices
$\delta_{A}$ and $\delta_{B}$, we assume access to a minimum weight decoder
for parity matrices $\delta_{A}$, $\delta_{B}$, $\delta_{A}^{T}$ and
$\delta_{B}^{T}$. The ReShape decoder calls these classical decoders as
blackbox oracles without any modification or knowledge of their internal
working, and furthermore only requires $O(k)$ oracle calls, and only a
polynomial amount of additional classical computation. Under these conditions
we prove that ReShape works in the adversarial setting, correcting errors (up
to stabilisers) of weight less than half the code distance. Therefore, ReShape
lifts the classical decoders to the status of a quantum decoder, providing the
first general purpose hypergraph product codes decoder proven to correct
adversarial errors. Formally we prove:

######  Theorem 1.

Any $[[n,k,d]]$ hypergraph product code constructed from the classical parity
check matrices $\delta_{A}$ and $\delta_{B}$ can be successfully decoded from
error of weight up to $(d-1)/2$ using $O(k)$ oracle calls to classical
decoders for the seed matrices and their transpose plus $O(n^{2})$ classical
operations.

Theorem 1 though, does not state anything about stochastic noise or error
correcting thresholds. Families of $n$-qubit hypergraph product codes have
distance of at most $O(\sqrt{n})$ and so they are bad codes in the sense that
the distance is sub-linear. However, given a stochastic noise model with each
qubit affected independently with probability $p$, the typical error size will
be $pn$. Thus, for $n>(d/2p)$, the most likely errors will not necessarily be
corrected by ReShape and there is no guarantee that a threshold will be
observed. Indeed, we implemented ReShape for several code families and found
evidence that ReShape fails to provide a threshold (see Fig. 3). A clear open
problem is whether there exists a similar general lifting procedure, or
modification of ReShape, for which one can prove good performance in the
stochastic settings. Hence, if on one hand Theorem 1 provides a solution to
the adversarial decoding problem for hypergraph product codes, on the other, a
stronger, difficult and much longed-for result is desirable. Namely, the
solution of the stochastic decoding problem for hypergraph product codes both
on a theoretical level (proof of a threshold) and on a practical one
(numerical observation of a high correcting threshold). Even so, if we
contrast ReShape with what said on BP and union-find like decoders, we see
that ReShape improves on the former in that it is provably correct and on the
latter because its correction capability are optimal, $(d-1)/2$ against a
polynomial in $d$.

##  I Preliminaries and notation

A classical $[n,k,d]$ linear code is compactly described by its parity check
matrix $H$. The matrix $H$ is a binary matrix of size $m\times n$ such that
the codespace $\mathcal{C}(H)\subseteq\mathbb{F}_{2}^{n}$ is described by:

$\displaystyle\mathcal{C}(H)=\\{v\in\mathbb{F}_{2}^{n}$
$\displaystyle:Hv=0\\}.$ (1)

The codespace $\mathcal{C}(H)$ has dimension
$k=n-\operatorname{\mathrm{rank}}(H)$ and distance $d$ defined as:

$\displaystyle d=\min\\{|v|$ $\displaystyle:v\in\mathcal{C}(H),v\neq 0\\},$

where $|v|$ is the Hamming weight of the binary vector $v$. Whenever the
parity check matrix has columns and rows of small weight we say that it is a
low density parity check (LDPC) matrix; when $H$ has constant column and row
weight $w_{c},w_{r}$ we shortly say that it is a $(w_{c},w_{r})$-matrix.

The classical decoding problem can be stated as: given a _syndrome_ vector
$s\in\mathbb{F}_{2}^{m}$, find the minimum weight solution
$e_{r}\in\mathbb{F}_{2}^{n}$ to the equation

$\displaystyle He=s.$ (2)

It is easy to show that the optimal decoder for any classical linear code can
correct errors of weight up to half the code distance (see, for instance,
huffman2010fundamentals ).

A quantum $[[n,k,d]]$ stabiliser code gottesman1997stabilizer  is a subspace
of dimension $2^{k}$ of the Hilbert space $(\mathbb{C}^{2})^{\otimes n}$. It
is described as the common $+1$ eigenspace of its stabiliser group
$\mathcal{S}$, an Abelian subgroup of the Pauli group $\mathcal{P}_{n}$ such
that $-\mathbb{1}\not\in\mathcal{S}$. The Pauli group on $n$ qubits is the
group generated by the $n$-fold tensor product of single qubit Pauli
operators. The weight $|P|$ of a Pauli operator $P\in\mathcal{P}_{n}$ is the
number of its non-identity factors. We indicate by $\mathcal{N}(\mathcal{S})$
the normaliser of $\mathcal{S}$ i.e. the group of Paulis which commute with
the stabiliser group $\mathcal{S}$. Because
$\mathcal{S}\subseteq\mathcal{N}(\mathcal{S})$, the quotient group
$\mathcal{L}=\nicefrac{{\mathcal{N(\mathcal{S})}}}{{\mathcal{S}}}$ is well
defined. Elements $[P]$ of $\mathcal{L}$ are equivalence classes with respect
to the congruence modulo multiplication by stabiliser operators:

$\displaystyle[P]=\\{PS$ $\displaystyle:S\in\mathcal{S}\\}.$

Each Pauli $P$ such that $[P]\neq 0$ in $\mathcal{L}$ is an operator that
preserves the codespace and has non-trivial action on it. We refer to such
code operators modulo $\mathcal{S}$ as _logical Pauli operators_ ; with slight
abuse of notation we write $P\in\mathcal{L}$, meaning $[P]\in\mathcal{L}$. Two
logical operators $P,Q$ are said to be homologically equivalent, or just
equivalent, if and only if $[P]=[Q]$. Importantly, for a code of dimension
$k$, $\mathcal{L}\simeq\mathcal{P}_{k}$. The distance $d$ of the code is the
minimum weight of any non-trivial logical operator in $\mathcal{L}$. Any
generating set of the stabiliser group $\mathcal{S}$ induces a syndrome map
$\sigma$. Namely, if $\mathcal{S}=\langle S_{1},\dots,S_{m}\rangle$, the
associated syndrome function $\sigma$ maps any Pauli $P\in\mathcal{P}_{n}$ in
a binary vector $s=(s_{1},\dots,s_{m})^{T}\in\mathbb{F}_{2}^{m}$ such that
$s_{i}=0$ if and only if $P$ commutes with $S_{i}$ and $1$ otherwise. We refer
to the vector $s$ as the _syndrome_. Conventionally, when considering a
stabiliser code, it is always intended that a generating set
$\\{S_{1},\dots,S_{m}\\}$ for the stabiliser group is chosen and with it a
syndrome map. We say that a stabiliser code is LDPC if each $S_{i}$ has low
weight and each qubit is in the support of only a few generators.

The decoding problem for stabiliser codes can be stated as: given a syndrome
vector $s\in\mathbb{F}_{2}^{m}$, find an operator $E_{r}\in\mathcal{P}_{n}$
such that (i) $\sigma(E_{r})=s$ and (ii) $[E_{r}]=[E_{\min}]$, where $E_{min}$
is a minimum weight operator with syndrome $s$. We call any operator that
satisfies (i) a _valid_ solution of the syndrome equation and operators for
which both (i) and (ii) are true, _correct_ solutions.

Pauli operators can be put into a one-to-one correspondence with binary
vectors, if we discard the phase factor $\pm i$. In fact, any Pauli $P$ can be
written as:

$\displaystyle P$ $\displaystyle\propto X[v]\cdot Z[w],$
$\displaystyle=X^{v_{1}}\otimes\dots\otimes X^{v_{n}}\cdot
Z^{w_{1}}\otimes\dots\otimes Z^{w_{n}},$ $\displaystyle
v,w\in\mathbb{F}_{2}^{n}$

from which it follows:

$\displaystyle(X[v]Z[w])(X[v^{\prime}]Z[w^{\prime}])$
$\displaystyle=X[v+v^{\prime}]Z[w+w^{\prime}],$ (3)
$\displaystyle\big{\langle}X[v]Z[w],X[v^{\prime}]Z[w^{\prime}]\big{\rangle}$
$\displaystyle=\langle v,w^{\prime}\rangle+\langle v^{\prime},w\rangle.$ (4)

This correspondence between binary vectors and Pauli operators is particularly
handy when dealing with CSS codes calderbank1996good ; steane1996multiple .
CSS codes are stabiliser codes for which the stabiliser group can be generated
by two disjoint sets $\mathcal{S}_{x}$ and $\mathcal{S}_{z}$ of $X$ and $Z$
type operators respectively. If $\mathcal{S}_{x}=\\{X[v_{1}],\dots
X[v_{m_{x}}]\\}$, $\mathcal{S}_{z}=\\{Z[w_{1}],\dots,Z[w_{m_{z}}]\\}$ and we
define $H_{X}$ and $H_{Z}$ as the matrices whose rows are the $v_{i}$s and the
$w_{i}$s respectively, then the commutation relation on the stabilisers
generators translate in to the binary constraint $H_{X}H_{Z}^{T}=0$. Using Eq.
(4), it is easy to show that the syndrome for a Pauli error
$E=X[e_{x}]Z[e_{z}]$ is described by the two binary vectors $s_{z}=H_{Z}e_{x}$
and $s_{x}=H_{X}e_{z}$. Since these two linear equations are independent, we
can treat the $X$-part and $Z$-part of the error separately. For CSS codes, we
define the $X$-distance $d_{x}$ as the minimum weight of an operator $X[v]$
which commutes with all the stabilisers in $\mathcal{S}_{z}$ but does not
belong to the group generated by $\mathcal{S}_{x}$. Note that the weight of an
operator $X[v]$ equates the Hamming weight $|v|$ of the vector $v$. Therefore,
combining Eq. (3), Eq. (4) and the definition of $d_{x}$, we shortly say that
$d_{x}$ is the minimum weight of a vector $v$ in $\ker H_{Z}$ which does not
belong to the row span of $H_{Z}$, i.e. $H_{Z}v=0$,
$v\not\in\operatorname{\mathrm{Im}}H_{Z}^{T}$. Similarly, $d_{z}$ is the
minimum weight of a vector in $\ker H_{X}$ not in
$\operatorname{\mathrm{Im}}H_{Z}^{T}$.

The $Z$-error decoding problem for CSS code can be stated as: given a syndrome
vector $s\in\mathbb{F}_{2}^{m_{x}}$, find a valid and correct solution
$e_{r}\in\mathbb{F}_{2}^{n}$ to the equation:

$\displaystyle H_{X}e=s,$ (5)

where $e_{r}$ is valid if and only if $H_{X}e_{r}=s$ and it is correct if and
only if it belongs to the homology class of the minimum weight operator with
syndrome $s$. Because for an operator $Z[e]$ its weight equates the Hamming
weight of the vector $e$, the $Z$-decoding problem for CSS codes can be
reformulated exactly as done for the classical decoding problem in Eq. (2).
Explicitly, given $s$, find the minimum weight solution to the linear equation
$H_{X}e=s$. The $X$-decoding problem is derived from Eq. (5) by duality,
exchanging the role of $X$ and $Z$.

It goes without saying that, if any CSS code defines two classical parity
check matrices, the converse is also true. Namely, starting from any two
binary matrices $H_{1},H_{2}$ such that $H_{1}H_{2}^{T}=0$, it is well defined
the CSS code with $H_{X}=H_{1}$, $H_{Z}=H_{2}$. If the classical linear code
with parity check $H_{i}$ has parameters $[n,k_{i},d_{i}]$, the associated
quantum code code has parameters $[[n,k_{1}+k_{2}-n,d_{x},d_{z}]]$ where
$d_{x}\geq d_{2}$ and $d_{z}\geq d_{1}$. A review on quantum codes can be
found, for instance, in roffe2019quantum ; NC01b .

In this article we focus on a sub-class of CSS codes, the hypergraph product
codes tillich14 ; bravyi14 ; audoux2015tensor ; zeng2019higher . We give a
minimal description of these codes in Sec. II and we refer the reader to App.
B for a more detailed presentation. We study some homology invariants for the
logical operators of the hypergraph product codes in Sec. III.1. These
invariants are the algebraic core upon which we design a decoder for these
codes, the ReShape decoder. We prove that ReShape is an efficient and correct
decoder for adversarial noise in Sec. III.2. We conclude with some
consideration on the performance of ReShape under stochastic noise in Sec.
III.3.

##  II Hypergraph product codes

We here present a bottom-up overview on hypergraph product codes. The purpose
of this Section is dual: we both want to describe the hypergraph product codes
with the least possible technical overhead and introduce the notation
necessary to motivate and give an intuition for the results presented in Sec.
III. We refer the reader interested in the homology theory approach to App. B.

The most well-known example of hypergraph product code is the toric code and
its variations Kit03 ; bravyi1998quantum . The toric code is conventionally
represented by a square lattice where qubits sit on edges, $X$-stabilisers are
identified with vertices and $Z$-stabilisers with faces. The first evident
feature of this identification is that in a square lattice we have two kind of
edges: vertical and horizontal edges. The second is that each vertex uniquely
identifies a row of horizontal edges and a column of vertical one, starting
from the four ones that are incident to it. The third is that faces, similarly
to vertices, uniquely identify a column of horizontal edges and a row of
vertical ones, starting from the four which lie on its boundary. Very similar
attributes can be found in all the hypergraph product codes, as we now
explain.

Consider two classical parity check matrices $\delta_{A},\delta_{B}$ of size
$m_{a}\times n_{a}$ and $m_{b}\times n_{b}$; we indicate with
$\mathcal{C}(\delta_{A},\delta_{B})$ their hypergraph product code and refer
to the matrices $\delta_{A}$ and $\delta_{B}$ as _seed_ matrices. The qubits
of the code $\mathcal{C}(\delta_{A},\delta_{B})$ can be labelled as _left_ and
_right_ qubits. Left qubits can be placed in a $n_{a}\times n_{b}$ grid and
right qubits in a $m_{a}\times m_{b}$ grid, see Fig. 1. Under this labelling,
left and right qubits are uniquely identified by pair of indices
$(j_{a},j_{b})$ and $(i_{a},i_{b})$ respectively, where $j_{a},j_{b}$ vary
among the column indices of $\delta_{A},\delta_{B}$ while $i_{a},i_{b}$ vary
among their row indices. Given a pair $(L,R)$ of binary matrices, of size
$n_{a}\times n_{b}$ and $m_{a}\times m_{b}$ respectively, we define the
$Z$-operator:

$\displaystyle Z(L,R)$
$\displaystyle=\left(\bigotimes_{j_{a},j_{b}}Z_{j_{a},j_{b}}^{L_{j_{a},j_{b}}}\right)\otimes\left(\bigotimes_{i_{a},i_{b}}Z_{i_{a},i_{b}}^{R_{i_{a},i_{b}}}\right),$
(6)

and similarly for $X$-operators. We refer to $L$ as the left part of the
operator and to $R$ as its right part.

The code $\mathcal{C}(\delta_{A},\delta_{B})$ has $m_{a}\times n_{b}$
$X$-stabiliser generators which can be indexed by $(i_{a},j_{b})$. The
$X$-stabiliser $S^{x}_{(i_{a},j_{b})}$ has support contained in the union of
the $j_{b}$th column of left qubits and the $i_{a}$th row of right qubits.
More precisely111Here and in the following, for a $m\times n$ matrix $\delta$
we indicate by $\delta_{i}\in\mathbb{F}_{2}^{n}$ the transpose of its $i$th
row, and by $\delta^{j}\in\mathbb{F}_{2}^{m}$ its $j$th column., it acts as
$X[(\delta_{A})_{i_{a}}]$ on the left qubits located at column $j_{b}$ and as
$X[(\delta_{B})^{j_{b}}]$ on the right qubits located on row $i_{a}$, see Fig.
1b. Using the $X$-version of Eq. (6), $S^{x}{(i_{a},j_{b})}$ is uniquely
represented by the pair of matrices, $L=\delta_{A}^{T}E_{{i_{a}j_{b}}}$ and
$R=E_{i_{a}j_{b}}\delta_{B}^{T}$, so that

$\displaystyle
S^{x}{(i_{a},j_{b})}:=X(\delta_{A}^{T}E_{{i_{a}j_{b}}},E_{i_{a}j_{b}}\delta_{B}^{T}),$

where $E_{i_{a},j_{b}}$ is the all-zero $m_{a}\times n_{b}$ matrix but for the
$(i_{a},j_{b})$th entry which is $1$. From the characteristic ‘cross’ shape of
the stabilisers generators $S^{x}(i_{a},j_{b})$, it follows that if
$(G_{L},G_{R})$ is an $X$-stabiliser for $\mathcal{C}(\delta_{A},\delta_{B})$,
then (i) each column of $G_{L}$, as vector in $\mathbb{F}_{2}^{n_{b}}$,
belongs to $\operatorname{\mathrm{Im}}\delta_{A}^{T}$ and (ii) each row of
$G_{R}$, as vector in $\mathbb{F}_{2}^{n_{a}}$, belongs to
$\operatorname{\mathrm{Im}}\delta_{B}^{T}$.

Similarly, $Z$-stabiliser generators are indexed by $(j_{a},i_{b})$ for $1\leq
j_{a}\leq n_{a}$ and $1\leq i_{b}\leq m_{b}$ and $S^{z}_{(j_{a},i_{b})}$ is
uniquely represented by the pair of matrices:

$\displaystyle(L,R)=(E_{j_{a}i_{b}}\delta_{B},\delta_{A}E_{j_{a}i_{b}}),$

for $E_{j_{a}i_{b}}$ of size $m_{a}\times n_{b}$, with all entries $0$ but for
the $(j_{a},i_{b})$th entry which is $1$. Given a $Z$-operator $(L,R)$, its
$X$-syndrome is the $m_{a}\times n_{b}$ binary matrix:

$\displaystyle\sigma(L,R)\coloneqq\delta_{A}L+R\delta_{B}.$ (SE)

It is easy to show that any $Z$-stabiliser has trivial $X$-syndrome, which is
equivalent to $X$-stabilisers and $Z$-stabilisers commuting. As a consequence,
$\mathcal{C}(\delta_{A},\delta_{B})$ is a well-defined CSS code. A minimal
generating set of logical $Z$-operators for
$\mathcal{C}(\delta_{A},\delta_{B})$ is given by :

$\displaystyle\mathcal{L}_{z}$
$\displaystyle\coloneqq\mathcal{L}_{z}^{\mathrm{left}}\cup\mathcal{L}_{z}^{\mathrm{right}}$
(7)

where:

$\displaystyle\mathcal{L}_{z}^{\mathrm{left}}\coloneqq\big{\\{}(L,0)$
$\displaystyle:L=k_{a}\cdot e_{j_{b}}^{T},$ $\displaystyle\quad k_{a}\text{
varies among a basis of }\ker\delta_{A},$ $\displaystyle\quad e_{j_{b}}\text{
varies among a basis of }\operatorname{\mathrm{Im}}(\delta_{B}^{T})^{\bot},$
$\displaystyle\quad|e_{j_{b}}|=1\big{\\}},$

and

$\displaystyle\mathcal{L}_{z}^{\mathrm{right}}\coloneqq\big{\\{}(0,R)$
$\displaystyle:R=e_{i_{a}}\cdot\bar{k}_{b}^{T},$ $\displaystyle\quad
e_{i_{a}}\text{ varies among a basis of
}\operatorname{\mathrm{Im}}(\delta_{A})^{\bot},$
$\displaystyle\quad|e_{i_{a}}|=1,$ $\displaystyle\quad\bar{k}_{b}\text{ varies
among a basis of }\ker\delta_{B}^{T}\big{\\}}.$

Here, given a vector space $V\subseteq\mathbb{F}_{2}^{n}$, $V^{\bot}$ denotes
any space such that $V\oplus V^{\bot}\simeq\mathbb{F}_{2}^{n}$, see App. A for
details. Similarly, a minimal generating set of logical $X$-operators is:

$\displaystyle\mathcal{L}_{x}$
$\displaystyle\coloneqq\mathcal{L}_{x}^{\mathrm{left}}\cup\mathcal{L}_{x}^{\mathrm{right}}$
(8)

where:

$\displaystyle\mathcal{L}_{x}^{\mathrm{left}}\coloneqq\big{\\{}(L,0)$
$\displaystyle:L=e_{j_{a}}\cdot k_{b}^{T},$ $\displaystyle\quad
e_{j_{a}}\text{ varies among a basis of
}\operatorname{\mathrm{Im}}(\delta_{A}^{T})^{\bot},$
$\displaystyle\quad|e_{j_{a}}|=1,$ $\displaystyle\quad k_{b}\text{ varies
among a basis of }\ker\delta_{B}\big{\\}},$

and

$\displaystyle\mathcal{L}_{x}^{\mathrm{right}}\coloneqq\big{\\{}(0,R)$
$\displaystyle:R=\bar{k}_{a}\cdot e_{i_{b}}^{T},$
$\displaystyle\quad\bar{k}_{a}\text{ varies among a basis of
}\ker\delta_{A}^{T},$ $\displaystyle\quad e_{i_{b}}\text{ varies among a basis
of }\operatorname{\mathrm{Im}}(\delta_{B})^{\bot},$
$\displaystyle\quad|e_{i_{b}}|=1\big{\\}}.$

To sum up, the code $\mathcal{C}(\delta_{A},\delta_{B})$ is a CSS code with
parameters $[[n,k,d_{x},d_{z}]]$, where:

$\displaystyle n$ $\displaystyle=n_{a}n_{b}+m_{a}m_{b}$ $\displaystyle k$
$\displaystyle=(n_{a}-\mathrm{rk}_{a})(n_{b}-\mathrm{rk_{b}})+(m_{a}-\mathrm{rk}_{a})(m_{b}-\mathrm{rk_{b}})$
$\displaystyle d_{x}$ $\displaystyle=\min\\{d_{a}^{T},d_{b}\\}$ $\displaystyle
d_{z}$ $\displaystyle=\min\\{d_{a},d_{b}^{T}\\}$

for $\mathrm{rk}_{\ell}=\operatorname{\mathrm{rank}}(\delta_{\ell})$ and
$d_{\ell}$/$d_{\ell}^{T}$ distance of the classical code with parity check
matrix $\delta_{\ell}/\delta_{\ell}^{T}$, $\ell=A,B$.

The similarities in structure between general hypergraph product codes
$\mathcal{C}(\delta_{A},\delta_{B})$ and the toric codes (with and without
boundaries) should now be clear: the toric code with boundaries (resp.
without) of lattice size $L$ is just the hypergraph product code
$\mathcal{C}(\delta_{L},\delta_{L})$ where $\delta_{L}$ is the $L-1\times L$
(resp. $L\times L$) parity check matrix of the classical repetition code. Left
and right qubits correspond to vertical and horizontal edges; vertices and
faces on the square lattice can be indexed in the natural way yielding the
same stabiliser indexing of the general hypergraph product codes; string like
(resp. loop like) logical operators correspond precisely to the left and right
logical operators described above which have single column/single row support.

In what follows, we focus on $Z$-errors and their correction. With slight
abuse of notation, we will refer to pair of matrices $(L,R)$ as operators (and
vice versa sometimes) where the identification is clear via Eq. (6). The
corresponding results for $X$-errors are easily obtained exploiting the dual
structure of $\mathcal{C}(\delta_{A},\delta_{B})$.

(a)  (b)  (c)  (d)

(e)  (f)  (g)

Figure 1: A graphical representation of the qubit space of the homological
product code $\mathcal{C}(\delta_{A},\delta_{B})$ where
$\delta_{A}=\delta_{B}=\delta$ and $\delta$ is a degenerate parity check
matrix for the $[7,4,3]$ Hamming code reported in (a). The code
$\mathcal{C}(\delta_{A},\delta_{B})$ pictured has parameters $[[65,17,3,3]]$.
It has $16$ independent logical left operators, i.e.
$|\mathcal{L}_{x}^{\mathrm{left}}|=|\mathcal{L}_{z}^{\mathrm{left}}|=16$, and
$1$ logical right operator, i.e.
$|\mathcal{L}_{x}^{\mathrm{right}}|=|\mathcal{L}_{z}^{\mathrm{right}}|=1$. In
figures (b), …, (g), the $7\times 7$ grid represents the left qubits while the
$4\times 4$ grid represents the right qubits. We have drawn the support of
some $X$ and $Z$ operators $(L,R)$ on $\mathcal{C}(\delta_{A},\delta_{B})$.
Every circle correspond to a qubit: the left circle at position
$(j_{a},j_{b})$ is colored if and only if it belongs to the support of $L$
i.e. if and only if $L_{j_{a},j_{b}}=1$; the right circle at position
$(i_{a},i_{b})$ is colored if and only if it belongs to the support of $R$
i.e. if and only if $R_{i_{a},i_{b}}=1$; circles with no fill correspond to
the identity factors $\mathbb{1}$ of the operator $(L,R)$.

##  III Results

The ultimate aim of this Section is to exhibit the ReShape decoder for
hypergraph product codes and prove Theorem 1. The correctness of ReShape
strongly relies on the determination of some algebraic invariant for the
logical operators of the code $\mathcal{C}(\delta_{A},\delta_{B})$, which we
now proceed to study. We will detail ReShape in Sec. III.2 and discuss its
limitations in Sec. III.3. All the proof of this Section are deferred to App.
C.

###  III.1 Invariants

The characteristic shape of operators on the codespace of
$\mathcal{C}(\delta_{A},\delta_{B})$ and the structure of its stabilisers and
logical operators, induces a canonical form for $Z$-operators in
$\mathcal{C}(\delta_{A},\delta_{B})$. More precisely, by combining the
construction outlined in Sec. II and the definition of complement of a vector
subspace (see App. A) we have proven the following:

######  Proposition 1 (Canonical form).

Let $(L,R)$ be a $Z$-operator on the codespace of
$\mathcal{C}(\delta_{A},\delta_{B})$. Then its left part $L$ can be expressed
as a sum of a _free part_ $M_{L}$ and a _logical part_ $O_{L}$ such that every
row of $M_{L}$ belongs to $\operatorname{\mathrm{Im}}\delta_{B}^{T}$ and every
row of $O_{L}$ belongs to $(\operatorname{\mathrm{Im}}\delta_{B}^{T})^{\bot}$.
Similarly, its right part $R$ can be expressed as a sum of a free part $M_{R}$
and a logical part $O_{R}$ such that every column of $M_{R}$ belongs to
$\operatorname{\mathrm{Im}}\delta_{A}$ and every column of $O_{R}$ belongs to
$(\operatorname{\mathrm{Im}}\delta_{A})^{\bot}$. Hence, for $(L,R)$ holds:

$\displaystyle(L,R)=(M_{L}+O_{L},M_{R}+O_{R}).$ (CF)

We refer to the writing given by Eq. (CF) as _canonical form_ of the operator
$(L,R)$.

Crucially, as we detail in App. B, it is always possible to ‘move’ the support
of the free part of an operator from the left qubits to the right qubits and
vice versa. Opposite is the situation for the logical part: the support of the
logical part of an operator cannot be moved from the left to the right qubits
without changing its homology class. These two observations (see also
Proposition 2) justify the name free and logical part in the canonical form of
a $Z$-operator on $\mathcal{C}(\delta_{A},\delta_{B})$.

Given a $Z$-operator $(L,R)$ we define its _row-column weight_ as

######  Definition 1.

Let $(L,\,R)$ be a $Z$-operator on the codespace of
$\mathcal{C}(\delta_{A},\delta_{B})$. Its row-column weight is the integer
pair:

$\mathrm{wt_{rc}}(L,\,R)\coloneqq(\\#\mathrm{row}(L),\,\\#\mathrm{col}(R))$

where

$\displaystyle\mathrm{row}(L)$ $\displaystyle\coloneqq\\{L_{i}\text{ row of
}L\,:L_{i}\neq 0\\},$ $\displaystyle\mathrm{col}(R)$
$\displaystyle\coloneqq\\{R^{j}\text{ column of }R\,:R^{j}\neq 0\\},$

and the hash symbol $\\#$ denotes the cardinality of a set.

The primary significance of this novel notion of weight is explained by
Proposition 2, which also represents a key result towards the construction of
the ReShape decoder.

######  Proposition 2.

If $(L,\,R)$ is a non-trivial logical $Z$-operator of
$\mathcal{C}(\delta_{A},\delta_{B})$ then either $\\#\mathrm{row}(L)\geq
d_{a}$ or $\\#\mathrm{col}(R)\geq d_{b}^{T}$ (or both).

Corollary 1 below further specifies the structure of logical $Z$-operators and
it is easily derived from the proof of Proposition 2, which is deferred to
App. C.

######  Corollary 1.

If $(L,R)$ is a non-trivial logical $Z$-operator on
$\mathcal{C}(\delta_{A},\delta_{B})$, at least one of the following hold:

  1. (i)

$L$ has at least $d_{a}$ rows which are not in
$\operatorname{\mathrm{Im}}\delta^{T}_{B}$ when seen as vectors in
$\mathbb{F}_{2}^{n_{b}}$.

  2. (ii)

$R$ has at least $d_{b}^{T}$ columns which are not in
$\operatorname{\mathrm{Im}}\delta_{A}$ when seen as vectors of
$\mathbb{F}_{2}^{m_{a}}$.

Proposition 2 and Corollary 1 naturally yield

######  Definition 2.

Let $(L,R)$ be a $Z$-operator on $\mathcal{C}(\delta_{A},\delta_{B})$. Its
logical row-column weight is the integer pair

$\displaystyle\mathrm{wt_{rc}^{log}}(L,R)$
$\displaystyle:=(\\#\mathrm{row_{log}}(L),\\#\mathrm{col_{log}}(R))$

where

$\displaystyle\mathrm{row_{log}}(L)$ $\displaystyle:=\\{L_{i}\text{ row of
}L\,:L_{i}\not\in\operatorname{\mathrm{Im}}\delta_{B}^{T}\\},$
$\displaystyle\mathrm{col_{log}}(R)$ $\displaystyle:=\\{R^{j}\text{ column of
}R\,:R^{j}\not\in\operatorname{\mathrm{Im}}\delta_{A}\\}.$

Equivalently, if $(L,R)$ has canonical form given by

$(L,R)=(O_{L}+M_{L},O_{R}+M_{R}),$

for its logical row-column weight holds:

$\mathrm{wt_{rc}^{log}}(L,R)=\mathrm{wt_{rc}}(O_{L},O_{R}).$

The pivotal property of the logical row-column weight is expressed by
Proposition 3.

######  Proposition 3.

The logical row-column weight of a $Z$-operator on
$\mathcal{C}(\delta_{A},\delta_{B})$ is an invariant of its homology class.

Proposition 3 not only justifies the introduction of the notion of logical
row-column weight but also constitutes the core resource upon which we prove
the correctness of the ReShape decoder, which we now introduce.

###  III.2 The ReShape decoder

An hypergraph product code $\mathcal{C}(\delta_{A},\delta_{B})$ is a CSS code
and as such the decoding for $X$ and $Z$ error can be treated separately but
in a symmetric way. Here we focus on $Z$-errors and therefore we measure a
generating set of $X$-stabilisers. The $Z$-error decoding problem for
$\mathcal{C}(\delta_{A},\delta_{B})$ can be stated as: given a $m_{a}\times
n_{b}$ syndrome matrix $S$, find a valid and correct solution
$(\tilde{L},\tilde{R})$ to the equation:

$\displaystyle S=\sigma(L,\,R)\coloneqq\delta_{A}L+R\delta_{B},$ (SE)

where $(\tilde{L},\tilde{R})$ is valid if $\sigma(\tilde{L},\tilde{R})=S$ and
it is correct if it belongs to the homology class of the minimum weight
operator with syndrome $S$.

The ReShape decoder for $Z$-errors is build upon two classical minimum weight
decoding algorithms: $\mathscr{D}_{\delta_{A}}$ and
$\mathscr{D}_{\delta_{B}^{T}}$. By this we mean that (i) the algorithms
$\mathscr{D}_{\delta_{A}}$ and $\mathscr{D}_{\delta_{B}^{T}}$ are optimal
decoders for the classical linear code with parity check matrix $\delta_{A}$
and $\delta_{B}^{T}$ respectively, and (ii) they solve the classical decoding
problem of Eq. (2) for errors of weight up to $(d_{a}-1)/2$ and
$(d_{b}^{T}-1)/2$ respectively. Reshape takes as input
$\mathscr{D}_{\delta_{A}}$, $\mathscr{D}_{\delta_{B}^{T}}$, a syndrome matrix
$S$ and a valid solution $(L,\,R)$ of the Syndrome Equation (SE):
$\sigma(L,R)=S$. It outputs a correct solution of (SE): an operator
$(\tilde{L},\tilde{R})$ homologically equivalent to the minimum weight
operator $(L_{\min},R_{\min})$ with syndrome $S$.

ReShape (Algorithm 1) works separately on the left part $L$ and on the right
part $R$ of the operator $(L,\,R)$ and in fact it could be run in parallel
(lines 3-12 and lines 13-22). Starting from a valid solution $(L,\,R)$, it
minimises its logical row-column weight by minimizing
$\\#\mathrm{row_{log}}(L)$ (lines 3-12) first and $\\#\mathrm{col_{log}}(R)$
after (lines 13-22). Because the logical row-column weight is an homology
invariant for $Z$-operators (Proposition 3) and ReShape minimises it, this
suffices to assure that ReShape is correct, as stated in Proposition 4.

Algorithm 1 ReShape decoder for $Z$-errors.

1:Classical decoder $\mathscr{D}_{\delta_{A}}$ and
$\mathscr{D}_{\delta_{B}^{T}}$. Syndrome matrix $S$ and operator $(L,\,R)$ on
$\mathcal{C}(\delta_{A},\delta_{B})$ s.t. $\sigma(L,\,R)=S$.

2:Operator $(\tilde{L},\tilde{R})$ on $\mathcal{C}(\delta_{A},\delta_{B})$
s.t. $\sigma(\tilde{L},\tilde{R})=S$ and
$[\tilde{L},\tilde{R}]=[L_{\min},R_{\min}]$, where $(L_{\min},R_{\min})$ is a
minimum weight operator with syndrome $S$.

3:for all $L_{i}$ rows of $L$ do

4: $\mathrm{Split}$:
$L_{i}=m_{i}+\mu_{i}\in\operatorname{\mathrm{Im}}\delta_{B}^{T}\oplus(\operatorname{\mathrm{Im}}\delta_{B}^{T})^{\bot}$,
as in (13)

5:end for

6:$M_{L}\leftarrow$ matrix whose rows are $m_{i}$

7:$O_{L}\leftarrow$ matrix whose rows are $\mu_{i}$

8:for all $O_{L}^{j}$ columns of $O_{L}$ do

9: $\mathrm{Decode}$: $\rho^{j}=\mathscr{D}_{\delta_{A}}(O_{L}^{j})$

10:end for

11:$\tilde{L}\leftarrow$ matrix whose columns are $\rho^{j}$

12:$\tilde{L}\leftarrow\tilde{L}+O_{L}+M_{L}$

13:for all $R^{j}$ columns of $R$ do

14: $\mathrm{Split}$:
$R^{j}=m^{j}+\mu^{j}\in\operatorname{\mathrm{Im}}\delta_{A}\oplus(\operatorname{\mathrm{Im}}\delta_{A})^{\bot}$,
as in (13)

15:end for

16:$M_{R}\leftarrow$ matrix whose columns are $m^{j}$

17:$O_{R}\leftarrow$ matrix whose columns are $\mu^{j}$

18:for all ${(O_{R})}_{i}$ rows of $O_{R}$ do

19: $\mathrm{Decode}$: $\rho_{i}=\mathscr{D}_{\delta_{B}^{T}}({(O_{R})}_{i})$

20:end for

21:$\tilde{R}\leftarrow$ matrix whose rows are $\rho_{i}$

22:$\tilde{R}\leftarrow\tilde{R}+R_{L}+M_{R}$

23:return $(\tilde{L},\tilde{R})$

We now detail how ReShape works on the left part $L$ of the inputted valid
solution $(L,R)$ (lines 3-12) and refer the reader to the pseudocode in
Algorithm 1 for the right part $R$.

ReShape has two steps, each of which exploits a feature of the left part of
$Z$-operators on the codespace of $\mathcal{C}(\delta_{A},\delta_{B})$:

  1. (i)

Split step: a $Z$-stabilizer $(G_{L},G_{R})$ has left part $G_{L}$ such that
every row is in the image of $\delta_{B}^{T}$;

  2. (ii)

Decode step: a logical $Z$-operator which acts non-trivially on the left
qubits has a representative $(L_{z},R_{z})$ such that at least one column of
$L_{z}$ is in $\ker\delta_{A}\setminus\\{0\\}$.

We now proceed to explain how these two steps are performed while specifying
their computational cost. This analysis, together with Proposition 4, yields a
proof of Theorem 1.

Let $(L,\,R)$ be any valid solution of (SE) given in input to ReShape.

(i) Split. First, in lines 3-5, $L$ is written in its canonical form with
respect to the basis described by Eq. (13):

$\displaystyle L=M_{L}+O_{L}.$

This operation has the cost of a $n_{a}\times n_{b}$ times $n_{b}\times n_{b}$
matrix multiplication and therefore the Split step of ReShape has cost
$O(n_{a}n_{b}^{2})$.

(ii) Decode. The second step performed by ReShape (lines 8-12) aims to
minimise the logical row-column weight of $(L,\,R)$ by looking at non-
homologically equivalent operators:

$\displaystyle(L,\,R)+(L_{z},0),$

as $L_{z}$ varies in $\mathcal{L}_{z}^{\mathrm{left}}$. More precisely,
ReShape exploits the canonical form of $L$ computed at the previous step and
scans through all the columns of its logical part $O_{L}$. By construction,
any row $(O_{L})_{i}$ of $O_{L}$ belongs to the complement of
$\operatorname{\mathrm{Im}}\delta_{B}^{T}$. For this reason, $(O_{L})_{i}$ can
be written as the linear combination of
$k_{b}=n_{b}-\operatorname{\mathrm{rank}}(\delta_{B})$ unit vectors in
$\mathbb{F}_{2}^{n_{b}}$ which does not belong to
$\operatorname{\mathrm{Im}}\delta_{B}^{T}$ i.e. $k_{b}$ unit vectors which
span $(\operatorname{\mathrm{Im}}\delta_{B}^{T})^{\bot}$, see App. A.
Importantly, when we stack these row vectors $(O_{L})_{i}$ all together and
consider the columns of the matrix $O_{L}$, we observe that $O_{L}$ cannot
have more than $k_{b}$ non-zero columns. Each non-zero column of $O_{L}$ is
then treated as if it corresponded to a code-word of the classical code with
parity check matrix $\delta_{A}$ (plus eventually a noise vector) and decoded
individually using the classical minimum weight decoder
$\mathscr{D}_{\delta_{A}}$ (line 9):

$\displaystyle\mathscr{D}_{\delta_{A}}(O_{L}^{j})=\rho^{j}\Longleftrightarrow\rho^{j}\
\in\arg\min_{k\in\ker\delta_{A}}(|k+O_{L}^{j}|).$ (9)

If the computational cost of the classical decoder $\mathscr{D}_{\delta_{A}}$
is $O(c_{a})$, the computational cost of the second step of ReShape is
$O(k_{b}c_{a})$.

The Split and Decode steps described for the left part are replicated, with
opportune modifications, for the right part.

Proposition 4 below ensures that the recovery operator $(\tilde{L},\tilde{R})$
found by ReShape is a correct solution of (SE), as long as the classical
decoders $\mathscr{D}_{\delta_{A}}$ and $\mathscr{D}_{\delta_{B}^{T}}$
succeed.

######  Proposition 4.

Let $S$ be an $X$-syndrome matrix for $\mathcal{C}(\delta_{A},\delta_{B})$ and
$(L,R)$ any valid solution to the Syndrome Equation:

$\displaystyle\sigma(L,\,R)=S.$ (SE)

Suppose that the minimum weight operator $(L_{\min},\,R_{\min})$ with syndrome
$S$ has $(d_{a}/2,d_{b}^{T}/2)$-bounded logical row-column weight i.e.

$\displaystyle\mathrm{wt_{rc}^{log}}(L_{\min},\,R_{\min})=(\\#\mathrm{row_{log}}(L_{\min}),\\#\mathrm{col_{log}}(R_{\min})),$

is such that

$\displaystyle\\#\mathrm{row_{log}}(L_{\min})<\frac{d_{a}}{2}\quad\text{ and
}\quad\\#\mathrm{col_{log}}(R_{\min})<\frac{d_{b}^{T}}{2}.$ (10)

Then, on input $\mathscr{D}_{\delta_{A}}$, $\mathscr{D}_{\delta_{B}^{T}}$, $S$
and $(L,\,R)$, ReShape outputs a correct solution $(\tilde{L},\,\tilde{R})$ of
(SE), provided that the classical decoders $\mathscr{D}_{\delta_{A}}$,
$\mathscr{D}_{\delta_{B}^{T}}$ succeed. In other words, the solution
$(\tilde{L},\tilde{R})$ found by ReShape is in the same homology class as the
minimum weight operator with syndrome $S$:

$\displaystyle[L_{\min},\,R_{\min}]=[\tilde{L},\,\tilde{R}].$

It is important to note that the condition (10) on the weight of the original
error is on its row-column weight, while usually decoding success is assessed
depending on the weight of an operator, meaning the number of its non-identity
factors. Obviously, for any operator $(L,\,R)$ it holds:

$\\#row(L)\leq|L|\quad\text{and}\quad\\#col(R)\leq|R|.$

As a consequence, Proposition 4 entails that ReShape succeeds in correcting
any $Z$-error of weight up to half the code distance
$d_{z}=\min\\{d_{A},d_{B}^{T}\\}$. Combining this with the cost analysis of
the Split and Decode steps detailed above, gives a proof of Theorem 1.

It is worth to observe that actually ReShape can correct errors of weight
strictly bigger than half the code distance, as long as they are not too
‘spread’. In fact, whenever an error is homologically equivalent to an
operator $(L,R)$ such that $L$ has ‘few’ non-zero rows and $R$ has ‘few’ non-
zero columns, ReShape succeeds. Formally, because by definition:

$\\#\mathrm{row}(L)\geq\\#\mathrm{row_{log}}(L)\quad\text{and}\quad\\#\mathrm{col}(R)\geq\\#\mathrm{col_{log}}(R).$

Proposition 4 yields

######  Corollary 2.

Provided that the classical decoders succeed, ReShape successfully corrects
any $Z$-error $(L,R)$ with bounded row-column weight:

$\displaystyle\\#\mathrm{row}(L)<\frac{d_{a}}{2}\quad\text{ and
}\quad\\#\mathrm{col}(R)<\frac{d_{b}^{T}}{2}.$

To sum up, ReShape successfully solves the decoding problem for any hypergraph
product code requiring only $k$ oracle calls to a classical decoder for the
seed matrices, where $k$ is the logical dimension of the code. Furthermore, it
is able to correct for a vast class of errors of weight strictly bigger than
half the code distance, provided that they have a ‘good’ shape.

The next Section focuses on what happens when we cannot control the shape of
the errors but we assume that the probability of a given error to occur decays
exponentially in its weight.

###  III.3 ReShape for Stochastic noise

Up till now, we have focused on the adversarial noise model: errors on qubits
are always correctable because we assume they have weight less than half the
code distance. In real systems though, this is rarely the case and it is more
faithful to assume that errors are sampled accordingly to a local stochastic
noise model, where qubits errors have arbitrary location but the probability
of a given error decays exponentially in its weight. More precisely the
probability of a Pauli error $E\in\mathcal{P}_{n}$ to occur is given by:

$\mathbb{P}(E)=p^{|E|}(1-p)^{n-|E|}.$ (11)

Under the binomial distribution associated to Eq. (11), the expected error
weight on the encoded state is $pn$. Because the best possible distance
scaling for the hypergraph product codes is $\sim\sqrt{n}$ (when the classical
seed codes have linear distance), as $n$ increases, we eventually find
$pn>\sqrt{n}/2\sim d/2$. Nonetheless, it is well known that LDPC hypergraph
product codes do have a positive error correcting threshold Kovalevbadcode . A
family of codes has threshold $p_{\mathrm{th}}>0$ if, for noise rate below
$p_{\mathrm{th}}$, non-correctable errors that destroy the logical information
occur with probability $p_{\mathrm{non-correctable}}$ which decays
exponentially in the system size:

$\displaystyle p_{\mathrm{non-
correctable}}\propto\left(\frac{p}{p_{th}}\right)^{\alpha d^{\beta}}$ (12)

for some $\alpha,\beta>0$. It is important to stress that Eq. (12) does not
contrast with the fact that the typical error under the stochastic noise model
will have weight $pn$. Instead, Eq. (12) entails that, among all the errors
sampled, the non-correctable ones are only a small fraction. Beyond the
theoretical threshold that Kovalev and Pryadko proved in Kovalevbadcode , the
literature offers several numerical evidence of decoders for hypergraph
product or related families of codes which exhibit a threshold. Nonetheless
these decoders either lack a correctness proof, e.g. BP in
panteleev2019degenerate ; roffe2020decoding , or need some additional
constraints on the seed matrices, e.g. expander codes with small-set flip
decoder fawzi2018 , or augmented surface codes with the union-find decoder in
delfosse2020union .

On the contrary, for any choice of the seed matrices in the hypergraph
product, ReShape is provably correct for adversarial errors. Not surprisingly
though, ReShape does not show a threshold and the reason behind its anti-
threshold behaviour can be understood as follows.

A common ingredient for decoders that exhibit a threshold on LDPC codes is
their local nature on the syndrome graph, where nodes are stabiliser
generators that are connected by an edge if and only if their support overlap.
Roughly, local stochastic errors tend to form small disjoint clusters on the
qubit graph222i.e. nodes are qubit and two qubits are connected if and only if
there exists a stabiliser generator whose support contains both qubits. which
do not destroy the logical information as long as they are (1) small enough
(2) sufficiently far apart. If a decoder manages to mimic the error cluster
distribution on the syndrome graph and finds recovery operators accordingly,
then it is likely to show a threshold. ReShape, on the other hand, has a
deeply global nature. The Split step _groups_ all the clusters of flipped
stabilisers scattered across the syndrome graph in a small pre-assigned
region; a recovery is then chosen (Decode step) based on the syndrome
information there contained. If we take the planar code as an example (see
Fig. 2), the Split step groups the error (and the syndrome) weight on one
column of the left qubits. The subsequent Decode step decodes that column and
find a recovery operator with support there contained. Because for the planar
code a logical $Z$-operator can be chosen to have support on only one column
of the left qubits, this procedure can easily destroy the logical information.

Figure 2: Graphical representation of one instance of ReShape for $Z$-errors.
The code considered is the planar code of distance $3$ (toric code with
boundaries) or, equivalently, the hypergraph product code
$\mathcal{C}(\delta,\delta)$ for $\delta$ full-rank parity check matrix of the
distance-$3$ repetition code. We use the same graphical representation used in
Fig. 1. Input: the valid solution in input is $(L,R)$, whose support is
represented by the black qubits. Split step: $(L,R)$ is written as sum of its
free part $(M_{L},M_{R})$, with support on the striped qubits; and its logical
part $(O_{L},O_{R})$ with support on the polka-dot qubits. Decode step: the
column $(0,1,1)^{T}$ of the polka-dot qubits is given in input to a decoder
for the classical distance-3 repetition code. The solution found is
$(1,1,1)^{T}$, represented by the red qubits. Output: the output solution
$(\tilde{L},\tilde{R})$ is obtained by adding the input operator $(L,R)$ and
the operator found in the decode step, with support on the red qubits. The
support of $(\tilde{L},\tilde{R})$ is represented by the blue qubits.

Our intuition on the performance of ReShape under stochastic noise finds
confirmation in the plots reported in Fig. 3. Even if at first sight the plots
in Fig. 3a and 3b could indicate the presence of a very low threshold (below
$1\%$), a closer analysis suggests that this is not the case. In fact, as $d$
increases, the crossing point between the dashed curve labelled $d=0$ and the
$d$-curves slips leftwards. Since the dashed curve is the locus of points
where the failure probability $p_{\mathrm{fail}}$ equates the noise rate $p$,
it corresponds to the case of no encoding i.e. $d=0$. The common crossing
point, in other words, represents the _pseudo-threshold_ of the code
svore2005flow . Importantly, if a code family has a threshold
$p_{\mathrm{th}}$ in the sense of Eq. (12), then all the codes of the family
crosses the curve $d=0$ at the same point of coordinates
$(p_{\mathrm{th}},p_{\mathrm{th}})$. Fig. 3c clearly illustrates this left
slipping phenomenon for the toric codes without boundaries. For close
distances $d=6,8,10$, there it seems to be a common crossing point with the
$d=0$ curve. However, the crossing point lowers if we increase $d$ more
substantially, e.g. $d=20$. The situation appears less clear in Fig. 3d
because the pseudo-threshold seems to increase with the distance of the code.
Still though, there is no common crossing point of the three curves; besides,
we would expect the same trend as the one observed for the toric codes if
codes of bigger distance were considered.

In conclusion, ReShape is not suited to tackle stochastic errors in the regime
where typical errors has weight exceeding the code distance bound.

(a)

(b)

(c)

(d)

Figure 3: Anti-threshold behaviour of ReShape on two families of hypergraph
product codes. For both families, we plot the failure probability
$p_{\mathrm{fail}}$ as a function of the phase-flip noise rate $p$ for codes
with $Z$-distance $d$. All data points are generated with at least $10^{4}$
Monte Carlo trials. (a) and (c): The toric code without boundaries. (b) and
(d): A family of hypergraph product codes $\mathcal{C}(\delta,\delta^{T})$
where $\delta$ is a full-rank $(3,4)$-matrix randomly generated, see
roffe2020decoding .

##  IV Conclusions and outlook

In this paper we determined some important homology invariants of hypergraph
product codes. Exploiting these invariants, we designed the ReShape decoder.
ReShape is the first decoder to efficiently decode for all errors up to half
the code distance, across the whole spectrum of hypergraph product codes.

We foresee two natural extensions of this work. The first is to adapt ReShape
for it to work in the stochastic noise model settings. Because ReShape
actually succeeds in correcting errors of weight substantially bigger than
$(d-1)/2$ (namely it corrects error of weight as big as $\sim d^{2}$, when
they have the right shape!), this gives us some hope that ReShape would work
under stochastic noise if paired with the right clustering technique. For
instance, something on the line of the clustering methods used in the
renormalisation group or the union-find decoders bravyi2011analytic ;
bravyi2013quantum ; delfosse2017almost ; delfosse2021union_ldpc .

The second is to find the corresponding invariants for other families of
homological product codes. Specifically, for the codes in evra2020decodable ,
which have ‘rectangular’ shaped logical operators instead of ‘string’ like as
the standard hypergraph product codes here studied; or the balanced product
codes proposed in breuckmann2020balanced . Once found, the right invariants
could be plugged-in an appropriately modified version of ReShape and yield a
provable correct decoder for these class of codes too.

Acknowledgements.- This work was supported by the Engineering and Physical
Sciences Research Council [grant numbers EP/M024261/1 (E.T.C)]. ETC’s
contributions were made while he was at the University of Sheffield. We thank
Christophe Vuillot for helpful discussions and for carefully reading a draft
of this work. AOQ thanks Joschka Roffe for providing the matrices used in the
simulations.

## References

  * [1] Jean-Pierre Tillich and Gilles Zémor.  Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength.  IEEE Transactions on Information Theory, 60(2):1193–1202, 2014\.
  * [2] Alexey A. Kovalev and Leonid P. Pryadko.  Fault tolerance of quantum low-density parity check codes with sublinear distance scaling.  Phys. Rev. A, 87:020304, Feb 2013.
  * [3] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill.  Topological quantum memory.  Journal of Mathematical Physics, 43(9):4452–4505, 2002.
  * [4] Austin G. Fowler, Ashley M. Stephens, and Peter Groszkowski.  High-threshold universal quantum computation on the surface code.  Phys. Rev. A, 80:052312, Nov 2009.
  * [5] Nicolas Delfosse and Naomi H Nickerson.  Almost-linear time decoding algorithm for topological codes.  arXiv preprint arXiv:1709.06218, 2017.
  * [6] Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor.  Quantum expander codes.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 810–824. IEEE, 2015.
  * [7] Michael Sipser and Daniel A Spielman.  Expander codes.  IEEE transactions on Information Theory, 42(6):1710–1722, 1996\.
  * [8] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier.  Efficient decoding of random errors for quantum expander codes.  In Proc. STOC, pages 521–534. ACM, 2018.
  * [9] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier.  Constant overhead quantum fault-tolerance with quantum expander codes.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 743–754. IEEE, 2018.
  * [10] David Poulin and Yeojin Chung.  On the iterative decoding of sparse quantum codes.  Quantum Info. Comput., 8(10):987–1000, November 2008.
  * [11] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo.  Fifteen years of quantum ldpc coding and improved decoding strategies.  IEEE Access, 3:2492–2519, 2015.
  * [12] Ye-Hua Liu and David Poulin.  Neural belief-propagation decoders for quantum error-correcting codes.  Physical review letters, 122(20):200501, 2019.
  * [13] Alex Rigby, J. C. Olivier, and Peter Jarvis.  Modified belief propagation decoders for quantum low-density parity-check codes.  Phys. Rev. A, 100:012330, Jul 2019.
  * [14] Pavel Panteleev and Gleb Kalachev.  Degenerate quantum ldpc codes with good finite length performance.  arXiv preprint arXiv:1904.02703, 2019.
  * [15] M. Li and T. J. Yoder.  A numerical study of bravyi-bacon-shor and subsystem hypergraph product codes.  In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 109–119, 2020.
  * [16] Antoine Grospellier, Lucien Grouès, Anirudh Krishna, and Anthony Leverrier.  Combining hard and soft decoders for hypergraph product codes.  arXiv preprint arXiv:2004.11199, 2020.
  * [17] Joschka Roffe, David R White, Simon Burton, and Earl Campbell.  Decoding across the quantum low-density parity-check code landscape.  Physical Review Research, 2(4):043423, 2020.
  * [18] Nicolas Delfosse, Vivien Londe, and Michael Beverland.  Toward a union-find decoder for quantum ldpc codes.  arXiv preprint arXiv:2103.08049, 2021.
  * [19] Héctor Bombín.  Single-shot fault-tolerant quantum error correction.  Phys. Rev. X, 5(3):031043, 2015.
  * [20] Armanda O Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T Campbell.  Single-shot error correction of three-dimensional homological product codes.  arXiv preprint arXiv:2009.11790, 2020.
  * [21] W Cary Huffman and Vera Pless.  Fundamentals of error-correcting codes.  Cambridge university press, 2010.
  * [22] Daniel Gottesman.  Stabilizer codes and quantum error correction.  arXiv preprint quant-ph/9705052, 1997.
  * [23] A Robert Calderbank and Peter W Shor.  Good quantum error-correcting codes exist.  Physical Review A, 54(2):1098, 1996.
  * [24] Andrew Steane.  Multiple-particle interference and quantum error correction.  Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 452(1954):2551–2577, 1996.
  * [25] Joschka Roffe.  Quantum error correction: an introductory guide.  Contemporary Physics, 60(3):226–245, 2019.
  * [26] Micheal. A. Nielsen and Isaac. L. Chuang.  Quantum Computation and Quantum Information.  Cambridge, 2000.
  * [27] Jean-Pierre Tillich and Gilles Zémor.  Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength.  IEEE Transactions on Information Theory, 60(2):1193–1202, 2014\.
  * [28] Sergey Bravyi and Matthew B Hastings.  Homological product codes.  In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 273–282. ACM, 2014.
  * [29] Benjamin Audoux and Alain Couvreur.  On tensor products of css codes.  arXiv preprint arXiv:1512.07081, 2015.
  * [30] Weilei Zeng and Leonid P Pryadko.  Higher-dimensional quantum hypergraph-product codes with finite rates.  Physical review letters, 122(23):230501, 2019.
  * [31] A.Yu. Kitaev.  Fault-tolerant quantum computation by anyons.  Ann. Phys., 303:2, 2003.
  * [32] Sergey B Bravyi and A Yu Kitaev.  Quantum codes on a lattice with boundary.  arXiv preprint quant-ph/9811052, 1998.
  * [33] Nicolas Delfosse and Matthew B Hastings.  Union-find decoders for homological product codes.  arXiv preprint arXiv:2009.14226, 2020.
  * [34] Krysta M Svore, Andrew W Cross, Isaac L Chuang, and Alfred V Aho.  A flow-map model for analyzing pseudothresholds in fault-tolerant quantum computing.  arXiv preprint quant-ph/0508176, 2005.
  * [35] Sergey Bravyi and Jeongwan Haah.  Analytic and numerical demonstration of quantum self-correction in the 3d cubic code. december 2011.  arXiv preprint arXiv:1112.3252, 2011.
  * [36] Sergey Bravyi and Jeongwan Haah.  Quantum self-correction in the 3d cubic code model.  Phys. Rev. Lett., 111(20):200501, 2013.
  * [37] Shai Evra, Tali Kaufman, and Gilles Zémor.  Decodable quantum ldpc codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders.  arXiv preprint arXiv:2004.07935, 2020.
  * [38] Nikolas P Breuckmann and Jens N Eberhardt.  Balanced product quantum codes.  arXiv preprint arXiv:2012.09271, 2020.
  * [39] Serge Lang.  Undergraduate algebra.  Springer Science & Business Media, 2005.
  * [40] Israel N Herstein.  Abstract algebra.  Prentice Hall, 1996.
  * [41] Hector Bombin and Miguel A Martin-Delgado.  Homological error correction: Classical and quantum codes.  Journal of mathematical physics, 48(5):052105, 2007.
  * [42] Sergey Bravyi and Matthew B Hastings.  Homological product codes.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 273–282. ACM, 2014.
  * [43] Allen Hatcher.  Algebraic topology. 2002.  Cambridge UP, Cambridge, 606(9), 2002.
  * [44] Earl Campbell.  A theory of single-shot error correction for adversarial noise.  Quantum Science and Technology, 2019.

##  Appendix A Linear algebra: Space complement

In this Appendix we review some known linear algebra facts that we use in our
proofs. We refer the reader for instance to [39, 40] for a detailed
presentation on the topic.

Consider a $m\times n$ binary matrix $\delta$. If
$\operatorname{\mathrm{rank}}(\delta)=\mathrm{rk}$ then we can choose binary
vectors $v_{1},\dots,v_{\mathrm{rk}}$ in $\mathbb{F}_{2}^{m}$ whose span is
$\operatorname{\mathrm{Im}}\delta$:

$\displaystyle\operatorname{\mathrm{Im}}\delta=\langle
v_{1},\dots,v_{\mathrm{rk}}\rangle.$

Let $\mathbb{1}$ be the $m\times m$ identity matrix. Perform Gaussian
reduction on the $(\mathrm{rk}+m)$-row matrix $M$:

$\displaystyle M=\begin{pmatrix}v_{1}\\\ \vdots\\\ v_{\mathrm{rk}}\\\
\hline\cr\mathbb{1}\end{pmatrix}.$

By selecting the pivot rows, we obtain a basis of $\mathbb{F}_{2}^{m}$ of the
form:

$\displaystyle\\{v_{1},\dots,v_{\mathrm{rk}},f_{\mathrm{rk}+1},\dots,f_{m}\\},$
(13)

where the $f_{i}$ are unit vectors. Letting:

$(\operatorname{\mathrm{Im}}\delta)^{\bot}\coloneqq\langle
f_{\mathrm{rk}+1},\dots,f_{m}\rangle,$

we have:

$\mathbb{F}^{m}=(\operatorname{\mathrm{Im}}\delta)\oplus(\operatorname{\mathrm{Im}}\delta)^{\bot}.$
(14)

We refer to the space $(\operatorname{\mathrm{Im}}\delta)^{\bot}$ as
complement of the space $\operatorname{\mathrm{Im}}\delta$.

##  Appendix B Hypergraph product codes

CSS codes can be easily described in terms of homology theory [31, 41, 42] via
the identification of the objects of the code with a chain complex [43]. For
our purposes, a length $\ell$ chain complex is an object described by a
sequence of $\ell+1$ vector spaces $\\{\mathcal{C}_{i}\\}_{i}$ over
$\mathbb{F}_{2}$ and $\ell$ binary matrices
$\\{\partial_{i}:\mathcal{C}_{i}\longrightarrow\mathcal{C}_{i+1}\\}_{i}$ such
that, for each $i$, $\partial_{i}\partial_{i-1}=0$. In the following, we use
the symbol $\partial$ to indicate the maps of a chain complex of length
$\ell>1$ and the symbol $\delta$ to indicate the map of a chain complex of
length $1$. Given a chain complex $\mathfrak{C}$:

$\mathcal{C}_{-1}\xrightarrow[]{\partial_{-1}}\mathcal{C}_{0}\xrightarrow[]{\partial_{0}}\mathcal{C}_{1},$
($\mathfrak{C}$)

we can define a CSS code $\mathcal{C}$ by equating:

$\displaystyle H_{Z}=\partial_{-1}^{T},\quad H_{X}=\partial_{0}.$

Since $\partial_{0}\partial_{-1}=0$ by construction, $X$-type and $Z$-type
operators do commute i.e. $H_{X}\cdot H_{Z}^{T}=0$ and the code $\mathcal{C}$
associated to the chain complex ($\mathfrak{C}$) is well defined. The code
$\mathcal{C}$ has length $n=\dim(\mathcal{C}_{0})$ and its dimension $k$
equates to the dimension of the $0$th homology group
$\mathcal{H}_{0}=\ker\partial_{0}/\operatorname{\mathrm{Im}}\partial_{-1}$ or,
equivalently, to the dimension of the $0$th co-homology group
$\mathcal{H}_{0}^{*}=\ker{\partial_{-1}}/\operatorname{\mathrm{Im}}\partial_{0}$.
Its $Z$-distance and $X$-distance are given by the minimum Hamming weight of
any representative of a non-zero element in $\mathcal{H}_{0}$ and
$\mathcal{H}_{0}^{*}$ respectively:

$\displaystyle d_{z}$
$\displaystyle=\min_{v\in\mathbb{F}_{2}^{n}}\\{|v|:[v]\in\mathcal{H}_{0},[v]\neq
0\\},$ $\displaystyle d_{x}$
$\displaystyle=\min_{v\in\mathbb{F}_{2}^{n}}\\{|v|:[v]\in\mathcal{H}_{0}^{*},[v]\neq
0\\}.$

An hypergraph product code $\mathcal{C}(\delta_{A},\delta_{B})$, which is a
CSS code, can be easily defined in terms of product of chain complexes.
Consider the two length-1 chain complexes defined by the seed matrices
$\delta_{A}$ and $\delta_{B}$:

$\displaystyle C^{0}_{A}$ $\displaystyle\xrightarrow[]{\delta_{A}}C^{1}_{A},$
$\displaystyle C^{0}_{B}$ $\displaystyle\xrightarrow[]{\delta_{B}}C^{1}_{B}.$

We define their homological product as follows. Take the tensor product spaces
$\mathcal{C}_{-1}=C^{0}_{A}\otimes C_{B}^{1}$ and
$\mathcal{C}_{1}=C^{1}_{A}\otimes C^{0}_{B}$ and the direct sum space
$\mathcal{C}_{0}=C^{0}_{A}\otimes C^{0}_{B}\oplus C^{1}_{A}\otimes C^{1}_{B}$.
The chain complex $\mathfrak{C}_{A,B}$:

${C^{1}_{A}\otimes C^{0}_{B}}$${C^{0}_{A}\otimes C^{0}_{B}}$${C^{1}_{A}\otimes
C^{1}_{B}}$${C^{0}_{A}\otimes
C^{1}_{B}}$$\scriptstyle{\delta_{A}\otimes\mathbb{1}}$$\scriptstyle{\mathbb{1}\otimes\delta_{B}^{T}}$$\scriptstyle{\mathbb{1}\otimes\delta_{B}^{T}}$$\scriptstyle{\delta_{A}\otimes\mathbb{1}}$
${\mathcal{C}_{1}}$${\mathcal{C}_{0}}$${\mathcal{C}_{-1}}$$\scriptstyle{\partial_{0}}$$\scriptstyle{\partial_{-1}}$
($\mathfrak{C}_{A,B}$)

$\partial_{-1}=\left(\mathbb{1}\otimes\delta_{B},\quad\delta_{A}^{T}\otimes\mathbb{1}\right)^{T},\\\
\partial_{0}=\left(\delta_{A}\otimes\mathbb{1},\quad\mathbb{1}\otimes\delta_{B}^{T}\right)$

is well defined. In fact:

$\displaystyle\partial_{-1}\partial_{0}=\delta_{A}\otimes\delta_{B}^{T}+\delta_{A}\otimes\delta_{B}^{T}=0.$

Therefore, the complex $\eqref{eq:cab}$ defines a valid CSS code, which we
denote by $\mathcal{C}(\delta_{A},\delta_{B})$ and refer to as the hypergraph
product code of the seed matrices $\delta_{A}$ and $\delta_{B}$. If the
classical code with parity check $\delta_{\ell},\delta_{\ell}^{T}$ has
parameters $[n_{\ell},k_{\ell},d_{\ell}]$ and
$[n_{\ell}^{T},k_{\ell}^{T},d_{\ell}^{T}]$ respectively ($\ell=A,B$) then the
hypergraph product code $\mathcal{C}(\delta_{A},\delta_{B})$ has parameters:

$\displaystyle[[n_{a}n_{b}+n_{a}^{T}n_{b}^{T},\,k_{a}k_{b}+k_{a}^{T}k_{b}^{T},\,d_{x},\,d_{z}]],$

where $d_{x}=\min\\{d_{a}^{T},d_{b}\\}$ and $d_{z}=\min\\{d_{a},d_{b}^{T}\\}$,
see [42].

###  B.1 Reshaping of vectors

One tool we make extensive use of, and from which our decoder takes its name,
is the reshaping of vectors of a two-fold tensor product space into matrices
(see, for instance, [42, 44]). Consider a basis $\mathcal{B}$ of the vector
space $\mathbb{F}_{2}^{n_{1}}\otimes\mathbb{F}_{2}^{n_{2}}$:

$\mathcal{B}=\\{a_{i}\otimes b_{j}\mid i=1,\dots,n_{1}\text{ and
}j=1,\dots,n_{2}\\}.$

Then any $v\in\mathbb{F}_{2}^{n_{1}}\otimes\mathbb{F}_{2}^{n_{2}}$ can be
written as:

$\displaystyle v=\sum_{a_{i}\otimes b_{j}\in\mathcal{B}}v_{ij}(a_{i}\otimes
b_{j}),$

for some $v_{ij}\in\mathbb{F}_{2}$. We call the $n_{1}\times n_{2}$ matrix $V$
with entries $v_{ij}$ the reshaping of the vector $v$. By this identification,
if $\varphi$, $\theta$ are respectively $m_{1}\times n_{1}$ and $m_{2}\times
n_{2}$ matrices, then $(\varphi\otimes\theta)(V)=\varphi V\theta^{T}$. The
inner product between $u\otimes w$ and $v$ in
$\mathbb{F}_{2}^{n_{1}}\otimes\mathbb{F}_{2}^{n_{2}}$ can be computed as

$\displaystyle\langle u\otimes w,v\rangle=u^{T}Vw.$ (15)

As we here detail, the identification of operators on the code space
$\mathcal{C}(\delta_{A},\delta_{B})$ with pairs of binary matrices that we
used in the main text is rigorously justified by the reshaping of vectors into
matrices. With slight abuse of notation, we refer to binary vectors and binary
matrices as operators and vice versa, where the identification is clear via
Eq. (6).

###  B.2 Graphical representation

Physical qubits of the code $\mathcal{C}(\delta_{A},\delta_{B})$ are in one-
to-one correspondence with basis element of the space $\mathcal{C}_{0}$. If
$\\{e_{j_{a}}\\}_{j_{a}}$, $\\{e_{j_{b}}\\}_{j_{b}}$,
$\\{e_{i_{a}}\\}_{i_{a}}$, $\\{e_{i_{b}}\\}_{i_{b}}$ are basis of the spaces
$C_{0}^{A},C_{0}^{B},C_{1}^{A},C^{B}_{1}$ of dimension
$n_{a},n_{b},m_{a},m_{b}$ respectively, then the union of the two sets

$\displaystyle\mathcal{B}_{L}$ $\displaystyle\coloneqq\\{(e_{j_{a}}\otimes
e_{j_{b}},\,0)\\}$ $\displaystyle\mathcal{B}_{R}$
$\displaystyle\coloneqq\\{(0,\,e_{i_{a}}\otimes e_{i_{b}})\\}$

is a basis of $\mathcal{C}_{0}$. We refer to qubits associated to elements in
$\mathcal{B}_{L}$, or its span, as _left_ qubits and to those associated to
$\mathcal{B}_{R}$, or its span, as _right_ qubits. Since qubit operators are
vectors in $\mathcal{C}_{0}$, by reshaping, they can be identified with pairs
of matrices $(L,\,R)$ where $L$ has size $n_{a}\times n_{b}$ and $R$ has size
$m_{a}\times m_{b}$; in particular, $L$ acts on the left qubits while $R$ acts
on the right qubits.

A $Z$-stabilizer for the code associated to the complex ($\mathfrak{C}_{A,B}$)
is any vector in $\operatorname{\mathrm{Im}}\partial_{-1}$. A generating set
for $Z$-stabilizers is:

$\mathcal{S}_{z}\coloneqq\\{\partial_{-1}(e_{j_{a}}\otimes
e_{i_{b}})\\}_{j_{a},i_{b}}$

where $e_{j_{a}}$ and $e_{i_{b}}$ are unit vectors of $C^{0}_{A}$ and
$C^{1}_{B}$ respectively, i.e. they are a basis of the two spaces. Let
$E_{j_{a}i_{b}}\in C^{0}_{A}\otimes C_{B}^{1}$ be the reshaping of
$(e_{j_{a}}\otimes e_{i_{b}})$, i.e. it is the matrix with all zeros entries
but for the $(j_{a},i_{b})$-th entry which is 1. The reshape of
$\partial_{-1}(e_{j_{a}}\otimes e_{i_{b}})$ is then given by the pair of
matrices:

$(L,R)=(E_{j_{a}i_{b}}\delta_{B},\delta_{A}E_{j_{a}i_{b}}).$

Logical $Z$-operators are vectors in $\ker\partial_{0}$ which are not in
$\operatorname{\mathrm{Im}}\partial_{-1}$. Specifically, a minimal generating
set of logical $Z$-operators is given by [30]:

$\displaystyle\hat{\mathcal{L}}_{z}$
$\displaystyle\coloneqq\hat{\mathcal{L}}_{z}^{\mathrm{left}}\cup\hat{\mathcal{L}}_{z}^{\mathrm{right}}$
(16)

where

$\displaystyle\hat{\mathcal{L}}_{z}^{\mathrm{left}}\coloneqq\big{\\{}(k_{a}\otimes
e_{j_{b}},0)$ $\displaystyle:k_{a}\text{ varies among a basis of
}\ker\delta_{A},$ $\displaystyle\quad|e_{j_{b}}|=1\text{ and it varies}$
$\displaystyle\quad\text{among a basis of
}\operatorname{\mathrm{Im}}(\delta_{B}^{T})^{\bot}\big{\\}},$

and

$\displaystyle\hat{\mathcal{L}}_{z}^{\mathrm{right}}\coloneqq\big{\\{}(0,e_{i_{a}}\otimes\bar{k}_{b})$
$\displaystyle:|e_{i_{a}}|=1\text{ and it varies}$
$\displaystyle\quad\text{among a basis of
}\operatorname{\mathrm{Im}}(\delta_{A})^{\bot},$
$\displaystyle\quad\bar{k}_{b}\text{ varies among a basis of
}\ker\delta_{B}^{T}\big{\\}}.$

The reshaping of vectors in $\hat{\mathcal{L}}_{z}$ gives the set
$\mathcal{L}_{z}$ of Eq. (7) in the main text. The vector version of logical
$X$-operators is likewise obtained from the set of matrices $\mathcal{L}_{x}$
of Eq. (8).

##  Appendix C Proofs

This Section contains all the proofs of the statements made in the main text.

Broadly speaking, in this work we wanted to characterize $Z$-errors operators
on the codespace of $\mathcal{C}(\delta_{A},\delta_{B})$ associated to the
chain complex ($\mathfrak{C}_{A,B}$). In order to do so, we first studied the
logical $Z$-operators of $\mathcal{C}(\delta_{A},\delta_{B})$. From homology
theory, we know that non-trivial logical $Z$-operators are associated to
vectors in $\ker\partial_{0}$ which do not belong to
$\operatorname{\mathrm{Im}}\partial_{-1}$. Lemma 1 below describes all the
vectors in $\ker\partial_{0}$.

######  Lemma 1.

Let $(L,R)\in\mathcal{C}_{0}$ be in $\ker\partial_{0}$, then:

$\displaystyle L$ $\displaystyle\in\ker\delta_{A}\otimes
C_{B}^{0}+C_{A}^{0}\otimes\operatorname{\mathrm{Im}}(\delta_{B}^{T}),$
$\displaystyle R$ $\displaystyle\in
C_{A}^{1}\otimes\ker\delta_{B}^{T}+\operatorname{\mathrm{Im}}(\delta_{A})\otimes
C_{B}^{1}.$

###### Proof.

Let $(L,R)\in\ker\partial_{0}$. Then:

$\displaystyle\partial_{0}(L,R)=0$
$\displaystyle\Longleftrightarrow(\delta_{A}\otimes\mathbb{1})L+(\mathbb{1}\otimes\delta_{B}^{T})R=0,$
$\displaystyle\Longleftrightarrow\delta_{A}L+R\delta_{B}=0.$ (17)

Eq. (17) yields:

$\displaystyle\delta_{A}L=R\delta_{B}=V,$ (18)

for some $V\in C_{A}^{1}\otimes C_{B}^{0}$. Eq. (18) entails that all columns
of $V$ belong to $\operatorname{\mathrm{Im}}(\delta_{A})$ while its rows
belong to $\operatorname{\mathrm{Im}}\delta_{B}^{T}$. As a consequence, it
must exists $U\in C_{A}^{0}\otimes C_{B}^{1}$ such that:

$\displaystyle V=\delta_{A}U\delta_{B}.$

Therefore Eq. (18) can be re-written as:

$\displaystyle\delta_{A}L=\delta_{A}U\delta_{B}$

which yields:

$\displaystyle(\delta_{A}\otimes\mathbb{1})(L+U\delta_{B})$
$\displaystyle=\delta_{A}L+\delta_{A}U\delta_{B}$ $\displaystyle=V+V$
$\displaystyle=0$ (19)

Equivalently, Eq. (19) states that $L+U\delta_{B}$ has columns in
$\ker\delta_{A}$:

$\displaystyle L+U\delta_{B}\in\ker\delta_{A}\otimes C_{B}^{0}$

and therefore:

$\displaystyle L\in\ker\delta_{A}\otimes
C_{B}^{0}+C_{A}^{0}\otimes\operatorname{\mathrm{Im}}(\delta_{B}^{T}),$

as in the thesis. Similarly, we find

$\displaystyle R\in
C_{A}^{1}\otimes\ker\delta_{B}^{T}+\operatorname{\mathrm{Im}}(\delta_{A})\otimes
C_{B}^{1}.$

∎

In the main text, we have introduced the notions of row-column weight and
logical row-column weight for a $Z$-operator on
$\mathcal{C}(\delta_{A},\delta_{B})$. The definition of these two quantities
finds its explanation in Proposition 2, whose proof builds on the results of
Lemma 1.

######  Proposition 2.

If $(L,\,R)$ is a non-trivial logical $Z$-operator of
$\mathcal{C}(\delta_{A},\delta_{B})$ then either $\\#\mathrm{row}(L)\geq
d_{a}$ or $\\#\mathrm{col}(R)\geq d_{b}^{T}$ (or both).

###### Proof.

If $(L,R)$ is a non-trivial logical $Z$-operator, it must anti-commute with at
least one logical $X$-operator $(L_{x},R_{x})$. Because a $Z$-operator and a
$X$-operator anti-commute if and only if their supports overlap on an odd
number of positions, either $L$ and $L_{x}$ or $R$ and $R_{x}$ have odd
overlap. Without loss of generality, we can assume that the former is verified
and we can choose $(L_{x},R_{x})$ as a left operator of the form

$\displaystyle(L_{x},R_{x})=(f\otimes k,0),$

where $f$ is a unit vector in
$(\operatorname{\mathrm{Im}}\delta_{A}^{T})^{\bot}$ and $k\in\ker\delta_{B}$.
In other words, we choose logical $X$-operator $(f\otimes k,0)$ from the set
of generators of $X$-logical operators
$\hat{\mathcal{L}}_{x}^{\mathrm{left}}$, as in the $X$-version of Eq. (16).
The inner product equation for reshaped vectors Eq. (15) then yields:

$\displaystyle 1=\big{\langle}(L_{x},0),(L,\,R)\big{\rangle}$
$\displaystyle=\langle L_{x},L\rangle+\langle 0,R\rangle$
$\displaystyle=f^{T}Lk.$ (20)

Now, observe that $(L,\,R)\in\mathcal{C}_{0}$ is a non-trivial logical
$Z$-operator of $\mathcal{C}(\delta_{A},\delta_{B})$ if and only if
$[L,R]\in\mathcal{H}_{0}=\ker\partial_{0}/\operatorname{\mathrm{Im}}\partial_{-1}$
and $[L,R]\neq 0$ or, equivalently, if and only if:

$\displaystyle(L,\,R)\in\ker\partial_{0}\setminus\operatorname{\mathrm{Im}}\partial_{-1}.$

In particular, $(L,R)$ belongs to $\ker\partial_{0}$ and thanks to Lemma 1, we
can re-write it as:

$\displaystyle(L,R)=(K_{A}+U_{L}\delta_{B},\bar{K}_{B}+\delta_{A}U_{R}),$

where columns of $K_{A}$ belong to $\ker\delta_{A}$ and rows of $\bar{K}_{B}$
belong to $\ker\delta_{B}^{T}$. Using Lemma 1’s decomposition for
$(L,R)\in\ker\partial_{0}$, we can expand the matrix-vector product $Lk$ as:

$\displaystyle Lk$ $\displaystyle=(K_{A}+U_{L}\delta_{B})k$
$\displaystyle=K_{A}k+U_{L}\delta_{B}k$ $\displaystyle=K_{A}k$
$\displaystyle\text{since }k\in\ker\delta_{B}.$ (21)

Eq. (21) entails $Lk=K_{A}k$ and therefore that $Lk$, being a linear
combination of column-vectors in $\ker\delta_{A}$, belongs to $\ker\delta_{A}$
itself. Furthermore, by Eq. (20), $Lk\neq 0$. To sum up, $Lk$ is a non-zero
vector in $\ker\delta_{A}$ and therefore it must have Hamming weight at least
$d_{a}$. As a consequence, $L$ is a matrix with at least $d_{a}$ rows:

$\displaystyle\\#\mathrm{row}(L)\geq d_{a}.$

Similarly, we would have found:

$\displaystyle\\#\mathrm{col}(R)\geq d_{b}^{T},$

if we had assumed that $(L,R)$ anti-commuted with a logical $X$-operator
$(0,R_{x})$ in $\hat{\mathcal{L}}_{x}^{\mathrm{right}}$. ∎

Corollary 1 follows easily.

######  Corollary 1.

If $(L,R)$ is a non-trivial logical $Z$-operator on
$\mathcal{C}(\delta_{A},\delta_{B})$, at least one of the following hold:

  1. (i)

$L$ has at least $d_{a}$ rows which are not in
$\operatorname{\mathrm{Im}}\delta^{T}_{B}$ when seen as vectors in
$C^{0}_{B}$.

  2. (ii)

$R$ has at least $d_{b}^{T}$ columns which are not in
$\operatorname{\mathrm{Im}}\delta_{A}$ when seen as vectors of $C^{1}_{A}$.

###### Proof.

Write $(L,R)$ in its canonical form:

$\displaystyle(L,R)=(M_{L}+O_{L},M_{R}+O_{R}),$

and let

$\displaystyle M_{L}$ $\displaystyle=N_{L}\delta_{B},$ $\displaystyle M_{R}$
$\displaystyle=\delta_{A}N_{R},$

for some binary matrices $N_{L},N_{R}$ of size $n_{a}\times m_{b}$. As done in
the proof of Proposition 2, consider a logical $X$-operator $(f\otimes k,0)$
such that it anti-commutes with $(L,R)$. Combining the canonical form of $L$
and Eq. (21), yields:

$\displaystyle Lk$ $\displaystyle=(O_{L}+N_{L}\delta_{B})k$
$\displaystyle=O_{L}k$ $\displaystyle\text{since }k\in\ker\delta_{B}$
$\displaystyle=K_{A}k$ by Eq. (21)

for some $n_{a}\times n_{b}$ matrix $K_{A}$ with columns in $\ker\delta_{A}$.
By the same argument used in the proof of Proposition 2, we find:

$\displaystyle|K_{A}k|\geq d_{A}\Rightarrow|O_{L}k|\geq d_{A},$

and in particular that $O_{L}$ has at least $d_{a}$ non-zero rows. Since by
definition of canonical form the non-zero rows of $O_{L}$ are precisely those
rows of $L$ which do not belong to $\operatorname{\mathrm{Im}}\delta_{B}$, we
have proven point (i). Point (ii) follows similarly in the case $(L,R)$ anti-
commutes with at least one logical $X$-operator of the form $(0,R_{x})$. ∎

Corollary 1, together with Proposition 3 below, justifies the definition of
the logical row-column weight for $Z$-operators on
$\mathcal{C}(\delta_{A},\delta_{B})$ (Definition 2). The logical row-column
weight of $(L,R)$ is denoted by the symbol $\mathrm{wt_{rc}^{log}}(L,R)$ and
stands for the integer pair
$(\\#\mathrm{row_{log}}(L),\,\\#\mathrm{col_{log}}(R))$ where
$\\#\mathrm{row_{log}}(L)$ is the number of rows of $L$ that are not in
$\operatorname{\mathrm{Im}}\delta_{B}^{T}$ and $\\#\mathrm{col_{log}}(R)$ is
the number of columns of $R$ which are not in
$\operatorname{\mathrm{Im}}\delta_{A}$. Proposition 3, that we now prove,
states that the logical row-column weight of a $Z$-operator on
$\mathcal{C}(\delta_{A},\delta_{B})$ is an homology invariant of the chain
complex ($\mathfrak{C}_{A,B}$) and therefore it legitimates the name choice
for this quantity.

######  Proposition 3.

The logical row-column weight of a $Z$-operator on
$\mathcal{C}(\delta_{A},\delta_{B})$ is an invariant of its homology class.

###### Proof.

Let $[L,R]$ be the homology class of $(L,\,R)$:

$\displaystyle[L,\,R]=\big{\\{}(L+G_{L},\,R+G_{R}):$
$\displaystyle\,(G_{L},\,G_{R})\big{.}$ $\displaystyle\big{.}\text{ is a
$Z$-stabiliser}\big{\\}}.$

The operator $(G_{L},G_{R})\in\mathcal{C}_{0}$ is a $Z$-stabilizer for
$\mathcal{C}(\delta_{A},\delta_{B})$ if and only if

$\displaystyle(G_{L},G_{R})$ $\displaystyle=\partial_{-1}(U)$
$\displaystyle=(U\delta_{B},\delta_{A}U)$ (22)

For some $n_{a}\times m_{b}$ binary matrix $U$. Eq. (22) entails that any row
of $G_{L}$ belongs to $\operatorname{\mathrm{Im}}\delta_{B}^{T}$ and any
column of $G_{R}$ belongs to $\operatorname{\mathrm{Im}}\delta_{A}$.
Therefore, if we write $(L,R)$ in its canonical form:

$\displaystyle(L,R)=(M_{L}+O_{L},M_{R}+O_{R}),$

we see that we can ‘delete’ all the rows of $M_{L}$ by adding a stabiliser and
hence ‘move’ part of the support of the operator $(L,R)$ from the left qubits
to the right qubits. Specifically, if $M_{L}=N_{L}\delta_{B}$ for some
$n_{a}\times m_{b}$ binary matrix $N_{L}$, we consider the stabiliser
$G=(N_{L}\delta_{B},\delta_{A}N_{L})$ and we obtain:

$\displaystyle(L,R)+G=(O_{L},M_{R}+O_{R}+\delta_{A}N_{L}).$

Similarly, we could move the $M_{R}$ part of the operator $(L,R)$ from the
right qubits to the left qubits, by adding the stabilizer
$G^{\prime}=(N_{R}\delta_{B},\delta_{A}N_{R})$, for a $n_{a}\times m_{b}$
matrix $N_{R}$ such that $M_{R}=\delta_{A}N_{R}$.

On the other hand though, it is not possible to delete non-zero rows of
$O_{L}$ via stabiliser addition. In other words, it is not possible to remove,
via stabiliser addition, any of the rows of $L$ that are not in
$\operatorname{\mathrm{Im}}\delta_{B}^{T}$. Hence, the number
$\\#\mathrm{row_{log}}(L)$ of non-zero rows of $O_{L}$ is an homology
invariant. Likewise, we find that it is not possible to delete any column in
$O_{R}$ by adding stabilisers and therefore $\\#\mathrm{col_{log}}(R)$ is a
logical invariant too. ∎

The proof of Proposition 3 actually entails a stronger result than the
invariance of the row-column weight of $Z$-operators on
$\mathcal{C}(\delta_{A},\delta_{B})$. Namely, we have proven that the indices
of the rows and the columns in the sets $\mathrm{row_{log}}$ and
$\mathrm{col_{log}}$ respectively, are homology invariants of the reshaped
$Z$-operators $(L,R)$ on $\mathcal{C}(\delta_{A},\delta_{B})$. However,
because to prove the correctness of ReShape it is sufficient to look at the
cardinality of the two sets $\mathrm{row_{log}}$ and $\mathrm{col_{log}}$, we
decided to state Proposition in this more compact and elegant form.

We can now prove Proposition 4.

######  Proposition 4.

Let $S$ be a $X$-syndrome matrix for $\mathcal{C}(\delta_{A},\delta_{B})$ and
$(L,R)$ any valid solution to the Syndrome Equation

$\displaystyle\sigma(L,\,R)=S.$ (SE)

Suppose that the minimum weight operator $(L_{\min},\,R_{\min})$ with syndrome
$S$ has $(d_{a}/2,d_{b}^{T}/2)$-bounded logical row-column weight i.e.

$\displaystyle\mathrm{wt_{rc}^{log}}(L_{\min},\,R_{\min})=(\\#\mathrm{row_{log}}(L_{\min}),\\#\mathrm{col_{log}}(R_{\min})),$

is such that

$\displaystyle\\#\mathrm{row_{log}}(L_{\min})<\frac{d_{a}}{2}\quad\text{ and
}\quad\\#\mathrm{col_{log}}(R_{\min})<\frac{d_{b}^{T}}{2}.$ (10)

Then, on input $\mathscr{D}_{\delta_{A}}$, $\mathscr{D}_{\delta_{B}^{T}}$, $S$
and $(L,\,R)$, ReShape outputs a correct solution $(\tilde{L},\,\tilde{R})$ of
(SE), provided that the classical decoders $\mathscr{D}_{\delta_{A}}$,
$\mathscr{D}_{\delta_{B}^{T}}$ succeed. In other words, the solution
$(\tilde{L},\tilde{R})$ found by ReShape is in the same homology class as the
minimum weight operator with syndrome $S$:

$\displaystyle[L_{\min},\,R_{\min}]=[\tilde{L},\,\tilde{R}].$

###### Proof.

This is a proof by contradiction: we suppose that the minimum weight solution
and the solution found by ReShape (Algorithm 1) are not homologically
equivalent and we find as a consequence that the minimum weight solution need
to have high logical row-column weight.

Let $(L,R)$ be the valid solution of (SE) in input to ReShape and
$(\tilde{L},\,\tilde{R})$ be the recovery operator found.

First note that $\sigma(\tilde{L},\tilde{R})=\sigma(L,R)$. In fact, the Split
step only finds the canonical form of $(L,R)$ and therefore does not change
neither the operator $(L,R)$ nor its syndrome. The Decode step, possibly adds
to $(L,R)$ logical $Z$-operators $(L_{z},R_{z})$ such that
$\sigma(L_{z},R_{z})=0$ and therefore, even when it changes the operator, it
preserves its syndrome.

Suppose now that the solution found by ReShape and the minimum weight solution
$(L_{\min},R_{\min})$ of (SE) belong to two different homology classes:

$\displaystyle[\tilde{L},\,\tilde{R}]\neq[L_{\min},\,R_{\min}],$

where:

$\displaystyle\\#\mathrm{row_{log}}(L)<\frac{d_{a}}{2}\quad\text{ and
}\quad\\#\mathrm{col_{log}}(R)<\frac{d_{b}^{T}}{2}.$

Since both $(L_{\min},R_{\min})$ and $(\tilde{L},\tilde{R})$ are valid
solution of (SE), they must differ for an operator with zero $X$-syndrome.
Because $(L_{\min},R_{\min})$ and $(\tilde{L},\tilde{R})$ are not
homologically equivalent, they must differ for a non-trivial $Z$-operator in
the normaliser $\mathcal{N}(\mathcal{S})$ of the stabiliser group. As such,
they must differ for an operator which is the sum of a $Z$-stabiliser and a
non-trivial logical operator:

$\displaystyle(L_{\min},R_{\min})=(\tilde{L},\tilde{R})+(G_{L},G_{R})+(L_{z},R_{z}),$
(23)

where $(G_{L},G_{R})$ is a $Z$-stabiliser and $(L_{z},R_{z})$ is a non-trivial
logical $Z$-operator.

Without loss of generality we assume that $(L_{z},R_{z})$ is non-trivial on
the left qubits, meaning that $L_{z}$ has at least one non-zero column in
$\ker\delta_{A}$. The proof is substantially the same in case it is non-
trivial on the right qubits.

First, write the left operators $L_{\min}$ and $\tilde{L}$ in their canonical
form with respect to the same unit-vector basis used to write the logical
operators in $\mathcal{L}_{z}$ (see Eq. (13)):

$\displaystyle L_{\min}$ $\displaystyle=M_{\min}+O_{\min},$
$\displaystyle\tilde{L}$ $\displaystyle=\tilde{M}+\tilde{O}.$

Note that, by construction, the left operator $L_{z}+G_{L}$ is already in its
canonical form, where $L_{z}$ is its logical part and $G_{L}$ is its free
part. By Eq. (14), the sum is direct and therefore the equality given by Eq.
(23) must hold component-wise for the free part and the logical part:

$\displaystyle M_{\min}$ $\displaystyle=\tilde{M}+G_{L}$ $\displaystyle
O_{\min}$ $\displaystyle=\tilde{O}+L_{z}.$ (24)

Let now focus on the logical part equality expressed by Eq. (24) and let
$L_{z}^{j}$ be a non-zero column of $L_{z}$ in $\ker\delta_{A}$. Then:

$\displaystyle O_{\min}^{j}=\tilde{O}^{j}+L_{z}^{j},\quad
L_{z}^{j}\in\ker{\delta_{A}}.$ (25)

Eq. (9) for the classical decoder $\mathscr{D}_{\delta_{A}}$, entails:

$\displaystyle|\tilde{O}^{j}|=\min_{k\in\ker\delta_{A}}|v+k|$

for some input vector $v$ defined by $L$. In particular, no vector
$k^{\prime}\in\ker\delta_{A}$ can overlap with $\tilde{O}^{j}$ in more than
$d_{A}/2$ positions, otherwise we would have $|v+k^{\prime}|<|\tilde{O}^{j}|$,
against the assumption that $|\tilde{O}^{j}|$ is minimum. Thanks to this
observation and considering the Hamming weight of the terms in Eq. (25), we
obtain:

$\displaystyle\lvert O_{\min}^{j}\rvert$
$\displaystyle=\lvert\tilde{O}^{j}+L_{z}^{j}\rvert$
$\displaystyle=|\tilde{O}^{j}|+|L_{z}^{j}|-2|\tilde{O}^{j}\wedge L_{z}^{j}|$
$\displaystyle\geq\lvert L_{z}^{j}\rvert-\lvert\tilde{O}^{j}\wedge
L_{z}^{j}\rvert$ $\displaystyle\geq d_{a}-\frac{d_{a}}{2}=\frac{d_{a}}{2},$
$\displaystyle\text{by Eq.~{}\eqref{eq:colum_logical_part}}.$

Because the weight of any of the columns of a matrix is a lower bound on the
number of its non-zero rows, we have:

$\displaystyle\\#\mathrm{row}(O_{\min})\geq\frac{d_{a}}{2}.$

By definition of canonical form, this is equivalent to:

$\displaystyle\\#\mathrm{row_{log}}(L_{\mathrm{min}})\geq\frac{d_{a}}{2},$

against the assumption.

We stress that the number $\\#\mathrm{row}(O_{\min})$ of rows of $L_{\min}$
which do not belong to $\operatorname{\mathrm{Im}}\delta_{B}^{T}$, does not
depend on the particular splitting chosen for the canonical form. In fact, as
stated in Proposition 3, the logical row weight of the left part of a
$Z$-operator is an homology invariant. An argument similar to the one just
outlined for the left part of $(L_{\min},R_{\min})$ holds for its right part
and yields:

$\displaystyle\\#\mathrm{col_{log}}(R_{\min})\geq d_{b}^{T}/2,$

again contradicting the assumption. In conclusion, we have reached a
contradiction and therefore it must be:

$\displaystyle[L_{\min},R_{\min}]=[\tilde{L},\tilde{R}].$

∎