Institut für Theoretische Physik, ETH Zürich, Schweiz
Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.
Abstrakt
Kürzlich hat Renes einen Quantenalgorithmus namens Belief Propagation with Quantum Messages (BPQM) zum Decodieren klassischer Daten vorgeschlagen, die mit einem binären linearen Code mit Baum-Tanner-Graph codiert sind, der über einen reinen CQ-Kanal übertragen wird [1], also ein Kanal mit klassischem Eingang und reinem Quantenausgang. Der Algorithmus stellt ein echtes Quantengegenstück zur Decodierung dar, die auf dem klassischen Belief-Propagation-Algorithmus basiert, der in der klassischen Codierungstheorie großen Erfolg hat, wenn er in Verbindung mit LDPC- oder Turbo-Codes verwendet wird. In jüngerer Zeit Rengaswamy $et$ $al.$ [2] beobachtete, dass BPQM den optimalen Decoder an einem kleinen Beispielcode implementiert, indem es die optimale Messung implementiert, die die Quantenausgabezustände für den Satz von Eingabecodewörtern mit der höchsten erreichbaren Wahrscheinlichkeit unterscheidet. Hier erweitern wir das Verständnis, den Formalismus und die Anwendbarkeit des BPQM-Algorithmus mit den folgenden Beiträgen erheblich. Zunächst beweisen wir analytisch, dass BPQM eine optimale Dekodierung für jeden binären linearen Code mit Baum-Tanner-Graph realisiert. Wir liefern auch die erste formale Beschreibung des BPQM-Algorithmus in vollem Detail und ohne Mehrdeutigkeit. Dabei identifizieren wir einen Schlüsselfehler, der im ursprünglichen Algorithmus und in nachfolgenden Arbeiten übersehen wurde, was impliziert, dass die Realisierung von Quantenschaltkreisen in der Code-Dimension exponentiell groß sein wird. Obwohl BPQM Quantennachrichten weiterleitet, werden andere vom Algorithmus benötigte Informationen global verarbeitet. Wir beheben dieses Problem, indem wir einen echten Message-Passing-Algorithmus formulieren, der sich BPQM annähert und eine Quantenschaltungskomplexität $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$ hat, wobei $n$ ist die Codelänge und $epsilon$ ist der Näherungsfehler. Schließlich schlagen wir auch eine neue Methode vor, um BPQM auf Faktorgraphen zu erweitern, die Zyklen enthalten, indem wir ungefähres Klonen verwenden. Wir zeigen einige vielversprechende numerische Ergebnisse, die darauf hindeuten, dass BPQM auf Faktorgraphen mit Zyklen den bestmöglichen klassischen Decoder deutlich übertreffen kann.
► BibTeX-Daten
► Referenzen
[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 und 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 und RL Urbanke, „Räumlich gekoppelte Ensembles erreichen universell Kapazität unter Glaubensausbreitung“, IEEE Transactions on Information Theory 59, 7761–7813 (2013).
https: / / doi.org/ 10.1109 / TIT.2013.2280915
arXiv: 1201.2999
[4] HA Loeliger und 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 und 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 und William K. Wootters „Eine „ziemlich gute“ Messung zur Unterscheidung von Quantenzuständen“, Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
[9] Narayanan Rengaswamy und Henry D. Pfister „Ein semiklassischer Beweis der Dualität zwischen der klassischen BSC und der Quanten-PSC“ (2021).
https:///doi.org/10.48550/arXiv.2103.09225
arXiv: 2103.09225
[10] Masashi Ban, Keiko Kurokawa, Rei Momose und 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 und 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 und 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 und 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 und 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 und 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 und 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 und 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 und 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 und Gleb Kalachev „Degenerierte Quanten-LDPC-Codes mit guter Leistung endlicher Länge“ Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] Juli X. Li und 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
arXiv: 1903.01202
[22] Joschka Roffe, David R. White, Simon Burton und 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 und Pascal O. Vontobel, „Pseudocodeword-Based Decoding of Quantum Color Codes“ (2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[24] Srikar Kasi und 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 und 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 „Statistische Theorie von Übergittern mit ungleichen Konzentrationen der Komponenten“ 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 und 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 und Yair Weiss, „Verständnis der Verbreitung von Überzeugungen und ihrer Verallgemeinerung“, Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publications/docs/TR2001-22.pdf
[30] JS Yedidia, WT Freeman und Y. Weiss, „Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms“ Informationstheorie, 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 und 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 und 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 und 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“ 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 Atain 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 und A. Vardy, „Welche Codes haben zyklusfreie Tanner-Diagramme?“ IEEE Transactions on Information Theory 45, 2173–2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
[39] Jacob C. Bridgeman und 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 und Martti M. Salomaa, „Quantum Circuits with Uniformally 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 und 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 und 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 und 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 und 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 und 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 „Die Theorie der Quanteninformation“ 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 und 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 „Kanalpolarisation: Eine Methode zum Erstellen von Codes zum Erreichen von Kapazitäten für gedächtnislose Kanäle mit symmetrischem Binäreingang“ IEEE Transactions on Information Theory 55, 3051–3073 (2009).
https: / / doi.org/ 10.1109 / TIT.2009.2021379
arXiv: 0807.3917
[51] Mark M. Wilde und Saikat Guha „Polarcodes für klassische Quantenkanäle“ IEEE Transactions on Information Theory 59, 1175–1187 (2013).
https: / / doi.org/ 10.1109 / TIT.2012.2218792
arXiv: 1109.2591
[52] Joseph M. Renes und Mark M. Wilde „Polarcodes für private und Quantenkommunikation über beliebige Kanäle“ IEEE Transactions on Information Theory 60, 3090–3103 (2014).
https: / / doi.org/ 10.1109 / TIT.2014.2314463
arXiv: 1212.2537
[53] S. Guha und MM Wilde „Polarcodierung zur Erreichung der Holevo-Kapazität eines optischen Kanals mit reinem Verlust“, 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
Zitiert von
[1] S. Brandsen, Avijit Mandal und Henry D. Pfister, „Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels“, arXiv: 2207.04984.
Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2022, 08:23:14 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.
Konnte nicht abrufen Crossref zitiert von Daten während des letzten Versuchs 2022-08-23 14:04:14: Von Crossref konnten keine zitierten Daten für 10.22331 / q-2022-08-23-784 abgerufen werden. Dies ist normal, wenn der DOI kürzlich registriert wurde.
Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.
