2025 Volume 34 Issue 5
Article Contents

Dongyang Feng, Hanyan Cao, Pan Zhang. Planar: A software for exact decoding quantum error correction codes with planar structure[J]. Chinese Physics B, 2025, 34(5): 050311. doi: 10.1088/1674-1056/adcb26
Citation: Dongyang Feng, Hanyan Cao, Pan Zhang. Planar: A software for exact decoding quantum error correction codes with planar structure[J]. Chinese Physics B, 2025, 34(5): 050311. doi: 10.1088/1674-1056/adcb26

Planar: A software for exact decoding quantum error correction codes with planar structure

  • Received Date: 14/03/2025
    Accepted Date: 09/04/2025
    Available Online: 01/05/2025
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(8)

Article Metrics

Article views(1151) PDF downloads(5) Cited by(0)

Access History

Planar: A software for exact decoding quantum error correction codes with planar structure

Abstract: Quantum error correction is essential for realizing fault-tolerant quantum computing, where both the efficiency and accuracy of the decoding algorithms play critical roles. In this work, we introduce the implementation of the Planar algorithm, a software framework designed for fast and exact decoding of quantum codes with a planar structure. The algorithm first converts the optimal decoding of quantum codes into a partition function computation problem of an Ising spin glass model. Then it utilizes the exact Kac–Ward formula to solve it. In this way, Planar offers the exact maximum likelihood decoding in polynomial complexity for quantum codes with a planar structure, including the surface code with independent code-capacity noise and the quantum repetition code with circuit-level noise. Unlike traditional minimum-weight decoders such as minimum-weight perfect matching (MWPM), Planar achieves theoretically optimal performance while maintaining polynomial-time efficiency. In addition, to demonstrate its capabilities, we exemplify the implementation using the rotated surface code, a commonly used quantum error correction code with a planar structure, and show that Planar achieves a threshold of approximately puc ≈ 0.109 under the depolarizing error model, with a time complexity scaling of O(N0.69), where N is the number of spins in the Ising model.

1.   Introduction
  • The realization of fault-tolerant quantum computing (FTQC) marks a pivotal milestone in the advancement of quantum technologies, and significant progress has been achieved in recent years.[1–9] To achieve FTQC, the development of quantum error correction codes (QECCs) with robust properties, as well as fast and accurate decoders, is of paramount importance.[10–15] A quantum code, denoted as [n, k, d], encodes k logical qubits with minimum distance d using n physical qubits. The encoded states are fixed points (i.e., as eigenvectors with eigenvalue 1) by operators generated by m generators, which are known as stabilizers S.[16] Measuring the ancilla qubits corresponding to the stabilizers yields a result of 1 without affecting the encoded states. When a Pauli error O ∈ {I, X, Y, Z}n occurs and anti-commutes with the stabilizers, the stabilizer measurements produce −1, resulting in syndromes γ ∈ {1, −1}m. This tells us that there were errors and we need to identify the error and then correct it to recover the encoded states. Identifying the possible errors given syndrome γ is the task of decoding.

    There are two kinds of decoding approaches, the first one finds the most probable error with

    where P(O|γ) is the conditional probability of finding the error operator O given syndrome γ in the error model. This kind is known as minimum weight decoding (MWD),[17–19] where the weight can be understood as the negative log probability. The most commonly used MWD algorithm is the minimum-weight perfect matching (MWPM) algorithm.[17] In the case of quantum Calderbank–Shor–Steane (CSS) code, where X and Z sectors can be decoded independently, the MWD of these sectors can be reformulated as matching problems. Efficient implementations of MWPM, such as Blossom[20] and Union-Find,[21] can rapidly resolve the MWD problem for specific codes. The advantage of the minimum-weight decoding is the efficiency, as it turns the problem into an optimization task that can be effectively addressed across various codes and noise models.

    However, in quantum codes, a degeneracy issue arises, where multiple errors produce identical effects on the encoded logical space. The effect is presented by the logical sectors L characterized using the commutation relation between the error operator O and logical operators I, LX, LY, and LZ. In other words, the optimal decoding problem is to estimate the logical sector L given the syndrome γ. This is actually the principle of the maximum likelihood decoding (MLD),[22,23] which maximizes the conditional probability of the logical sector given syndrome

    where L ranges over all possible logical sectors and the summation extends over all elements of the stabilizer group. Since MLD accounts for the properties of the stabilizer group and incorporates quantum degeneracy, its performance is generally superior to MWD. However, MLD is more computationally demanding, as it requires the evaluation of 4k coset probabilities, each of which belongs to the #P-hard complexity class and lacks a polynomial-time exact solution.

    For specific quantum codes with lattice-like structures, the maximum likelihood decoding can be effectively performed using tensor network algorithms, especially the boundary matrix product state (bMPS) algorithms.[24] The performance of such algorithms can closely approach the theoretical optimum as they rigorously adhere to the MLD decoding formula. Additionally, the approximation error in these algorithms can be accurately controlled using the canonical form of MPS. However, the primary limitation of this method is its scaling, which is O(nχ3), where χ is the bond dimension of MPS. As the bond dimension typically increases with code size, the tensor network decoding method becomes less efficient for larger codes. Recently, an exact maximum likelihood encoding approach[25] has been established for the repetition code with circuit-level noise. We refer to it as Planar. The approach has a polynomial time complexity to the number of qubits. Regarding decoding accuracy, Planar achieves optimal performance by strictly adhering to the MLD criterion. For decoding speed, it scales polynomially with the number of stabilizers. This scaling is comparable to the performance of the MWPM algorithm and significantly faster than MLD algorithms based on tensor network contraction. Additionally, it outperforms the minimum weight perfect matching algorithm on various noise models in repetition codes.[1] In this work, we extend the study of the Planar to a broad class of quantum error-correcting codes with planar structures, using an example of rotated surface code with independent code-capacity noise and explain the details of the implementation.[26]

    In the following sections, we first present the statistical mechanical mapping of quantum error correction code problems and the principles of Planar decoding. This includes examining the planar Ising model mapping for specific QECCs and introducing a polynomial-time solver for the planar Ising model partition function. Subsequently, we detail the mapping procedure using Python code for rotated surface codes of arbitrary distances. We then provide numerical results to demonstrate the performance of Planar. Finally, we conclude with discussions and outline potential future research directions.

2.   Principles of the Planar decoder
  • Planar belongs to the maximum likelihood decoding, which aims to identify the most likely logical sector by computing the probability P(L) for each logical sector L. Here, P(L) represents the total probability of all error configurations that are consistent with the syndrome measurements and have the same commutation relation with the logical operator. This is achieved by considering all possible error configurations through the decomposition of each Pauli error O into three components: O = S · L · E, where S represents the stabilizer group element, L denotes the logical operator, and E corresponds to the pure error operator. Each component comprises Pauli operators acting on all encoded qubits under the given stabilizer code, with each operator parametrized by a binary configuration {α,β,γ} indicating the activation state of each constituent operator. We will abuse the notation of syndrome γ ∈ {+1,−1}m and pure error configuration γ ∈ {0,1}m. Consequently, the pure error configuration γ ∈ {0,1}m is fixed by the syndrome, requiring summation over all stabilizer group elements (parametrized by α ∈ {0,1}m) to determine the optimal logical operator. For the details of the ELS decomposition, we refer to Ref. [27]. Then the probability of the error belonging to the logical sector L is given by

    and the most probable logical operator can be selected using

    The challenge of the MLD as shown in the last equation is performing the summation over all possible stabilizer operators S∈S, which requires enumerating all possible binary configurations α ∈ {0,1}m. This problem belongs to the #P complexity class, and no general polynomial-time algorithms exist for solving it exactly. However, in Ref. [25], it has been shown that for quantum codes with planar structures, such as the repetition codes with circuit-level noise, there exist exact MLD algorithms with polynomial complexity.

  • To achieve a polynomial-complexity exact algorithm for quantum codes with a planar structure, Planar first maps the decoding problem to the partition function computation of an Ising spin glass model on a planar graph. The mapping allows the error correction problem to be expressed as a statistical mechanics problem, where the partition function of the Ising model corresponds to the probability of the sum of all error configurations consistent with the syndrome measurements and belongs to the same logical sector. During the mapping, stabilizer generators serve as spins while data qubits correspond to (hyper)edges. The Hamiltonian is formulated as[28]

    where Oi denotes the component of Pauli error operator O acting on the i-th qubit. (gk)i is the i-th component of the k-th stabilizer. Such representation holds under the Nishimori condition[29]

    where 〈 〉 represents the scalar commutator which equals 1 if the two inputs commute and −1 otherwise, p(ρ) represents the probability of error ρ occurring on a specific qubit. We can easily check the probability of an error

    Non-trivial configurations of spins means there are stabilizers acting on the error O and causing a new error O′ which belongs to the same equivalence class as O. Therefore, summing all elements which are equivalent to O is equal to summing all spin configurations, i.e., the coset probability of a quantum code equals the partition function of the corresponding Ising model,

    The planar nature of the Ising model ensures that the problem can be solved exactly using polynomial-time algorithms such as the Kac–Ward formula,[30] as discussed in Subsection 3.3.3. This approach selects the most likely logical section, eliminating traditional methods’ suboptimality. Moreover, the polynomial complexity of the Kac–Ward solution renders it highly efficient for large-scale quantum codes.

3.   Implementation of Planar demonstrated under the rotated surface code
  • Planar is designed with modularity in mind, separating graph construction, probability calculation, and decoding logic into distinct components. This modular design enables straightforward extension to diverse code families and error models. The software handles both X and Z errors independently, ensuring optimal performance for all error types. In this section, we will take the standard rotated surface code as an illustrative example to explain the implementation of the Planar decoder. Under the uncorrelated code-capacity noise model, the decoding graph of the rotated surface code exhibits a planar structure, making it a simple and ideal candidate for decoding with Planar.

  • We first introduce the rotated surface code, a commonly used quantum error correction code on a two-dimensional lattice. It is constructed from a two-dimensional lattice, where each plaquette represents a stabilizer generator, and each vertex represents a qubit. To convert the decoding problem into a partition-function computation problem of a spin glass, we first index every qubit in the rotated surface lattice, which corresponds to the edges in Fig. 1(a). Then, we represent each stabilizer generator, pure error generator, and logical operator by a parity check matrix (PCM). In general, the logical generator can be generated by calculating the kernel of the PCM of the stabilizer generator. For the rotated surface code, we can easily find it using the symmetry of the code. This is achieved by the function gen_rotated_surface_code in experiments/codes.py in our implementation.[26] Then, we construct the PCM of the pure error generator by using the commutation relation between the stabilizer generator and the pure error generator. More specifically, we calculate the kernel of the PCM of the stabilizer generator and check if it commutes with the logical operator. For the detailed mathematics, we refer to Ref. [25]. In our implementation, it is implemented in the function cal_pure_error_basis in planar/planar_decoder.py in Ref. [26].

  • In this section, we introduce how to convert the rotated surface code into a planar Ising model on a decoding graph. Here we consider the independent code-capacity noise, where the X stabilizers and Z stabilizers belong to two separate graphs. We first construct the planar decoding graph from the PCM for both X and Z stabilizer generators. The process generates dangling edges, as illustrated in Fig. 1(b), necessitating the introduction of a virtual node to connect these edges for each decoding graph, as shown in Fig. 1(c). The Kac–Ward solution is then applied, implemented by the function construct_kac_ward_solution in planar/planar_decoder.py as detailed in Ref. [26].

  • This step calculates the partition function of the Ising model generated in step 2. To apply the Kac–Ward formula, a non-backtracking matrix is first constructed to encode the spatial relationships between edges in the graph. This matrix is constructed during the initialization of the class KacWardSolution. Specifically, each entry in the matrix represents the angle between connected edges. The graph layout, including node positions, is represented using networkx to calculate these angles, which are then expressed as complex numbers in the non-backtracking matrix.

    The partition function of the Ising model is then computed using the Kac–Ward formula

    The non-backtracking matrix A and the matrix for computing det(I – W) are represented in sparse format, where W = AD. Here, D is a diagonal matrix with Dij,ij = Jij, corresponding to the edge weights, as defined by the formula

    where ϕijl denotes the angle between the edges ij and kl, which corresponds to the angle formed by the nodes i, j, and l.

    The LU decomposition of matrix A is computed using scipy.sparse.linalg.splu(A). The real part of the sum of the logarithms of the diagonal elements of U yields the logarithmic partition function. This is implemented in the function logZ within the KacWardSolution class.

  • Following the Kac–Ward solution for the partition function of the planar Ising model, the probabilities of different logical sectors (cosets) are computed to identify the most probable logical recovery operator. This is implemented in the log_coset_p and decode functions within the Planar decoder.[26]

  • The function accepts the pure error operator, with or without the corresponding logical operator (X/Z or I, representing distinct logical sectors), the error rate, the Kac–Ward solution, and a dictionary mapping graph edges to indices consistent with the Kac–Ward solution. It computes edge weights based on the error rate, which are then used to determine the logarithm of the partition function (logZ) via the Kac–Ward solution. The output is the log probability for the specified logical error configuration, enabling comparison across logical sectors.

  • The decoding process decode begins by determining the pure error corresponding to the syndrome, which represents an error configuration consistent with the syndrome measurements. For both X and Z components of the decoding graph, the log_coset_p function calculates the probabilities of different logical cosets (i.e., the pure error combined with or without the logical operator). The most probable logical operator is selected by comparing these probabilities. The recovery operation is then constructed by combining the pure error with the chosen logical operator.

    This approach ensures the decoder selects the most likely error configuration, achieving maximum likelihood decoding. The Kac–Ward solution guarantees exact probability computations, eliminating the suboptimality associated with minimum weight methods such as MWPM.

4.   Numerical results
  • We first employ the rotated surface code family to evaluate the performance of Planar. To determine the threshold of the rotated surface code, we adopt the standard assumption of uncorrelated noise. In this model, the error probabilities for each qubit are defined as follows:

    Under the uncorrelated noise assumption, there are no correlations between X and Z types of stabilizers, implying that J(Y) = 0 in the system’s Hamiltonian as shown in Eq. (5). This simplification allows the Hamiltonian to be decomposed into two independent terms corresponding to X and Z errors:

    where e denotes edges, and i, j and k, l represent spins connected by these edges in the X or Z subgraph. This formulation demonstrates that the subsystems associated with X and Z errors are decoupled. Thus, the partition function of the entire system can be expressed as the product of the partition functions of the two subsystems, i.e., Z=Zx·Zz. This independence extends to the logical error probabilities P(Lx) and P(Lz), such that P(Lx, Lz) = P(Lx) · P(Lz). Consequently, the original Ising model graph can be partitioned into X and Z subgraphs, each forming a planar lattice that retains the planar structure. This decoupling simplifies the analysis and improves the computational efficiency of the decoding process.

    We first evaluated Planar on the rotated surface code, testing its performance for code distances ranging from 9 to 25. The decoder achieves optimal maximum-likelihood decoding results for this error model, with a threshold of approximately puc ≈ 0.109, as depicted in the main graph of Fig. 2(a). Additionally, as observed from the subgraph in the upper left corner, the decoding time for each trial scales polynomially with the increase in the number of spins, which corresponds to the nodes in Fig 1(c). This polynomial scaling behavior indicates that the algorithm remains computationally efficient even as the system size grows. The algorithm’s time complexity is quantified as O(N0.69), where N represents the number of spins in the Ising model. This scaling value further underscores the efficiency of the algorithm, making it suitable for practical applications in large-scale quantum error correction tasks. The observed scaling behavior aligns with theoretical expectations and demonstrates the algorithm’s capability to handle increasingly complex systems without significant computational overhead.

    It is worth noting that, under this error model, Planar provides a theoretically optimal solution, eliminating the need for comparison with other decoders. This optimality is crucial for practical quantum error correction, as it ensures the highest possible accuracy in error detection and correction.

    This theoretical guarantee is particularly significant in the context of fault-tolerant quantum computing, where even small error rates can compromise the integrity of quantum computations. By providing an optimal solution, Planar not only enhances the reliability of quantum error correction but also sets a benchmark against which other decoding algorithms can be evaluated. Furthermore, the elimination of the need for comparative analysis with other decoders simplifies the implementation and validation process, allowing researchers and practitioners to focus on optimizing other aspects of quantum error correction protocols.

    Furthermore, we also tested Planar on the commonly used depolarizing error model, where the error probabilities are defined as

    Consequently, the system’s Hamiltonian includes an additional term compared to Eq. (10), corresponding to the contribution of J(Y):

    To apply Planar to this error model, we approximate the contribution of J(Y) by separating it into its X and Z components, eliminating the correlation caused by the Y component, redefining the error probabilities for each qubit as follows:

    This approximation is also utilized by several well-known minimum-weight decoders, such as MWPM[17] and BP-OSD.[31] However, these decoders consistently exhibit inferior decoding performance compared to Planar, even when employing the same uncorrelated approximation. This discrepancy arises because minimum-weight decoders introduce additional approximations during their decoding process, as they aim to identify the most probable error (i.e., the error with the minimum weight). In contrast, Planar rigorously seeks to determine the maximum likelihood logical sector without such approximations. The ability of Planar to directly target the maximum likelihood solution, rather than relying on intermediate approximations, underscores its theoretical and practical advantages over conventional minimum-weight decoders.

    Under this uncorrelated approximation, Planar still yields remarkable results for the rotated surface code with depolarizing noise model, as shown in Fig. 2(b), with a threshold of approximately pucdep≈0.164 and time complexity scaling as O(N0.75). This result of threshold matches the theoretical prediction of pucdep=32puc≈0.164,[29] and also demonstrates the robustness and adaptability of Planar in handling different error models, which is essential for its application in diverse quantum computing environments.

    To further demonstrate the generality of Planar, we also tested it on the hexagon code, a novel quantum error correction code with a planar structure, as shown in Fig. 3. The hexagon code is constructed from a hexagonal lattice, where each vertex and plaquette represents a stabilizer generator, and each edge represents a qubit. The planar structure of the hexagon code ensures that the decoding problem can be mapped to a planar Ising model, enabling efficient and exact decoding with Planar. For the hexagon code, we tested Planar on code distances ranging from 5 to 25. The decoder achieves optimal maximum-likelihood decoding results under the uncorrelated noise model as well, with a threshold of approximately puchex≈0.07 and time complexity scaling as O(N0.74), as shown in Fig. 2(c). These results further validate the versatility and efficiency of Planar for decoding quantum codes with planar structures. The ability of Planar to handle different code geometries and error models underscores its potential as a universal decoding tool in quantum error correction.

5.   Conclusion
  • In this work, we presented the implementation details of Planar, a software framework designed for the exact decoding of quantum codes with planar structures. By leveraging the Kac–Ward formula, Planar achieves maximum likelihood decoding with polynomial time complexity. The introduction of the rotated surface code demonstrates the practical applicability of Planar, showcasing its ability to efficiently handle complex quantum error correction tasks. We also presented a new quantum error correction code, the hexagon code, to demonstrate the generality of Planar.

    Our numerical results indicate that the rotated surface code using Planar achieves a threshold of approximately puc ≈ 0.109 under the uncorrelated error model, with a time complexity scaling of O(N0.69). For hexagon codes, these values would be puchex≈0.07 and O(N0.74). This performance highlights the potential of Planar for real-world quantum error correction applications, particularly in large-scale quantum systems where efficiency and accuracy are paramount. Future work will focus on extending Planar to other code families that have planar structures and optimizing its implementation for faster or even real-time decoding in experimental quantum hardware. The modular design of Planar ensures its adaptability to various quantum error correction scenarios, making it a versatile tool for advancing fault-tolerant quantum computing.

Program availability
  • The source code is openly available on GitHub at https://github.com/CHY-i/planar.

Figure (8)  Reference (31)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return