MaxSAT decoders for arbitrary CSS codes

• URL: http://arxiv.org/abs/2410.01673v1
• Date: Wed, 2 Oct 2024 15:45:05 GMT
• Title: MaxSAT decoders for arbitrary CSS codes
• Authors: Mohammadreza Noormandipour, Tobias Haug,
• Abstract summary: We show how to map quantum maximum likelihood problem of CSS codes of arbitrary geometry and parity check weight into MaxSAT problems. Our decoder can be further parallelised or implemented on ASICs and FPGAs, promising potential further speedups of several orders of magnitude.
• Score: 2.3895981099137535
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Quantum error correction (QEC) is essential for operating quantum computers in the presence of noise. Here, we accurately decode arbitrary Calderbank-Shor-Steane (CSS) codes via the maximum satisfiability (MaxSAT) problem. We show how to map quantum maximum likelihood problem of CSS codes of arbitrary geometry and parity check weight into MaxSAT problems. We incorporate the syndrome measurements as hard clauses, while qubit and measurement error probabilities, including biased and non-uniform, are encoded as soft MaxSAT clauses. For the code capacity of color codes on a hexagonal lattice, our decoder has a higher threshold and superior scaling in noise suppression compared to belief propagation with ordered statistics post-processing (BP-OSD), while showing similar scaling in computational cost. Further, we decode surface codes and recently proposed bivariate quantum low-density parity check (QLDPC) codes where we find lower error rates than BP-OSD. Finally, we connect the complexity of MaxSAT decoding to a computational phase transition controlled by the clause density of the MaxSAT problem, where we show that our mapping is always in the computationally ''easy`` phase. Our MaxSAT decoder can be further parallelised or implemented on ASICs and FPGAs, promising potential further speedups of several orders of magnitude. Our work provides a flexible platform towards practical applications on quantum computers.

Related papers

• IGMaxHS -- An Incremental MaxSAT Solver with Support for XOR Clauses [0.0]
  We introduce IGMaxHS, which is based on the solvers iMaxHS and GaussMaxHS, but poses fewer restrictions on the XOR constraints than GaussMaxHS. IGMaxHS is the only solver that reported neither incorrect unsatisfiability verdicts nor invalid models nor incoherent cost model combinations. We show that IGMaxHS is capable of decoding quantum color codes through simulation with the Munich Quantum Toolkit.
  arXiv  Detail & Related papers  (2024-10-21T11:21:21Z)
• Coherent information for CSS codes under decoherence [0.0]
  A class called Calderbank-Shor-Steane (CSS) codes includes many important examples such as toric codes, color codes, and fractons. Recent studies have revealed that the decoding transition for these QECCs could be intrinsically captured by calculating information-theoretic quantities from the mixed state.
  arXiv  Detail & Related papers  (2024-07-02T18:00:02Z)
• A SAT Scalpel for Lattice Surgery: Representation and Synthesis of Subroutines for Surface-Code Fault-Tolerant Quantum Computing [0.029541734875307393]
  We develop a synthesizer for LaS, LaSsynth, that encodes a LaS construction problem into a SAT instance, subsequently querying SAT solvers for a solution. LaSsynth can exhaustively explore the design space, yielding optimal designs in volume. For example, it achieves 8% and 18% volume reduction respectively over two states-of-the-art human designs for the 15-to-1 T-factory.
  arXiv  Detail & Related papers  (2024-04-29T02:14:45Z)
• Testing the Accuracy of Surface Code Decoders [55.616364225463066]
  Large-scale, fault-tolerant quantum computations will be enabled by quantum error-correcting codes (QECC) This work presents the first systematic technique to test the accuracy and effectiveness of different QECC decoding schemes.
  arXiv  Detail & Related papers  (2023-11-21T10:22:08Z)
• Hardness results for decoding the surface code with Pauli noise [0.0]
  We show that quantum maximum likelihood decoding (QMLD) and degenerate quantum maximum likelihood decoding (DQMLD) for the surface code are NP-hard and #P-hard, respectively. We transform a formula into a qubit-dependent Pauli noise model and set of syndromes that encode the satisfiability properties of the formula.
  arXiv  Detail & Related papers  (2023-09-19T05:29:01Z)
• Decoding quantum color codes with MaxSAT [4.29377170477633]
  We propose a novel decoder for quantum color codes using a formulation as a MaxSAT problem based on the LightsOut puzzle. We show that the decoding performance of the proposed decoder achieves state-of-the-art decoding performance on color codes.
  arXiv  Detail & Related papers  (2023-03-24T19:00:02Z)
• Scalable Quantum Error Correction for Surface Codes using FPGA [67.74017895815125]
  A fault-tolerant quantum computer must decode and correct errors faster than they appear. We report a distributed version of the Union-Find decoder that exploits parallel computing resources for further speedup. The implementation employs a scalable architecture called Helios that organizes parallel computing resources into a hybrid tree-grid structure.
  arXiv  Detail & Related papers  (2023-01-20T04:23:00Z)
• Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array [59.24209911146749]
  This paper explores the relationship between the width of a qubit lattice constrained in one dimension and physical thresholds. We engineer an error bias at the lowest level of encoding using the surface code. We then address this bias at a higher level of encoding using a lattice-surgery surface code bus.
  arXiv  Detail & Related papers  (2022-12-03T06:16:07Z)
• Tailored XZZX codes for biased noise [60.12487959001671]
  We study a family of codes having XZZX-type stabilizer generators. We show that these XZZX codes are highly qubit efficient if tailored to biased noise.
  arXiv  Detail & Related papers  (2022-03-30T17:26:31Z)
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes [61.411482146110984]
  We introduce decoders that are both fast and accurate, and can be used with a wide class of quantum error correction codes. Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC. We find that the decoders led to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.
  arXiv  Detail & Related papers  (2022-03-09T18:48:54Z)
• 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)

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.