انسٹی ٹیوٹ برائے نظریاتی طبیعیات، ای ٹی ایچ زیورخ، سوئٹزرلینڈ
اس کاغذ کو دلچسپ لگتا ہے یا اس پر بات کرنا چاہتے ہیں؟ SciRate پر تبصرہ کریں یا چھوڑیں۔.
خلاصہ
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 ڈیٹا
► حوالہ جات
ہے [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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 2001.00807
ہے [48] جان واٹرس "دی تھیوری آف کوانٹم انفارمیشن" کیمبرج یونیورسٹی پریس (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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 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
آر ایکس سی: 1202.0533
کی طرف سے حوالہ دیا گیا
[1] S. Brandsen, Avijit Mandal, and Henry D. Pfister, “Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels”, آر ایکس سی: 2207.04984.
مذکورہ بالا اقتباسات سے ہیں۔ SAO/NASA ADS (آخری بار کامیابی کے ساتھ 2022-08-23 14:04:15)۔ فہرست نامکمل ہو سکتی ہے کیونکہ تمام ناشرین مناسب اور مکمل حوالہ ڈیٹا فراہم نہیں کرتے ہیں۔
نہیں لا سکا کراس ریف کا حوالہ دیا گیا ڈیٹا آخری کوشش کے دوران 2022-08-23 14:04:14: Crossref سے 10.22331/q-2022-08-23-784 کے لیے حوالہ کردہ ڈیٹا حاصل نہیں کیا جا سکا۔ یہ عام بات ہے اگر DOI حال ہی میں رجسٹر کیا گیا ہو۔
یہ مقالہ کوانٹم میں کے تحت شائع کیا گیا ہے۔ Creative Commons انتساب 4.0 انٹرنیشنل (CC BY 4.0) لائسنس کاپی رائٹ اصل کاپی رائٹ ہولڈرز جیسے مصنفین یا ان کے اداروں کے پاس رہتا ہے۔