Ινστιτούτο Θεωρητικής Φυσικής, ETH Ζυρίχη, Ελβετία
Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.
Περίληψη
Πρόσφατα, ο Renes πρότεινε έναν κβαντικό αλγόριθμο που ονομάζεται διάδοση πεποιθήσεων με κβαντικά μηνύματα (BPQM) για την αποκωδικοποίηση κλασικών δεδομένων που κωδικοποιούνται χρησιμοποιώντας έναν δυαδικό γραμμικό κώδικα με δέντρο Tanner γράφημα που μεταδίδεται μέσω ενός καναλιού CQ καθαρής κατάστασης.1], δηλαδή, ένα κανάλι με κλασική είσοδο και κβαντική έξοδο καθαρής κατάστασης. Ο αλγόριθμος παρουσιάζει ένα γνήσιο κβαντικό αντίστοιχο στην αποκωδικοποίηση που βασίζεται στον κλασικό αλγόριθμο διάδοσης πεποιθήσεων, ο οποίος έχει βρει μεγάλη επιτυχία στην κλασική θεωρία κωδικοποίησης όταν χρησιμοποιείται σε συνδυασμό με κώδικες LDPC ή Turbo. Πιο πρόσφατα Rengaswamy $et$ $al.$ [2] παρατήρησε ότι το BPQM εφαρμόζει τον βέλτιστο αποκωδικοποιητή σε ένα μικρό παράδειγμα κώδικα, καθώς εφαρμόζει τη βέλτιστη μέτρηση που διακρίνει τις κβαντικές καταστάσεις εξόδου για το σύνολο των κωδικών λέξεων εισόδου με την υψηλότερη δυνατή πιθανότητα. Εδώ επεκτείνουμε σημαντικά την κατανόηση, την τυπικότητα και την εφαρμογή του αλγορίθμου BPQM με τις ακόλουθες συνεισφορές. Πρώτον, αποδεικνύουμε αναλυτικά ότι το BPQM πραγματοποιεί τη βέλτιστη αποκωδικοποίηση για οποιονδήποτε δυαδικό γραμμικό κώδικα με δέντρο Tanner γράφημα. Παρέχουμε επίσης την πρώτη επίσημη περιγραφή του αλγορίθμου BPQM με πλήρη λεπτομέρεια και χωρίς καμία ασάφεια. Με αυτόν τον τρόπο, εντοπίζουμε ένα βασικό ελάττωμα που παραβλέπεται στον αρχικό αλγόριθμο και οι επόμενες εργασίες που υποδηλώνουν ότι οι πραγματοποιήσεις κβαντικών κυκλωμάτων θα είναι εκθετικά μεγάλες στη διάσταση του κώδικα. Αν και το BPQM περνά κβαντικά μηνύματα, άλλες πληροφορίες που απαιτούνται από τον αλγόριθμο επεξεργάζονται σφαιρικά. Αντιμετωπίζουμε αυτό το πρόβλημα διατυπώνοντας έναν αλγόριθμο αληθινής μετάδοσης μηνυμάτων που προσεγγίζει το BPQM και έχει πολυπλοκότητα κβαντικού κυκλώματος $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, όπου $n$ είναι το μήκος του κώδικα και το $epsilon$ είναι το σφάλμα προσέγγισης. Τέλος, προτείνουμε επίσης μια νέα μέθοδο για την επέκταση του BPQM σε γραφήματα παραγόντων που περιέχουν κύκλους χρησιμοποιώντας κατά προσέγγιση κλωνοποίηση. Δείχνουμε μερικά πολλά υποσχόμενα αριθμητικά αποτελέσματα που υποδεικνύουν ότι το BPQM σε γραφήματα παραγόντων με κύκλους μπορεί να ξεπεράσει σημαντικά τον καλύτερο δυνατό κλασικό αποκωδικοποιητή.
► Δεδομένα BibTeX
► Αναφορές
[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 και 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 και RL Urbanke, «Χωρικά συζευγμένα σύνολα 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 και PO Vontobel «Γραφήματα παραγόντων για κβαντικές πιθανότητες» IEEE Transactions on Information Theory 63, 5642–5665 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2716422
arXiv: 1508.00689
[5] MX Cao και PO Vontobel «Γραφήματα παραγόντων διπλής ακμής: Ορισμός, ιδιότητες και παραδείγματα» 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 και William K. Wootters «Μια «αρκετά καλή» μέτρηση για τη διάκριση κβαντικών καταστάσεων» Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
[9] Narayanan Rengaswamy και 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 και Osamu Hirota, «Βέλτιστες μετρήσεις για τη διάκριση μεταξύ συμμετρικών κβαντικών καταστάσεων και εκτίμηση παραμέτρων» International Journal of Theoretical Physics 36, 1269–1288 (1997).
https: / / doi.org/ 10.1007 / BF02435921
[11] Masahide Sasaki, Kentaro Kato, Masayuki Izutsu και 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 και 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 και Rüdiger Urbanke “Modern Coding Theory” Cambridge University Press (2008).
https: / / doi.org/ 10.1017 / CBO9780511791338
[14] David Poulin «Βέλτιστη και αποτελεσματική αποκωδικοποίηση συνεκτικών κωδικών κβαντικών μπλοκ» Φυσική Ανασκόπηση A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
[15] David Poulin και 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 και 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 και 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 και David Poulin “Neural Belief-Propagation Decoders for Quantum Error-Corecting Codes” Physical Review Letters 122, 200501 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.200501
arXiv: 1811.07835
[19] Alex Rigby, JC Olivier και Peter Jarvis, «Τροποποιημένοι αποκωδικοποιητές διάδοσης πεποιθήσεων για κβαντικούς κώδικες ελέγχου ισοτιμίας χαμηλής πυκνότητας» Φυσική ανασκόπηση A 100, 012330 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.012330
arXiv: 1903.07404
[20] Pavel Panteleev και Gleb Kalachev «Εκφυλισμένοι κβαντικοί κωδικοί LDPC με καλή απόδοση πεπερασμένου μήκους» Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] Ιούλιος X. Li και Pascal O. Vontobel «Αποκωδικοποίηση με βάση την ψευδοκωδική λέξη των κβαντικών κωδικών σταθεροποίησης» 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 και Earl Campbell, «Αποκωδικοποίηση σε ολόκληρο το τοπίο κώδικα ισοτιμίας ελέγχου κβαντικής χαμηλής πυκνότητας» Physical Review Research 2, 043423 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.043423
arXiv: 2005.07016
[23] Ιούλιος X. Li, Joseph M. Renes και Pascal O. Vontobel, «Αποκωδικοποίηση με βάση την ψευδοκωδικοποίηση των κβαντικών κωδικών χρωμάτων» (2020).
https://doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[24] Srikar Kasi και Kyle Jamieson «Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks» Πρακτικά του 26ου ετήσιου διεθνούς συνεδρίου για φορητούς υπολογιστές και δικτύωση 1–14 (2020).
https: / / doi.org/ 10.1145 / 3372224.3419207
arXiv: 2007.11069
[25] MS Leifer και 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 “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] JS Yedidia, WT Freeman και 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 και 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 και 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 και HA Loeliger, «Γραφήματα παραγόντων και ο αλγόριθμος αθροίσματος-προϊόντος» 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 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 και 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 και 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 και 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 και 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, Ανάργυρος Παπαγεωργίου, Iasonas Petras, Joseph Traub, and Saber 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, Ανάργυρος Παπαγεωργίου και 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 και 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 και Yongjian Gu, «Σχεδίαση κβαντικών κυκλωμάτων για την αξιολόγηση υπερβατικών συναρτήσεων με βάση μια μέθοδο δυαδικής επέκτασης συνάρτησης-τιμής» Κβαντική Επεξεργασία πληροφοριών 19,
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/book
[49] Dagmar Bruß, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello και 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 «Πόλωση καναλιού: Μέθοδος για την κατασκευή κωδικών επίτευξης χωρητικότητας για συμμετρικά κανάλια χωρίς μνήμη δυαδικής εισόδου» IEEE Transactions on Information Theory 55, 3051–3073 (2009).
https: / / doi.org/ 10.1109 / TIT.2009.2021379
arXiv: 0807.3917
[51] Mark M. Wilde και 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 και 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 και 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
Αναφέρεται από
[1] S. Brandsen, Avijit Mandal, and Henry D. Pfister, “Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels”. arXiv: 2207.04984.
Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2022-08-23 14:04:15). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.
Δεν ήταν δυνατή η λήψη Crossref αναφερόμενα δεδομένα κατά την τελευταία προσπάθεια 2022-08-23 14:04:14: Δεν ήταν δυνατή η λήψη των αναφερόμενων δεδομένων για το 10.22331 / q-2022-08-23-784 από την Crossref. Αυτό είναι φυσιολογικό αν το DOI καταχωρήθηκε πρόσφατα.
Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους
