סיבית, וקיוביט
סיבית רגילה היא מתג: 0 או 1, ואפשר להסתכל עליה כמה פעמים שרוצים בלי לשנות אותה. קיוביט הוא הגרסה הקוונטית שלה. בשבב שבתחתית הסצנה הוא לולאה זעירה של מתכת מוליכת־על, מקוררת למאית מעלה מעל האפס המוחלט, שהזרם בה יכול להתייצב בשני מצבים נפרדים שנקראים |0⟩ ו־|1⟩ (קוראים “קט אפס” ו“קט אחד”). מכונות אחרות משתמשות באטומים בודדים לכודים, בפוטונים או בספינים של אלקטרונים; הרעיון זהה.
מה שהופך אותו ליותר מסיבית הוא מה שהוא יכול לעשות בין שני המצבים האלה. המצב שלו מתואר בשני מספרים, שנקראים משרעות, אחד ל־|0⟩ ואחד ל־|1⟩. דרך נאה לצייר אותם היא ספירת בלוך: המצב הוא חץ מהמרכז אל פני הספירה. ישר למעלה זה |0⟩, ישר למטה זה |1⟩, וכל נקודה אחרת היא סופרפוזיציה, מצב מוגדר שאינו אף אחד מהשניים. הגובה של החץ אומר איך מתחלקים הסיכויים לקרוא 0 ו־1; הכיוון שאליו הוא פונה סביב קו המשווה, שנקרא פאזה, הוא דבר שני שלסיבית פשוט אין.
שערים מסובבים את החץ
תוכנית קוונטית היא רשימה של שערים, וכל שער מסובב את הספירה. בשבב מוליך־על, שער הוא פולס קצר של גלי מיקרו, שנמשך כמה עשרות ננו־שניות ונשלח בכבל אל הקיוביט.
שער X הוא חצי סיבוב סביב ציר שמאל–ימין: הוא מוביל את |0⟩ למטה אל |1⟩ ואת |1⟩ בחזרה למעלה, כך שהוא עושה מה ש־NOT עושה לסיבית. שער H (אדמר) הוא חצי סיבוב סביב ציר שנוטה באמצע הדרך בין למעלה לימין. הוא לוקח את |0⟩ אל הנקודה על קו המשווה שמסומנת |+⟩, סופרפוזיציה שווה. שער Z הוא חצי סיבוב סביב הציר האנכי. הוא משאיר את |0⟩ ואת |1⟩ במקומם, אבל מסובב חץ שעל קו המשווה אל הצד הנגדי, מ־|+⟩ אל |−⟩: אותו גובה, פאזה הפוכה.
נסו: תחת שער, בחרו X (NOT), אחר כך H, ואחר כך H ואז Z. השובל המנוקד מראה את המסלול שלאורכו כל שער מסובב את החץ, ובכל פעם מתחילים מ־|0⟩.
מדידה נותנת סיבית אחת
הזיזו את מדידה וחיפוש אל מדידה. כל חרוז זוהר הוא הרצה אחת של הניסוי: מכינים את הקיוביט, מפעילים את השער ומודדים אותו. מדידה יכולה לענות רק 0 או 1, והקיוביט נשאר במצב שהמדידה דיווחה עליו, כך שאי אפשר לקרוא סופרפוזיציה בבת אחת. במקום זה, הגובה של החץ קובע את הסיכויים: הסיכוי לקרוא 1 הוא (1 − z)/2, כאשר z הוא הגובה של החץ על ספירה שהרדיוס שלה 1. זהו כלל בורן.
עם H השפופרות מתמלאות בערך חצי־חצי, והטבעות מסמנות בדיוק 50%. כל סדרה של 40 מדידות נודדת סביב זה: 18 ו־22 סביר כמעט כמו 20 ו־20. עם H ואז Z השפופרות נראות בדיוק אותו דבר, כי מדידה של 0 או 1 לא יכולה לראות את הפאזה. עד כאן קיוביט נראה כמו מטבע יקר.
הפאזה יוצרת התאבכות
עכשיו בחרו H ואז H. אילו H היה הטלת מטבע, הפעלה כפולה שלו הייתה עדיין נותנת הטלת מטבע. במקום זה הקיוביט נותן 0 בכל פעם. ה־H השני מוביל את החץ בשאר הדרך סביב המעגל שלו ובחזרה למעלה.
במונחים של משרעות, יש שני מסלולים מ־|0⟩ אל |1⟩ דרך שני השערים, והם מגיעים עם סימנים הפוכים, ולכן מבטלים זה את זה. שני המסלולים אל |0⟩ מגיעים עם אותו סימן ומצטרפים זה לזה. זו התאבכות, אותה תופעה שיוצרת פסים בהירים וכהים כשגלים חופפים, והיא המשאב שאלגוריתמים קוונטיים מנצלים. הפאזה, שמדידה בודדת לא יכולה לראות, קובעת מה יעשה השער הבא. אלגוריתם קוונטי הוא רצף של שערים שמסודרים כך שהמסלולים אל התשובות השגויות מבטלים זה את זה, והמסלולים אל התשובה הנכונה מחזקים זה את זה, עוד לפני שמשהו נמדד.
ההתאבכות מוצאת את התשובה
המשיכו אל חיפוש. הלוח מציג את אלגוריתם החיפוש של לוב גרובר משנת 1996 על אוגר של 4 קיוביטים, שיש להם יחד 16 ערכים אפשריים, מ־0000 עד 1111. אחד מהם, 1011, הוא התשובה, והדרך היחידה לזהות אותו היא בדיקה שמסמנת אותו, שנקראת אורקל. במחשב קלאסי הייתם בודקים את הפריטים אחד אחד, בערך 8 ניסיונות בממוצע ו־16 במקרה הגרוע ביותר.
החיפוש מתחיל בהפעלת H על כל קיוביט, וזה נותן לכל 16 הערכים אותה משרעת, רבע לכל אחד. מדידה עכשיו היא ניחוש עיוור, עם סיכוי של 1 מתוך 16. אחר כך כל סבב עושה שני דברים לכל האוגר בבת אחת:
- האורקל הופך את הסימן של המשרעת של התשובה. העמודה שלה צוללת אל מתחת לקו; שום דבר שמדידה הייתה יכולה לראות עדיין לא השתנה.
- צעד שני, הדיפוזיה, משקף כל משרעת סביב הממוצע, שמצויר כקו מנוקד. מכיוון שהעמודה של התשובה נמצאת עכשיו מתחת לממוצע, היא נזרקת הרחק מעליו, וכל שאר העמודות מתכווצות מעט.
אחרי סבב אחד הסיכוי למצוא את 1011 הוא 47%, אחרי שניים 91% ואחרי שלושה 96%. בינתיים החץ על הספירה מספר את אותו הסיפור. כשהקצה העליון מסומן מחדש “כל התשובות השגויות” והתחתון “התשובה”, כל האוגר מתנהג כמו קיוביט אחד, וכל סבב מסובב את החץ באותה זווית לעבר התשובה. הגובה שלו עדיין נותן את הסיכוי למצוא אותה.
נסו: העלו את גודל החיפוש ל־6 קיוביטים, 64 פריטים, והעלו את סבבי החיפוש מ־0. שישה סבבים מעלים את הסיכוי אל מעל 99%, בזמן שבדיקה של פריט אחד בכל פעם הייתה דורשת בערך 32 ניסיונות בממוצע.
יותר מדי מדבר טוב
הוסיפו עוד סבבים, והסיכוי יורד שוב: עם 16 פריטים, 4 סבבים נותנים 58% ו־6 נותנים 2%. כל סבב הוא אותו סיבוב, ולכן החץ חולף על פני התשובה וחוזר לכיוון התשובות השגויות. מספר הסבבים הטוב ביותר הוא בערך (π/4)√N עבור N פריטים, כך שהחיפוש דורש בערך √N סבבים, כשבדיקה של הפריטים אחד אחד דורשת בערך N/2 ניסיונות. למיליון פריטים זה בערך 785 סבבים במקום חצי מיליון ניסיונות.
ההאצה הזאת, בשורש ריבועי, אמיתית אבל צנועה, והיא המרב שמחשב קוונטי יכול להשיג בחיפוש שאין בו מבנה לנצל; הדבר הוכח ב־1997. רווחים גדולים יותר מגיעים מבעיות עם תבניות נסתרות שהתאבכות יכולה לחשוף, כמו השיטה של פיטר שור משנת 1994 לפירוק מספרים גדולים לגורמים, שמאיימת על חלק משיטות ההצפנה של היום, וכמו סימולציה של מולקולות וחומרים, שהם בעצמם מערכות קוונטיות.
מה המודל הזה משמיט
הסצנה מראה קיוביט מושלם. קיוביטים אמיתיים מופרעים על ידי חום, שדות תועים והחיווט שלהם עצמם, ובשבבי מוליכי־העל של היום הם מאבדים את הפאזה שלהם בתוך בערך עשירית אלפית עד אלפית שנייה, כך שכל שער גם מוסיף שגיאה קטנה. מכונות שימושיות יצטרכו תיקון שגיאות קוונטי, הרבה קיוביטים פיזיים שפועלים יחד כקיוביט אמין אחד, ובנייתו היא האתגר ההנדסי העיקרי.
ספירת בלוך היא מפה של המצב של קיוביט יחיד, לא עצם שנמצא בתוך השבב; שום דבר פיזי לא מסתובב. כמה קיוביטים יחד יכולים להיות שזורים, כלומר לחלוק מצב שאף אוסף של חצים נפרדים לא יכול לתאר; החיפוש משתמש בזה, אבל הסצנה לא מציירת את זה. הספירה של החיפוש עובדת כי המצב של גרובר נשאר תמיד במישור של “התשובה” ו“כל השאר”. באמצע צעד העמודות נעות בקווים ישרים בין המצבים המדויקים שבקצותיו, וזה מראה לאן הצעד הולך ולא את המסלול שאוגר אמיתי עובר בו, והמדידות לקוחות מרשימה קבועה של הגרלות אקראיות.