Actis: איחוד מקומי למהדרין – מצא מפענח

Actis: איחוד מקומי למהדרין – מצא מפענח

צומת המקור: 2382796

טים צ'אן1 ו שמעון סי בנימין1,2

1המחלקה לחומרים, אוניברסיטת אוקספורד, Parks Road, Oxford OX1 3PH, בריטניה
2Quantum Motion, 9 Sterling Way, London N7 9HJ, בריטניה

מצא את העיתון הזה מעניין או רוצה לדון? סקייט או השאירו תגובה ב- SciRate.

תַקצִיר

מחשוב קוונטי סובלני לתקלות דורש חומרה קלאסית כדי לבצע את הפענוח הדרוש לתיקון שגיאות. מפענח Union–Find הוא אחד המועמדים הטובים ביותר לכך. יש לו מאפיינים אורגניים להפליא, הכוללים צמיחה ומיזוג של מבני נתונים באמצעות שלבים של השכנים הקרובים ביותר; זה מצביע באופן טבעי על אפשרות מימושו באמצעות רשת של מעבדים פשוטים עם קישורים של השכנים הקרובים ביותר. בדרך זו ניתן לחלק את העומס החישובי בהקבלה כמעט אידיאלית. כאן אנו מראים לראשונה שהמקום המחמיר (ולא חלקי) זה הוא מעשי, עם זמן ריצה במקרה הגרוע ביותר $mathcal O(d^3)$ ותת ריצה ממוצעת במרחק קוד פני השטח $d$. נעשה שימוש בסכימת חישוב זוגיות חדשה שיכולה לפשט ארכיטקטורות שהוצעו בעבר, והגישה שלנו מותאמת לרעש ברמת המעגל. אנו משווים את המימוש המקומי שלנו למימוש המוגבר בקישורים ארוכי טווח; בעוד שהאחרון כמובן מהיר יותר, נציין שהלוגיקה האסינכרונית המקומית יכולה לשלול את ההבדל.

למחשבים קוונטיים יש פוטנציאל להציע כוח חישוב פורץ דרך, אבל רק אם הם מוגנים מפני רעש. זה נעשה באמצעות תיקון שגיאות: דרך להחליף קיוביטים רועשים רבים (יחידות חישוב) בפחות קיוביטים אך מושלמים יותר. תת-המשימה המכריעה של ניטור מדידות מהמעבד הקוונטי כדי להסיק מתי התרחשו שגיאות נקראת פענוח. יש לבצע זאת במהירות רבה על מנת לעמוד בקצב המכונה הקוונטית. כאן אנו משנים אלגוריתם פענוח קיים כדי להפוך אותו למקומי, כלומר ניתן להרצה על רשת של תאי עיבוד זהים, כל אחד מתקשר רק עם שכניהם הקרובים ביותר. ליישוב יש יתרונות מעשיים שונים במהירות, פריסה וחוסן. אנו בודקים את העיצוב המקומי שלנו ומגלים שזמן הריצה שלו אכן מתנהג בצורה חיובית יותר מהאלגוריתם המקורי; לאחר מכן אנו מציעים להשתמש בחומרה 'אסינכרונית' כדי למקסם את הביצועים המוחלטים של העיצוב שלנו.

► נתוני BibTeX

► הפניות

[1] אריק דניס, אלכסיי קיטאיב, אנדרו לנדהל וג'ון פרסקיל. "זיכרון קוונטי טופולוגי". Journal of Mathematical Physics 43, 4452–4505 (2002).
https: / / doi.org/ 10.1063 / 1.1499754

[2] אוסטין ג'י פאולר, מתאו מריאנטוני, ג'ון מ. מרטניס ואנדרו נ. קללנד. "קודי שטח: לקראת חישוב קוונטי מעשי בקנה מידה גדול". סקירה פיזית א 86, 032324 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.86.032324

[3] דניאל ליטינסקי. "משחק של קודי שטח: מחשוב קוונטי בקנה מידה גדול עם ניתוח סריג". Quantum 3, 128 (2019).
https:/​/​doi.org/​10.22331/​q-2019-03-05-128

[4] ג'ק אדמונדס. "שבילים, עצים ופרחים". Canadian Journal of Mathematics 17, 449–467 (1965).
https: / / doi.org/ 10.4153 / CJM-1965-045-4

[5] אוסטין ג'י פאולר, אדם סי ווייטסייד ולויד CL הולנברג. "לקראת עיבוד קלאסי מעשי לקוד השטח". מכתבי סקירה פיזית 108, 180501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.180501

[6] גיום דוקלוס-סיאנצ'י ודיוויד פולין. "מפענחים מהירים לקודים קוונטיים טופולוגיים". מכתבי ביקורת פיזיים 104, 050504 (2010).
https: / / doi.org/ 10.1103 / PhysRevLett.104.050504

[7] גיום דוקלוס-סיאנצ'י ודיוויד פולין. "אלגוריתם פענוח של קבוצת רנורמליזציה לקודים קוונטיים טופולוגיים". בשנת 2010 סדנת תורת המידע של IEEE. עמודים 1-5. (2010).
https://doi.org/​10.1109/​CIG.2010.5592866

[8] ג'יימס אר ווטון ודניאל לוס. "תיקון שגיאות סף גבוה עבור קוד השטח". מכתבי סקירה פיזית 109, 160503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.160503

[9] בן קריגר ועמרן אשרף. "סיכום רב-נתיבי לפענוח קודים טופולוגיים דו מימדיים". Quantum 2, 2 (102).
https:/​/​doi.org/​10.22331/​q-2018-10-19-102

[10] אוסקר היגוט, תומאס סי בוהדנוביץ', אלכסנדר קוביקה, סטיבן טי פלמיה וארל טי קמפבל. "פענוח משופר של רעשי מעגל וגבולות שבירים של קודי משטח מותאמים". סקירה פיזית X 13, 031007 (2023).
https: / / doi.org/ 10.1103 / PhysRevX.13.031007

[11] אוסקר היגוט וניקולס פ. ברוקמן. "פענוח משופר של צילום יחיד של קודי היפרגרף-מוצר בממדים גבוהים יותר". PRX Quantum 4, 020332 (2023).
https: / / doi.org/ 10.1103 / PRXQuantum.4.020332

[12] קאו-יוה קואו וצ'ינג-אי לאי. "ניצול ניוון בפענוח התפשטות האמונה של קודים קוונטיים". npj Quantum Information 8, 111 (2022).
https:/​/​doi.org/​10.1038/​s41534-022-00623-2

[13] מילאפ שת, שרה זפאר ג'פרזאדה, ולאד גאורגיו. "פענוח אנסמבל עצבי לקודי תיקון שגיאות קוונטיים טופולוגיים". Physical Review A 101, 032338 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032338

[14] רמון WJ Overwater, מסעוד באבאי ופאביו סבסטיאנו. "מפענחי רשת עצבית לתיקון שגיאות קוונטי באמצעות קודי שטח: חקר חלל של פשרות עלות-ביצועים של החומרה". IEEE Transactions on Quantum Engineering 3, 1–19 (2022).
https: / / doi.org/ 10.1109 / TQE.2022.3174017

[15] ניקולס דלפוס. "פענוח היררכי להפחתת דרישות החומרה עבור מחשוב קוונטי" (2020). arXiv:2001.11427.
arXiv: 2001.11427

[16] קאי מיינרז, פארק צ'ה-יון וסימון טרבסט. "מפענח עצבי ניתן להרחבה עבור קודי משטח טופולוגיים". מכתבי סקירה פיזית 128, 080505 (2022).
https: / / doi.org/ 10.1103 / PhysRevLett.128.080505

[17] גוקול סוברמאניאן ראווי, ג'ונתן מ. בייקר, ארש פייאזי, סופיה פוהוי לין, עלי ג'אווהדי-אבהארי, מסעוד פדרם ופרדריק ט. צ'ונג. "עדיף מפענוח המקרה הגרוע ביותר לתיקון שגיאות קוונטי". בהליכי הכנס הבינלאומי ה-28 של ACM בנושא תמיכה ארכיטקטונית בשפות תכנות ומערכות הפעלה, כרך 2. עמודים 88–102. ניו יורק, ניו יורק, ארה"ב (2023). האגודה למכונות מחשוב.
https: / / doi.org/ 10.1145 / 3575693.3575733

[18] סמואל סי סמית', בנג'מין ג'יי בראון וסטיבן ד' בארטלט. "מקודד מקומי להפחתת רוחב הפס והשהייה של תיקון שגיאות קוונטי". סקירה פיזית החלה 19, 034050 (2023).
https: / / doi.org/ 10.1103 / PhysRevApplied.19.034050

[19] ניקולס דלפוס וז'יל זמור. "פענוח הסבירות המקסימלית בזמן לינארי של קודי פני השטח מעל ערוץ המחיקה הקוונטית". Physical Review Research 2, 033042 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.033042

[20] ניקולס דלפוס ונעמי ה' ניקרסון. "אלגוריתם פענוח זמן כמעט ליניארי לקודים טופולוגיים". Quantum 5, 595 (2021).
https:/​/​doi.org/​10.22331/​q-2021-12-02-595

[21] Namitha Liyanage, Yue Wu, Alexander Deters ולין Zhong. "תיקון שגיאות קוונטי ניתן להרחבה עבור קודי שטח באמצעות FPGA" (2023). arXiv:2301.08419.
arXiv: 2301.08419

[22] אלכסיי יו קיטאיב. "חישוב קוונטי סובלני לתקלות על ידי מישהו". Annals of Physics 303, 2–30 (2003).
https:/​/​doi.org/​10.1016/​S0003-4916(02)00018-0

[23] טים צ'אן (2023). קוד: timchan0/​localuf.
https://github.com/​timchan0/​localuf

[24] טים צ'אן. "נתונים עבור `Actis: A striktly Local Union-Find Decoder"' (2023).
https: / / doi.org/ 10.5281 / zenodo.10075207

[25] מייקל א. נילסן ואייזק ל. צ'ואנג. "חישוב קוונטי ומידע קוונטי: מהדורת 10 שנים". הוצאת אוניברסיטת קיימברידג'. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[26] Xinyu Tan, Fang Zhang, Rui Chao, Yaoyun Shi, Jianxin Chen. "מפענחי קוד משטח הניתנים להרחבה עם הקבלה בזמן" (2022). arXiv:2209.09219.
arXiv: 2209.09219

[27] לוקה סקוריק, דן אי. בראון, קנטון מ. בארנס, ניל אי. גילספי וארל טי קמפבל. "פענוח חלונות מקבילים מאפשר חישוב קוונטי סביל לתקלות". תקשורת טבע 14, 7040 (2023).
https:/​/​doi.org/​10.1038/​s41467-023-42482-1

[28] שואי הו. "אלגוריתם פענוח זמן קואזילינארי לקודים טופולוגיים עם סף שגיאה גבוה". תזה לתואר שני. אוניברסיטת דלפט לטכנולוגיה. (2020).
https:/​/​doi.org/​10.13140/​RG.2.2.13495.96162

[29] אוסקר היגוט. "PyMatching: חבילת Python לפענוח קודים קוונטיים עם התאמה מושלמת של משקל מינימום". ACM Transactions on Quantum Computing 3, 1–16 (2022).
https: / / doi.org/ 10.1145 / 3505637

[30] Yue Wu, Namitha Liyanage, ולין Zhong. "פרשנות של מפענח Union-Find על גרפים משוקללים" (2022). arXiv:2211.03288.
arXiv: 2211.03288

[31] רוברט אנדרה טארג'אן. "יעילות של אלגוריתם איחוד סט טוב אך לא ליניארי". Journal of the ACM 22, 215–225 (1975).
https: / / doi.org/ 10.1145 / 321879.321884

[32] שילין הואנג, מייקל ניומן וקנת ר. בראון. "פענוח איגוד-מצא משוקלל סובלני לתקלות בקוד הטורי". Physical Review A 102, 012419 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.012419

[33] LMK Vandersypen, H. Bluhm, JS Clarke, AS Dzurak, R. Ishihara, A. Morello, DJ Reilly, LR Schreiber, and M. Veldhorst. "התממשקות ספין קיוביטים בנקודות קוונטיות ובתורמים - חמים, צפופים וקוהרנטיים". npj Quantum Information 3, 34 (2017).
https: / doi.org/â € ‹10.1038 / s41534-017-0038-y

[34] אנדרו ריצ'רדס. "מחשוב מחקר מתקדם של אוניברסיטת אוקספורד". (2015).
https: / / doi.org/ 10.5281 / zenodo.22558

[35] סם ג'יי גריפית'ס ודן אי בראון. "איחוד-מצא פענוח קוונטי ללא איחוד-מצא" (2023). arXiv:2306.09767.
arXiv: 2306.09767

[36] בן ברבר, Kenton M. Barnes, Tomasz Bialas, Okan Buğdaycı, Earl T. Campbell, Neil I. Gillespie, Kauser Johar, Ram Rajan, Adam W. Richardson, Luka Skoric, Canberk Topal, Mark L. Turner, and Abbas B. זיאד. "מפענח בזמן אמת, ניתן להרחבה, מהיר וחסכוני במשאבים עבור מחשב קוונטי" (2023). arXiv:2309.05558.
arXiv: 2309.05558

[37] דיוויד ס. וואנג, אוסטין ג'י פאולר, ולויד CL הולנברג. "מחשוב קוונטי של קוד שטח עם שיעורי שגיאה מעל 1%". סקירה פיזית A 83, 020302 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.020302

[38] עמנואל קניל. "מחשוב קוונטי עם מכשירים רועשים בצורה מציאותית". טבע 434, 39–44 (2005).
https: / / doi.org/ 10.1038 / nature03350

[39] אוסקר היגוט וקרייג גידני. "פריחה דלילה: תיקון מיליון שגיאות לשנייה ליבה עם התאמת משקל מינימום" (2023). arXiv:2303.15933.
arXiv: 2303.15933

[40] אוסטין ג'י פאולר, אדם סי ווייטסייד ולויד CL הולנברג. "לקראת עיבוד קלאסי מעשי לקוד השטח: ניתוח תזמון". סקירה פיזית א 86, 042313 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.86.042313

[41] יו וו ולין ז'ונג. "Fusion Blossom: מפענחי MWPM מהירים עבור QEC" (2023). arXiv:2305.08307.
arXiv: 2305.08307

מצוטט על ידי

[1] סם ג'יי גריפית'ס ודן אי בראון, "פענוח קוונטי של איחוד מוצא ללא מוצא איחוד", arXiv: 2306.09767, (2023).

[2] Asmae Benhemou, Kaavya Sahay, Lingling Lao, ובנג'מין J. Brown, "מזעור כשלים בקוד פני השטח באמצעות מפענח קוד צבע", arXiv: 2306.16476, (2023).

הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2023-11-15 01:29:45). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.

On השירות המוזכר של קרוסרף לא נמצאו נתונים על ציטוט עבודות (ניסיון אחרון 2023-11-15 01:29:44)

בול זמן:

עוד מ יומן קוונטים