Cycle Basis Algorithms for Reducing Maximum Edge Participation

A cycle basis of an undirected graph $G=(V,E)$ is a minimal set of cycles such that every cycle in $G$ can be expressed as the symmetric difference (i.e., edgewise XOR) of some subset of the basis cycles (i.e., cycles in the basis). The cycles are not necessarily simple and are just viewed as Eulerian subgraphs, i.e., subgraphs in which every vertex has even degree. For any connected graph with $n$ vertices and $m$ edges, the dimension of the cycle space – and hence the number of basis cycles – is exactly $m-n+1$ [11].

One intuitive way to see this is via a spanning tree of $G$: such a tree has exactly $n-1$ edges and no cycles. Each of the remaining $m-(n-1)=m-n+1$ non-tree edges, when added back to the spanning tree, closes a unique simple cycle. These cycles, formed by combining each non-tree edge with the unique tree path connecting its endpoints, constitute a valid cycle basis. A cycle basis constructed this way is called a fundamental cycle basis.

Much of the literature on cycle bases focuses on finding a minimum-weight cycle basis in weighted graphs, where the weight of a cycle is the sum of its edge weights, and the weight of the basis is the sum of the weights of all basis cycles [15, 17, 16]. In unweighted graphs, this reduces to minimizing the total length of the basis cycles. In contrast, we consider a different structural property that disregards edge weights: the maximum edge participation of a basis. This measures the maximum number of basis cycles that any edge participates in. Formally, for a cycle basis $B$ of $G=(V,E)$, we define: $\mu (B)={\max }_{e\in E}\left|\{C\in B:e\in C\}\right|.$ The motivation for minimizing the maximum edge participation comes from a well-known construction for quantum fault tolerance and is described further in Section 2.

Due to the fragile nature of quantum systems, quantum error correction (QEC) is an important challenge for building quantum computers capable of practical applications. QEC protects quantum information from environmental noise by redundantly encoding it using a quantum error-correcting code (QECC). In recent years, a particular class of QECCs known as quantum low-density parity-check (QLDPC) codes [10] has attracted significant attention for their potential to reduce the overhead associated with encoding and logical operations. A parity check is a measurement which measures whether an error has occurred. Low-density parity checks, which only operate on a constant number of qubits, are easier to implement in a fault-tolerant way. Recent works [24, 5, 25, 19] have proposed constructions of good QLDPC codes – those with constant rate and linear distance.

However, a major challenge remains: how to perform logical gates fault-tolerantly on information encoded using these codes. A technique known as lattice surgery was originally developed for implementing logical gates on surface codes [14], and has since been generalized to broader classes of QLDPC codes [6, 7, 32, 13]. The core goal of lattice surgery is to enable fault-tolerant measurements of logical operators, which in turn allows the implementation of an almost universal gate set – the Clifford group. This set, when supplemented by magic state distillation [4], yields a universal gate set for quantum computation [20].

Every QLDPC code has a Tanner graph representation, where physical qubits and checks are nodes, and edges indicate which checks act on which qubits. We define the weight of a check to be the number of physical qubits it touches, and the degree of a qubit to be the number of checks connected to it.

Without loss of generality, we focus on CSS codes, which involve only two types of checks: $Z$-checks and $X$-checks. (In general, a check can involve both $X$ and $Z$ operators.) These two types of checks correspond to the two common types of errors in quantum systems: $X$-errors (bit-flip errors) and $Z$-errors (phase-flip errors). For CSS codes, the Tanner graph is a tripartite graph – one part for qubits, one for $X$-checks, and one for $Z$-checks – analogous to the bipartite structure in classical LDPC codes.

Correspondingly, there are two types of logical measurements: Pauli $X$ measurements and Pauli $Z$ measurements. In this discussion, we focus on Pauli $X$ measurements; the procedure for Pauli $Z$ measurements is analogous. A Pauli $X$ measurement can be viewed as a measurement on a subset of physical qubits. However, such measurements often have high weight, meaning they involve many physical qubits. Performing high-weight measurements directly is challenging in a fault-tolerant manner.

The goal of lattice surgery is to decompose such high-weight measurements into a sequence of lower-weight, fault-tolerant measurements. The basic idea is to introduce an ancillary system (which can also be thought of as another QLDPC code) that is coupled to the original code on which we wish to perform the measurement. By measuring all the $X$-checks in the ancilla system, one can effectively obtain the outcome of the desired high-weight Pauli $X$ measurement.

There have been several approaches for constructing the ancilla system [6, 7, 32]. These constructions share a common starting point: they begin with the Tanner graph and focus on the induced subgraph of the support (i.e., the set of qubits involved in the Pauli $X$ measurement.) The cycle basis problem comes out of the Williamson et. al. construction. Although the details of the construction are beyond what we can cover here, the result of the construction is a new graph based on the induced subgraph of the Tanner graph in which edges represent physical qubits, vertices correspond to $X$-checks, and $Z$-checks are defined via a cycle basis $B$ of the graph $G$, which together define the ancilla system.

Each basis cycle corresponds to a $Z$-check in the ancilla system, and its length determines the weight of that check. Long cycles lead to high-weight checks, which can violate the LDPC property of the original code. However, there is a straightforward method to resolve this: cellulation – the process of subdividing long cycles into multiple short cycles by adding auxiliary edges, thereby restoring LDPC properties.

In contrast, maximum edge participation corresponds to the maximum qubit degree in the ancilla system – that is, the number of $Z$-checks attached to a given qubit. High qubit degrees can violate the LDPC property of the code, and unlike the case of high-weight checks, there is no comparably low-cost fix such as cellulation. The overhead of the construction is then dominated by the cost of reducing the maximum edge participation.

In this section, we present five different variants of the original Freedman–Hastings algorithm by varying the three key design choices listed in Table 1. We will refer to the Freedman–Hastings algorithm as Version $0$.

The only difference between Version 1 and Version 0 is the edge removal strategy: while Version 0 removes a random edge from the selected cycle, Version 1 removes the edge with the highest load (breaking ties randomly). This strategy helps reduce long-term edge congestion by preferentially eliminating the most heavily used edges early in the recursion.

The difference between Version 2 and Version 1 lies in the BFS root selection. While Version 1 selects the BFS root randomly, Version 2 always starts from the vertex with the highest load. Although this factor may seem less impactful than edge removal, empirical results show that prioritizing the max-load vertex leads to better performance. Intuitively, a high-load vertex is likely incident to multiple heavily loaded edges. By starting BFS from such a vertex, the resulting cycle has a higher chance of containing one of these high-load edges, which can then be removed using the same greedy strategy.

Version 3 improves upon Version 2 by refining both the cross edge selection and edge removal strategies. Instead of selecting the first encountered cross edge during BFS, we restrict the choice to those that yield a cycle containing the BFS root. This ensures that the starting vertex – which is chosen based on maximum load – remains in the cycle, increasing the chance of targeting heavily used edges.

Additionally, when multiple edges in the cycle have the same maximum load, we prioritize removing an edge that is incident to the BFS root. This tie-breaking rule is particularly effective in the later stages of the algorithm when the graph becomes sparse. For instance, in a 3-regular graph, removing one edge via a short cycle (as in Case 3) typically creates two degree-two vertices – the endpoints of the removed edge – which will each trigger additional reductions via Case 2; see Figure 2 for an illustrative example. If the BFS root lies on the cycle and has high load, this refinement increases the likelihood of further removing overloaded edges connected to it, thus improving overall balance in the cycle basis.

Version 4 introduces a probabilistic edge removal strategy. Instead of deterministically removing the highest-load edge, we remove edge $i$ from the selected cycle $C$ with probability $2^{L(i)}/{\sum }_{j\in C}{2}^{L(j)},$ where $L(i)$ denotes the load of edge $i$. This softmax-style weighting introduces randomness into the algorithm, which may help avoid worst-case scenarios that can trap greedy variants. However, empirical results suggest that Version 4 does not outperform Version 3 on average.

Finally, Version 5 is a significantly more expensive algorithm. It selects the cycle of minimum length and then removes the maximum-load edge from that cycle. To identify the shortest cycle, the algorithm performs a BFS from each vertex as the root, searches for a cycle containing that root, and then takes the shortest cycle among all roots. Owing to its high computational cost, we evaluate Version 5 only in the next section, where the graphs – arising from small quantum codes – are relatively small.

We evaluate the variants (Versions 0–4) on random regular graphs, which are known to be asymptotically close to Ramanujan graphs – optimal spectral expanders – according to the result of Friedman [9]. This motivates our choice, as most random d-regular graphs are constant-degree expanders, resembling the structure of graphs that arise in real quantum LDPC codes.

To generate these graphs, we use Python’s NetworkX package, which internally implements the configuration model of Steger and Wormald [30]. Specifically, we test our heuristics on random 3-regular and 8-regular graphs across a range of sizes. We chose these graphs to roughly mimic the structure of near-term quantum codes, which typically do not exhibit very high connectivity, check weight, or qubit degree. For each graph size, we generate a number of random instances (as detailed in Table 2) and apply all five algorithmic variants.

In this section, we evaluate our algorithms on graphs arising from practical quantum codes. Here we consider two different families of codes: quantum radial codes [29] and quantum Tanner Codes [19, 26].

Quantum radial codes were introduced by Scruby et al. [29], which are based on the lifted product construction [24] applied to certain quasi-cyclic classical codes. The lifted product is one of the first constructions known to yield good quantum LDPC codes, and it is also effective for generating near-term deployable codes. Quantum radial codes exhibit promising features for fault-tolerant quantum computing. In particular, they offer comparable error suppression to surface codes while requiring roughly five times fewer physical qubits. Moreover, they have been observed to support single-shot decoding [2], making them strong candidates for near-term implementations.

Quantum Tanner codes were introduced by Leverrier and Zémor [19] as another construction of asymptotically good quantum LDPC codes. Building on this framework, Radebold, Bartlett, and Doherty presented explicit instances of quantum Tanner codes based on dihedral groups and pairs of classical component codes [26]. Numerical simulations show that these explicit codes achieve logical error rates comparable to surface codes of similar distance under both phenomenological and circuit-level noise models, highlighting their potential for fault-tolerant quantum error correction.

We consider a balls-into-bins model as a proxy for the behavior of our algorithms on 3-regular graphs. In this model, each bin corresponds to an edge in the graph, and each selected cycle is a subset of $k$ bins. The load on each edge is represented by placing a ball in each of the selected bins. Then three bins are removed, representing the edges that are removed from the graph. Note that when the graph is exactly $3$-regular, each iteration of Case $3$ (followed by two applications of Case 2A) decreases the total number of edges by three, as illustrated in Figure 2. Indeed, the local transformation removes five existing edges and inserts two new edges, so the net change in the number of edges is $-3$.

The goal of the model is to understand the extent to which we can analyze the asymptotic behavior of our best variant without using detailed graph-theoretic properties. As discussed above, one iteration consisting of Case 3 followed by two applications of Case 2A can potentially remove up to three heavily loaded edges from the graph. In the balls-to-bins model, we model the selection of a cycle as selecting the three most heavily loaded edges/bins, and the rest of the $k-3$ bins are selected at random. Then the three most heavily loaded bins are removed from the system, representing the removal of those edges from the graph. This model is favorable to the algorithm by allowing the algorithm to select and remove the three most heavily loaded bins in the entire system. In a real graph, the three most heavily loaded edges might not even be located on a single short cycle. The selection of the rest of the edges is simplified to be a random set. Intuitively, getting a better analysis for the behavior of our cycle basis algorithms will require a more sophisticated understanding of the distribution of the edges participating in each selected cycle.

There are a few other ways in which our proxy process differs from cycle basis selection in a real graph. The proxy process assumes that the cycle selected will have length exactly $k=2\lceil {\log }_{2}n\rceil$ in each round. The versions which select the cycle arising from the first cross edge encountered may yield shorter cycles, resulting in less load on the edges. To better justify this choice, we provide an analysis of the cycle length produced during a BFS exploration of a random regular graph. In particular, we show that with constant probability, the exploration remains tree-like up to depth $\mathrm{\Theta }(\log n)$, and the first back edge creates a cycle of length $\mathrm{\Omega }(\log n)$. The detailed proof is deferred to Appendix E. Thus, without a more refined model for how the graph evolves over time, we cannot exploit the possibility of shorter selected cycles to obtain sharper bounds on the performance of our heuristics. The proxy process also does not capture vertex removals from Cases $1$ and $2B$. However, our numerical results suggest that these are relatively infrequent events and therefore do not contribute significantly to edge load as shown in Appendix A.

The balls-and-bins process is called Process 1 and is given in Algorithm 1. However, Process 1 remains analytically challenging. To facilitate analysis, we define a further simplification, which still preserves the essential features needed for bounding load growth. In the simplified process, we define an epoch as a sequence of iterations in which the number of buckets $m$ decreases by a factor of $2$. During each iteration within an epoch, we add a ball to each of $k$ randomly chosen bins and decrease $m$, the counter for the number of buckets, by $3$. However, the buckets are not actually removed until the end of an epoch, at which point a new epoch begins. The delayed-removal process is called Process 2 and is given in Algorithm 1.

This delayed-deletion model allows additional load to accumulate before pruning. As a result, more balls are discarded during each epoch compared to Process 1. Therefore, any lower bound established for Process 2 also applies to Process 1, and thus to the original algorithm. In Appendix D, we provide a formal proof that Process 2 lower-bounds Process 1 if we select $(k-3)$ buckets instead of $k$ buckets in Process 2; note that this modification does not affect the asymptotic lower bound for Process 2 discussed below.

In what follows, we prove the following theorem, which provides a lower bound on the maximum load $L_{\max }$ in Process 2. All logarithms are base $2$, unless stated otherwise.

Before proving the theorem, we prove several lemmas. Define $m_j=M/2^j$, $n_j=\frac{2}{3}{m}_j$, and $k_j=2\lceil {\log }_2{n}_j\rceil$. During epoch $j$, we begin with $m_j$ buckets and perform ball tossing for $m_j/6$ rounds. In each round, we toss $k_j$ balls into $k_j$ distinct buckets chosen uniformly at random without replacement. No deletions occur during the rounds.

Consider a particular an epoch j. The probability that a fixed bucket is chosen during a single round in epoch $j$ is $k_j/m_j$. The incremental load placed on any bucket during epoch $j$ is

Fix a constant $c\in (0,0.16)$ and call a bucket bad in epoch $j$ if the incremental load satisfies $X_j\le c{\mu }_j.$ During epoch $j$ let $B_j$ be the number of bad buckets. We state the following two lemmas, whose proofs are provided in Appendix C.

We are now ready to prove Theorem 1. The basic idea is that for the chosen value of $L$ (which is $\mathrm{\Omega }(\log n)$), with high probability the number of buckets that have ever gone bad in $L$ rounds is less than the total number of buckets remaining. Thus, with high probability, there will be a bucket remaining which was never bad in the first $L$ rounds. A bucket with this property received $\mathrm{\Omega }(\log n)$ incremental load in each of the $L$ rounds, resulting in a bucket with total load $\mathrm{\Omega }({\log }^{2}n)$. For a complete proof of Theorem 1 check Appendix C.