Quantum Message-passing Algorithm For Optimal And Efficient Decoding

Republished By Plato

Followers: 0

Christophe Piveteau and Joseph M. Renes

Institute for Theoretical Physics, ETH Zürich, Switzerland

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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 $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.

► BibTeX data

@article{Piveteau2022quantummessage, doi = {10.22331/q-2022-08-23-784}, url = {https://doi.org/10.22331/q-2022-08-23-784}, title = {Quantum message-passing algorithm for optimal and efficient decoding}, author = {Piveteau, Christophe and Renes, Joseph M.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {6}, pages = {784}, month = aug, year = {2022} }

► References

[1] Joseph M. Renes “Belief Propagation Decoding of Quantum Channels by Passing Quantum Messages” New Journal of Physics 19, 072001 (2017).
https://doi.org/10.1088/1367-2630/aa7c78
arXiv:1607.04833
http://stacks.iop.org/1367-2630/19/i=7/a=072001

[2] Narayanan Rengaswamy, Kaushik P. Seshadreesan, Saikat Guha, and Henry D. Pfister, “Belief Propagation with Quantum Messages for Quantum-Enhanced Classical Communications” npj Quantum Information 7, 97 (2021).
https://doi.org/10.1038/s41534-021-00422-1
arXiv:2003.04356
https://www.nature.com/articles/s41534-021-00422-1

[3] S. Kudekar, T. Richardson, and R.L. Urbanke, “Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation” IEEE Transactions on Information Theory 59, 7761–7813 (2013).
https://doi.org/10.1109/TIT.2013.2280915
arXiv:1201.2999

[4] H. A. Loeliger and P. O. Vontobel “Factor Graphs for Quantum Probabilities” IEEE Transactions on Information Theory 63, 5642–5665 (2017).
https://doi.org/10.1109/TIT.2017.2716422
arXiv:1508.00689

[5] M. X. Cao and P. O. Vontobel “Double-Edge Factor Graphs: Definition, Properties, and Examples” 2017 IEEE Information Theory Workshop (ITW) 136–140 (2017).
https://doi.org/10.1109/ITW.2017.8277985
arXiv:1706.00752

[6] Hans-Andrea Loeliger “An Introduction to Factor Graphs” IEEE Signal Processing Magazine 21, 28–41 (2004).
https://doi.org/10.1109/MSP.2004.1267047

[7] V. P. Belavkin “Optimal Multiple Quantum Statistical Hypothesis Testing” Stochastics 1, 315 (1975).
https://doi.org/10.1080/17442507508833114

[8] Paul Hausladen and William K. Wootters “A `Pretty Good’ Measurement for Distinguishing Quantum States” Journal of Modern Optics 41, 2385 (1994).
https://doi.org/10.1080/09500349414552221

[9] Narayanan Rengaswamy and Henry D. Pfister “A Semiclassical Proof of Duality Between the Classical BSC and the Quantum PSC” (2021).
https://doi.org/10.48550/arXiv.2103.09225
arXiv:2103.09225

[10] Masashi Ban, Keiko Kurokawa, Rei Momose, and Osamu Hirota, “Optimum Measurements for Discrimination among Symmetric Quantum States and Parameter Estimation” International Journal of Theoretical Physics 36, 1269–1288 (1997).
https://doi.org/10.1007/BF02435921

[11] Masahide Sasaki, Kentaro Kato, Masayuki Izutsu, and Osamu Hirota, “Quantum Channels Showing Superadditivity in Classical Capacity” Physical Review A 58, 146–158 (1998).
https://doi.org/10.1103/PhysRevA.58.146

[12] Y.C. Eldar and Jr. Forney “On Quantum Detection and the Square-Root Measurement” IEEE Transactions on Information Theory 47, 858–872 (2001).
https://doi.org/10.1109/18.915636

[13] Tom Richardson and Rüdiger Urbanke “Modern Coding Theory” Cambridge University Press (2008).
https://doi.org/10.1017/CBO9780511791338

[14] David Poulin “Optimal and Efficient Decoding of Concatenated Quantum Block Codes” Physical Review A 74, 052333 (2006).
https://doi.org/10.1103/PhysRevA.74.052333

[15] David Poulin and Yeojin Chung “On the Iterative Decoding of Sparse Quantum Codes” Quantum Information and Computation 8, 987–1000 (2008).
https://doi.org/10.26421/QIC8.10-8
arXiv:0801.1241

[16] Yun-Jiang Wang, Barry C. Sanders, Bao-Ming Bai, and Xin-Mei Wang, “Enhanced Feedback Iterative Decoding of Sparse Quantum Codes” IEEE Transactions on Information Theory 58, 1231–1241 (2012).
https://doi.org/10.1109/TIT.2011.2169534
arXiv:0912.4546

[17] Ben Criger and Imran Ashraf “Multi-Path Summation for Decoding 2D Topological Codes” Quantum 2, 102 (2018).
https://doi.org/10.22331/q-2018-10-19-102
arXiv:1709.02154

[18] Ye-Hua Liu and David Poulin “Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes” Physical Review Letters 122, 200501 (2019).
https://doi.org/10.1103/PhysRevLett.122.200501
arXiv:1811.07835

[19] Alex Rigby, J. C. Olivier, and Peter Jarvis, “Modified Belief Propagation Decoders for Quantum Low-Density Parity-Check Codes” Physical Review A 100, 012330 (2019).
https://doi.org/10.1103/PhysRevA.100.012330
arXiv:1903.07404

[20] Pavel Panteleev and Gleb Kalachev “Degenerate Quantum LDPC Codes With Good Finite Length Performance” Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585

[21] July X. Li and Pascal O. Vontobel “Pseudocodeword-Based Decoding of Quantum Stabilizer Codes” 2019 IEEE International Symposium on Information Theory (ISIT) 2888–2892 (2019).
https://doi.org/10.1109/ISIT.2019.8849833
arXiv:1903.01202

[22] Joschka Roffe, David R. White, Simon Burton, and Earl Campbell, “Decoding across the Quantum Low-Density Parity-Check Code Landscape” Physical Review Research 2, 043423 (2020).
https://doi.org/10.1103/PhysRevResearch.2.043423
arXiv:2005.07016

[23] July X. Li, Joseph M. Renes, and Pascal O. Vontobel, “Pseudocodeword-Based Decoding of Quantum Color Codes” (2020).
https://doi.org/10.48550/arXiv.2010.10845
arXiv:2010.10845

[24] Srikar Kasi and Kyle Jamieson “Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks” Proceedings of the 26th Annual International Conference on Mobile Computing and Networking 1–14 (2020).
https://doi.org/10.1145/3372224.3419207
arXiv:2007.11069

[25] M.S. Leifer and D. Poulin “Quantum Graphical Models and Belief Propagation” Annals of Physics 323, 1899–1946 (2008).
https://doi.org/10.1016/j.aop.2007.10.001
arXiv:0708.1337
http://www.sciencedirect.com/science/article/pii/S0003491607001509

[26] H. A. Bethe “Statistical Theory of Superlattices” Proceedings of the Royal Society A 150, 552–575 (1935).
https://doi.org/10.1098/rspa.1935.0122
http://rspa.royalsocietypublishing.org/content/150/871/552

[27] Rudolf Peierls “Statistical Theory of Superlattices with Unequal Concentrations of the Components” Proceedings of the Royal Society A 154, 207–222 (1936).
https://doi.org/10.1098/rspa.1936.0047

[28] Jonathan S. Yedidia, William T. Freeman, and Yair Weiss, “Generalized Belief Propagation” Proceedings of the 13th International Conference on Neural Information Processing Systems 668–674 (2000).

[29] Jonathan S. Yedidia, William T. Freeman, and Yair Weiss, “Understanding Belief Propagation and Its Generalizations” Morgan Kaufmann Publishers Inc. (2003).
https://www.merl.com/publications/docs/TR2001-22.pdf

[30] J.S. Yedidia, W.T. Freeman, and Y. Weiss, “Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms” Information Theory, IEEE Transactions on 51, 2282–2312 (2005).
https://doi.org/10.1109/TIT.2005.850085

[31] M. B. Hastings “Quantum Belief Propagation: An Algorithm for Thermal Quantum Systems” Physical Review B 76, 201102 (2007).
https://doi.org/10.1103/PhysRevB.76.201102
arXiv:0706.4094

[32] David Poulin and Matthew B. Hastings “Markov Entropy Decomposition: A Variational Dual for Quantum Belief Propagation” Physical Review Letters 106, 080403 (2011).
https://doi.org/10.1103/PhysRevLett.106.080403
arXiv:1012.2050

[33] M. X. Cao and P. O. Vontobel “Quantum Factor Graphs: Closing-the-Box Operation and Variational Approaches” 2016 International Symposium on Information Theory and Its Applications (ISITA) 651–655 (2016).
https://ieeexplore.ieee.org/document/7840505

[34] F. R. Kschischang, B. J. Frey, and H. A. Loeliger, “Factor Graphs and the Sum-Product Algorithm” IEEE Transactions on Information Theory 47, 498–519 (2001).
https://doi.org/10.1109/18.910572

[35] G. David Forney “Codes on Graphs: Normal Realizations” IEEE Transactions on Information Theory 47, 520–548 (2001).
https://doi.org/10.1109/18.910573

[36] C. W. Helstrom “Quantum Detection and Estimation Theory” Academic (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http://www.sciencedirect.com/science/bookseries/00765392/123

[37] Saikat Guha “Structured Optical Receivers to Attain Superadditive Capacity and the Holevo Limit” Physical Review Letters 106, 240502 (2011).
https://doi.org/10.1103/PhysRevLett.106.240502
arXiv:1101.1550

[38] T. Etzion, A. Trachtenberg, and A. Vardy, “Which Codes Have Cycle-Free Tanner Graphs?” IEEE Transactions on Information Theory 45, 2173–2181 (1999).
https://doi.org/10.1109/18.782170

[39] Jacob C. Bridgeman and Christopher T. Chubb “Hand-Waving and Interpretive Dance: An Introductory Course on Tensor Networks” Journal of Physics A: Mathematical and Theoretical 50, 223001 (2017).
https://doi.org/10.1088/1751-8121/aa6dc3
arXiv:1603.03039
http://stacks.iop.org/1751-8121/50/i=22/a=223001

[40] Ville Bergholm, Juha J. Vartiainen, Mikko Mottonen, and Martti M. Salomaa, “Quantum Circuits with Uniformly Controlled One-Qubit Gates” Physical Review A 71, 052330 (2005).
https://doi.org/10.1103/PhysRevA.71.052330
http://arxiv.org/abs/quant-ph/0410066

[41] C. H. Bennett “Logical Reversibility of Computation” IBM Journal of Research and Development 17, 525–532 (1973).
https://doi.org/10.1147/rd.176.0525

[42] Richard P. Brent “Multiple-Precision Zero-Finding Methods and the Complexity of Elementary Function Evaluation” Academic Press (1976).
https://doi.org/10.1016/B978-0-12-697560-4.50014-9
arXiv:1004.3412
https://www.sciencedirect.com/science/article/pii/B9780126975604500149

[43] Harvey and van der Hoeven “Integer Multiplication in Time O(n Log n)” Annals of Mathematics 193, 563 (2021).
https://doi.org/10.4007/annals.2021.193.2.4

[44] Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub, and Sabre Kais, “Quantum Algorithm and Circuit Design Solving the Poisson Equation” New Journal of Physics 15, 013021 (2013).
https://doi.org/10.1088/1367-2630/15/1/013021
arXiv:1207.2485

[45] Mihir K. Bhaskar, Stuart Hadfield, Anargyros Papageorgiou, and Iasonas Petras, “Quantum Algorithms and Circuits for Scientific Computing” Quantum Information & Computation 16, 197–236 (2016).
https://doi.org/10.26421/QIC16.3-4-2
arXiv:1511.08253

[46] Thomas Häner, Martin Roetteler, and Krysta M. Svore, “Optimizing Quantum Circuits for Arithmetic” (2018).
https://doi.org/10.48550/arXiv.1805.12445
arXiv:1805.12445

[47] Shengbin Wang, Zhimin Wang, Wendong Li, Lixin Fan, Guolong Cui, Zhiqiang Wei, and Yongjian Gu, “Quantum Circuits Design for Evaluating Transcendental Functions Based on a Function-Value Binary Expansion Method” Quantum Information Processing 19, 347 (2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv:2001.00807

[48] John Watrous “The Theory of Quantum Information” Cambridge University Press (2018).
https://doi.org/10.1017/9781316848142
https://www.cambridge.org/core/product/identifier/9781316848142/type/book

[49] Dagmar Bruß, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello, and John A. Smolin, “Optimal Universal and State-Dependent Quantum Cloning” Physical Review A 57, 2368–2378 (1998).
https://doi.org/10.1103/PhysRevA.57.2368

[50] E. Arıkan “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels” IEEE Transactions on Information Theory 55, 3051–3073 (2009).
https://doi.org/10.1109/TIT.2009.2021379
arXiv:0807.3917

[51] Mark M. Wilde and Saikat Guha “Polar Codes for Classical-Quantum Channels” IEEE Transactions on Information Theory 59, 1175–1187 (2013).
https://doi.org/10.1109/TIT.2012.2218792
arXiv:1109.2591

[52] Joseph M. Renes and Mark M. Wilde “Polar Codes for Private and Quantum Communication Over Arbitrary Channels” IEEE Transactions on Information Theory 60, 3090–3103 (2014).
https://doi.org/10.1109/TIT.2014.2314463
arXiv:1212.2537

[53] S. Guha and M.M. Wilde “Polar Coding to Achieve the Holevo Capacity of a Pure-Loss Optical Channel” Proceedings of the 2012 IEEE International Symposium on Information Theory (ISIT) 546–550 (2012).
https://doi.org/10.1109/ISIT.2012.6284250
arXiv:1202.0533

Cited by

[1] S. Brandsen, Avijit Mandal, and Henry D. Pfister, “Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels”, arXiv:2207.04984.

The above citations are from SAO/NASA ADS (last updated successfully 2022-08-23 14:04:15). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2022-08-23 14:04:14: Could not fetch cited-by data for 10.22331/q-2022-08-23-784 from Crossref. This is normal if the DOI was registered recently.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

Time Stamp: August 23, 2022August 23, 2022

Time Stamp: Jun 22, 2023

Quantum message-passing algorithm for optimal and efficient decoding

Republished By Plato

Abstract

► BibTeX data

► References

Cited by

More from Quantum Journal

Quantum error correction with fractal topological codes

Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era

Continuous-Variable Entanglement through Central Forces: Application to Gravity between Quantum Masses

Quantifying EPR: the resource theory of nonclassicality of common-cause assemblages

Probing quantum entanglement from magnetic-sublevels populations: beyond spin squeezing inequalities

Robust phase-controlled gates for scalable atomic quantum processors using optical standing waves

LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States

Fast quantum transfer mediated by topological domain walls

About Us

Vertical Search & Ai

Platform

Stay Connected

Account