QuOne Lab, Phanous Research and Innovation Centre, טהראן, איראן
מצא את העיתון הזה מעניין או רוצה לדון? סקייט או השאירו תגובה ב- SciRate.
תַקצִיר
התפתחות של המילטון המקומיים בזמן קצר צפויות להישאר מקומיות ולכן מוגבלות. במאמר זה, אנו מאמתים את האינטואיציה הזו על ידי הוכחת מספר מגבלות על התפתחות קצרת זמן של המילטון מקומיים תלויי זמן. אנו מראים שהתפלגות תפוקת המדידה של התפתחות קצרת זמן (לכל היותר לוגריתמית) של המילטון המקומיים היא $מרוכזת$ ומספקת $textit{אי-שוויון איזופרימטרי}$. כדי להציג יישומים מפורשים של התוצאות שלנו, אנו חוקרים את בעיית $M$$small{AX}$$C$$small{UT}$ ומגיעים למסקנה שחישול קוונטי צריך לפחות זמן ריצה שמתאים לוגריתמי בגודל הבעיה ל- ניצחו את האלגוריתמים הקלאסיים ב-$M$$small{AX}$$C$$small{UT}$. כדי לבסס את התוצאות שלנו, אנו גם מוכיחים קשר של ליב-רובינסון שעובד עבור המילטון תלויי זמן שעשוי להיות בעל עניין עצמאי.
תמונה מוצגת: איור זה מתאר את התפלגות ההסתברות של משקל Hamming של שלושה מצבי $n$-qubit שונים עבור $n=100$. ההתפלגות הממורכזת באמצע (כחול) היא ההתפלגות האופיינית למצב התחלתי של מוצר (למשל, $|+rangle^{otimes n}$). ההתפלגות ששיאה ימינה (כתום) מייצגת את ההתפלגות לאחר התפתחות של זמן קצר של המצב ההתחלתי המתואר במשפט 2 של כתב היד. ההתפלגות שיש לה שני פסגות משני צדי הספקטרום (ירוק) היא קירוב למצב ה-GHZ. זה מראה שלא ניתן ליצור את מצב ה-GHZ אפילו בקירוב על ידי חישול קוונטי קצר בזמן.
סיכום פופולרי
► נתוני BibTeX
► הפניות
[1] ט' קדוואקי וה' נישימורי. חישול קוונטי במודל Ising רוחבי. Physical Review E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355
[2] E. Farhi, J. Goldstone, S. Gutmann and M. Sipser. חישוב קוונטי על ידי אבולוציה אדיאבטית. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106
[3] טי קאטו. על המשפט האדיאבטי של מכניקת הקוונטים. Journal of the Physical Society of Japan 5, 435–439 (1950).
https: / / doi.org/ 10.1143 / JPSJ.5.435
[4] מ' בורן ו' פוק. Beweis des adiabatensatzes. Zeitschrift für Physik 51, 165–180 (1928).
https: / / doi.org/ 10.1007 / BF01343193
[5] ט' אלבש וד"א לידר. חישוב קוונטי אדיאבטי. ביקורות על פיזיקה מודרנית 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002
[6] I. Hen and FM Spedalieri. חישול קוונטי לאופטימיזציה מוגבלת. סקירה פיזית החלה 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007
[7] S. Puri, CK Andersen, AL Grimsmo, and A. Blais. חישול קוונטי עם מתנדים לא ליניאריים מחוברים הכל-לכולם. תקשורת טבע 8, 15785 (2017).
https: / / doi.org/ 10.1038 / ncomms15785
[8] W. Lechner, P. Hauke, and P. Zoller. ארכיטקטורת חישול קוונטית עם קישוריות הכל לכול מאינטראקציות מקומיות. Science Advances 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838
[9] S. Jiang, KA Britt, AJ McCaskey, TS Humble, and S. Kais. חישול קוונטי עבור פריים פקטוריזציה. דוחות מדעיים 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z
[10] RY Li, R. Di Felice, R. Rohs, ו-DA Lidar. חישול קוונטי לעומת למידת מכונה קלאסית מיושם על בעיית ביולוגיה חישובית פשוטה. מידע קוונטי NPJ 4, 1-10 (2018).
https://doi.org/10.1038/s41534-018-0060-8
[11] L. Stella, GE Santoro, ו-E. Tosatti. אופטימיזציה על ידי חישול קוונטי: לקחים ממקרים פשוטים. סקירה פיזית B 72, 014303 (2005).
https: / / doi.org/ 10.1103 / PhysRevB.72.014303
[12] או' טיטילוי וא' קריספין. חישול קוונטי של בעיית צביעת הגרפים. דיסקרטי אופטימיזציה 8, 376–384 (2011).
https://doi.org/10.1016/j.disopt.2010.12.001
[13] A. Mott, J. Job, J.-R. Vlimant, D. Lidar, and M. Spiropulu. פתרון בעיית אופטימיזציה של Higgs עם חישול קוונטי ללמידת מכונה. טבע 550, 375–379 (2017).
https: / / doi.org/ 10.1038 / nature24047
[14] KL Pudenz, T. Albash, and D. A Lidar. תיקון חישול קוונטי לבעיות Ising אקראיות. סקירה פיזית A 91, 042302 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.042302
[15] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Asspuru-Guzik. מציאת קונפורמציות באנרגיה נמוכה של מודלים של חלבון סריג על ידי חישול קוונטי. דוחות מדעיים 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571
[16] KL Pudenz, T. Albash, and D. A Lidar. חישול קוונטי מתוקן שגיאות עם מאות קיוביטים. תקשורת טבע 5, 1–10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243
[17] R. Martoňák, GE Santoro, and E. Tosatti. חישול קוונטי של בעיית המוכר הנוסע. סקירה פיזית E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701
[18] SH Adachi ו-MP הנדרסון. יישום חישול קוונטי לאימון של רשתות עצביות עמוקות. arXiv:1510.06356 [quant-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356
[19] M.W Johnson, et al. חישול קוונטי עם ספינים מיוצרים. טבע 473, 194–198 (2011).
https: / / doi.org/ 10.1038 / nature10012
[20] S. Boixo, T. Albash, FM Spedalieri, N. Chancellor, and DA Lidar. חתימה נסיונית של חישול קוונטי ניתן לתכנות. תקשורת טבע 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067
[21] AD King, et al. חישול קוונטי קוהרנטי בשרשרת Ising ניתנת לתכנות של 2000 קיוביטים. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847
[22] ב.פוקסן ואח'. הדגמת קבוצה רציפה של שערים של שני קיוביטים עבור אלגוריתמים קוונטיים לטווח קצר. Physical Review Letters 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504
[23] K. Wright, et al. השוואת מחשב קוונטי של 11 קיוביטים. תקשורת טבע 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2
[24] EJ Crosson ו-DA Lidar. סיכויים לשיפור קוונטי עם חישול קוונטי דיאבטי. Nature Reviews Physics 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6
[25] E. Farhi, J. Goldstone, and S. Gutmann. אלגוריתם אופטימיזציה קוונטי משוער. arXiv:1411.4028 [quant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028
[26] E. Farhi, D. Gamarnik, and S. Gutmann. אלגוריתם האופטימיזציה הקוואנטית צריך לראות את כל הגרף: דוגמאות למקרה הגרוע ביותר. arXiv:2005.08747 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747
[27] E. Farhi, D. Gamarnik, and S. Gutmann. אלגוריתם האופטימיזציה הקוואנטית צריך לראות את כל הגרף: מקרה טיפוסי. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002
[28] S. Bravyi, A. Kliesch, R. Koenig, and E. Tang. מכשולים לאופטימיזציה קוונטית וריאציונית מהגנה על סימטריה. Physical Review Letters 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[29] S. Bravyi, D. Gosset, and R. Movassagh. אלגוריתמים קלאסיים לערכים ממוצעים קוונטיים. טבע פיזיקה 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8
[30] S. Bravyi, A. Kliesch, R. Koenig, and E. Tang. אלגוריתמים קוונטיים-קלאסיים היברידיים לצביעה משוערת של גרפים. Quantum 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678
[31] ל' אלדר ו-AW Harrow. המילטון המקומיים שקשה להעריך את מדינות הקרקע שלהם. בשנת 2017 IEEE 58th Annual Symposium on Foundations of Science (FOCS), 427–438 (2017).
https: / / doi.org/ 10.1109 / FOCS.2017.46
[32] LT Brady, CL Baldwin, A. Bapat, Y. Kharkov, and AV Gorshkov. פרוטוקולים אופטימליים בחישול קוונטי ובבעיות אלגוריתם אופטימיזציה קוונטית. מכתבי סקירה פיזית 126, 070505 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.070505
[33] LT Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov, and AV Gorshkov. התנהגות של אלגוריתמים קוונטיים אנלוגיים. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218
[34] LC Venuti, D. D'Alessandro, ו-DA Lidar. בקרה אופטימלית לאופטימיזציה קוונטית של מערכות סגורות ופתוחות. סקירה פיזית החלה 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023
[35] AM Childs, Y. Su, MC Tran, N. Wiebe, and S. Zhu. התיאוריה של שגיאת טרטר עם קנה מידה של קומוטטור. סקירה פיזית X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
[36] ב' נכטרגאלה, י' אוגאטה ור' סימס. התפשטות מתאמים במערכות סריג קוונטיות. Journal of Statistical Physics 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6
[37] ב' נכטרגאלה ור' סימס. ליב-רובינסון מגביל בפיזיקה קוונטית של הרבה גופים. מתמטיקה עכשווית 529, 141–176 (2010).
https: / / doi.org/ 10.1090 / conm / 529/10429
[38] S. Bravyi, MB Hastings, ו-F. Verstraete. גבולות ליב-רובינסון ויצירת מתאמים וסדר קוונטי טופולוגי. מכתבי סקירה פיזית 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401
[39] C.-F. חן וא' לוקאס. גבולות הצמיחה של המפעיל מתורת הגרפים. תקשורת בפיזיקה מתמטית 385, עמודים1273–1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6
[40] EH Lieb ו-DW רובינסון. מהירות הקבוצה הסופית של מערכות ספין קוונטיות. תקשורת בפיזיקה מתמטית 28, 251–257 (1972).
https: / / doi.org/ 10.1007 / BF01645779
[41] J. Haah, MB Hastings, R. Kothari, ו-GH Low. אלגוריתם קוונטי להדמיית אבולוציה בזמן אמת של המילטון סריג. 2018 IEEE 59th Annual Symposium on Foundations of Science Computer (FOCS), 350–360 (2018).
https: / / doi.org/ 10.1109 / FOCS.2018.00041
[42] א' לובוצקי, ר' פיליפס, ופ' סרנק. גרפים של רמאנוג'אן. Combinatorica 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799
[43] ב' מוהר. מספרים איזופרימטריים של גרפים. כתב עת לתיאוריה קומבינטורית, סדרה B 47, 274–291 (1989).
https://doi.org/10.1016/0095-8956(89)90029-4
[44] AW Marcus, DA Spielman, and N. Srivastava. שילוב משפחות IV: גרפי רמנוג'אן דו-צדדיים בכל הגדלים. בשנת 2015 IEEE 56th Annual Symposium on Foundations of Science (FOCS), 1358–1377 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.87
[45] AW Marcus, DA Spielman, and N. Srivastava. שילוב משפחות IV: גרפי רמנוג'אן דו-צדדיים בכל הגדלים. SIAM Journal on Computing 47, 2488–2509 (2018).
https://doi.org/ 10.1137/16M106176X
[46] C. Hall, D. Puder, ו-WF Sawin. כיסויי רמאנוג'אן של גרפים. התקדמות במתמטיקה 323, 367–410 (2018).
https://doi.org/10.1016/j.aim.2017.10.042
[47] MX Goemans ו-DP Williamson. אלגוריתמי קירוב משופרים לבעיות חיתוך וסיפוק מקסימליות באמצעות תכנות חצי מוגדר. Journal of the ACM 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684
[48] RD Somma, D. Nagaj, and M. Kieferová. Quantum Speedup על ידי חישול קוונטי. מכתבי סקירה פיזית 109, 050501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.050501
[49] MB Hastings. הכוח של חישוב קוונטי אדיאבטי ללא בעיית סימנים. Quantum 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597
[50] A. Gilyén, MB Hastings, and U. Vazirani. (תת) יתרון אקספוננציאלי של חישוב קוונטי אדיאבטי ללא בעיית סימנים. ב-Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), 1357–1369 (2021).
https: / / doi.org/ 10.1145 / 3406325.3451060
[51] ר' בהתיא. ניתוח מטריקס. טקסטים לתואר שני במתמטיקה. ספרינגר ניו יורק (1996).
https://doi.org/10.1007/978-1-4612-0653-8
[52] ר' בהתיא. מטריצות מוגדרות חיוביות. הוצאת אוניברסיטת פרינסטון, (2007).
https: / / doi.org/ 10.1515 / 9781400827787
[53] BD McKay, NC Wormald, ו-B. Wysocka. מחזורים קצרים בגרפים רגילים אקראיים. The Electronic Journal of Combinatorics 11, 1–12 (2004).
https: / / doi.org/ 10.37236 / 1819
[54] F. Kardoš, D. Král, and J. Volec. חיתוך קצה מרבי בגרפים מעוקבים בעלי היקף גדול ובגרפים מעוקבים אקראיים. מבנים ואלגוריתמים אקראיים 41, 506–520 (2012).
https: / / doi.org/ 10.1002 / rsa.20471
[55] D. Coppersmith, D. Gamarnik, MT Hajiaghayi, ו-GB Sorkin. אקראי MAX SAT, אקראי MAX CUT, ומעברי השלב שלהם. מבנים ואלגוריתמים אקראיים 24, 502–545 (2004).
https: / / doi.org/ 10.1002 / rsa.20015
[56] A. Dembo, A. Montanari ו-S. Sen. חתכים קיצוניים של גרפים אקראיים דלילים. Annals of Probability 45, 1190–1217 (2017).
https://doi.org/ 10.1214/15-AOP1084
מצוטט על ידי
[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, ו-Daniel Stilck França, "מגבלות של אלגוריתמים קוונטיים וריאציות: גישת תחבורה קוונטית אופטימלית", arXiv: 2204.03455.
הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2022-07-19 03:10:09). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.
On השירות המוזכר של קרוסרף לא נמצאו נתונים על ציטוט עבודות (ניסיון אחרון 2022-07-19 03:10:07)
מאמר זה מתפרסם בקוונטים תחת התקציב ייחוס Creative Commons 4.0 הבינלאומי (CC BY 4.0) רישיון. זכויות יוצרים נשארות עם בעלי זכויות היוצרים המקוריים כמו המחברים או מוסדותיהם.
