Institute for Theoretical Physics, ETH Zürich, Svájc
Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.
Absztrakt
A közelmúltban Renes egy kvantum-algoritmust javasolt, amelyet hiedelemterjesztésnek kvantumüzenetekkel (BPQM) neveztek a bináris lineáris kóddal kódolt klasszikus adatok dekódolására fa Tanner-gráffal, amelyet egy tiszta állapotú CQ csatornán továbbítanak.1], azaz egy csatorna klasszikus bemenettel és tiszta állapotú kvantumkimenettel. Az algoritmus a klasszikus hiedelem-terjesztési algoritmuson alapuló dekódolás valódi kvantum megfelelőjét mutatja be, amely széles körű sikert aratott a klasszikus kódoláselméletben, ha LDPC vagy Turbo kódokkal együtt használják. Újabban Rengaswamy $et$ $al.$ [2] megfigyelte, hogy a BPQM az optimális dekódert egy kis példakódon valósítja meg, vagyis olyan optimális mérést valósít meg, amely a bemeneti kódszavak kvantumkimeneti állapotait a legnagyobb elérhető valószínűséggel megkülönbözteti. Itt jelentősen bővítjük a BPQM algoritmus megértését, formalizmusát és alkalmazhatóságát a következő hozzájárulásokkal. Először is, analitikusan bizonyítjuk, hogy a BPQM optimális dekódolást valósít meg bármilyen bináris lineáris kódra fa Tanner gráf segítségével. A BPQM algoritmus első formális leírását is megadjuk teljes részletességgel és minden félreértés nélkül. Ennek során azonosítunk egy kulcsfontosságú hibát, amelyet az eredeti algoritmus figyelmen kívül hagyott, és a későbbi munkák arra utalnak, hogy a kvantumáramkörök megvalósítása exponenciálisan nagy lesz a kóddimenzióban. Bár a BPQM kvantumüzeneteket ad át, az algoritmus által igényelt egyéb információkat globálisan dolgozza fel. Ezt a problémát úgy orvosoljuk, hogy megfogalmazunk egy valóban üzenettovábbítási algoritmust, amely közelíti a BPQM-et, és kvantumáramkör-bonyolultsága $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, ahol $n$ a kód hossza, az $epsilon$ pedig a közelítési hiba. Végül egy új módszert is javasolunk a BPQM kiterjesztésére ciklusokat tartalmazó faktorgráfokra, közelítő klónozás alkalmazásával. Mutatunk néhány ígéretes numerikus eredményt, amelyek azt jelzik, hogy a ciklusos faktorgráfokon a BPQM jelentősen felülmúlhatja a lehető legjobb klasszikus dekódert.
► BibTeX adatok
► Referenciák
[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, 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
arXiv: 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
arXiv: 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
arXiv: 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
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] 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 2001.00807
[48] John Watrous „A kvantuminformáció elmélete” 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, 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
arXiv: 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
arXiv: 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
arXiv: 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
arXiv: 1202.0533
Idézi
[1] S. Brandsen, Avijit Mandal, and Henry D. Pfister, “Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels”, arXiv: 2207.04984.
A fenti idézetek innen származnak SAO/NASA HIRDETÉSEK (utolsó sikeres frissítés: 2022-08-23 14:04:15). Előfordulhat, hogy a lista hiányos, mivel nem minden kiadó ad megfelelő és teljes hivatkozási adatokat.
Nem sikerült lekérni Az adatok által hivatkozott kereszthivatkozás utolsó próbálkozáskor 2022-08-23 14:04:14: Nem sikerült lekérni a 10.22331/q-2022-08-23-784 hivatkozás által hivatkozott adatokat a Crossref-től. Ez normális, ha a DOI-t nemrég regisztrálták.
Ez a tanulmány a Quantumban jelent meg Creative Commons Nevezd meg 4.0 International (CC BY 4.0) engedély. A szerzői jog az eredeti szerzői jog tulajdonosainál marad, például a szerzőknél vagy intézményeiknél.
