אלגוריתם האופטימיזציה הקוונטית ומודל שרינגטון-קירקפטריק בגודל אינסופי

עבודה זו חוקרת את הביצועים של אלגוריתם קוונטי למטרות כלליות לאופטימיזציה קומבינטורית, הנקרא QAOA, המיושם על המודל המפורסם של שרינגטון-קירקפטריק (SK) של זכוכית ספין. זו הבעיה של מזעור אנרגיה של סיבובים משולבים באופן אקראי. המחברים מייצרים נוסחה לחישוב הערך הצפוי של האנרגיה שהושגה על ידי ה-QAOA בגבול גודל המערכת האינסופי, כפונקציה של פרמטרי האלגוריתם. הם גם מוכיחים שמדידות טיפוסיות של מקרים אקראיים של הבעיה מתרכזות בערך זה. תוצאות אלו מאפשרות השוואה לאלגוריתמים הקלאסיים המתקדמים ביותר. בפרט, המחברים מוצאים שה-QAOA עם 11 שכבות עולה על אלגוריתם התכנות הרגיל למחצה מוגדר בבעיה זו. זו נותרה שאלה פתוחה כיצד קנה המידה של הביצועים של ה-QAOA משתווה לאלגוריתם הקלאסי הטוב ביותר הידוע כיום על ידי Montanari.

[1] קישור בהארטי, אלבה סרוורה-ליארטה, ת'י הא קיאו, טוביאס האג, סאמנר אלפרין-לאה, אבהינב אנאנד, מתיאס דגרוט, הרמני היימונן, יעקב ס. קוטמן, טים מנקה, וואי-קיונג מוק, סוקין סים, ליונג- צ'ואן קוואק, ואלן אספורו-גוזיק, "אלגוריתמים קוונטיים רועשים בקנה מידה בינוני", ביקורות על פיזיקה מודרנית 94 1, 015004 (2022).

[2] מתיו פ. הריגן, קווין ג'יי סונג, מתיו נילי, קווין ג'יי סאצינגר, פרנק ארוט, קונאל אריה, חואן אטלאיה, ג'וזף סי ברדין, רמי בארנדס, סרג'יו בוישו, מייקל ברוטון, בוב ב. באקלי, דיוויד א. ביואל, בריאן בורקט, ניקולס בושנל, יו צ'ן, זיון צ'ן, קולינס בן קיארו, וויליאם קורטני, שון דמורה, אנדרו דונסוורת', דניאל אפנס, אוסטין פאולר, ברוקס פוקסן, קרייג גידני, מריסה ג'וסטינה, רוב גראף, סטיב האבגר, אלן הו, סברינה הונג, טרנט הואנג, LB Ioffe, סרגיי ו' איסקוב, אוון ג'פרי, ז'אנג ג'יאנג, קודי ג'ונס, דביר כפרי, קוסטיאנטין קצ'דז'י, ג'וליאן קלי, סון קים, פול ו' קלימוב, אלכסנדר נ. קורוטקוב, פדור קוסטריצה. , דייוויד לנדהויז, פאבל לאפטב, מייק לינדמרק, מרטין לייב, אוריון מרטין, ג'ון מ. מרטניס, ג'רוד ר. מקלין, מאט מקיוון, אנתוני מגאנט, שיאו מי, מסעוד מוחסני, וויצ'ך מרוצ'קביץ', ג'וש מוטוס, עופר נעמן, צ'ארלס ניל, פלוריאן נויקארט, מרפי יואז'ן ניו, תומאס אי. אובריאן, בריאן או'גורמן, אריק אוסטבי, אנדרה פטוחוב, האראלד פוטרמן,כריס קווינטנה, פדרם רושן, ניקולס סי רובין, דניאל סאנק, אנדראה סקוליק, ואדים סמליאנסקי, דאג סטריין, מייקל סטרייף, מרקו סלאי, עמית וינסנצ'ר, תיאודור ווייט, ז' ג'יימי יאו, פינג יה, אדם זלמן, ליאו ז'ו, הרטמוט Neven, Dave Bacon, Erik Lucero, Edward Farhi ו- Ryan Babbush, "אופטימיזציה קוונטית משוערת של בעיות גרפים לא מישוריים במעבד מוליך-על מישוריים", טבע פיזיקה 17 3, 332 (2021).

[3] Filip B. Maciejewski, Flavio Baccari, Zoltán Zimborás, and Michał Oszmaniec, "מודל והפחתה של אפקטים של דיבור צולב ברעשי קריאה עם יישומים לאלגוריתם האופטימיזציה הקוואנטית". arXiv: 2101.02331.

[4] אדוארד פרחי, דיוויד גמרניק וסם גוטמן, "אלגוריתם האופטימיזציה הקוואנטית צריך לראות את כל הגרף: מקרה טיפוסי", arXiv: 2004.09002.

[5] אנטוניו אנה מלה, גלן ביגן מבנג, ג'וזפה ארנסטו סנטורו, מריו קולורה ופייטרו טורטה, "הימנעות מרמות עקרה באמצעות העברה של פתרונות חלקים בהילטון וריאציונלי Ansatz", arXiv: 2206.01982.

[6] Thais de Lima Silva, Márcio M. Taddei, Stefano Carrazza, and Leandro Aolita, "אבולוציה מפוצלת בזמן דמיוני עבור מעבדי אותות קוונטיים בשלבים מוקדמים", arXiv: 2110.13180.

[7] קלמנס דלאסקה, קיליאן אנדר, גלן ביגן מבנג, אנדראס קרוקנהאוזר, וולפגנג לכנר, וריק ואן ביינן, "אופטימיזציה קוונטית באמצעות שערים של רידברג ארבעה גופים", מכתבי ביקורת גופנית 128 12, 120503 (2022).

[8] ג'ייסון לרקין, מתיאס ג'ונסון, דניאל ג'סטיס וג'יאן ג'אקומו גרסקי, "הערכה של QAOA מבוססת על יחס הקירוב של דגימות בודדות", arXiv: 2006.04831.

[9] ג'רוד ר. מקלין, מתיו פ. הריגן, מסעוד מוחסני, ניקולס סי רובין, ז'אנג ג'יאנג, סרג'יו בויצו, ואדים נ. סמיליאנסקי, ריאן באבוש והרטמוט נבן, "מנגנונים בעומק נמוך לאופטימיזציה קוונטית", PRX Quantum 2 3, 030312 (2021).

[10] V. Akshay, D. Rabinovich, E. Campos ו- J. Biamonte, "ריכוזי פרמטרים באופטימיזציה משוערת קוונטית", סקירה פיזית A 104 1, L010401 (2021).

[11] Chenfeng Cao, Zheng An, Shi-Yao Hou, DL Zhou, ובי Zeng, "אבולוציה קוונטית של זמן מדומה המנווטת על ידי למידת חיזוק", פיזיקת תקשורת 5 1, 57 (2022).

[12] ג'ורדי ר. ווגמנס, אלכסנדר אורץ ', אלכסנדר ראוש, רוברט שפריו, ריצ'רד בושרי, פלוריאן שרק, קארלג'אן שואטנס, ג'רי מינאור ופלוריאן שפילמן, "פתרון קשרי מתאם עם QAOA ומערכת רידברג: גישת מחסנית מלאה ”, arXiv: 2106.11672.

[13] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, ו-Daniel Stilck França, "מגבלות של אלגוריתמים קוונטיים וריאציות: גישת תחבורה קוונטית אופטימלית", arXiv: 2204.03455.

[14] נתן לקרואה, כריסטוף הלינגס, כריסטיאן קרגלונד אנדרסן, אגוסטין די פאולו, אנטס רם, סטפניה לאזאר, סבסטיאן קרינר, גרהם ג'יי נוריס, מיחאי גאבוראק, יוהנס הינסו, אלכסנדר בלייז, כריסטופר אייכלר ואנדראס וולרף, "לשפר את ביצועים של אלגוריתמי אופטימיזציה קוונטית עמוקה עם ערכות שערים מתמשכים", PRX Quantum 1 2, 020304 (2020).

[15] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou, "אלגוריתם האופטימיזציה הקוואנטית בעומק גבוה עבור MaxCut בגרפים רגילים בהיקף גדול ומודל שרינגטון-קירקפטריק", arXiv: 2110.14206.

[16] Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng, and Giuseppe E. Santoro, "Reinforcement-learning-assisted optimization quantum optimization", מחקר סקירה גופנית 2 3, 033446 (2020).

[17] Hajo Leschke, Chokri Manai, Rainer Ruder, ו- Simone Warzel, "קיומה של העתק-סימטריה נשברת במשקפיים קוונטיים", מכתבי ביקורת גופנית 127 20, 207204 (2021).

[18] טאג טומש, פראנב גוקהיל, ויקטורי אומול, גוקול סוברמאניאן ראווי, קייטלין נ. סמית', ג'ושוע ויסלאי, שין-צ'ואן וו, ניקוס הרדובלאס, מרגרט ר. מרטונוסי ופרדריק ט צ'ונג, "סופרמרק: מדד קוונטי שניתן להרחיב סְוִיטָה", arXiv: 2202.11045.

[19] Luca Lumia, Pietro Torta, Glen B. Mbeng, Giuseppe E. Santoro, Elisa Ercolessi, Michele Burrello, and Matteo M. Wauters, "Two-Dimensional Z 2 Lattice Gauge Theory on a Near-Term Quantum Simulator: Variational Quantum אופטימיזציה, כליאה וסדר טופולוגי", PRX Quantum 3 2, 020320 (2022).

[20] Nishant Jain, Brian Coyle, Elham Kashefi, and Niraj Kumar, "אתחול גרף של רשת עצבית של אופטימיזציה קוונטית משוערת", arXiv: 2111.03016.

[21] סטיוארט הדפילד, טד הוג, ואלינור ג'י ריפל, "מסגרת אנליטית ל-Quantum Alternating Operator Ansätze", arXiv: 2105.06996.

[22] Akel Hashim, Rich Rines, Victory Omole, Ravi K. Naik, John Mark Kreikebaum, David I. Santiago, Frederic T. Chong, Irfan Siddiqi, and Pranav Gokhale, "רשתות SWAP אופטימליות עם ממוצע מעגלים שווה ל-QAOA", מחקר סקירה גופנית 4 3, 033028 (2022).

[23] דניס ווילש, מדיטה ווילש, פנגפינג ג'ין, קריסטל מיכלסן והנס דה ראדט, "סימולציות מואצות ב-GPU של חישול קוונטי ואלגוריתם האופטימיזציה הקוונטי המשוער", Computer Physics Communications 278, 108411 (2022).

[24] פונטוס ויקסטאל, מתיאס גרונקוויסט, מאריקה סוונסון, מרטין אנדרסון, גורן ג'והנסון וג'וליה פריני, "החלת אלגוריתם האופטימיזציה הקוואנטית לבעיית הקצאת הזנב", סקירה פיזית הוחלה 14 3, 034009 (2020).

[25] P. Chandarana, NN Hegade, K. Paul, F. Albarrán-Arriagada, E. Solano, A. Del Campo, and Xi Chen, "אלגוריתם אופטימיזציה קוונטי משוער דיגיטאלי-נגד-דיאבטי", מחקר סקירה גופנית 4 1, 013141 (2022).

[26] Wei-Feng Zhuang, Ya-Nan Pu, Hong-Ze Xu, Xudan Chai, Yanwu Gu, Yunheng Ma, Shahid Qamar, Chen Qian, Peng Qian, Xiao Xiao, Meng-Jun Hu, and Dong E. Liu, "חישוב קלאסי יעיל של ערכי ממוצע קוונטיים עבור מעגלי QAOA רדודים", arXiv: 2112.11151.

[27] Jahan Claes ו- Wim van Dam, "Instance Independence of Single Layer Quantum Approximate Algorithm on מודלים מעורבים ב-Spin בגודל אינסופי", arXiv: 2102.12043.

[28] האן ג'נג, זימו לי, ג'וניו ליו, סרגיי סטרלצ'וק וריסי קונדור, "האצת למידה של מדינות קוונטיות באמצעות קבוצת קוונטיות קוונטית שוות משתנה", arXiv: 2112.07611.

[29] צ'י-נינג צ'ו, פיטר ג'יי לאב, ג'וספריט סינג סנדהו וג'ונתן שי, "המגבלות של אלגוריתמים קוונטיים מקומיים על מקס-ק-XOR אקראי ומעבר לכך", arXiv: 2108.06049.

[30] יואניס קולוטורוס ופטרוס וולדן, "תפקוד אובייקטיבי מתפתח לשיפור אופטימיזציה קוונטית וריאציות", מחקר סקירה גופנית 4 2, 023225 (2022).

[31] פראסנה דייט, דייויס ארתור ולורן פוסי-נזארו, "ניסוחים של QUBO לאימון מודלים של למידת מכונה", דוחות מדעיים 11, 10029 (2021).

[32] יובל ר. סנדרס, דומיניק וו. ברי, פדרו CS קוסטה, לואיס וו. טסלר, נתן וויבה, קרייג גידני, הרטמוט נבן וריאן בבוש, "קומפילציה של היוריסטיות קוונטיות סובלניות לתקלות לאופטימיזציה קומבינטורית", arXiv: 2007.07391.

[33] Benjamin Tan, Marc-Antoine Lemonde, Supanut Thanasilp, Jirawat Tangpanitanon ודימיטריס G. Angelakis, "סכימות קידוד יעילות ב-Qubit לבעיות אופטימיזציה בינארית", arXiv: 2007.01774.

[34] פול מ. שינדלר, Tommaso Guaita, Tao Shi, Eugene Demler, and J. Ignacio Cirac, "Ansatz Variational for the Ground State of the Quantum Sherington-Kirkpatrick Model", arXiv: 2204.02923.

[35] Laszlo Gyongyosi, "אופטימיזציה של מצב קוונטי והערכת מסלול חישובי למחשבים קוונטיים לפי מודל שער", דוחות מדעיים 10, 4543 (2020).

[36] ג'ואאו באסו, דיוויד גמרניק, סונג מי וליאו ז'ואו, "ביצועים ומגבלות של ה-QAOA ברמות קבועות על היפרגרפים דלילים ודגמי זכוכית ספינים", arXiv: 2204.10306.

[37] דיוויד ג'וזף, אנטוניו ג'יי מרטינז, קונג לינג ופלוריאן מינטרט, "קירוב ערך ממוצע קוונטי לבעיות קשות של ערכים שלמים", ביקורת גופנית A 105 5, 052419 (2022).

[38] לאסלו ג'יונגיוסי וסנדור אימרה, "הפחתת עומק מעגלים למחשבים קוונטיים ממודל שער", דוחות מדעיים 10, 11229 (2020).

[39] י' -ה. Bae, Paul M. Alsing, Doyeol Ahn, ו-Warner A. Miller, "אופטימיזציה של מעגלים קוונטיים באמצעות מפת Karnaugh קוונטית", דוחות מדעיים 10, 15651 (2020).

[40] Bingzhi Zhang, Akira Sone, ו-Quntao Zhuang, "מעבר שלב חישובי קוונטי בבעיות קומבינטוריות", arXiv: 2109.13346.

[41] א 'קמפוס, ד' רבינוביץ ', ו' אקשי וג'יי ביאמונטה, "אימון רוויה באופטימיזציה משוערת קוונטית שכבתית", arXiv: 2106.13814.

[42] סמי בולבנן, "שיפור האלגוריתם האופטימיזציה הקוונטי המשוער עם הבחירה שלאחר הבחירה", arXiv: 2011.05425.

[43] גבריאל מטוס, סוניקה ג'והרי וזלטקו פאפיץ ', "כימות היעילות של הכנת המדינה באמצעות פתרונות משתנים קוונטיים", arXiv: 2007.14338.

[44] Gregory Quiroz, Paraj Titum, Phillip Lotshaw, Pavel Lougovski, Kevin Schultz, Eugene Dumitrescu, and Itay Hen, "כימות ההשפעה של שגיאות דיוק על אלגוריתמי אופטימיזציה קוונטיים משוערים", arXiv: 2109.04482.

[45] קייל מילס, פויה רונה ואייזק טמבלין, "למידת אופטימיזציה מקוונת מבוקרת (COOL): מציאת מצב הקרקע של ספין המילטון עם למידת חיזוק", arXiv: 2003.00011.

[46] טפי סוזוקי ומיצ'יו קטודה, "ניבוי רעילות על ידי למידת מכונה קוונטית", Journal of Physics Communications 4 12, 125012 (2020).

[47] Ruslan Shaydulin, Phillip C. Lotshaw, Jeffrey Larson, James Ostrowski, Travis S. Humble, "Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut", arXiv: 2201.11785.

[48] Laszlo Gyongyosi, "אומדן פונקציות אובייקטיבי לפתרון בעיות אופטימיזציה במחשבים קוונטיים במודל שער", דוחות מדעיים 10, 14220 (2020).

[49] Xuchen You ו- Xiaodi Wu, "הרבה מינימות מקומיות באופן אקספוננציאלי ברשתות עצביות קוונטיות", arXiv: 2110.02479.

[50] לאסלו ג'יונגיוסי, "בקרת שער קוונטי ללא פיקוח למחשבים קוונטיים מדגם שער", דוחות מדעיים 10, 10701 (2020).

[51] ​​V. Akshay, H. Philathong, E. Campos, D. Rabinovich, I. Zacharov, Xiao-Ming Zhang, and J. Biamonte, "On Circuit Depth Scaling For Quantum Approximate Optimization", arXiv: 2205.01698.

[52] לאסלו ג'יונגיוסי, "דינמיקה של רשתות מסובכות של האינטרנט הקוונטי", דוחות מדעיים 10, 12909 (2020).

[53] סמי בולבנין ואשלי מונטנרו, "חיזוי פרמטרים עבור אלגוריתם האופטימיזציה הקוואנטית ל-MAX-CUT ממגבלת הגודל האינסופי", arXiv: 2110.10685.

[54] Laszlo Gyongyosi ו- Sandor Imre, "מחשבים קוונטיים המופצים על-ידי מודל שער המופצים בהרחבה. דוחות מדעיים 11, 5172 (2021).

[55] Laszlo Gyongyosi ו- Sandor Imre, "ניתוב חקר החלל לצורך ניתוב מדרגי באינטרנט הקוונטי", דוחות מדעיים 10, 11874 (2020).

[56] G. Pederiva, A. Bazavov, B. Henke, L. Hostetler, D. Lee, HW Lin, and A. Shindler, "Quantum State Preparation for the Schwinger Model", הסימפוזיון הבינלאומי ה-38 על תורת שדות הסריג 47 (2022).

[57] סינאן בוגו, פאטיח אוזיידין וטטסואו קודרה, "עובר את הגבול הקלאסי במשחק ריבועי קסם עם נקודות קוונטיות מרוחקות המקושרות לחללים אופטיים", דוחות מדעיים 10, 22202 (2020).

[58] Laszlo Gyongyosi, "אומדן דינמיקת דקו-מכירה למחשבים קוונטיים המוליכים-על-מודל שער", עיבוד מידע קוונטי 19 10, 369 (2020).

[59] Aida Ahmadzadegan, Petar Simidzija, Ming Li, ואחים Kempf, "רשתות עצביות יכולות ללמוד להשתמש ברעש עזר מתאם", דוחות מדעיים 11, 21624 (2021).

[60] מישל חלופניק, הנס מלו, יורי אלכסייב ואלכסיי גאלדה, "הגדלת QAOA Ansatz עם שכבה בלתי תלויה בבעיות מרובות פרמטרים", arXiv: 2205.01192.

[61] Hari Krovi, "קשיות ממוצעת של הערכת הסתברויות של מעגלים קוונטיים אקראיים עם קנה מידה ליניארי במעריך השגיאה", arXiv: 2206.05642.

[62] דנייל רבינוביץ', סומיק אדהיקארי, ארנסטו קמפוס, וישוואנתן אקשיי, יבגני אניקין, ריצ'יק סנגופטה, אולגה לחמנסקיה, קיריל לחמנסקי, ויעקוב ביאמונטה, "הוספה של יון וריאציה מקורית לאופטימיזציה קוונטית משוערת", arXiv: 2206.11908.

הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2022-07-27 14:28:25). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.

On השירות המוזכר של קרוסרף לא נמצאו נתונים על ציטוט עבודות (ניסיון אחרון 2022-07-27 14:28:23)