Quantum message-passing algorithm for optimal and efficient decoding

Abstract

Recently, Renes proposed a quantum algorithm called belief propagation with quantum messages (BPQM) for decoding classical data encoded using a binary linear code with tree Tanner graph that is transmitted over a pure-state CQ channel [Renes, NJP 19 072001 (2017)]. The algorithm presents a genuine quantum counterpart to decoding based on the classical belief propagation algorithm, which has found wide success in classical coding theory when used in conjunction with LDPC or Turbo codes. More recently Rengaswamy et al. [npj Quantum Information 7 97 (2021)] observed that BPQM implements the optimal decoder on a small example code. Here we significantly expand the understanding, formalism, and applicability of the BPQM algorithm with the following contributions. First, we prove analytically that BPQM realizes optimal decoding for any binary linear code with tree Tanner graph. We also provide the first formal description of the BPQM algorithm in full detail and without any ambiguity. In so doing, we identify a key flaw overlooked in the original algorithm and subsequent works which implies quantum circuit realizations will be exponentially large in the code dimension. Although BPQM passes quantum messages, other information required by the algorithm is processed globally. We remedy this problem by formulating a truly message-passing algorithm which approximates BPQM and has quantum circuit complexity $\mathcal{O}(\text{poly }n,\text{polylog }\frac{1}{\epsilon })$, where $n$ is the code length and $\epsilon$ is the approximation error. Finally, we also propose a novel method for extending BPQM to factor graphs containing cycles by making use of approximate cloning. We show some promising numerical results that indicate that BPQM on factor graphs with cycles can significantly outperform the best possible classical decoder.

arXiv comment56 pages, 22 figures, submitted to Quantum

References in corpus (25)

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Optimal Universal and State-Dependent Quantum Cloning
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Degenerate Quantum LDPC Codes With Good Finite Length Performance
• Decoding Across the Quantum LDPC Code Landscape
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum circuits with uniformly controlled one-qubit gates
• Quantum Graphical Models and Belief Propagation
• Structured optical receivers to attain superadditive capacity and the Holevo limit
• Quantum channels showing superadditivity in capacity
• Polar codes for classical-quantum channels
• Quantum Belief Propagation
• Optimal and Efficient Decoding of Concatenated Quantum Block Codes
• Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes
• Polar coding to achieve the Holevo capacity of a pure-loss optical channel
• Markov entropy decomposition: a variational dual for quantum belief propagation
• Polar codes for private and quantum communication over arbitrary channels
• Multi-path Summation for Decoding 2D Topological Codes
• Enhanced Feedback Iterative Decoding of Sparse Quantum Codes
• Modified belief propagation decoders for quantum low-density parity-check codes
• Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks
• Quantum circuits design for evaluating transcendental functions based on a function-value binary expansion method
• Belief Propagation with Quantum Messages for Quantum-Enhanced Classical Communications
• Belief propagation decoding of quantum channels by passing quantum messages
• Double-Edge Factor Graphs: Definition, Properties, and Examples

Cited by in corpus (3)

• Reed-Muller Codes on BMS Channels Achieve Vanishing Bit-Error Probability for All Rates Below Capacity
• Optimization by Decoded Quantum Interferometry
• Explicit decoders using fixed-point amplitude amplification based on QSVT