Instituut voor Theoretische Fysica, ETH Zürich, Zwitserland
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
Onlangs heeft Renes een kwantumalgoritme voorgesteld met de naam geloofspropagatie met kwantumberichten (BPQM) voor het decoderen van klassieke gegevens die zijn gecodeerd met behulp van een binaire lineaire code met een boom Tanner-grafiek die wordt verzonden via een zuiver CQ-kanaal [1], dwz een kanaal met klassieke invoer en zuivere kwantumuitvoer. Het algoritme biedt een echte kwantumtegenhanger van decodering op basis van het klassieke algoritme voor het verspreiden van overtuigingen, dat veel succes heeft gevonden in de klassieke coderingstheorie wanneer het wordt gebruikt in combinatie met LDPC- of Turbo-codes. Meer recent Rengaswamy $et$ $al.$ [2] merkte op dat BPQM de optimale decoder implementeert op een kleine voorbeeldcode, in die zin dat het de optimale meting implementeert die de kwantumuitvoerstatussen onderscheidt voor de set invoercodewoorden met de hoogst haalbare waarschijnlijkheid. Hier breiden we het begrip, formalisme en toepasbaarheid van het BPQM-algoritme aanzienlijk uit met de volgende bijdragen. Eerst bewijzen we analytisch dat BPQM optimale decodering realiseert voor elke binaire lineaire code met een boom Tanner-grafiek. We geven ook de eerste formele beschrijving van het BPQM-algoritme in volledig detail en zonder enige dubbelzinnigheid. Door dit te doen, identificeren we een sleutelfout die over het hoofd is gezien in het oorspronkelijke algoritme en daaropvolgende werken, wat impliceert dat realisaties van kwantumcircuits exponentieel groot zullen zijn in de codedimensie. Hoewel BPQM kwantumberichten doorgeeft, wordt andere door het algoritme vereiste informatie wereldwijd verwerkt. We lossen dit probleem op door een echt berichtendoorlatend algoritme te formuleren dat BPQM benadert en de complexiteit van het kwantumcircuit $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$ heeft, waarbij $n$ is de codelengte en $epsilon$ is de benaderingsfout. Ten slotte stellen we ook een nieuwe methode voor om BPQM uit te breiden naar factorgrafieken die cycli bevatten door gebruik te maken van benaderend klonen. We laten enkele veelbelovende numerieke resultaten zien die aangeven dat BPQM op factorgrafieken met cycli aanzienlijk beter kan presteren dan de best mogelijke klassieke decoder.
► BibTeX-gegevens
► Referenties
[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 en Henry D. Pfister, "Overtuigingsvoortplanting met kwantumberichten voor kwantumverbeterde klassieke communicatie" npj Quantum Information 7, 97 (2021).
https://doi.org/10.1038/s41534-021-00422-1
arXiv: 2003.04356
https: / / www.nature.com/ artikelen / s41534-021-00422-1
[3] S. Kudekar, T. Richardson en 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 en PO Vontobel "Factorgrafieken voor kwantumkansen" IEEE Transactions on Information Theory 63, 5642–5665 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2716422
arXiv: 1508.00689
[5] MX Cao en PO Vontobel "Double-Edge Factor Graphs: definitie, eigenschappen en voorbeelden" 2017 IEEE Information Theory Workshop (ITW) 136–140 (2017).
https: / / doi.org/ 10.1109 / ITW.2017.8277985
arXiv: 1706.00752
[6] Hans-Andrea Loeliger "Een inleiding tot factorgrafieken" 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 en William K. Wootters "Een 'redelijk goede' meting voor het onderscheiden van kwantumtoestanden" Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
[9] Narayanan Rengaswamy en Henry D. Pfister "Een semi-klassiek bewijs van dualiteit tussen de klassieke BSC en de Quantum PSC" (2021).
https://doi.org/10.48550/arXiv.2103.09225
arXiv: 2103.09225
[10] Masashi Ban, Keiko Kurokawa, Rei Momose en Osamu Hirota, "Optimum Measurements for Discrimination between 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 en Osamu Hirota, "Quantumkanalen die superadditiviteit tonen in klassieke hoedanigheid" Physical Review A 58, 146–158 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.146
[12] YC Eldar en Jr. Forney "Over kwantumdetectie en de vierkantswortelmeting" IEEE Transactions on Information Theory 47, 858-872 (2001).
https: / / doi.org/ 10.1109 / 18.915636
[13] Tom Richardson en Rüdiger Urbanke "Moderne coderingstheorie" Cambridge University Press (2008).
https: / / doi.org/ 10.1017 / CBO9780511791338
[14] David Poulin "Optimale en efficiënte decodering van aaneengeschakelde kwantumblokcodes" Physical Review A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
[15] David Poulin en Yeojin Chung "Over de iteratieve decodering van schaarse kwantumcodes" Kwantuminformatie en -berekening 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 en 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 en Imran Ashraf "Multi-Path Sommation 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 en 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 en 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 en Gleb Kalachev "Gedegenereerde Quantum LDPC-codes met goede eindige lengteprestaties" Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] Juli X. Li en Pascal O. Vontobel "Pseudocodewoord-gebaseerde decodering van kwantumstabilisatorcodes" 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 en 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 en Pascal O. Vontobel, "Pseudocodewoord-gebaseerde decodering van kwantumkleurcodes" (2020).
https://doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[24] Srikar Kasi en 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] MS Leifer en 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 "Statistische theorie van superroosters" 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 "Statistische theorie van superroosters met ongelijke concentraties van de componenten" 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 en 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 en 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 en Y. Weiss, "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms" Informatietheorie, IEEE Transactions on 51, 2282–2312 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.850085
[31] MB Hastings "Quantum Belief Propagation: een algoritme voor thermische kwantumsystemen" Physical Review B 76, 201102 (2007).
https: / / doi.org/ 10.1103 / PhysRevB.76.201102
arXiv: 0706.4094
[32] David Poulin en 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 en PO Vontobel "Quantum Factor Graphs: Closing-the-Box Operation and Variational Approaches" 2016 Internationaal symposium over informatietheorie en haar toepassingen (ISITA) 651-655 (2016).
https: / / ieeexplore.ieee.org/ document / 7840505
[34] FR Kschischang, BJ Frey en HA Loeliger, "Factorgrafieken en het somproductalgoritme" IEEE Transactions on Information Theory 47, 498-519 (2001).
https: / / doi.org/ 10.1109 / 18.910572
[35] G. David Forney "Codes op grafieken: normale realisaties" IEEE Transactions on Information Theory 47, 520-548 (2001).
https: / / doi.org/ 10.1109 / 18.910573
[36] CW 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 "Gestructureerde optische ontvangers om superadditieve capaciteit en de Holevo-limiet te bereiken" Physical Review Letters 106, 240502 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.240502
arXiv: 1101.1550
[38] T. Etzion, A. Trachtenberg en A. Vardy, "Welke codes hebben cyclusvrije Tanner-grafieken?" IEEE-transacties op informatietheorie 45, 2173-2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
[39] Jacob C. Bridgeman en 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 en 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 "Logische omkeerbaarheid van berekeningen" 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 en 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 en Saber Kais, "Quantumalgoritme en circuitontwerp voor het oplossen van de Poisson-vergelijking" 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 en Iasonas Petras, "Quantumalgoritmen en circuits voor wetenschappelijke berekeningen", 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 en 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 en 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 "De theorie van kwantuminformatie" 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 en 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 en 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 en 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 en MM 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
Geciteerd door
[1] S. Brandsen, Avijit Mandal en Henry D. Pfister, "Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels", arXiv: 2207.04984.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2022-08-23 14:04:15). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
Kon niet ophalen Door Crossref geciteerde gegevens tijdens laatste poging 2022-08-23 14:04:14: kon niet geciteerde gegevens voor 10.22331 / q-2022-08-23-784 niet ophalen van Crossref. Dit is normaal als de DOI recent is geregistreerd.
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
