Quantum message-passing algorithm for optimal and efficient decoding
Quantum message-passing algorithm for optimal and efficient decoding
复制标题
DOI：
10.22331/q-2022-08-23-784
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
C. Piveteau;J. Renes
中科院分区：
文献类型：
--
作者：
C. Piveteau;J. Renes
最近，Renes 提出了一种称为量子消息置信传播 (BPQM) 的量子算法，用于解码使用带有树 Tanner 图的二进制线性码编码的经典数据，该数据通过纯态经典量子通道传输 [1]。该算法提供了基于经典置信传播算法的解码的真正量子对应物，该算法在与 LDPC 或 Turbo 码结合使用时在经典编码理论中取得了广泛的成功。在这里，我们通过以下贡献显着扩展了 BPQM 算法的理解、形式主义和适用性。首先，我们分析证明BPQM可以利用树Tanner图实现任意二进制线性码的最优解码。我们还提供了 BPQM 算法的第一个正式描述，详细且没有任何歧义。通过这样做，我们发现了原始算法中被忽视的一个关键缺陷，该缺陷导致量子电路实现的代码大小呈指数级增长。我们通过制定一个真正的消息传递算法来解决这个问题，该算法近似BPQM并具有电路复杂性，${\mathcal{O}}\left({{\text{ poly }}n{\text{, polylog }}\frac{1}{ \in }}\right)$，其中n是代码长度，ϵ是近似误差。最后，我们还提出了一种利用近似克隆将 BPQM 扩展到包含循环的因子图的新方法。
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 classical-quantum channel [1]. 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. 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 which causes quantum circuit realizations to be exponentially large in the code size. We remedy this problem by formulating a truly message-passing algorithm which approximates BPQM and has circuit complexity, ${\mathcal{O}}\left({{\text{ poly }}n{\text{, polylog }}\frac{1}{ \in }}\right)$, 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.