בינה מלאכותית הוכיחה את השערת אהרונסון–אמבייניס: מחשבים קוונטיים מוגבלים במשימות ללא מבנה

נערך על ידי: Svitlana Velhush

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

בנובמבר 2026 הכריז הסטארט-אפ Physical Superintelligence (PSI) בארצות הברית על הוכחת השערה שניסחו בשנת 2011 סקוט אהרונסון מאוניברסיטת טקסס באוסטין ואנדריס אמבייניס מאוניברסיטת לטביה. ההשערה קבעה: עבור פולינומים ממעלה נמוכה המקבלים ערכים מ-0 עד 1 על הקובייה הבוליאנית, תמיד יימצא משתנה בעל השפעה ניכרת. את ההוכחה מצאה מערכת המחקר הפנימית של PSI המבוססת על מודל לא פומבי של Anthropic. הטקסט המלא עבר בדיקה במערכת Lean, ואת התצוגה הכינו חוקרים מסטנפורד — גאי בלנק, ג'ורדן דוקטר, כרמן שטרסל ולי-יאנג טאן.

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

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

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

מאמר ב-New Scientist מ-12 בנובמבר 2026 ואת ה-preprint ב-arXiv מ-8 בנובמבר מתארים בפירוט את מהלך ההוכחה ואת השלכותיה על היחס בין המחלקות BPP ו-BQP בעולם של אורקלים אקראיים.

העליונות הקוונטית מתוחמת כעת בבירור רב יותר: היא ממשית, אך דורשת לא אקראיות אלא חוקיות נסתרת.

3 צפיות

מקורות

  • AI confirms a long-suspected limit on quantum computers’ advantages

  • psi.inc

  • arxiv.org

תגובות

מצאתם טעות או אי-דיוק?הערותיכם ייבחנו בהקדם האפשרי.