גישת חלוקה-וכבוש היברידית עבור אלגוריתמי חיפוש עצים

גישת חלוקה-וכבוש היברידית עבור אלגוריתמי חיפוש עצים

חותמת זמן: 23 במרץ 2023 9:57
צומת המקור: 2029300

מתייס רנלה1, סבסטיאן ברנד2, אלפונס לארמן2, ו-Vedran Dunjko2

1Laboratoire de Physique de l'Ecole Normale Supérieure, אינריה, CNRS, ENS-PSL, Mines-Paristech, אוניברסיטת סורבון, אוניברסיטת PSL למחקר, פריז, צרפת
2LIACS, אוניברסיטת ליידן, ליידן, הולנד

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

תַקצִיר

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

סיכום פופולרי

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

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

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

► נתוני BibTeX

► הפניות

[1] Vedran Dunjko, Yimin Ge, ו-J Ignacio Cirac. "האצות חישוביות באמצעות התקנים קוונטיים קטנים". מכתבי סקירה פיזית 121, 250501 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.250501

[2] ימין גה וודראן דונג'קו. "מסגרת אלגוריתם היברידית למחשבים קוונטיים קטנים עם יישום למציאת מחזורים המילטוניים". Journal of Mathematical Physics 61, 012201 (2020).
https: / / doi.org/ 10.1063 / 1.5119235

[3] אשלי מונטנרו. "מהירות ההליכה הקוונטית של אלגוריתמי מעקב לאחור". תורת המחשוב 14, 1–24 (2018).
https: / / doi.org/ 10.4086 / toc.2018.v014a015

[4] מרטין דייויס, ג'ורג' לוגמן ודונלד וו לאבלנד. "תוכנית מכונה להוכחת משפט". אוניברסיטת ניו יורק, המכון למדעי המתמטיקה. (1961).
https: / / doi.org/ 10.1145 / 368273.368557

[5] Ramamohan Paturi, Pavel Pudlák, Michael E Saks, ופרנסיס זיין. "אלגוריתם זמן אקספוננציאלי משופר עבור k-SAT". Journal of the ACM (JACM) 52, 337–364 (2005).
https: / / doi.org/ 10.1145 / 1066100.1066101

[6] ארל קמפבל, אנקור חוראנה ואשלי מונטנרו. "יישום אלגוריתמים קוונטיים לבעיות שביעות רצון מהאילוצים". Quantum 3, 167 (2019).
https:/​/​doi.org/​10.22331/​q-2019-07-18-167

[7] סיימון מרתיאל ומקסים רמאוד. "יישום מעשי של אלגוריתם מעקב קוונטי לאחור". בכנס בינלאומי על מגמות נוכחיות בתיאוריה ובפרקטיקה של אינפורמטיקה. עמודים 597–606. ספרינגר (2020).
https:/​/​doi.org/​10.1007/​978-3-030-38919-2_49

[8] תומס דוהולם הנסן, חיים קפלן, אור זמיר ואורי זוויק. "אלגוריתמי k-sat מהירים יותר באמצעות מוטי-ppsz". בהליכים של סימפוזיון ACM SIGACT השנתי ה-51 על תורת המחשוב. עמודים 578–589. STOC 2019 ניו יורק, ניו יורק, ארה"ב (2019). ACM.
https: / / doi.org/ 10.1145 / 3313276.3316359

[9] ארמין ביירה, מרין הולה והנס ואן מארן. "מדריך לשביעות רצון". כרך 185. עיתונות IOS. (2009).

[10] מארק מזארד, מארק מזארד ואנדריאה מונטנארי. "מידע, פיזיקה וחישוב". הוצאת אוניברסיטת אוקספורד. (2009).
https: / / doi.org/ 10.1063 / 1.3397047

[11] מרטין דייויס והילרי פוטנם. "נוהל מחשוב לתורת כימות". J. ACM 7, 201–215 (1960).
https: / / doi.org/ 10.1145 / 321033.321034

[12] Marijn JH Heule, Matti Juhani Järvisalo, Martin Suda, et al. "תיאורי פותרים וברנצ'מרק". בהליכי תחרות SAT 2018. המחלקה למדעי המחשב, אוניברסיטת הלסינקי (2018). כתובת אתר: http://hdl.handle.net/​10138/​237063.
http: // hdl.handle.net/ 10138 / 237063

[13] רוברט ניוונהויס, אלברט אוליברס וצ'זארה טינלי. "תיאוריות מופשטות של DPLL ותיאוריות מופשטות של DPLL". בכנס בינלאומי בנושא לוגיקה לתכנות בינה מלאכותית והיגיון. עמודים 36–50. ספרינגר (2005).
https:/​/​doi.org/​10.1007/​978-3-540-32275-7_3

[14] יסמין כריסטיאן בלאנשט, סשה בוהם ולורנס סי פולסון. "הרחבת Sledgehammer עם פותרי SMT". Journal of Automated reasoning 51, 109–128 (2013).
https:/​/​doi.org/​10.1007/​s10817-013-9278-5

[15] דניאל רולף. "דרנדומיזציה של PPSZ עבור ייחודי-k-SAT". בכנס בינלאומי לתיאוריה ויישומים של בדיקת שביעות רצון. עמודים 216–225. ספרינגר (2005).
https: / doi.org/â € ‹10.1007 / 11499107_16

[16] דומיניק שדר וג'ון פ שטיינברגר. "PPSZ עבור k-SAT כללי, מה שהופך את הניתוח של Hertli לפשוט יותר ו-3-SAT מהיר יותר". בכנס ה-32 של מורכבות חישובית (CCC 2017). כרך 79, עמודים 9:1–9:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017).
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.9

[17] דניאל רולף. "הגבלה משופרת עבור אלגוריתם PPSZ/Schoning עבור 3-SAT". Journal on Satisfiability, Boolean Modeling and Computation 1, 111–122 (2006).
https://doi.org/​10.3233/​SAT190005

[18] טימון הרטלי. "3-SAT מהיר ופשוט יותר - גבולות SAT ייחודיים עבור PPSZ אחיזה באופן כללי". SIAM Journal on Computing 43, 718–729 (2014).
https: / / doi.org/ 10.1137 / 120868177

[19] טימון הרטלי. "שבירת מחסום PPSZ עבור 3-SAT ייחודי". באוטומט, שפות ותכנות: 41st International Colloquium, ICALP 2014, קופנהגן, דנמרק, 8-11 ביולי, 2014, Proceedings, Part I 41. עמודים 600–611. ספרינגר (2014).
https:/​/​doi.org/​10.1007/​978-3-662-43948-7_50

[20] דומיניק שדר. "PPSZ יותר טוב ממה שאתה חושב". בשנת 2021 IEEE סימפוזיון שנתי 62 על יסודות מדעי המחשב (FOCS). עמודים 205–216. (2022).
https: / / doi.org/ 10.1109 / FOCS52979.2021.00028

[21] לאב ק גרובר. "אלגוריתם מכאני קוונטי מהיר לחיפוש מסד נתונים". בהליכים של סימפוזיון ACM השנתי העשרים ושמונה על תורת המחשוב. עמודים 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[22] אנדריס אמביניס. "אלגוריתמי חיפוש קוונטיים". חדשות ACM SIGACT 35, 22–35 (2004).
https: / / doi.org/ 10.1145 / 992287.992296

[23] אנדריס אמביניס ומרטינס קוקאיניס. "אלגוריתם קוונטי להערכת גודל עץ, עם יישומים למעקב לאחור ומשחקים לשני שחקנים". בהליכים של סימפוזיון ACM SIGACT השנתי ה-2 על תורת המחשוב. עמודים 49–989. (1002).
https: / / doi.org/ 10.1145 / 3055399.3055444

[24] מייקל ג'ארט וקיאנה וואן. "אלגוריתמי מעקב קוונטיים משופרים באמצעות הערכות התנגדות אפקטיביות". סקירה פיזית A 97, 022337 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022337

[25] דומיניק ג'יי מוילט, נואה לינדן ואשלי מונטנרו. "האצה קוונטית של בעיית איש המכירות הנוסעים עבור גרפים של דרגות מוגבלות". פיזי. ר' א 95, 032323 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.032323

[26] ניל ד' ג'ונס וויליאם טי לאזר. "בעיות שלמות עבור זמן פולינום דטרמיניסטי". מדעי המחשב העיוני 3, 105 – 117 (1976).
https:/​/​doi.org/​10.1016/​0304-3975(76)90068-2

[27] ריימונד גרינלאו, H James Hoover, Walter L Ruzzo, et al. "גבולות לחישוב מקביל: תורת השלמות P". הוצאת אוניברסיטת אוקספורד לפי דרישה. (1995).

[28] תומס לנגאואר ורוברט אי טארג'אן. "גבולות הדוקים באופן אסימפטוטי על פשרות זמן-חלל במשחק חלוקים". Journal of the ACM (JACM) 29, 1087–1130 (1982).
https: / / doi.org/ 10.1145 / 322344.322354

[29] צ'ארלס ה' בנט. "פשרות זמן/מרחב לחישוב הפיך". SIAM Journal on Computing 18, 766–776 (1989).
https: / / doi.org/ 10.1137 / 0218053

[30] ט' אלטמן וי' איגרשי. "מיון גס: גישה רציפה ומקבילה". J. Inf. תהליך. 12, 154–158 (1989). כתובת אתר: http://​/​id.nii.ac.jp/​1001/​00059782/​.
http://​/​id.nii.ac.jp/​1001/​00059782/​

[31] הונג-יו ליאנג וג'ינג הי. "הסתפקות עם תלות במדד". כתב עת למדעי המחשב והטכנולוגיה 27, 668–677 (2012).
https:/​/​doi.org/​10.1007/​978-3-642-17517-6_7

[32] מרצ'לו בנדטי, ג'ון רילפ-גומז ואלחנדרו פרדומו-אורטיז. "מכונות הלמהולץ בסיוע קוונטים: מסגרת למידה עמוקה קוונטית-קלאסית עבור מערכי נתונים תעשייתיים במכשירים לטווח קצר". Quantum Science and Technology 3, 034007 (2018).
https: / / doi.org/ 10.1088 / 2058-9565 / aabd98

[33] ארם וו. הארו. "מחשבים קוונטיים קטנים ומערכי נתונים קלאסיים גדולים" (2020) arXiv:2004.00026.
arXiv: 2004.00026

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

[35] רוברט ב. גריפית'ס וצ'י-שנג ניו. "טרנספורמציה פורייה חצי קלאסית לחישוב קוונטי". פיזי. הכומר לט. 76, 3228–3231 (1996).
https: / / doi.org/ 10.1103 / PhysRevLett.76.3228

[36] רוברט ראוסנדורף והנס ג'יי בריגל. "מחשב קוונטי חד כיווני". פיזי. הכומר לט. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[37] תומס אי אובריאן, בריאן טרסינסקי וברברה מ.טרהל. "הערכת פאזה קוונטית של ערכים עצמיים מרובים עבור ניסויים בקנה מידה קטן (רועש). New Journal of Physics 21, 023022 (2019).
https://doi.org/​10.1088/​1367-2630/​aafb8e

[38] Akshay Ajagekar, Travis Humble, ו-Fengqi You. "אסטרטגיות פתרון היברידיות המבוססות על מחשוב קוונטי לבעיות אופטימיזציה בקנה מידה גדול-מתמשך". מחשבים והנדסה כימית 132, 106630 (2020).
https:/​/​doi.org/​10.1016/​j.compchemeng.2019.106630

[39] טיאני פנג, ארם וו הארו, מאריס אוזול ושיאודי וו. "הדמיית מעגלים קוונטיים גדולים במחשב קוונטי קטן". מכתבי סקירה פיזית 125, 150504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.150504

[40] סרגיי בראווי, גראם סמית' וג'ון א' סמולין. "מסחר במשאבי חישוב קלאסיים וקוונטיים". סקירה פיזית X 6 (2016).
https: / / doi.org/ 10.1103 / physrevx.6.021043

[41] מרטין סוון. "פתרון SAT במחשבים קוונטים רועשים". https:/​/​theses.liacs.nl/​1725 (2019). עבודת גמר לתואר ראשון.
https://​/​theses.liacs.nl/​1725

[42] תיאודור ג'יי יודר, גואנג האו לואו ואייזק ל' צ'ואנג. "חיפוש קוונטי בנקודה קבועה עם מספר אופטימלי של שאילתות". מכתבי סקירה פיזית 113 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.210501

[43] אלסנדרו קוסנטינו, רובין קוטארי ואדם פצניק. "סיקור נוסחאות קוונטיות של קריאה פעם אחת". בכנס ה-8 בנושא תורת החישוב הקוונטי, התקשורת והקריפטוגרפיה (TQC 2013). כרך 22 של Leibniz International Proceedings in Informatics (LIPIcs), עמודים 80–92. Dagstuhl, גרמניה (2013). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.80

[44] דיוויד א ברינגטון. "תוכניות הסתעפות בגודל פולינום מוגבל מכירות בדיוק את השפות הללו ב-NC1". כתב עת למדעי המחשב והמערכת 38, 150–164 (1989).
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

מצוטט על ידי

[1] קספר גיריק, כריס קייד, ו-ודראן דוניקו, "לקראת יתרון קוונטי באמצעות ניתוח נתונים טופולוגי", arXiv: 2005.02607, (2020).

[2] קייל EC Booth, בריאן או'גורמן, ג'פרי מרשל, סטיוארט הדפילד ואלינור ריפל, "תכנות אילוצים מואצות קוונטיות", קוונטום 5, 550 (2021).

[3] קספר גיריק, כריס קייד, ו-ודראן דוניקו, "לקראת יתרון קוונטי באמצעות ניתוח נתונים טופולוגי", קוונטום 6, 855 (2022).

הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2023-03-25 02:02:00). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.

On השירות המוזכר של קרוסרף לא נמצאו נתונים על ציטוט עבודות (ניסיון אחרון 2023-03-25 02:01:59)

מאמר זה מתפרסם בקוונטים תחת התקציב ייחוס Creative Commons 4.0 הבינלאומי (CC BY 4.0) רישיון. זכויות יוצרים נשארות עם בעלי זכויות היוצרים המקוריים כמו המחברים או מוסדותיהם.

בול זמן:

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