Institut for Teoretisk Fysik, ETH Zürich, Schweiz
Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.
Abstrakt
For nylig foreslog Renes en kvantealgoritme kaldet belief propagation with quantum messages (BPQM) til afkodning af klassiske data kodet ved hjælp af en binær lineær kode med træ Tanner-graf, der transmitteres over en ren-state CQ-kanal [1], dvs. en kanal med klassisk input og pure-state quantum output. Algoritmen præsenterer et ægte kvantemodstykke til afkodning baseret på den klassiske trosforplantningsalgoritme, som har fundet stor succes i klassisk kodningsteori, når den bruges sammen med LDPC- eller Turbo-koder. Senere Rengaswamy $et$ $al.$ [2] observerede, at BPQM implementerer den optimale dekoder på en lille eksempelkode, idet den implementerer den optimale måling, der adskiller kvanteoutputtilstandene for sættet af inputkodeord med højest opnåelige sandsynlighed. Her udvider vi betydeligt forståelsen, formalismen og anvendeligheden af BPQM-algoritmen med følgende bidrag. For det første beviser vi analytisk, at BPQM realiserer optimal afkodning for enhver binær lineær kode med træ Tanner-graf. Vi giver også den første formelle beskrivelse af BPQM-algoritmen i fuld detaljer og uden nogen tvetydighed. Ved at gøre det identificerer vi en nøglefejl, der er overset i den originale algoritme, og efterfølgende værker, som indebærer, at kvantekredsløbsrealiseringer vil være eksponentielt store i kodedimensionen. Selvom BPQM videregiver kvantemeddelelser, behandles anden information, der kræves af algoritmen, globalt. Vi afhjælper dette problem ved at formulere en virkelig meddelelsesoverførselsalgoritme, som tilnærmer BPQM og har kvantekredsløbskompleksitet $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, hvor $n$ er kodelængden og $epsilon$ er tilnærmelsesfejlen. Endelig foreslår vi også en ny metode til at udvide BPQM til faktorgrafer indeholdende cyklusser ved at gøre brug af omtrentlig kloning. Vi viser nogle lovende numeriske resultater, der indikerer, at BPQM på faktorgrafer med cyklusser kan udkonkurrere den bedst mulige klassiske dekoder.
► BibTeX-data
► Referencer
[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 og 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 og 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 og 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 og 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 og 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 og 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 og Osamu Hirota, "Optimale målinger for diskrimination blandt symmetriske kvantetilstande og parameterestimering" International Journal of Theoretical Physics 36, 1269-1288 (1997).
https:///doi.org/10.1007/BF02435921
[11] Masahide Sasaki, Kentaro Kato, Masayuki Izutsu og Osamu Hirota, "Quantum Channels Showing Superadditivity in Classical Capacity" Fysisk gennemgang A 58, 146-158 (1998).
https:///doi.org/10.1103/PhysRevA.58.146
[12] YC Eldar og 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 og Rüdiger Urbanke "Modern Coding Theory" Cambridge University Press (2008).
https:///doi.org/10.1017/CBO9780511791338
[14] David Poulin "Optimal og effektiv afkodning af sammenkædede kvanteblokkoder" Fysisk gennemgang A 74, 052333 (2006).
https:///doi.org/10.1103/PhysRevA.74.052333
[15] David Poulin og 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 og 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 og 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 og 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 og 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 og Gleb Kalachev "Degenererede 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 og Pascal O. Vontobel "Pseudokodeord-baseret dekodning af kvantestabilisatorkoder" 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 og 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 og Pascal O. Vontobel, "Pseudokodeord-baseret afkodning af kvantefarvekoder" (2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[24] Srikar Kasi og Kyle Jamieson "Mod 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 og 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] 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 ulige koncentrationer af komponenterne" 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 og Yair Weiss, "Generalized Belief Propagation" Proceedings of the 13th International Conference on Neurale Information Processing Systems 668-674 (2000).
[29] Jonathan S. Yedidia, William T. Freeman og 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 og 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 og 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 og PO 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] FR Kschischang, BJ Frey og 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 og A. Vardy, "Hvilke koder har cyklusfrie garvergrafer?" IEEE Transactions on Information Theory 45, 2173-2181 (1999).
https:///doi.org/10.1109/18.782170
[39] Jacob C. Bridgeman og 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 og 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 og 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 og 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 og 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 og 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 og 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/bog
[49] Dagmar Bruß, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello og 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 metode til at konstruere kapacitets-opnående koder for symmetriske binære-input hukommelsesløse 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 og 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 og Mark M. Wilde "Polære koder for privat og kvantekommunikation over vilkårlige kanaler" IEEE Transactions on Information Theory 60, 3090–3103 (2014).
https:///doi.org/10.1109/TIT.2014.2314463
arXiv: 1212.2537
[53] S. Guha og MM Wilde "Polar kodning for at opnå Holevo-kapaciteten af en optisk kanal med rent tab" Proceedings fra 2012 IEEE International Symposium on Information Theory (ISIT) 546-550 (2012).
https:///doi.org/10.1109/ISIT.2012.6284250
arXiv: 1202.0533
Citeret af
[1] S. Brandsen, Avijit Mandal og Henry D. Pfister, "Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels", arXiv: 2207.04984.
Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2022-08-23 14:04:15). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.
Kunne ikke hente Crossref citeret af data under sidste forsøg 2022-08-23 14:04:14: Kunne ikke hente citerede data for 10.22331/q-2022-08-23-784 fra Crossref. Dette er normalt, hvis DOI blev registreret for nylig.
Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.
