Spatial overhead reduction for 2D hypergraph product codes

This paper proposes a method to reduce the physical qubit overhead of 2D hypergraph product codes while preserving their code dimension, logical basis, and minimum distance, demonstrating through simulations and examples that these reduced codes maintain fault-tolerant performance and compatibility with logical computation gadgets.

The Gist

The Big Picture: Building a Better Quantum Safe

Imagine you are trying to build a super-secure digital safe to protect a single secret (a "logical qubit"). To make this safe unbreakable, you don't just lock the door; you wrap the secret in a massive, redundant web of checks and balances. This is what Quantum Error Correction does.

The most famous design for this safe is called the Surface Code. It's like a grid of tiles. To protect one secret, you need a huge number of physical tiles (physical qubits). The problem? It's incredibly expensive. To get a high level of security, you might need 1,000 physical tiles just to store one secret.

The authors of this paper are working with a different, more complex design called Hypergraph Product (HGP) codes. Think of HGP codes as a 3D web or a complex tapestry woven from two simpler patterns. These webs are very efficient in theory, but in practice, they often require too many physical tiles to be built with current technology.

The Goal: The authors wanted to shrink the size of these HGP webs (reduce the "spatial overhead") without breaking the secret inside or making the safe easier to crack.

The Problem: The "Check-Type" Qubits

In an HGP code, the physical tiles are divided into two groups:

1. Bit-type qubits: These hold the actual information (the "data").
2. Check-type qubits: These are like the "glue" or "scaffolding." They don't hold data; they exist solely to ensure the data bits agree with each other and to make sure the math works out (specifically, to keep the quantum rules of "commutation" satisfied).

The authors realized that while we need the scaffolding to build the code, we might be able to remove some of it after the code is built, provided we rearrange the remaining pieces carefully.

The Solution: The "Color-Coded" Cleanup

The authors developed a procedure to remove these extra "check-type" qubits. Here is how they did it, using a simple analogy:

The Analogy: The Neighborhood Watch
Imagine a neighborhood where every house (a qubit) has a security camera. Some cameras are on the houses (data), and some are on streetlights (check-type qubits). The streetlight cameras exist only to make sure the house cameras are talking to each other correctly.

The authors asked: "Can we remove the streetlight cameras if we just tell the house cameras to talk to each other directly?"

The Catch: If you just rip out a streetlight, the houses it was watching might lose contact with each other, and the security system breaks.

The Method: The Color-Code Strategy
To solve this, the authors used a "color-coding" system based on the neighborhood's layout:

1. Grouping: They looked at the streetlights and grouped them by color. The rule was: "No two streetlights of the same color can be watching the same house."
2. Merging: Because they don't overlap, they can safely combine the instructions from all the red streetlights into one big "Red Command." They do the same for the blue, green, etc.
3. Removal: Once the commands are merged, the individual streetlights (the check-type qubits) are no longer needed. They are removed.
4. Result: The neighborhood is smaller (fewer physical qubits), but the houses still have full security coverage because the "Red Command" now handles the job of three red streetlights.

What They Proved (The Guarantees)

The authors didn't just guess this would work; they proved mathematically that the safe remains just as secure. Here are their main claims:

• The Secret is Safe (Distance Preservation): The "distance" of a code is a measure of how many errors it can fix. They proved that even after removing the check-type qubits, the code can fix the exact same number of errors as before. The safe is just as unbreakable.
• The Secret is Still the Same (Logical Basis): The way the secret is encoded didn't change. It's like rearranging the furniture in a room; the room is smaller, but the bed is still in the same spot relative to the walls.
• No New Weaknesses (Syndrome Extraction): In quantum computing, you have to constantly check for errors (syndrome extraction). The authors showed that by carefully ordering when you check things (like a specific schedule of who talks to whom), you don't accidentally create new ways for errors to spread.
• It Works with Other Tools: They showed that this smaller code still works with other advanced tools used in quantum computing, like special gates that perform calculations.

Real-World Examples

The paper provides concrete examples of this shrinking process:

• They took a code that required 610 physical qubits and shrank it to 441 qubits, while keeping the security level exactly the same.
• They took another code requiring 1,225 qubits and shrank it to 931 qubits.

The Trade-off

Is there a downside? Yes, but the authors argue it's worth it.

• Heavier Checks: Because they merged several small checks into one big check, the "weight" of the checks increased. It's like the neighborhood watch now has to talk to more houses at once.
• The Result: This makes the code slightly more sensitive to noise in the short term. However, the authors ran simulations showing that for the same amount of hardware, you can now build a larger, more secure code. At very low error rates (which is the goal of future quantum computers), this smaller, denser code actually performs better than the old, bulky one.

Summary

The authors found a way to trim the fat from complex quantum error-correcting codes. By identifying and removing the "scaffolding" qubits that aren't strictly necessary for the final structure, and by cleverly merging the remaining instructions, they created smaller, more efficient quantum codes that are just as secure as the original, larger versions. This brings us one step closer to building practical quantum computers that don't require millions of physical parts to store a single piece of data.

Technical Summary

Technical Summary: Spatial Overhead Reduction for 2D Hypergraph Product Codes

Problem Statement
Quantum error correction (QEC) is essential for fault-tolerant quantum computation, yet practical implementations face significant spatial overhead challenges. While the surface code is a leading candidate due to its high fault-tolerance threshold and planar connectivity, it requires a physical qubit overhead scaling as $O(d^2)$ per logical qubit, where $d$ is the code distance. Although quantum low-density parity-check (qLDPC) codes, such as Hypergraph Product (HGP) codes, offer asymptotically constant overhead, their practical implementation often requires large block sizes (exceeding 1,000 qubits) to outperform the surface code. Furthermore, HGP codes constructed from classical inputs typically contain "check-type" qubits that do not host logical information but are necessary for stabilizer commutation. The paper investigates whether the number of physical qubits in generic HGP codes can be reduced by removing these check-type qubits while preserving the code's dimension, minimum distance, and compatibility with existing fault-tolerant gadgets.

Methodology
The authors propose a qubit reduction procedure that systematically removes check-type qubits from HGP codes. The core of the method involves:

1. Coloring and Partitioning: The check-type qubits are partitioned into groups based on the coloring of the check-adjacency graphs of the classical input codes. Two checks share a color if they do not share any bits in common. This ensures that checks within a color group are disjoint.
2. Stabilizer Combination: Within selected color groups, the authors combine X-type (or Z-type) stabilizers linearly to eliminate the support on specific check-type qubits. This is achieved by constructing linear transformations (matrices $W_X$ and $W_Z$) that sum stabilizers, effectively "cleaning" the check-type qubits of their support.
3. Optimization: The selection of which color groups to combine is formulated as a maximum-weight matching problem on a bipartite graph, optimizing the number of removed qubits while adhering to constraints that prevent combining too many checks (to maintain LDPC properties) and ensuring disjoint support.
4. Syndrome Extraction Scheduling: To address the increased weight of combined stabilizers, the authors introduce a specific CNOT scheduling order (split syndrome extraction) for syndrome measurement. This "zigzag" scheduling ensures that hook errors remain confined to a single row or column, preserving the effective distance of the code.

Key Contributions

• Qubit Reduction Procedure: A general algorithm to reduce the physical qubit count of HGP codes by removing check-type qubits. The procedure guarantees that the code dimension ($k$) and minimum distances ($d_X, d_Z$) are preserved.
• LDPC Preservation: The authors prove that the reduced code remains LDPC, with qubit and check weights increasing by at most a factor of two ($\tilde{w}_q \le 2w_q$ and $\tilde{w}_c \le 2(w_c - 1)$).
• Preservation of Logical Structure: The canonical logical Pauli basis of the original HGP code remains valid for the reduced code. This is crucial for porting existing fault-tolerant gadgets.
• Compatibility with Gadgets: The paper demonstrates compatibility with several critical fault-tolerant mechanisms:
  • Distance-Preserving Syndrome Extraction: A specific scheduling algorithm (Algorithm 2) ensures the effective distance equals the code distance despite increased stabilizer weights.
  • Fold-Transversal Gates: For symmetric HGP codes, the reduction schedule can be constrained to preserve the diagonal reflection symmetry required for transversal Hadamard and phase gates.
  • Automorphisms and Homomorphisms: The reduction is compatible with code automorphisms and homomorphic gadgets (such as grid-Pauli-product measurements), allowing for logical operations and code switching on reduced codes.
• Special Cases: The procedure generalizes the transformation from unrotated to rotated surface codes and encompasses the Quantum Tanner transformation for codes built from bipartite graphs.

Results

• Parameter Improvements: The authors provide concrete examples of parameter improvements. For instance, an HGP code with parameters $[[610, 64, 6]]$ is reduced to $[[441, 64, 6]]$, and a $[[1225, 49, 11]]$ code is reduced to $[[931, 49, 11]]$.
• Numerical Simulations: Circuit-level depolarizing noise simulations were performed on reduced HGP codes (using QC-LDPC and Heawood cycle code inputs).
  • When using the proposed distance-preserving syndrome extraction schedule, the reduced codes exhibit a logical error rate (LER) slope similar to the unreduced versions, confirming the preservation of effective distance.
  • The reduced codes show a constant offset in performance (higher LER at the same physical error rate) due to increased stabilizer weights, but the authors argue that for a fixed number of physical qubits, the reduced code can achieve a higher distance, potentially offering an advantage at lower error rates.
  • Random scheduling on reduced codes resulted in a shallower LER slope, highlighting the necessity of the specific scheduling strategy.

Significance
The paper claims that this reduction procedure offers a practical pathway to lowering the spatial overhead of HGP codes without sacrificing their fundamental error-correcting capabilities or their compatibility with advanced fault-tolerant gadgets. By reducing the number of physical qubits, the authors argue that HGP codes can become viable for near-term hardware with fewer than 1,000 qubits, bridging the gap between the asymptotic promises of qLDPC codes and practical implementation constraints. The work extends the utility of HGP codes by showing that their structural advantages (canonical logical bases, transversal gates) are robust against the specific structural modifications required for qubit reduction.