המכון לפיזיקה תיאורטית, ETH ציריך, שוויץ
מצא את העיתון הזה מעניין או רוצה לדון? סקייט או השאירו תגובה ב- SciRate.
תַקצִיר
לאחרונה, רנס הציע אלגוריתם קוונטי הנקרא התפשטות אמונה עם הודעות קוונטיות (BPQM) לפענוח נתונים קלאסיים המקודדים באמצעות קוד ליניארי בינארי עם גרף עץ Tanner המועבר בערוץ CQ במצב טהור [1], כלומר, ערוץ עם קלט קלאסי ופלט קוונטי של מצב טהור. האלגוריתם מציג מקבילה קוונטי אמיתית לפענוח המבוסס על אלגוריתם התפשטות האמונה הקלאסי, שמצא הצלחה רחבה בתורת הקידוד הקלאסית כאשר נעשה בו שימוש בשילוב עם קודי LDPC או טורבו. לאחרונה Rengaswamy $et$ $al.$ [2] הבחין כי BPQM מיישמת את המפענח האופטימלי על קוד דוגמה קטן, בכך שהיא מיישמת את המדידה האופטימלית שמבדילה את מצבי הפלט הקוונטי עבור קבוצת מילות הקוד הקלט עם ההסתברות הגבוהה ביותר שניתן להשיג. כאן אנו מרחיבים באופן משמעותי את ההבנה, הפורמליזם והישימות של אלגוריתם BPQM עם התרומות הבאות. ראשית, אנו מוכיחים אנליטית ש-BPQM מיישמת פענוח אופטימלי עבור כל קוד ליניארי בינארי עם גרף עץ טאנר. אנו מספקים גם את התיאור הפורמלי הראשון של אלגוריתם 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, and Henry D. Pfister, "הפצת אמונה עם מסרים קוונטיים לתקשורת קלאסית משופרת קוונטית" npj Quantum Information 7, 97 (2021).
https://doi.org/10.1038/s41534-021-00422-1
arXiv: 2003.04356
https: / / www.nature.com/ מאמרים / s41534-021-00422-1
[3] S. Kudekar, T. Richardson, and RL Urbanke, "Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation" עסקאות IEEE 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 "Double-Edge Factor Graphs: Definition, Properties ודוגמאות" 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 Multiple Quantum Statistical Hypothesis Testing" Stochastics 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114
[8] פול האוסלאדן וויליאם ק. ווטרס "מדידה 'די טובה' להבחנה בין מדינות קוונטיות" Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
[9] Narayanan Rengaswamy והנרי D. Pfister "הוכחה חצי-קלאסית של דואליות בין ה-BSC הקלאסי וה-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, "ערוצים קוונטיים המציגים תוספת יתר ביכולת קלאסית" סקירה פיזית A 58, 146–158 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.146
[12] YC Eldar and Jr. Forney "On Detection Quantum and the Square-Root Measurement" עסקאות IEEE על מידע תורת 47, 858–872 (2001).
https: / / doi.org/ 10.1109 / 18.915636
[13] טום ריצ'רדסון ורודיגר אורבנקה "תורת הקידוד המודרנית" הוצאת אוניברסיטת קיימברידג' (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 "על הפענוח האיטרטיבי של קודים קוונטיים דלילים" מידע וחישוב קוונטי 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, "פענוח איטרטיבי משופר של משוב של קודים קוונטיים דלילים" עסקאות IEEE on Information Theory 58, 1231–1241 (2012).
https: / doi.org/â € ‹10.1109 / TIT.2011.2169534
arXiv: 0912.4546
[17] בן קריגר ועמראן אשרף "סיכום רב-נתיבי לפענוח קודים טופולוגיים דו-ממדיים" קוונטים 2, 2 (102).
https://doi.org/10.22331/q-2018-10-19-102
arXiv: 1709.02154
[18] Ye-Hua Liu ו-David Poulin "מפענחי האמונה העצבית-התפשטות לקודים לתיקון שגיאות קוונטיות" Physical Review Letters 122, 200501 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.200501
arXiv: 1811.07835
[19] אלכס ריגבי, JC אוליבייה ופיטר ג'רוויס, "מפענחי התפשטות אמונות מתוקנים לקודי בדיקת זוגיות בצפיפות נמוכה בקוונטים" סקירה פיזית A 100, 012330 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.012330
arXiv: 1903.07404
[20] Pavel Panteleev ו-Gleb Kalachev "Code Quantum LDPC Degenerate With Good Finite Length Performance" Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] יולי X. Li ו-Pascal O. Vontobel "פענוח מבוסס-Pseudocodeword 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, דיוויד ר. ווייט, סיימון ברטון וארל קמפבל, "פענוח על פני נוף הקוד הקוונטי של צפיפות נמוכה בצפיפות נמוכה" 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] סריקאר קאסי וקייל ג'יימיסון "לקראת התפשטות אמונות קוונטיות לפענוח LDPC ברשתות אלחוטיות" הליכי הכנס הבינלאומי ה-26 השנתי על מחשוב נייד ורשתות 1–14 (2020).
https: / / doi.org/ 10.1145 / 3372224.3419207
arXiv: 2007.11069
[25] MS Leifer ו-D. Poulin "מודלים גרפיים קוונטיים והפצת אמונה" 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 / מאמר / pii / S0003491607001509
[26] HA Bethe "התיאוריה הסטטיסטית של רשתות העל" של החברה המלכותית A 150, 552–575 (1935).
https: / / doi.org/ 10.1098 / rspa.1935.0122
http://rspa.royalsocietypublishing.org/content/150/871/552
[27] רודולף פיירלס "תיאוריה סטטיסטית של רשתות על עם ריכוזים לא שווים של הרכיבים" הליכי החברה המלכותית A 154, 207–222 (1936).
https: / / doi.org/ 10.1098 / rspa.1936.0047
[28] יונתן ס. ידידיה, וויליאם ט. פרימן ויאיר וייס, "הפצת אמונה כללית" של הכנס הבינלאומי ה-13 למערכות עיבוד מידע עצבי 668–674 (2000).
[29] ג'ונתן ס. ידידיה, וויליאם ט. פרימן ויאיר וייס, "הבנת התפשטות האמונה והכללותיה" Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publications/docs/TR2001-22.pdf
[30] JS ידידיה, WT Freeman, ו-Y. Weiss, "בניית קירובים לאנרגיה חופשית ואלגוריתמים כלליים להפצת אמונה" תורת המידע, IEEE Transactions on 51, 2282–2312 (2005).
https: / doi.org/â € ‹10.1109 / TIT.2005.850085
[31] MB Hastings "התפשטות אמונות קוונטיות: אלגוריתם למערכות קוונטיות תרמיות" סקירה פיזיקלית B 76, 201102 (2007).
https: / / doi.org/ 10.1103 / PhysRevB.76.201102
arXiv: 0706.4094
[32] דיוויד פולין ומתיו ב' הייסטינגס "פירוק אנטרופיה של מרקוב: דואל וריאציוני להפצת אמונה קוונטית" מכתבי סקירה פיזית 106, 080403 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.080403
arXiv: 1012.2050
[33] MX Cao ו-PO Vontobel "גרפים של גורמים קוונטיים: סגירת התיבה וגישות שונות" 2016 סימפוזיון בינלאומי על תורת המידע ויישומיה (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 "קודים על גרפים: מימושים נורמליים" עסקאות IEEE על מידע תורת 47, 520–548 (2001).
https: / / doi.org/ 10.1109 / 18.910573
[36] CW Helstrom "תורת זיהוי והערכה קוונטית" אקדמית (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http:///www.sciencedirect.com/science/bookseries/00765392/123
[37] Saikat Guha "מקלטים אופטיים מובנים להשגת קיבולת סופרתוספית ומגבלה של Holevo" מכתבי סקירה פיזית 106, 240502 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.240502
arXiv: 1101.1550
[38] ת' עציון, א' טרכטנברג וא' ורדי, "באיזה קודים יש גרפי בורסקאות נטולי מחזור?" IEEE Transactions on Information Theory 45, 2173–2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
[39] ג'ייקוב סי ברידג'מן וכריסטופר ט צ'אב "ריקוד מנופף יד ופרשנות: קורס מבוא על רשתות טנזור" 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, "מעגלים קוונטיים עם שערים של קוביט אחד בשליטה אחידה" סקירה פיזית 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] ריצ'רד פ. ברנט "שיטות מציאת אפס מרובות דיוק והמורכבות של הערכת תפקוד יסודי" עיתונות אקדמית (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] הארווי ואן דר הובן "כפל שלם בזמן 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 Saber Kais, "אלגוריתם קוונטי ועיצוב מעגלים פותרים את משוואת Poisson" 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, ו-Iasonas Petras, "אלגוריתמים ומעגלים קוונטיים למחשוב מדעי" מידע וחישוב קוונטי 16, 197–236 (2016).
https: / / doi.org/ 10.26421 / QIC16.3-4-2
arXiv: 1511.08253
[46] תומס האנר, מרטין רוטלר וקריסטה מ. סבור, "אופטימיזציה של מעגלים קוונטיים לאריתמטיקה" (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, 347 (2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
[48] ג'ון ווטרוס "Theory of Quantum Information" הוצאת אוניברסיטת קיימברידג' (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, וג'ון A. Smolin, "שיבוט קוונטי אוניברסלי אופטימלי ותלוי מדינה" סקירה פיזית A 57, 2368–2378 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.57.2368
[50] E. Arıkan "קיטוב ערוצים: שיטה לבניית קודים משיגים קיבולת לערוצים ללא זיכרון בינאריים סימטריים" עסקאות IEEE על תורת המידע 55, 3051–3073 (2009).
https: / doi.org/â € ‹10.1109 / TIT.2009.2021379
arXiv: 0807.3917
[51] Mark M. Wilde ו-Saikat Guha "קודים קוטביים לערוצים קלאסיים-קוונטיים" IEEE Transactions on Information Theory 59, 1175–1187 (2013).
https: / doi.org/â € ‹10.1109 / TIT.2012.2218792
arXiv: 1109.2591
[52] ג'וזף מ' רנס ומארק מ' ווילד "קודים קוטביים לתקשורת פרטית וקוואנטית על ערוצים שרירותיים" עסקאות IEEE על תורת המידע 60, 3090–3103 (2014).
https: / doi.org/â € ‹10.1109 / TIT.2014.2314463
arXiv: 1212.2537
[53] S. Guha ו-MM Wilde "קידוד קוטבי להשגת קיבולת Holevo של ערוץ אופטי טהור עם אובדן טהור" הליכים של סימפוזיון 2012 IEEE International on Information Theory (ISIT) 546–550 (2012).
https: / / doi.org/ 10.1109 / ISIT.2012.6284250
arXiv: 1202.0533
מצוטט על ידי
[1] ס. ברנדסן, אביג'יט מנדל והנרי ד. פיסטר, "הפצת אמונה עם מסרים קוונטיים לערוצים סימטריים קלאסיים-קוונטיים", arXiv: 2207.04984.
הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2022-08-23 14:04:15). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.
לא ניתן היה להביא נתונים מצוטטים על ידי קרוסרף במהלך ניסיון אחרון 2022-08-23 14:04:14: לא ניתן היה להביא נתונים שהובאו עבור 10.22331 / q-2022-08-23-784 מקרוסרף. זה נורמלי אם ה- DOI נרשם לאחרונה.
מאמר זה מתפרסם בקוונטים תחת התקציב ייחוס Creative Commons 4.0 הבינלאומי (CC BY 4.0) רישיון. זכויות יוצרים נשארות עם בעלי זכויות היוצרים המקוריים כמו המחברים או מוסדותיהם.
