Optimization Using Locally-Quantum Decoders

• URL: http://arxiv.org/abs/2604.24633v1
• Date: Mon, 27 Apr 2026 16:02:59 GMT
• Title: Optimization Using Locally-Quantum Decoders
• Abstract summary: We develop an intrinsically quantum decoding technique, which decodes classical LDPC codes subject to coherent superpositions of bit flip errors.<n>For average-case instances of D-regular max-k-XORSAT drawn from Gallager's ensemble, this quantum decoder strongly outperforms classical belief propagation at many values of k and D.<n>We identify an enhancement to Prange's algorithm that recovers a precise tie, much as a precise tie was observed between the standard version of Prange's algorithm and a more limited version of locally-quantum decoding.
• Score: 3.953819147984722
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It was pointed out in [JSW+25] that widely-studied optimization problems such as D-regular max-k-XORSAT can be reduced to decoding of LDPC codes, using quantum algorithms related to Regev's reduction. LDPC codes have very good decoders, such as Belief Propagation (BP), and this therefore makes D-regular max-k-XORSAT an enticing target for this class of quantum algorithms. However, BP was found insufficient to achieve quantum advantage. Here, we develop an intrinsically quantum decoding technique, which decodes classical LDPC codes subject to coherent superpositions of bit flip errors. For average-case instances of D-regular max-k-XORSAT drawn from Gallager's ensemble, this quantum decoder strongly outperforms classical belief propagation at many values of k and D. For some (k,D) the approximate optima achievable using this decoder surpass both Prange's algorithm and simulated annealing. However, we stop short of achieving quantum advantage because we identify an enhancement to Prange's algorithm that recovers a precise tie, much as a precise tie was observed between the standard version of Prange's algorithm and a more limited version of locally-quantum decoding in [CT24].

Related papers

• Impulse Decoding of Quantum LDPC Codes: Equivalence of Degeneracy and Code-Shortening [1.9355898755215148]
  We show that degeneracy is closely related to the classical operation of shortening of a linear block code.<n>We present a parallel decoding scheme for quantum low-density parity-check codes, which we term impulse decoding.<n>We then present another algorithm based on decoding of residual errors, which when combined with impulse decoding achieves further performance improvement under circuit-level noise.
  arXiv  Detail & Related papers  (2026-06-16T17:58:26Z)
• Approximate level-by-level maximum-likelihood decoding based on the Chase algorithm for high-rate concatenated stabilizer codes [0.0]
  It is essential to encode logical qubits using quantum error-correcting codes.<n>High-rated codes have attracted attention due to theoretical advances in fault-tolerant protocols.<n>We propose a general, high-performance decoder for high-rated stabilizer codes.
  arXiv  Detail & Related papers  (2026-01-26T18:04:29Z)
• Efficient and optimal quantum state discrimination via quantum belief propagation [6.445605125467573]
  We present an efficient quantum algorithm for a structured state discrimination problem we call the subspace decoding task.<n>We show that the algorithm enables efficient and optimal decoding of certain families of structured classical linear codes transmitted over binary-input classical-quantum pure-state channels.
  arXiv  Detail & Related papers  (2025-09-23T18:00:07Z)
• Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes [0.30912596009895504]
  Decoding quantum error-correcting codes is a key challenge in enabling fault-tolerant quantum computation.<n>In this work, we uncover a key limitation of linear programming (LP) decoding for quantum low-density parity-check codes.<n>We incorporate a post-processing technique known as ordered statistics decoding (OSD) which significantly enhances LP decoding performance in practice.
  arXiv  Detail & Related papers  (2025-08-06T18:00:01Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  We introduce Decoded Quantum Interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems.<n>For approximating optimal fits over finite fields, DQI achieves a superpolynomial speedup over known classical algorithms.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Near-optimal decoding algorithm for color codes using Population Annealing [44.99833362998488]
  We implement a decoder that finds the recovery operation with the highest success probability. We study the decoder performance on a 4.8.8 color code lattice under different noise models.
  arXiv  Detail & Related papers  (2024-05-06T18:17:42Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)
• Quaternary Neural Belief Propagation Decoding of Quantum LDPC Codes with Overcomplete Check Matrices [45.997444794696676]
  Quantum low-density parity-check (QLDPC) codes are promising candidates for error correction in quantum computers.<n>One of the major challenges in implementing QLDPC codes in quantum computers is the lack of a universal decoder.<n>We first propose to decode QLDPC codes with a belief propagation (BP) decoder operating on overcomplete check matrices.<n>We extend the neural BP (NBP) decoder, which was originally studied for suboptimal binary BP decoding of QLPDC codes, to quaternary BP decoders.
  arXiv  Detail & Related papers  (2023-08-16T08:24:06Z)
• Single-shot decoding of good quantum LDPC codes [38.12919328528587]
  We prove that quantum Tanner codes facilitate single-shot quantum error correction (QEC) of adversarial noise. We show that in order to suppress errors over multiple repeated rounds of QEC, it suffices to run the parallel decoding algorithm for constant time in each round.
  arXiv  Detail & Related papers  (2023-06-21T18:00:01Z)
• Deep Quantum Error Correction [73.54643419792453]
  Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing. In this work, we efficiently train novel emphend-to-end deep quantum error decoders. The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy.
  arXiv  Detail & Related papers  (2023-01-27T08:16:26Z)
• 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)
• On Quantum-Assisted LDPC Decoding Augmented with Classical Post-Processing [1.0498337709016812]
  This paper looks into the Quadratic Unconstrained Binary Optimization (QUBO) and utilized D-Wave 2000Q Quantum Annealer to solve it. We evaluated and compared this implementation against the decoding performance obtained using Simulated Annealing (SA) and belief propagation (BP) decoding with classical computers.
  arXiv  Detail & Related papers  (2022-04-21T08:01:39Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.