Open access
Date
2022-08Type
- Journal Article
ETH Bibliography
yes
Altmetrics
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 [1], i.e., a channel with classical input and pure-state quantum output. 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. [2] observed that BPQM implements the optimal decoder on a small example code, in that it implements the optimal measurement that distinguishes the quantum output states for the set of input codewords with highest achievable probability. 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 O(poly n,polylog 1ϵ), where n is the code length and ϵ 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. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000568100Publication status
publishedExternal links
Journal / series
QuantumVolume
Pages / Article No.
Publisher
Verein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenOrganisational unit
03781 - Renner, Renato / Renner, Renato
Funding
186364 - (QuantEOM) Quantum-coherent electro-optic microwave-to-optical conversion with GaP and BaTiO3 (SNF)
Related publications and datasets
Is new version of: http://hdl.handle.net/20.500.11850/526528
More
Show all metadata
ETH Bibliography
yes
Altmetrics