{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T17:09:35Z","timestamp":1779210575813,"version":"3.51.4"},"reference-count":53,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T00:00:00Z","timestamp":1661212800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["20QT21_187724"],"award-info":[{"award-number":["20QT21_187724"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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 \\cite{renes_2017}, 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 e<\/mml:mi>t<\/mml:mi><\/mml:math>a<\/mml:mi>l<\/mml:mi>.<\/mml:mo><\/mml:math> \\cite{rengaswamy_2020} 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<\/mml:mi><\/mml:mrow>(<\/mml:mo>poly&#xA0;<\/mml:mtext>n<\/mml:mi>,<\/mml:mo>polylog&#xA0;<\/mml:mtext>1<\/mml:mn>&#x03F5;<\/mml:mi><\/mml:mfrac>)<\/mml:mo><\/mml:math>, where n<\/mml:mi><\/mml:math> is the code length and &#x03F5;<\/mml:mi><\/mml:math> 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.<\/jats:p>","DOI":"10.22331\/q-2022-08-23-784","type":"journal-article","created":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T14:29:41Z","timestamp":1661264981000},"page":"784","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":9,"title":["Quantum message-passing algorithm for optimal and efficient decoding"],"prefix":"10.22331","volume":"6","author":[{"given":"Christophe","family":"Piveteau","sequence":"first","affiliation":[{"name":"Institute for Theoretical Physics, ETH Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph M.","family":"Renes","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, ETH Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2022,8,23]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Joseph M. Renes ``Belief Propagation Decoding of Quantum Channels by Passing Quantum Messages'' New Journal of Physics 19, 072001 (2017).","DOI":"10.1088\/1367-2630\/aa7c78"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/s41534-021-00422-1"},{"key":"2","doi-asserted-by":"publisher","unstructured":"S. Kudekar, T. Richardson, and R.L. Urbanke, ``Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation'' IEEE Transactions on Information Theory 59, 7761\u20137813 (2013).","DOI":"10.1109\/TIT.2013.2280915"},{"key":"3","doi-asserted-by":"publisher","unstructured":"H. A. Loeligerand P. O. Vontobel ``Factor Graphs for Quantum Probabilities'' IEEE Transactions on Information Theory 63, 5642\u20135665 (2017).","DOI":"10.1109\/TIT.2017.2716422"},{"key":"4","doi-asserted-by":"publisher","unstructured":"M. X. Caoand P. O. Vontobel ``Double-Edge Factor Graphs: Definition, Properties, and Examples'' 2017 IEEE Information Theory Workshop (ITW) 136\u2013140 (2017).","DOI":"10.1109\/ITW.2017.8277985"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Hans-Andrea Loeliger ``An Introduction to Factor Graphs'' IEEE Signal Processing Magazine 21, 28\u201341 (2004).","DOI":"10.1109\/MSP.2004.1267047"},{"key":"6","doi-asserted-by":"publisher","unstructured":"V. P. Belavkin ``Optimal Multiple Quantum Statistical Hypothesis Testing'' Stochastics 1, 315 (1975).","DOI":"10.1080\/17442507508833114"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Paul Hausladenand William K. Wootters ``A `Pretty Good' Measurement for Distinguishing Quantum States'' Journal of Modern Optics 41, 2385 (1994).","DOI":"10.1080\/09500349414552221"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Narayanan Rengaswamyand Henry D. Pfister ``A Semiclassical Proof of Duality Between the Classical BSC and the Quantum PSC'' (2021).","DOI":"10.48550\/arXiv.2103.09225"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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\u20131288 (1997).","DOI":"10.1007\/BF02435921"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Masahide Sasaki, Kentaro Kato, Masayuki Izutsu, and Osamu Hirota, ``Quantum Channels Showing Superadditivity in Classical Capacity'' Physical Review A 58, 146\u2013158 (1998).","DOI":"10.1103\/PhysRevA.58.146"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Y.C. Eldarand Jr. Forney ``On Quantum Detection and the Square-Root Measurement'' IEEE Transactions on Information Theory 47, 858\u2013872 (2001).","DOI":"10.1109\/18.915636"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Tom Richardsonand R\u00fcdiger Urbanke ``Modern Coding Theory'' Cambridge University Press (2008).","DOI":"10.1017\/CBO9780511791338"},{"key":"13","doi-asserted-by":"publisher","unstructured":"David Poulin ``Optimal and Efficient Decoding of Concatenated Quantum Block Codes'' Physical Review A 74, 052333 (2006).","DOI":"10.1103\/PhysRevA.74.052333"},{"key":"14","doi-asserted-by":"publisher","unstructured":"David Poulinand Yeojin Chung ``On the Iterative Decoding of Sparse Quantum Codes'' Quantum Information and Computation 8, 987\u20131000 (2008).","DOI":"10.26421\/QIC8.10-8"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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\u20131241 (2012).","DOI":"10.1109\/TIT.2011.2169534"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Ben Crigerand Imran Ashraf ``Multi-Path Summation for Decoding 2D Topological Codes'' Quantum 2, 102 (2018).","DOI":"10.22331\/q-2018-10-19-102"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Ye-Hua Liuand David Poulin ``Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes'' Physical Review Letters 122, 200501 (2019).","DOI":"10.1103\/PhysRevLett.122.200501"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.100.012330"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Pavel Panteleevand Gleb Kalachev ``Degenerate Quantum LDPC Codes With Good Finite Length Performance'' Quantum 5, 585 (2021).","DOI":"10.22331\/q-2021-11-22-585"},{"key":"20","doi-asserted-by":"publisher","unstructured":"July X. Liand Pascal O. Vontobel ``Pseudocodeword-Based Decoding of Quantum Stabilizer Codes'' 2019 IEEE International Symposium on Information Theory (ISIT) 2888\u20132892 (2019).","DOI":"10.1109\/ISIT.2019.8849833"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevResearch.2.043423"},{"key":"22","doi-asserted-by":"publisher","unstructured":"July X. Li, Joseph M. Renes, and Pascal O. Vontobel, ``Pseudocodeword-Based Decoding of Quantum Color Codes'' (2020).","DOI":"10.48550\/arXiv.2010.10845"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Srikar Kasiand 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\u201314 (2020).","DOI":"10.1145\/3372224.3419207"},{"key":"24","doi-asserted-by":"publisher","unstructured":"M.S. Leiferand D. Poulin ``Quantum Graphical Models and Belief Propagation'' Annals of Physics 323, 1899\u20131946 (2008).","DOI":"10.1016\/j.aop.2007.10.001"},{"key":"25","doi-asserted-by":"publisher","unstructured":"H. A. Bethe ``Statistical Theory of Superlattices'' Proceedings of the Royal Society A 150, 552\u2013575 (1935).","DOI":"10.1098\/rspa.1935.0122"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Rudolf Peierls ``Statistical Theory of Superlattices with Unequal Concentrations of the Components'' Proceedings of the Royal Society A 154, 207\u2013222 (1936).","DOI":"10.1098\/rspa.1936.0047"},{"key":"27","unstructured":"Jonathan S. Yedidia, William T. Freeman, and Yair Weiss, ``Generalized Belief Propagation'' Proceedings of the 13th International Conference on Neural Information Processing Systems 668\u2013674 (2000)."},{"key":"28","unstructured":"Jonathan S. Yedidia, William T. Freeman, and Yair Weiss, ``Understanding Belief Propagation and Its Generalizations'' Morgan Kaufmann Publishers Inc. (2003)."},{"key":"29","doi-asserted-by":"publisher","unstructured":"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\u20132312 (2005).","DOI":"10.1109\/TIT.2005.850085"},{"key":"30","doi-asserted-by":"publisher","unstructured":"M. B. Hastings ``Quantum Belief Propagation: An Algorithm for Thermal Quantum Systems'' Physical Review B 76, 201102 (2007).","DOI":"10.1103\/PhysRevB.76.201102"},{"key":"31","doi-asserted-by":"publisher","unstructured":"David Poulinand Matthew B. Hastings ``Markov Entropy Decomposition: A Variational Dual for Quantum Belief Propagation'' Physical Review Letters 106, 080403 (2011).","DOI":"10.1103\/PhysRevLett.106.080403"},{"key":"32","unstructured":"M. X. Caoand P. O. Vontobel ``Quantum Factor Graphs: Closing-the-Box Operation and Variational Approaches'' 2016 International Symposium on Information Theory and Its Applications (ISITA) 651\u2013655 (2016)."},{"key":"33","doi-asserted-by":"publisher","unstructured":"F. R. Kschischang, B. J. Frey, and H. A. Loeliger, ``Factor Graphs and the Sum-Product Algorithm'' IEEE Transactions on Information Theory 47, 498\u2013519 (2001).","DOI":"10.1109\/18.910572"},{"key":"34","doi-asserted-by":"publisher","unstructured":"G. David Forney ``Codes on Graphs: Normal Realizations'' IEEE Transactions on Information Theory 47, 520\u2013548 (2001).","DOI":"10.1109\/18.910573"},{"key":"35","doi-asserted-by":"publisher","unstructured":"C. W. Helstrom ``Quantum Detection and Estimation Theory'' Academic (1976).","DOI":"10.1016\/S0076-5392(08)60247-7"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Saikat Guha ``Structured Optical Receivers to Attain Superadditive Capacity and the Holevo Limit'' Physical Review Letters 106, 240502 (2011).","DOI":"10.1103\/PhysRevLett.106.240502"},{"key":"37","doi-asserted-by":"publisher","unstructured":"T. Etzion, A. Trachtenberg, and A. Vardy, ``Which Codes Have Cycle-Free Tanner Graphs?'' IEEE Transactions on Information Theory 45, 2173\u20132181 (1999).","DOI":"10.1109\/18.782170"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Jacob C. Bridgemanand Christopher T. Chubb ``Hand-Waving and Interpretive Dance: An Introductory Course on Tensor Networks'' Journal of Physics A: Mathematical and Theoretical 50, 223001 (2017).","DOI":"10.1088\/1751-8121\/aa6dc3"},{"key":"39","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.71.052330"},{"key":"40","doi-asserted-by":"publisher","unstructured":"C. H. Bennett ``Logical Reversibility of Computation'' IBM Journal of Research and Development 17, 525\u2013532 (1973).","DOI":"10.1147\/rd.176.0525"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Richard P. Brent ``Multiple-Precision Zero-Finding Methods and the Complexity of Elementary Function Evaluation'' Academic Press (1976).","DOI":"10.1016\/B978-0-12-697560-4.50014-9"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Harveyand van der Hoeven ``Integer Multiplication in Time O(n Log n)'' Annals of Mathematics 193, 563 (2021).","DOI":"10.4007\/annals.2021.193.2.4"},{"key":"43","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088\/1367-2630\/15\/1\/013021"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Mihir K. Bhaskar, Stuart Hadfield, Anargyros Papageorgiou, and Iasonas Petras, ``Quantum Algorithms and Circuits for Scientific Computing'' Quantum Information & Computation 16, 197\u2013236 (2016).","DOI":"10.26421\/QIC16.3-4-2"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Thomas H\u00e4ner, Martin Roetteler, and Krysta M. Svore, ``Optimizing Quantum Circuits for Arithmetic'' (2018).","DOI":"10.48550\/arXiv.1805.12445"},{"key":"46","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1007\/s11128-020-02855-7"},{"key":"47","doi-asserted-by":"publisher","unstructured":"John Watrous ``The Theory of Quantum Information'' Cambridge University Press (2018).","DOI":"10.1017\/9781316848142"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Dagmar Bru\u00df, 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\u20132378 (1998).","DOI":"10.1103\/PhysRevA.57.2368"},{"key":"49","doi-asserted-by":"publisher","unstructured":"E. Ar\u0131kan ``Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels'' IEEE Transactions on Information Theory 55, 3051\u20133073 (2009).","DOI":"10.1109\/TIT.2009.2021379"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Mark M. Wildeand Saikat Guha ``Polar Codes for Classical-Quantum Channels'' IEEE Transactions on Information Theory 59, 1175\u20131187 (2013).","DOI":"10.1109\/TIT.2012.2218792"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Joseph M. Renesand Mark M. Wilde ``Polar Codes for Private and Quantum Communication Over Arbitrary Channels'' IEEE Transactions on Information Theory 60, 3090\u20133103 (2014).","DOI":"10.1109\/TIT.2014.2314463"},{"key":"52","doi-asserted-by":"publisher","unstructured":"S. Guhaand 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\u2013550 (2012).","DOI":"10.1109\/ISIT.2012.6284250"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-08-23-784\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,4,11]],"date-time":"2024-04-11T14:00:28Z","timestamp":1712844028000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-08-23-784\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,23]]},"references-count":53,"URL":"https:\/\/doi.org\/10.22331\/q-2022-08-23-784","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,23]]},"article-number":"784"}}