A graph-based approach to entanglement entropy of quantum error correcting codes

This contribution presents a graph-based method for the efficient calculation and interpretation of the entanglement entropy of Calderbank-Shor-Steane quantum codes, which reveals the origins of local and long-range entanglement and demonstrates its utility through applications to toric and low-density parity-check codes.

The Gist

Imagine you have a huge, complex puzzle made of quantum pieces. In the world of quantum computing, these puzzles are called quantum error-correcting codes. Their task is to hide important information (such as a secret message) within a group of particles so that the message can still be recovered even if some particles are damaged by noise.

The secret to making these puzzles work is entanglement. Think of entanglement as a super-strong, invisible rubber band connecting the pieces. If the pieces are too far apart or not sufficiently connected, the puzzle falls apart. However, if they are bound together in a specific way, the puzzle becomes robust.

This work introduces a new, clever method to precisely measure how much these quantum puzzles are "entangled." Instead of using heavy, complicated mathematics that looks like a foreign language, the authors use graph theory—essentially the mathematics of drawing points and lines.

Here is a simple breakdown of their method and their results:

1. The "Point-and-Line" Map

The authors realized that a quantum code can be transformed into a simple map:

• Points (Nodes): These represent the connection points or "checkpoints" where the rules of the puzzle are applied.
• Lines (Edges): These represent the actual quantum bits (qubits) that carry the information.

On this map, "entanglement" (how strongly the pieces are connected) becomes visible by looking for loops. Imagine walking along the lines of your map. If you start at a point, wander along the lines, and can return to your starting point without retracing your steps, you have found a loop.

2. The "Tree" Analogy

To measure the entanglement between two parts of the puzzle (let's call them Part A and Part B), the authors use a concept called a Spanning Tree.

• Imagine a forest of trees. A "spanning tree" is a way to connect all points in a forest with the fewest possible lines, without loops.
• The authors take Part A and turn it into a tree (by removing lines to break loops). They do the same for Part B.
• Then, they glue these two trees together.

The magic number: When you glue the two trees together, new loops are created. The number of these new loops corresponds exactly to the entanglement entropy.

• More loops = More entanglement.
• Fewer loops = Less entanglement.

It is like counting how many new bridges you need to build to connect two islands. The number of bridges tells you how strongly the islands are linked.

3. What They Discovered

The authors tested this "Point-and-Line" method on three different types of quantum puzzles:

• The Toric Code (The Local Puzzle): This is like a puzzle spread out on a flat sheet of paper (a 2D surface). The connections are very local; one part talks only to its immediate neighbors.

  • Result: Entanglement grows slowly, like the area of a circle. If you double the size of the puzzle piece, the entanglement does not double; it grows much more slowly. This is called the "area law." This means the information is stored locally.

• The qLDPC Codes (The Long-Distance Puzzle): These are newer, more complex puzzles (such as Bivariate Bicycle Codes and Quasi-Cyclic Codes). They are not limited to a flat surface; parts can be connected to distant parts, like a network of long-distance calls.

  • Result: Entanglement grows much faster. It scales almost with the volume of the puzzle. This means the information is distributed (delocalized) across the entire system. The "rubber bands" stretch across the entire puzzle, not just between neighbors.

4. Why This Matters

The work provides not just a new formula; it offers a new lens through which to view these systems.

• Simplicity: Instead of running massive computer simulations to calculate how "entangled" a system is, you can now simply draw the graph, count the loops, and get the answer.
• Understanding: It explains why some codes are better at protecting information. The "Long-Distance" puzzles (qLDPC) have high entanglement, suggesting they could be very powerful for error correction, but they are also harder to understand because the connections are so widely distributed.

Summary

The authors built a bridge between the abstract world of quantum physics and the simple world of map-drawing. They showed that entanglement is simply a counting of loops in a certain type of map. By using this map, they proved that newer, more complex quantum codes have a much more "widely distributed" type of connection than older, simpler ones, revealing a fundamental difference in how they store and protect information.

Technical Summary

Problem Statement
Entanglement is a fundamental resource in Quantum Error Correction Codes (QECCs), enabling the non-local encoding of logical information to protect against local errors. However, calculating entanglement entropy for complex quantum codes, particularly beyond simple topological models like the Toric Code, remains challenging. Existing methods, such as group-theoretic approaches, have been applied to stabilizer codes, yet there is a need for a more intuitive framework that elucidates the origins of both local (area law) and long-range entanglement. Furthermore, efficient computational procedures are required to evaluate entanglement entropy for modern, non-geometrically local codes, such as Quantum Low-Density Parity-Check codes (qLDPC).

Methodology
The authors develop a graph-based method to explicitly calculate the reduced density matrix and von Neumann entropy for Calderbank-Shor-Steane (CSS) quantum codes. The approach translates the algebraic structure of stabilizer codes into graph-theoretic concepts:

1. Graph Representation: The method utilizes the parity-check matrix ($H_Z$) of a CSS code. Stabilizer generators are treated as cycles in a graph, where qubits correspond to edges.
2. Spanning Trees and Common Cycles: For a bipartition of the system into subsystems $A$ and $B$, the authors construct spanning trees ($T_A$ and $T_B$) for each subsystem by removing edges to eliminate internal cycles. The union of these spanning trees ($T_A \cup T_B$) forms a graph containing "common cycles."
3. Entropy Calculation: It is shown that the von Neumann entropy $S_A$ equals the number of independent common cycles formed by the union of the spanning trees. This is mathematically equivalent to the cyclomatic number of the common cycle space.
4. Matrix Rank Formulation: The authors derive an analytical expression for entanglement entropy based on the ranks of submatrices of the parity-check matrix. Specifically, $S_A = \text{rank}(W_A) = \text{rank}(W_B)$, where $W_A$ and $W_B$ are submatrices describing the stabilizers shared between the subsystems. This leads to the efficient formula $S_A = r_A + r_B - r_H$, where $r_A$, $r_B$, and $r_H$ are the ranks of the parity-check submatrices for subsystem $A$, subsystem $B$, and the total system, respectively.
5. Generalization: For codes where the column weight of the parity-check matrix exceeds two (preventing a direct simple graph representation), the authors introduce a "qubit duplication" technique. This modifies the parity matrix so that it represents a simple planar graph without altering the entanglement entropy, thereby making the graph-theoretic formula applicable to general CSS codes.

Main Results
The method was applied to three distinct code families: the two-dimensional Toric Code, bivariate bicycle (BB) codes, and quasi-cyclic (QC) codes.

• Toric Codes: The method successfully reproduces known results and demonstrates that entanglement entropy for connected subsystems follows an area law ($S_A \propto \sqrt{n_A}$). It is shown that entropy depends on the global connectivity between subsystems and the number of boundary cycles.
• qLDPC Codes (BB and QC): The study reveals that BB and QC codes exhibit significantly different scaling behavior compared to Toric codes. Their entanglement entropy scales as $n_A^\gamma$ with $\gamma \approx 0.81$ (BB) and $\gamma \approx 0.95$ (QC), indicating a faster growth rate and the presence of stronger delocalized, long-range entanglement.
• Entropy Discrepancy: By analyzing the "entropy discrepancy" ($I_A = n_A - \bar{S}_A$) for randomly selected subsystems, the authors observe a sharp transition in the rate of change ($dI_A/dn_A$) for qLDPC codes as subsystem size increases. This transition becomes sharper with larger code sizes. In contrast, Toric codes exhibit a smooth transition independent of code size. This difference is attributed to the high stabilizer weights and non-local interactions in qLDPC codes, which enhance connectivity between subsystems in a manner fundamentally distinct from the strictly local interactions of Toric codes.

Significance and Claims
The work claims to offer a new perspective on understanding entanglement structure in quantum many-body systems by providing a direct graph-theoretic interpretation of entanglement entropy. The main contributions are:

• Interpretability: The method clarifies the origins of local and long-range entanglement by directly linking entropy to the topology of common cycles formed by subsystem spanning trees.
• Efficiency: The derivation of entropy as a function of matrix rank ($S_A = r_A + r_B - r_H$) provides an efficient calculation procedure applicable to all CSS codes, including complex qLDPC codes where previous methods might be less manageable.
• Universality: The approach is independent of the specific geometry and topology of the quantum system, enabling generalization to systems with higher spins, irregular structures, and broader classes of stabilizer codes.

The authors conclude that these distinct entanglement properties in qLDPC codes may be linked to their capacity for protecting information and their decoding performance, warranting further investigation; however, they propose no specific experimental implementations or applications beyond this theoretical characterization.