Institutet för teoretisk fysik, ETH Zürich, Schweiz
Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.
Abstrakt
Nyligen föreslog Renes en kvantalgoritm som kallas belief propagation with quantum messages (BPQM) för avkodning av klassisk data kodad med en binär linjär kod med träd Tanner-graf som sänds över en ren-state CQ-kanal [1], dvs en kanal med klassisk ingång och kvantutsignal i rent tillstånd. Algoritmen presenterar en äkta kvantmotsvarighet till avkodning baserad på den klassiska trosutbredningsalgoritmen, som har rönt stor framgång i klassisk kodningsteori när den används i kombination med LDPC- eller Turbo-koder. Senare Rengaswamy $et$ $al.$ [2] observerade att BPQM implementerar den optimala avkodaren på en liten exempelkod, genom att den implementerar den optimala mätningen som särskiljer kvantutdatatillstånden för uppsättningen inmatade kodord med högst möjliga sannolikhet. Här utökar vi avsevärt förståelsen, formalismen och tillämpbarheten av BPQM-algoritmen med följande bidrag. Först bevisar vi analytiskt att BPQM realiserar optimal avkodning för vilken binär linjär kod som helst med träd Tanner-graf. Vi tillhandahåller också den första formella beskrivningen av BPQM-algoritmen i full detalj och utan någon tvetydighet. Genom att göra så identifierar vi ett nyckelfel som förbises i den ursprungliga algoritmen och efterföljande arbeten som innebär att kvantkretsförverkliganden kommer att vara exponentiellt stora i koddimensionen. Även om BPQM skickar kvantmeddelanden, bearbetas annan information som krävs av algoritmen globalt. Vi löser detta problem genom att formulera en verkligt meddelandeöverförande algoritm som approximerar BPQM och har kvantkretskomplexitet $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, där $n$ är kodens längd och $epsilon$ är approximationsfelet. Slutligen föreslår vi också en ny metod för att utöka BPQM till faktorgrafer som innehåller cykler genom att använda ungefärlig kloning. Vi visar några lovande numeriska resultat som indikerar att BPQM på faktorgrafer med cykler avsevärt kan överträffa den bästa möjliga klassiska dekodern.
► BibTeX-data
► Referenser
[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 och 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 och RL 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] HA Loeliger och PO 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] MX Cao och PO 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] VP Belavkin "Optimal Multiple Quantum Statistical Hypothesis Testing" Stochastics 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114
[8] Paul Hausladen och 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 och 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 och Osamu Hirota, "Optimal 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 och 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] YC Eldar och 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 och Rüdiger Urbanke "Modern Coding Theory" Cambridge University Press (2008).
https: / / doi.org/ 10.1017 / CBO9780511791338
[14] David Poulin "Optimal och effektiv avkodning av sammanfogade kvantblockkoder" Fysisk granskning A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
[15] David Poulin och Yeojin Chung "Om iterativ avkodning av glesa kvantkoder" 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 och 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 och 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 och 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, JC Olivier och 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 och 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] Juli X. Li och Pascal O. Vontobel "Pseudokodord-baserad avkodning av kvantstabilisatorkoder" 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 och 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] Juli X. Li, Joseph M. Renes och Pascal O. Vontobel, "Pseudokodord-baserad avkodning av kvantfärgskoder" (2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[24] Srikar Kasi och Kyle Jamieson "Mot 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] MS Leifer och 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/ vetenskap / artikel / PII / S0003491607001509
[26] HA 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 "Statistisk teori om supergitter med ojämna koncentrationer av komponenterna" 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 och 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 och Yair Weiss, "Understanding belief propagation and its generalizations" Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publications/docs/TR2001-22.pdf
[30] JS Yedidia, WT Freeman och 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] MB 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 och 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] MX Cao och PO Vontobel "Quantum Factor Graphs: Closing-the-Box Operation and Variational Approaches" 2016 Internationellt symposium om informationsteori och dess tillämpningar (ISITA) 651–655 (2016).
https: / / ieeexplore.ieee.org/ dokument / 7840505
[34] FR Kschischang, BJ Frey och HA 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] CW Helstrom "Quantum Detection and Estimation Theory" Akademisk (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 och A. Vardy, "Vilka koder har cykelfria garvningsdiagram?" IEEE Transactions on Information Theory 45, 2173–2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
[39] Jacob C. Bridgeman och 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 och 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] CH 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 och 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 och 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 och 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 och 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 och 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/bok
[49] Dagmar Bruß, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello och 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 "Kanalpolarisering: En metod för att konstruera kapacitetsuppnående koder för symmetriska binära ingångsminneslösa kanaler" IEEE Transactions on Information Theory 55, 3051–3073 (2009).
https: / / doi.org/ 10.1109 / TIT.2009.2021379
arXiv: 0807.3917
[51] Mark M. Wilde och 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 och Mark M. Wilde "Polära koder för privat och kvantkommunikation över godtyckliga kanaler" IEEE Transactions on Information Theory 60, 3090–3103 (2014).
https: / / doi.org/ 10.1109 / TIT.2014.2314463
arXiv: 1212.2537
[53] S. Guha och MM Wilde "Polär kodning för att uppnå Holevo-kapaciteten hos en optisk kanal med ren förlust" Proceedings från 2012 IEEE International Symposium on Information Theory (ISIT) 546–550 (2012).
https: / ⠀ </ ⠀ <doi.org/†<10.1109 / ⠀ <ISIT.2012.6284250
arXiv: 1202.0533
Citerad av
[1] S. Brandsen, Avijit Mandal och Henry D. Pfister, "Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels", arXiv: 2207.04984.
Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2022-08-23 14:04:15). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.
Det gick inte att hämta Crossref citerade data under senaste försöket 2022-08-23 14:04:14: Det gick inte att hämta citerade data för 10.22331 / q-2022-08-23-784 från Crossref. Detta är normalt om DOI registrerades nyligen.
Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.
