In order to build a large scale quantum computer, one must be able to correct errors extremely fast. We design a fast decoding algorithm for topological codes to correct for Pauli errors and erasure and combination of both errors and erasure. Our algorithm has a worst case complexity of O ( n α ( n ) ) , where n is the number of physical qubits and α is the inverse of Ackermann's function, which is very slowly growing. For all practical purposes, α ( n ) ≤ 3 . We prove that our algorithm performs optimally for errors of weight up to ( d − 1 ) / 2 and for loss of up to d − 1 qubits, where d is the minimum distance of the code. Numerically, we obtain a threshold of 9.9 % for the 2d-toric code with perfect syndrome measurements and 2.6 % with faulty measurements.
In order to build a large scale quantum computer, one must be able to correct errors extremely fast. We design a fast decoding algorithm for topological codes to correct for Pauli errors and erasure and combination of both errors and erasure. Our algorithm has a worst case complexity of O ( n α ( n ) ) , where n is the number of physical qubits and α is the inverse of Ackermann's function, which is very slowly growing. For all practical purposes, α ( n ) ≤ 3 . We prove that our algorithm performs optimally for errors of weight up to ( d − 1 ) / 2 and for loss of up to d − 1 qubits, where d is the minimum distance of the code. Numerically, we obtain a threshold of 9.9 % for the 2d-toric code with perfect syndrome measurements and 2.6 % with faulty measurements.
Topological quantum error-correcting codes are a promising candidate for building fault-tolerant quantum computers. Decoding topological codes optimally, however, is known to be a computationally hard problem. Various decoders have been proposed that achieve approximately optimal error thresholds. Due to practical constraints, it is not known if there exists an obvious choice for a decoder. In this paper, we introduce a framework which can combine arbitrary decoders for any given code to significantly reduce the logical error rates. We rely on the crucial observation that two different decoding techniques, while possibly having similar logical error rates, can perform differently on the same error syndrome. We classify each error syndrome to the decoder which is more likely to decode it correctly using machine learning techniques. We apply our framework to an ensemble of minimum-weight perfect matching (MWPM) and hard-decision re-normalization-group decoders for the surface code in the depolarizing noise model. Our simulations show an improvement of 38.4%, 14.6%, and 7.1% over the pseudothreshold of MWPM in the instance of distance 5, 7, and 9 codes, respectively. Lastly, we discuss the advantages and limitations of our framework and applicability to other error-correcting codes. Our framework can provide a significant boost to error correction by combining the strengths of various decoders. In particular, it may allow for combining very fast decoders with moderate error-correcting capability to create a very fast ensemble decoder with high error-correcting capability.
Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the X- and Z-syndromes. For color codes under independent X- and Z-error models, we consider Separate Minimum-Weight decoding.
Assuming P=NP, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the 4.8.8 color code on the torus, there exists a constant c>0 such that no polynomial-time algorithm can always produce a solution whose weight is within cN1/14 of the optimum, where N is the number of qubits, unless P=NP. For the planar surface code, we obtain an Ω(N1/18) gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT.
Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.
Two-dimensional topological translationally invariant (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation, but using them requires solving the decoding problem. Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings, such as the color code with Pauli Z errors and the toric code with Pauli X, Y and Z errors. Here, we prove that minimum-weight decoding of 2D TTI codes nonetheless admits a polynomial-time approximation scheme (PTAS), i.e., for any constant ε>0, a recovery operator of weight within a multiplicative factor of 1+ε of the minimum can be found in polynomial time. Our approach builds on Arora's PTAS for Euclidean problems, such as the traveling salesman problem, and applies when decoding can be cast in terms of point-like excitations connected by string-like errors. It therefore extends beyond two dimensions, covering certain higher-dimensional topological codes and quantum memories, including the toric code with phenomenological or circuit-level noise.
The possibility of practical large-scale quantum computation is largely dictated by the error threshold and qubit overhead of the error correcting scheme. To achieve this goal, architectures that perform fault tolerance quantum computation (FTQC) with 3D cluster states have been designed; however, the current benchmarks for such constructions are still below general experimental requirements. In light of this, we propose a new 3D FTQC scheme by exploiting geometric tolerance to erasure errors using cluster states with novel lattice structures, specifically, by replacing the physical qubits with small-sized error detection codes that allow simple applications of logical CZ gates. We are able to locate Pauli errors locally and effectively convert them into loss errors. With a combination of code concatenation and multi-staged decoding, the scheme is able to achieve higher performance than traditional cubic lattices in protecting quantum information. We have surveyed a wide range of possible concatenation schemes and Monte-Carlo simulations have been performed on the decoders to study their respective scaling behavior. The scheme has demonstrated an overall decrement in active qubit overhead and an improvement of the error threshold, which varies from 10 % to 160% depending on the noise model, indicating a relatively higher rate of fault tolerance compared with previous cluster states-based codes.
Topological quantum codes are favored because they allow suitable qubit layouts for practical implementation. An N-qubit topological code can be decoded by minimum-weight perfect matching (MWPM) with complexity O(poly(N)). Recently it is shown that various quantum codes, including topological codes, can be decoded by an adapted belief propagation with memory effects (denoted MBP) with complexity almost linear in N. In this paper, we show that various two-dimensional topological codes, CSS or non-CSS, regardless of the layout, can be decoded by MBP, including color codes and a family of twisted XZZX codes. We will comprehensively compare these codes in terms of code efficiency and decoding performance, assuming perfect error syndromes.
Topological codes have many desirable properties that allow fault-tolerant quantum computation with relatively low overhead. A core challenge for these codes, however, is to achieve a low-overhead universal gate set with limited connectivity. In this work, we explore a non-Pauli stabilizer code that can be used to complete a universal gate set on topological toric and surface codes in strictly two dimensions. Fault-tolerant syndrome extraction for the non-Pauli code requires mid-circuit X corrections, a key difference to conventional Pauli codes. We construct and benchmark a just-in-time (JIT) matching decoder to reliably decide these corrections. Under a phenomenological error model with equally likely physical and measurement errors, we find a high threshold of ≈2.5%, close to the ≈2.9% of a decoder with access to the full syndrome history. We also perform a finite-size scaling analysis to estimate how the logical error rate scales below threshold and verify an exponential suppression in both physical error rate and in the system size. A second global decoding step for Z errors is required and the non-Clifford gates in the circuit reduce the threshold from ≈2.9% to ≈1.8% with a naive decoder. We show how Z decoding can be improved using knowledge of the X corrections, pushing the threshold to ≈2.2%. Our results suggest non-Clifford logic in 2D codes could perform comparably to 2D quantum memory. Our formalism for efficient benchmarking and decoding directly generalizes to a broader family of CSS codes whose X stabilizers are twisted by diagonal Clifford operators, and spacetime versions thereof, defined by CSS-like circuits enriched by CCZ, CS, and T gates.