קיוביטים וחיפוש.

שלב 1 מתוך 9

קיוביט

סיבית רגילה היא 0 או 1. קיוביט הוא סיבית קוונטית, ומצבו מצויר כאן כחץ על כדור: למעלה $|0\rangle$⁠, למטה $|1\rangle$⁠, וכל כיוון אחר הוא סופרפוזיציה, צירוף של שניהם. הקיוביט עצמו הוא מעגל זעיר על השבב שמתחת לכדור, מוליך־על שעובד רק בקור עז, סמוך לאפס המוחלט.

שערים הם הפעולות של מחשב קוונטי, כמו AND ו־NOT בשערים לוגיים, וכל שער מסובב את החץ. השער X (NOT) מסובב אותו חצי סיבוב, מ־$|0\rangle$⁠ אל $|1\rangle$⁠, בדיוק כמו NOT. השער H מטה אותו אל קו המשווה. מדידה וחיפוש נעולים עכשיו על קיוביט. נבאו מה ייתנו המדידות.

שלב 2 מתוך 9

פאזה

עכשיו המדידות פועלות: כל מדידה עפה מהחץ אל אחת המבחנות, 0 או 1, והטבעת מסמנת את הסיכוי. שער עומד על H ואז Z. השער Z מסובב את החץ חצי סיבוב סביב הציר האנכי, אל הצד הנגדי של קו המשווה. הכיוון של החץ סביב הציר הזה נקרא פאזה.

נסו: החליפו בין H ל־H ואז Z והשוו את המבחנות.

חזרה לניסוי ↑

שלב 3 מתוך 9

התאבכות

H ו־Z לבדם לא נראים מועילים: אחד נותן תוצאה אקראית, והשני משנה משהו שמדידה לא רואה. הכוח מגיע כשמחברים שערים. שער נעול עכשיו על H. נבאו מה יעשה H שני.

שלב 4 מתוך 9

חיפוש

החיפוש של גרובר מוצא פריט מסומן אחד מתוך $N$⁠ פריטים לא ממוינים. עם $n$⁠ קיוביטים יש $N = 2^n$⁠ פריטים, ובהתחלה שער H על כל קיוביט נותן לכולם אותו סיכוי: מדידה היא ניחוש עיוור. כל סבב הופך את הסימן של התשובה ואז משקף כל עמודה סביב הממוצע, והעמודה של התשובה גדלה. על הכדור, החץ זז בכל סבב באותה זווית, מ“כל התשובות השגויות” שבקוטב העליון אל התשובה שבקוטב התחתון.

ההתחלה קרובה מאוד אל “כל התשובות השגויות”, והזווית שכל סבב מוסיף קטנה, ביחס ישר ל־$\dfrac{1}{\sqrt{N}}$⁠. לכן צריך כ־$\dfrac{\pi}{4}\sqrt{N}$⁠ סבבים כדי להגיע אל התשובה. גודל החיפוש וסבבי החיפוש נעולים עכשיו.

שלב 5 מתוך 9

יותר מדי סבבים

16 פריטים ו־3 סבבים: העמודה של התשובה גבוהה, והחץ כמעט בקוטב התחתון. סבבי החיפוש נעול. נבאו מה יקרה אם תמשיכו לסובב.

שלב 6 מתוך 9

מיליון פריטים

חיפוש רגיל במאגר לא ממוין בודק פריט אחר פריט, ובממוצע צריך $\dfrac{N + 1}{2}$⁠ בדיקות. החיפוש של גרובר צריך כ־$\dfrac{\pi}{4}\sqrt{N}$⁠ סבבים. כשהמאגר קטן ההבדל קטן, אבל הוא גדל עם $N$⁠: מספר הבדיקות גדל כמו $N$⁠, ומספר הסבבים רק כמו $\sqrt{N}$⁠.

נסו: שנו את גודל החיפוש ואת סבבי החיפוש, ומצאו לכל גודל את מספר הסבבים שבו הסיכוי הגבוה ביותר.

חזרה לניסוי ↑

שלב 7 מתוך 9

היפוך

לא כל שער יוצר אקראיות. נתחיל מהשער שגם למחשב רגיל יש.

שלב 8 מתוך 9

כמה פריטים

במדידה וחיפוש על חיפוש כל פריט הוא צירוף אחד של אפסים ואחדות.

שלב 9 מתוך 9

הדרך הרגילה

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