Determining the upper bound of code distance of quantum stabilizer codes through Monte Carlo method based on fully decoupled belief propagation

• URL: http://arxiv.org/abs/2402.06481v1
• Date: Fri, 9 Feb 2024 15:40:55 GMT
• Title: Determining the upper bound of code distance of quantum stabilizer codes through Monte Carlo method based on fully decoupled belief propagation
• Abstract summary: In this paper, employing the idea of Monte Carlo method, we propose the algorithm of determining the upper bound of code distance of QSCs. Our algorithm shows high precision - the upper bound of code distance determined by the algorithm of a variety of QSCs whose code distance is known is consistent with actual code distance.
• Score: 19.39678519027849
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Code distance is an important parameter for quantum stabilizer codes (QSCs). Directly precisely computing it is an NP-complete problem. However, the upper bound of code distance can be computed by some efficient methods. In this paper, employing the idea of Monte Carlo method, we propose the algorithm of determining the upper bound of code distance of QSCs based on fully decoupled belief propagation. Our algorithm shows high precision - the upper bound of code distance determined by the algorithm of a variety of QSCs whose code distance is known is consistent with actual code distance. Besides, we explore the upper bound of logical X operators of Z-type Tanner-graph-recursive-expansion (Z-TGRE) code and Chamon code, which is a kind of XYZ product code constructed by three repetition codes. The former is consistent with the theoretical analysis, and the latter implies the code distance of XYZ product codes can very likely achieve $O(N^{2/3})$, which supports the conjecture of Leverrier et al..

Related papers

• Quantum codes from classical annealing [0.15293427903448023]
  Search for quantum error-correcting codes with high encoding rates and large distances.<n>For block lengths of up to $50$ physical qubits, our search finds state-of-the-art CSS and SWEL codes.<n>Codes found in this work are promising candidates for high-rate code demonstrations on near-term quantum computing hardware.
  arXiv  Detail & Related papers  (2026-07-21T21:01:37Z)
• A polynomial-time approximation scheme for minimum-weight decoding of topological codes [42.44256445495892]
  Two-dimensional topological translationally in (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation.<n>Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings.
  arXiv  Detail & Related papers  (2026-06-16T16:44:08Z)
• On Constructing and Decoding Quantum Triorthogonal Codes [8.986356590623483]
  A triorthogonal code is a binary quantum computation Calderbank-Shor-Steane code.<n>We study the construction and decoding of triorthogonal codes with prescribed dual-distance properties.
  arXiv  Detail & Related papers  (2026-05-23T11:13:06Z)
• Distance-Finding Algorithms for Quantum Codes and Circuits [0.016014822925318913]
  Distance of a classical or quantum code is a key figure of merit which reflects its capacity to detect errors.<n>We benchmark a wide range of distance-finding methods for various classical and quantum code families.<n>We develop the QDistEvol algorithm and show that it performs well for the quantum LDPC codes in our benchmark.
  arXiv  Detail & Related papers  (2026-03-23T19:52:23Z)
• The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding [42.44256445495892]
  We show that minimum-weight decoding is NP-hard in three quintessential settings.<n>Our results highlight a sharp computational complexity separation between minimum-weight decoding and its approximate realizations.
  arXiv  Detail & Related papers  (2026-03-23T14:57:38Z)
• Check-weight-constrained quantum codes: Bounds and examples [41.528148407718604]
  Quantum low-density parity-check (qLDPC) codes can be implemented by measuring only low-weight checks.<n>Here, we study stabilizer and subsystem codes with constrained check weight.<n>We show that stabilizer codes with checks of weight at most three cannot have nontrivial distance.
  arXiv  Detail & Related papers  (2026-01-21T20:24:51Z)
• Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks [18.20811830109862]
  We construct the first known quantum codes with linear dimension and distance supporting non-Clifford gates.<n>We design an efficient decoding algorithm for these codes.<n>Our results can be viewed as a new generalization of Prony's method for reconstructing a function from partial access to its transform.
  arXiv  Detail & Related papers  (2025-10-08T09:27:41Z)
• A topological theory for qLDPC: non-Clifford gates and magic state fountain on homological product codes with constant rate and beyond the $N^{1/3}$ distance barrier [0.0]
  We develop a unified theory for fault-tolerant quantum computation in quantum low-density parity-check (qLDPC) and topological codes. We show that there exist hidden simplicial complex structures encoding the topological data for all qLDPC and CSS codes obtained from product construction.
  arXiv  Detail & Related papers  (2025-01-31T18:25:24Z)
• List Decodable Quantum LDPC Codes [49.2205789216734]
  We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff. We get efficiently list decodable QLDPC codes with unique decoders.
  arXiv  Detail & Related papers  (2024-11-06T23:08:55Z)
• Almost Linear Decoder for Optimal Geometrically Local Quantum Codes [8.837439668920288]
  We show how to achieve geometrically local codes that maximize both the dimension and the distance, as well as the energy barrier of the code. This provides the first decoder for an optimal 3D geometrically local code.
  arXiv  Detail & Related papers  (2024-11-05T09:15:06Z)
• Fast Algorithms and Implementations for Computing the Minimum Distance of Quantum Codes [43.96687298077534]
  The distance of a stabilizer quantum code determines the number of errors that can be detected and corrected.<n>We present three new fast algorithms and implementations for computing the symplectic distance of the associated classical code.
  arXiv  Detail & Related papers  (2024-08-20T11:24:30Z)
• SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
  We present Safe Surgery by Identifying Pushouts (SSIP), an open-source lightweight Python package for automating surgery between qubit CSS codes. Under the hood, it performs linear algebra over $mathbbF$ governed by universal constructions in the category of chain complexes. We show that various logical measurements can be performed cheaply by surgery without sacrificing the high code distance.
  arXiv  Detail & Related papers  (2024-07-12T16:50:01Z)
• Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
  Low-Density Parity-Check (LDPC) codes possess several advantages over other families of codes. The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
  arXiv  Detail & Related papers  (2024-06-09T12:08:56Z)
• Geometrically Local Quantum and Classical Codes from Subdivision [10.357542321841887]
  A geometrically local quantum code is an error correcting code situated within $mathbbRD$, where the checks only act on qubits within a fixed spatial distance. Recently, Portnoy made a significant breakthrough with codes achieving optimal dimension and distance up to polylogs. This paper bypasses this step and streamlines the construction by noticing that a family of good quantum low-density parity-check codes, balanced product codes, naturally carries a two-dimensional structure.
  arXiv  Detail & Related papers  (2023-09-28T02:12:38Z)
• Quantum Lego Expansion Pack: Enumerators from Tensor Networks [1.489619600985197]
  We provide the first tensor network method for computing quantum weight enumerators in the most general form. For non-(Pauli)-stabilizer codes, this constitutes the current best algorithm for computing the code distance. We show that these enumerators can be used to compute logical error rates exactly and thus construct decoders for any i.i.d. single qubit or qudit error channels.
  arXiv  Detail & Related papers  (2023-08-09T18:00:02Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix. This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
  arXiv  Detail & Related papers  (2022-12-20T13:41:27Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)
• Quantum Tanner codes [0.38073142980732994]
  We prove a theorem that simultaneously gives a growing minimum distance for the quantum code and recovers the local testability of the Dinur et al. code.
  arXiv  Detail & Related papers  (2022-02-28T09:35:31Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
  arXiv  Detail & Related papers  (2021-08-10T15:00:20Z)
• Decoding Across the Quantum LDPC Code Landscape [4.358626952482686]
  We show that belief propagation combined with ordered statistics post-processing is a general decoder for quantum low density parity check codes. We run numerical simulations of the decoder applied to three families of hypergraph product code: topological codes, fixed-rate random codes and a new class of codes that we call semi-topological codes.
  arXiv  Detail & Related papers  (2020-05-14T14:33:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.