משפט הסף

הנושא האחרון בשיעור הזה הוא משפט חשוב מאוד הידוע בשם משפט הסף. להלן ניסוח לא-פורמלי יחסית של המשפט.

משפט

משפט הסף: ניתן לממש Circuit קוונטי בגודל $N$ עם דיוק גבוה באמצעות Circuit קוונטי רועש, בתנאי שהסתברות השגיאה בכל מיקום ב-Circuit הרועש נמוכה מערך סף קבוע ואי-אפסי $p_{\text{th}} > 0.$ גודל ה-Circuit הרועש מתקדם לפי $O(N \log^c(N))$ עבור קבוע חיובי $c.$

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

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

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

יש פרטים טכניים רבים בהוכחות הפורמליות של (ניסוחים פורמליים של) משפט זה, ופרטים אלה לא יוצגו כאן — אך את הרעיונות המהותיים ניתן להסביר ברמה אינטואיטיבית. כדי להפוך את ההסבר לפשוט ככל האפשר, נדמיין שאנחנו משתמשים בקוד שטיין בן $7$ ה-Qubitים לצורך תיקון שגיאות. זו תהיה בחירה לא מעשית ליישום פיזי ממשי — כפי שיבוא לידי ביטוי בערך סף זעיר ביותר $p_{\text{th}}$ — אך היא עובדת היטב להעברת הרעיונות המרכזיים. ההסבר גם יהיה די גמיש לגבי מודל הרעש, עם ההנחה שגיאה פוגעת בכל מיקום ביישום עמיד-לתקלות באופן עצמאי עם הסתברות $p.$

כעת, אם ההסתברות $p$ גדולה מהמהופך של $N,$ גודל ה-Circuit שאנחנו מכוונים לממש, הסיכויים גבוהים מאוד שגיאה תפגע איפשהו. לכן, נוכל לנסות להריץ יישום עמיד-לתקלות של ה-Circuit הזה, בהתאם לדרכי הפעולה שהוצגו בשיעור. לאחר מכן נוכל לשאול את עצמנו את השאלה שהועלתה קודם: האם זה משפר את המצב או מחמיר אותו?

אם ההסתברות $p$ לשגיאה בכל מיקום גדולה מדי, הרי שהמאמצים שלנו לא יעזרו ואף עלולים להחמיר את המצב, ממש כמו שקוד שור בן 9 ה-Qubitים לא עוזר כאשר הסתברות השגיאה עולה על כ-3.23%. בפרט, היישום העמיד-לתקלות גדול משמעותית מה-Circuit המקורי שלנו, ולכן יש הרבה יותר מיקומים שבהם שגיאות עלולות לפגוע.

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

ביתר פירוט, כדי שתתרחש שגיאה לוגית ב-Circuit המקורי, לפחות שתי שגיאות חייבות ליפול לאותו בלוק קוד ביישום העמיד-לתקלות, מכיוון שקוד שטיין יכול לתקן כל שגיאה בודדת בבלוק קוד. תוך התחשבות בכך שיש דרכים רבות לקבל שתי שגיאות ומעלה באותו בלוק קוד, ניתן לטעון שהסתברות שגיאה לוגית בכל מיקום ב-Circuit המקורי היא לכל היותר $C p^2$ עבור מספר ממשי חיובי קבוע $C$ התלוי בקוד ובגאדג'טים שבהם אנחנו משתמשים, אך באופן קריטי לא ב-$N,$ גודל ה-Circuit המקורי. אם $p$ קטן מ-$1/C,$ שהוא המספר שנוכל לקחת כערך הסף שלנו $p_{\text{th}},$ זה מתורגם להקטנת שגיאה.

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

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

נתחיל עם הסתברות השגיאה $p$ עבור מיקומים ב-Circuit המקורי. בהנחה ש-$p < p_{\text{th}} = 1/C,$ ניתן לחסום את שיעור השגיאות הלוגיות ב-$Cp^2 = (Cp) p$ לאחר האיטרציה הראשונה. כאשר מתייחסים ליישום העמיד-לתקלות ככל Circuit אחר, ומממשים אותו באופן עמיד-לתקלות, מקבלים חסם על שיעור השגיאות הלוגיות של

$$C \bigl((Cp) p \bigr)^2 = (Cp)^3 p.$$

איטרציה נוספת מורידה את חסם השגיאות עוד יותר, ל-

$$C \bigl((Cp)^3 p \bigr)^2 = (Cp)^7 p.$$

המשך בדרך זו עבור סך הכל $k$ איטרציות מוביל לשיעור שגיאות לוגיות (עבור ה-Circuit המקורי) שחסום על ידי

$$(Cp)^{2^k - 1} p,$$

שהוא חזקה כפולה של $k.$

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

אז, מה הוא ערך הסף בפועל? התשובה תלויה בקוד ובגאדג'טים שבהם משתמשים. עבור קוד שטיין יחד עם זיקוק מצבי מאגיה, הוא זעיר ביותר וסביר להניח שלא ניתן להשיגו בפועל. אך, באמצעות קודי שטח וגאדג'טים מתקדמים, הסף הוערך בסדר גודל של 0.1% עד 1%.

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

סקר לאחר הקורס

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