אלגוריתם היסטי וריאציוני חסכוני-קוביטים ל-MaxCut

למה שבבים קוונטיים זעירים חשובים לפאזלים גדולים

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

לחתוך רשת לשתי חצאים שימושיים

MaxCut שואל שאלה שנשמעת פשוטה: אם יש קבוצת נקודות (קודקודים) שמחוברות בקווים (קשתות), איך לצבוע כל קודקוד, למשל כחול או לבן, כך שכמה שיותר קווים יחברו בין קודקודים בצבעים שונים? החלוקה הטובה ביותר שימושית בתחומים כמו תכנון מעגלים ופיזיקה סטטיסטית, אך קשה למצוא אותה בדיוק כאשר הגרף גדול. גישה קלאסית נפוצה, אלגוריתם Goemans–Williamson (GW), מבצעת רילאקסציה חכמה של הבעיה ומבטיחה מציאת חיתוך שיהיה לפחות בערך 88% מהאופטימלי. המחשוב הקוונטי מבטיח דרכים חדשות להתמודדות עם בעיות כאלה, אך המכשירים העכשוויים רעשניים ומוגבלים בגודל, מה שמקשה על הרצת מעגלים גדולים ועמוקים.

לפתור גרפים גדולים עם רק כמה קיוביטים

גישות קוונטיות סטנדרטיות כמו Quantum Approximate Optimization Algorithm (QAOA) דורשות קיוביט אחד לכל קודקוד, כך שגרף של 1,000 קודקודים יצריך 1,000 קיוביטים — מעבר למכונות של היום. השיטה החדשה, שנקראת Qubit-Efficient MaxCut (QEMC), משנה את הסקיילינג הזה: היא משתמשת רק בערך בלוגריתם של מספר הקודקודים, כלומר 11 קיוביטים יכולים לייצג מידע על יותר מ-2,000 קודקודים. במקום לקשר כל קיוביט לקודקוד בודד, QEMC משתמשת בכל מצב הקוונטי כמרחב כתובות קומפקטי ומקשרת קודקודים שונים למצבי בסיס שונים של הרישום הקטן הזה. השימור הזה בקיוביטים שומר על מעגלים רדודים וקלים יותר לביצוע בחומרה רעשנית, ובמקביל מייצג גרפים מאוד גדולים.

צבעים של קודקודים על פי הסתברות במקום מצבים קבועים

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

בדיקת הביצועים במכונות אמיתיות וסימולציות

המחברים בוחנים את QEMC בשני צירים: מעבדים קוונטיים אמיתיים וסימולציות קלאסיות של המעגלים הקוונטיים. בגרפים רגולריים קטנים עד 32 קודקודים (בשימוש ב-2 עד 5 קיוביטים בלבד), QEMC שרץ על חומרת על-מוליכיות של IBM מוצא חיתוכים התואמים או קרובים מאוד לתוצאות הטובות ביותר שנמצאו באמצעות חיפוש ממצה, ובכך מתעלה בבירור על ניחוש אקראי ועל מחקרים קוונטיים קודמים מבוססי QAOA. בסימולציות ללא רעש, QEMC מגיע בעקביות ליותר מ-97% מהחיתוך האופטימלי עבור הגרפים הקטנים הללו. כוח הקידוד הופך לבולט עוד יותר עבור גרפים גדולים יותר: עבור גרפים רגולריים מדרגה 9 עד 2,048 קודקודים, סימולציות קלאסיות של QEMC עדיין מביסות את GW הן בממוצע והן בחיתוך הטוב ביותר בכמה אחוזים, ויתרונות דומים נראים גם בגרפים אקראיים של 128 קודקודים עם צפיפויות שונות.

מהירות, גבולות והבטחה בהשראת קוונטים

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

מה העבודה הזאת משמעותית לעתיד

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

ציטוט: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

מילות מפתח: MaxCut, אופטימיזציה קוונטית, אלגוריתמים וריאציוניים, חיתוך גרפים, חישוב בהשראת קוונטים