Demystifying the Balanced Product Code: A Review

Heather Leitch, Alastair Kay · 2025

Read Demystifying the Balanced Product Code: A Review by Heather Leitch, Alastair Kay (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13679.txt.

Introduction

Heather Leitch and Alastair Kay explain a landmark family of quantum error-correcting codes in plain terms. Balanced product codes were the breakthrough that led to good quantum codes, ones that store much information while keeping errors at bay. The original papers are dense, though, and the construction's logic can hide behind abstraction.

This review retells the story with the technical load stripped down wherever possible. It assumes readers know the standard stabilizer language of error correction, then shows how parity-check matrices for these high-density codes are built. The authors aim the piece at researchers who want to actually use the construction, not just admire it. Their hope is to widen the circle of people who can design the next generation of quantum codes.

Catalog record

CREATORHeather Leitch, Alastair Kay
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-13679

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Demystifying the Balanced Product Code: A Review Heather Leitch, Alastair Kay Abstract The discovery of the family of balanced product codes [ 1 ] was pivotal in the subsequent development of ‘good’ low density quantum error correcting codes that have optimal scaling of the key parameters of distance and storage density. We review this family, giving a completely different presentation to the original, minimising the abstraction and technicalities wherever possible. The target audience is anyone familiar with the stabilizer formalism for error correction wanting to understand how parity-check matrices can be constructed for high storage density quantum codes. Quantum computing sits at an inspiring threshold. There are exciting algorithms that we want to implement, such as Shor’s algorithm [ 2 ] , Grover’s search [ 3 ] , linear inversion [ 4 ] and Hamiltonian simulation/quantum chemistry [ 5 ] , which will out-perform the best-known subroutines on a classical computer. We can produce small-scale devices that promise quantum advantage [ 6 , 7 , 8 ] , and error correction is reaching the break-even point where it should be scalable [ 9 ] . This scaling up of error correction is the most significant barrier to achieving a universal fault-tolerant quantum computer that will implement all these amazing algorithms. Quantum error correction, however, is not only an engineering problem. It is a challenge to theorists to create high performance codes. An [[n,k,d]] code is specified by 3 key properties: n , the number of physical qubits that encode the k logical qubits, and the distance d , which indicates the number of errors that can be tolerated. Small-scale codes work remarkably well. For example, the 5-qubit code [ 10 ] utilises the state space so well, that it is said to be perfect. Steane’s 7-qubit code [ 11 ] similarly is perfect within the restrictions of CSS codes, while having a near-optimal set of transversal logical gates. However, just as with classical error correction, where scaling up the repetition code to large systems fails to pack data as densely as we otherwise might, encoding many logical qubits as densely as possible is far from trivial. We can assess the storage density by evaluating kd^{2} . Since neither can be larger than \order{n} , kd^{2}\sim n^{3} at best and any code saturating this is said to be ‘good’. Contrast this with the performance of many copies of the Steane code: an [[n,n/7,3]] code with kd^{2}\sim n ; far from good, but optimal performance for k is easy to achieve. The most commonly considered methods for scaling an error correcting code to large systems are concatenated codes [ 12 ] and surface codes, such as the Toric code [ 13 ] . The [[2d^{2},2,d]] Toric code achieves large distance, which gives us the ability to adapt to a broad range of scenarios, but only has kd^{2}\sim n . Meanwhile, a concatenated Steane code with D levels of concatenation, is a single code [[7^{D},1,3^{D}]] . Again, we can control the distance, but only achieve kd^{2}\sim n^{2\log_{7}3}\approx n^{1.13} . It should be noted that there are more sophisticated ways to perform concatenation which achieve much better performance [ 14 ] . One major advantage of the Toric code is its formulation – the syndrome extraction interrogates small clusters of qubits that are neighbours on some two-dimensional lattice, complying with the constraints of many physical implementations of quantum computers. Indeed, under these locality restrictions, the code is asymptotically optimal [ 15 ] ; it is impossible for a code that is local in two dimensions to exceed kd^{2}\sim n . Our search for well-performing codes must therefore violate the locality restriction. There are certainly experimental scenarios that can take advantage of this lifting of restrictions [ 16 ] . In studying [[n,k,d]] codes without the locality restriction, we still choose to retain the property that the check operators should only act on a small number of qubits. We say the code is “low density”, and hence the codes are known as low density parity check codes (LDPC). Classical versions of these codes are now extensively used in telecommunications. In the quantum regime, the best-known codes were, for a long time, the hypergraph product codes [ 17 ] , limited to the performance of kd^{2}\sim n^{2}. (1) Clearly, an exciting improvement, but still a large step away from being good codes, with the limitation being achieving large enough d . Then, in about 2022, a flurry of results [ 18 , 19 , 20 ] first showed that this performance could be exceeded, and ultimately resulted in good codes being produced. The tipping point was an initial example due to Hastings, Haah & O’Donnell [ 21 ] that showed Eq. 1 could be violated, and its generalisation by Breuckmann & Eberhardt [ 1 ] , achieving the same kd^{2}\sim n^{2} but crucially realising it with d\sim n^{3/5} , where previous studies were limited to d\sim\sqrt{n} . Breuckmann & Eberhardt [ 1 ] take the well-characterised LPS family of expander graphs [ 22 ] and formulate a ‘balanced product’ with a repetition code of appropriate size. However, this product was specified in an intensely mathematical way which is intimidating to mere mortals, such as ourselves. In this paper, we express the constructions in the language of parity check matrices and provide insight into the key results, making the conversion from graph to code particularly straightforward, Eq. 3 . Not all proofs are complete – we occasionally favour pedagogy, knowing that the rigorous results have appeared elsewhere [ 1 ] . I Quantum Error Correcting Codes In this section, we will briefly review some of the basics of error correction [ 23 ] . It is assumed that the interested reader will already be familiar with this, and our primary focus is to establish notation. In classical error correction, we can specify an error correcting code by its parity-check matrix H\in\{0,1\}^{(n-k)\times n} . A binary string x\in\{0,1\}^{n} is a codeword if Hx=0 , with the idea being that if any pair of codewords differ in at least d places, evaluating non-trivial Hy allows us to detect the presence of some errors and, under the assumption that fewer than d/2 errors have occurred, to return y=e\oplus x to the original x by determining e=\underset{v:H(y\oplus v)=0}{\text{argmin}}|v| . The code is said to be low-density if every row and every column of H has a weight bounded by some constant, s . In a quantum setting, we can use the same classical code to protect against bit-flip errors X_{i} . We start with a codeword as a quantum state, \ket{x} . It might acquire some bit-flip errors X_{e} such that the state becomes \ket{y}=\ket{e\oplus x}=X_{e}\ket{x} . Here, we use the notation X_{e}=\bigotimes_{i=1}^{n}X^{e_{i}}. to express the idea that Pauli X operations (bit-flips) have been applied to sites i where e_{i}=1 . For each parity-check of the code, r\in H , we associate a measurement Z_{r}=\bigotimes_{i=1}^{n}Z^{r_{i}}. This gives a measurement outcome \bra{y}Z_{r}\ket{y}=(-1)^{r\cdot y}=(-1)^{r\cdot e} , exactly the same as the result of computing the parity check in the classical case. In a quantum code, we must protect both against X errors and Z errors. CSS codes [ 24 , 11 ] ,

Read the complete text