חישוב קוונטי - טלפורטציה, קידוד צפוף ושערים קוונטיים

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

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

ובכן, לא, לא בלי שפן נוסף שאפשר לשלוף מהכובע - והשפן הנוסף הזה הוא משהו שאליס ובוב שיתפו ביניהם לפני שנפרדו - זוג קיוביטים שזורים, במצב \( \frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}} \) החביב עלינו. אני טוען שבעזרת הזוג הזה, וערוץ התקשורת הרגיל ביניהם, אליס יכולה לשלוח לבוב מצב קוונטי \( \left|\psi\right\rangle \) שרירותי לגמרי. איך זה לא סותר את משפט ה-No Cloning? פשוט מאוד - כחלק מתהליך השליחה הזה אליס תתעלל בקיוביט שלה בצורה שתגרום להרס המצב הקוונטי אצלה.

התהליך הזה נקרא בשם המאוד מפוצץ “העתקה קוונטית”, או “טלפורטציה קוונטית”. למה מפוצץ? כי זה גורם לנו לחשוב על המשגר של “מסע בין כוכבים”. אבל שימו לב שמדובר על מעבר של אינפורמציה קוונטית בלבד - הקיוביט של אליס לא משתגר לקצה השני של היקום; רק המידע שהיה “מקודד” בו ואבד. אני אשאיר לכם את ההחלטה מה המשמעויות הפילוסופיות של קיום טלפורטציה קוונטית שכזו (אבל קיומה לא שנוי במחלוקת; כבר הצליחו לממש טלפורטציה קוונטית בניסויים).

איך זה עובד בפועל? הנה התהליך ממעוף הציפור. בהתחלה לאליס יש את \( \left|\psi\right\rangle \) שאסמן \( \left|\psi\right\rangle =a\left|0\right\rangle +b\left|1\right\rangle \) וזאת בנוסף לקיוביטים השזורים שלה ושל בוב, שנמצאים במצב \( \left|\varphi\right\rangle =\frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}} \). המערכת המשולבת של זוג הקיוביטים הללו יחד עם המצב הקוונטי שיש לאליס היא \( \left|\varphi\right\rangle \otimes\left|\psi\right\rangle \) - כי מכפלה טנזורית היא מה שמתאר את מצב המערכת המשולבת כשאין עדיין קורלציה קוונטית כלשהי בין המערכות השונות.

בואו נכתוב בצורה מפורשת איך המערכת הזו נראית:

\( \frac{1}{\sqrt{2}}\left(a\left|000\right\rangle +a\left|011\right\rangle +b\left|100\right\rangle +b\left|111\right\rangle \right) \)

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

הדבר הבא שאליס עושה הוא להפעיל קסם על המערכת. וכשאני אומר “קסם”, אני מתכוון לטרנספורמציה אוניטרית שמעבירה את המערכת למצב הבא:

\( \frac{1}{2}\left|00\right\rangle \left(a\left|0\right\rangle +b\left|1\right\rangle \right)+\frac{1}{2}\left|01\right\rangle \left(a\left|1\right\rangle +b\left|0\right\rangle \right)+ \)

\( \frac{1}{2}\left|10\right\rangle \left(a\left|0\right\rangle -b\left|1\right\rangle \right)+\frac{1}{2}\left|11\right\rangle \left(a\left|1\right\rangle -b\left|0\right\rangle \right) \)

כאן הרשיתי לעצמי “לפרק” ביטוי כמו \( \left|101\right\rangle \) ל-\( \left|10\right\rangle \left|1\right\rangle \), מתוך מטרה לשמר את הקריאות של הביטוי ושנבין מה הולך פה. השאלה הראשונה שנשאלת, כמובן, היא מה הקסם שבזכותו אליס הצליחה להגיע למצב הזה; בכך נעסוק בהמשך - הרי כל עניין הטלפורטציה מיועד לתת לי מוטיבציה לתאר את הקסם. השאלה השניה היא מה זה עזר לנו.

עכשיו מגיע הפאנץ’: אליס מודדת את שני הקיוביטים שלה. את זה ששזור עם הקיוביט של בוב (“הביט האמצעי”) ואת זה שהיא רצתה לשלוח את המצב הקוונטי שלו (“הביט השמאלי”). כל אחת מארבע התוצאות האפשריות - \( \left|00\right\rangle ,\left|01\right\rangle ,\left|10\right\rangle ,\left|11\right\rangle \) היא סבירה באותה מידה, אבל ההסתברות לא מעניינת את אליס; מה שמעניין אותה הוא רק מה היו תוצאות המדידה. התוצאות הללו הן שני ביטים של מידע; את המידע הזה אליס שולחת לבוב באינטרנט.

עכשיו, נניח שאליס קיבלה \( \left|00\right\rangle \). מה זה אומר? זה אומר שאחרי המדידה שלה, המערכת קרסה למצב \( \left|00\right\rangle \left(a\left|0\right\rangle +b\left|1\right\rangle \right) \) . בפרט, הקיוביט של בוב הוא עכשיו במצב \(  a\left|0\right\rangle +b\left|1\right\rangle \), שזה בדיוק הקיוביט שהיה לאליס בהתחלה! קסם! בוב בעצם לא צריך לעשות כלום, וסיימנו!

ונניח שאליס קיבלה \( \left|01\right\rangle \). מה זה אומר? שהקיוביט של בוב קרס למצב \( a\left|1\right\rangle +b\left|0\right\rangle \). זה כמעט המצב שרצינו, אבל התפקידים של \( a,b \) התהפכו. העניין הוא שבוב יכול לתקן את ההתהפכות הזו על ידי הפעלת טרנספורמציה אוניטרית מתאימה. באופן דומה גם לכל תוצאה אחרת של אליס בוב יוכל לתקן את הקיוביט שלו כך שיהיה זהה לקיוביט שאליס התחילה ממנו - אבל בוב צריך לדעת מה משובש בקיוביט שלו - לכן הוא חייב לחכות לתקשורת-דרך-האינטרנט של אליס.

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

האופן שבו אנחנו רוצים להציג חישובים הוא באמצעות שערים. בעולם הקלאסי, שערים לוגיים הם דרך פשוטה ונאה לתאר חישובים מורכבים. כל “שער” שכזה מקבל כמות קטנה מאוד של ביטים כקלט - לרוב ביט בודד או שניים - ומחשב פונקציה כלשהי שלהם (השאלה איך בונים שער כזה ברמה הפיזיקלית היא מעניינת, כמובן, אבל פתורה לגמרי). באמצעות הרכבה של שערים אחד עם השני, מקבלים מעגל (למרות שהשם מטעה; אין בו בדרך כלל מעגליות) שמחשב פונקציות מורכבות. דוגמאות לשערים “קלאסיים” הם שער AND שמקבל שני ביטים ומחזיר 1 רק אם שניהם 1, אחרת מחזיר 0; שער OR שמקבל שני ביטים ומחזיר 0 רק אם שניהם 0, אחרת מחזיר 1; ושער NOT שמקבל ביט אחד ומחזיר את ההפך ממנו, כלומר על 0 מחזיר 1 ועל 1 מחזיר 0.

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

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

השער הראשון מסומן בתור \( H \), מלשון “הדמאר” (המתמטיקאי). עזבו אתכם כרגע מהשאלה למה. מה שהוא עושה פשוט למדי, מבחינה רעיונית: הוא מעביר את הבסיס הסטנדרטי לבסיס \( \left|+\right\rangle ,\left|-\right\rangle \) שראינו בפוסט הקודם כמה הוא מועיל. למי שלא קרא את הפוסט הקודם, נזכיר את ההגדרות:

\( \left|+\right\rangle =\frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}} \)

\( \left|-\right\rangle =\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}} \)

שני הוקטורים הללו מהווים בסיס אלטרנטיבי למרחב שמתאר את הקיוביט, והבסיס הזה מקיים את התכונה היפה שאם מודדים את \( \left|+\right\rangle \) או את \( \left|-\right\rangle \) ביחס לבסיס הסטנדרטי, כל אחת משתי התוצאות מתקבלת באותה הסתברות. הייתי אומר שהבסיס החדש הזה הוא “מאונך” לבסיס הסטנדרטי אם הייתה לכך משמעות מתמטית כלשהי.

אז פורמלית, \( H \) מוגדר כך:

\( \left|0\right\rangle \mapsto\left|+\right\rangle \)

\( \left|1\right\rangle \mapsto\left|-\right\rangle \)

אינטואיטבית, \( H \) מעביר את \( \left|0\right\rangle \) אל הסופרפוזיציה “הכי סימטרית” שקיימת עבור קיוביט בודד. לכן כשמפעילים את \( H \) על אוסף של כמה קיוביטים התוצאה היא הסופרפוזיציה “הכי סימטרית” עבור המערכת שמורכבת מהקיוביטים הללו. פורמלית:

\( \left(H\otimes H\otimes\dots\otimes H\right)\left|00\dots0\right\rangle =\frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^{n}-1}\left|x\right\rangle \)

כאשר כאן \( \left|x\right\rangle \) הוא סימון מוסכם לכתיב של \( x \) בבסיס בינארי עם בדיוק \( n \) ספרות, עם אפסים מובילים (כלומר, אם \( x=3 \) ו-\( n=4 \) אז \( \left|x\right\rangle \) הוא סימון מקוצר ל-\( \left|0011\right\rangle \)).

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

האופרטור השני שאני רוצה להציג כרגע הוא סוג של שער NOT שמערב שני קיוביטים ולא קיוביט בודד (לא שכחנו מה-NOT של קיוביט בודד והוא יחזור בהמשך). הוא מכונה \( C_{not} \), קיצור של Controlled not, שכן עקרון הפעולה שלו על אברי בסיס הוא זה: אם הקיוביט הראשון הוא 0 אז לא לעשות כלום, ואם הקיוביט הראשון הוא 1, אז לשמש בתור NOT של הקיוביט השני. פורמלית:

\( \left|00\right\rangle \mapsto\left|00\right\rangle \)

\( \left|01\right\rangle \mapsto\left|01\right\rangle \)

\( \left|10\right\rangle \mapsto\left|11\right\rangle \)

\( \left|11\right\rangle \mapsto\left|10\right\rangle \)

לא קשה לראות שזו טרנספורמציה אוניטרית (היא גם הצמוד של עצמה וגם ההופכית של עצמה).

עכשיו אפשר לתאר פורמלית את מה שאליס עושה במהלך הטלפורטציה: קודם היא מפעילה \( C_{not} \) על שני הקיוביטים שלה, ואז היא מפעילה \( H \) על הקיוביט שהיא רוצה לשכפל (ולסיום היא מודדת את שני הקיוביטים שלה).

בואו נראה למה זה עובד. כזכור, בהתחלה מצב המערכת כולה הוא

\( \frac{1}{\sqrt{2}}\left(a\left|000\right\rangle +a\left|011\right\rangle +b\left|100\right\rangle +b\left|111\right\rangle \right) \)

ואז באה אליס ומפעילה את \( C_{not} \), או ליתר דיוק את \( C_{not}\otimes I \) כי בקיוביט השלישי היא לא נוגעת. אם כן, אנו עוברים למצב

\( \frac{1}{\sqrt{2}}\left(a\left|000\right\rangle +a\left|011\right\rangle +b\left|110\right\rangle +b\left|101\right\rangle \right) \)

עכשיו אליס מפעילה \( H \) על הקיוביט הראשון. זה אומר שכל וקטור כמו \( \left|000\right\rangle \) הולך להתפצל לשני וקטורים, עבור שני הערכים השונים עבור הביט הראשון שלו, ושהכל יוכפל בשורש 2. מכיוון שאין שני וקטורים בסכום ששני הביטים האחרונים שלהם זהים (בזכות הפעלת \( C_{not} \)) נקבל שמונה מחוברים שונים:

\( \frac{1}{2}a\left(\left|000\right\rangle +\left|100\right\rangle +\left|011\right\rangle +\left|111\right\rangle \right)+ \)

\( \frac{1}{2}b\left(\left|010\right\rangle +\left|110\right\rangle +\left|001\right\rangle +\left|101\right\rangle \right) \)

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

נשאר לדבר על איך בוב “מתקן” את המצב הקוונטי במקרה שבה הוא לא בדיוק המצב שממנו התחלנו (אבל בוב כן יודע בדיוק איך הוא “השתבש”). הנה שלושת המקרים האפשריים:

• \( b\left|0\right\rangle +a\left|1\right\rangle \)
• \( -b\left|0\right\rangle +a\left|1\right\rangle \)
• \( a\left|0\right\rangle -b\left|1\right\rangle \)

בשביל המקרה הראשון אנחנו צריכים אופרטור שמחליף בין 0 ו-1, כלומר \( \left|0\right\rangle \mapsto\left|1\right\rangle \) ו-\( \left|1\right\rangle \mapsto\left|0\right\rangle \). לאופרטור הזה אקרא \( X \). בשביל המקרה השני אנחנו צריכים לבצע את אותה החלפה אבל גם לכפול ב-\( -1 \) את המקדם של \( \left|0\right\rangle \), כלומר \( \left|0\right\rangle \mapsto-\left|1\right\rangle \) ו-\( \left|1\right\rangle \mapsto\left|0\right\rangle \). את האופרטור הזה אסמן בתור \( Y \). לבסוף, במקרה האחרון רק צריך להכפיל ב-\( -1 \) את המקדם של \( \left|1\right\rangle \), כלומר האופרטור יהיה \( \left|0\right\rangle \mapsto\left|0\right\rangle \) ו-\( \left|1\right\rangle \mapsto-\left|1\right\rangle \). לאופרטור הזה אקרא \( Z \). השמות של האופרטורים מגיעים ממטריצות פאולי המתאימות - אבל צריך לשים לב שההתאמה הזו לא מדויקת (לאן \( i \) נעלם?) ולא חייבים להבין במטריצות פאולי כאן.

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

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

מה שאליס עושה הוא לבדוק מה ערכם של זוג הביטים שהיא רוצה לשדר. בהתאם לערך הזה, היא מפעילה שער כלשהו על הקיוביט שלה - אחד מבין \( I,X,Y,Z \) (\( I \) הוא ה”שער” שלא עושה כלום; אפשר לוותר עליו בפועל, כמובן). אחר כך היא שולחת לבוב את הקיוביט שלה (ההנחה כאן היא שיש לה ערוץ שידור קוונטי, כמובן). כשבוב מקבל את הקיוביט, הוא עושה שלושה דברים - ראשית הוא מבצע \( C_{not} \) על שני הקיוביטים; מודד את הקיוביט של עצמו ומקבל מזה מידע כלשהו על מה היו שני הביטים שנשלחו; ואז הוא מפעיל את \( H \) על הקיוביט של אליס, מודד אותו ומקבל את מידע שמאפשר לו לשחזר את שני הביטים. פשוט מאוד.

בואו נעבור לתיאורים פורמליים והסבר למה זה עובד. בהתחלה המצב הקוונטי שאליס ובוב חולקים הוא \( \frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}} \) הסטנדרטי של זוג שזור. עכשיו בואו נראה מה הוא הופך להיות אחרי שאליס מפעילה עליו את \( I,X,Y,Z \), בהתאם לזוג הביטים שהיא רוצה לשדר:

• אם הם \( 00 \) אז היא מפעילה \( I \) ומקבלת \( \frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}} \).
• אם הם \( 01 \) אז היא מפעילה \( X \)ומקבלת \( \frac{\left|10\right\rangle +\left|01\right\rangle }{\sqrt{2}} \).
• אם הם \( 10 \) אז היא מפעילה \( Y \) ומקבלת \( \frac{-\left|10\right\rangle +\left|01\right\rangle }{\sqrt{2}} \).
• אם הם \( 11 \) אז היא מפעילה \( Z \) ומקבלת \( \frac{\left|00\right\rangle -\left|11\right\rangle }{\sqrt{2}} \).

עכשיו תורו של בוב. הוא מפעיל \( C_{not} \) על המצב הקוונטי כולו, ואנחנו מקבלים:

• אם הביטים הם \( 00 \) אנחנו מקבלים \( \frac{\left|00\right\rangle +\left|10\right\rangle }{\sqrt{2}} \).
• אם הביטים הם 01 אנחנו מקבלים \( \frac{\left|11\right\rangle +\left|01\right\rangle }{\sqrt{2}} \).
• אם הביטים הם 10 אנחנו מקבלים \( \frac{-\left|11\right\rangle +\left|01\right\rangle }{\sqrt{2}} \).
• אם הביטים הם 11 אנחנו מקבלים \( \frac{\left|00\right\rangle -\left|10\right\rangle }{\sqrt{2}} \).

עכשיו בואו נראה מה קיבלנו. בכל אחד מארבעת המצבים הקוונטיים, אנחנו מקבלים סופרפוזיציה שבה הערך של הקיוביט השני זהה עבור שני המצבים האפשריים. למשל, את \( \frac{\left|11\right\rangle +\left|01\right\rangle }{\sqrt{2}} \) אפשר היה לכתוב גם בתור \( \left(\frac{\left|1\right\rangle +\left|0\right\rangle }{\sqrt{2}}\right)\otimes\left|1\right\rangle \) . כך שמדידה של הקיוביט השני מניבה את התוצאות הבאות:

• אם הביטים הם 00 המדידה מחזירה 0 והקיוביט של אליס עובר למצב \( \frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}} \).
• אם הביטים הם 01 המדידה מחזירה 1 והקיוביט של אליס עובר למצב \(  \frac{\left|1\right\rangle +\left|0\right\rangle }{\sqrt{2}} \).
• אם הביטים הם 10 המדידה מחזירה 1 והקיוביט של אליס עובר למצב \( \frac{-\left|1\right\rangle +\left|0\right\rangle }{\sqrt{2}} \).
• אם הביטים הם 11 המדידה מחזירה 0 והקיוביט של אליס עובר למצב \(  \frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}} \).

במילים אחרות, אחרי המדידה הקיוביט של אליס קרס או למצב \( \left|+\right\rangle \) או למצב \( \left|-\right\rangle \). כעת, את \( H \) הגדרתי על ידי ההעתקה \( \left|0\right\rangle \mapsto\left|+\right\rangle \) ו-\( \left|1\right\rangle \mapsto\left|-\right\rangle \), אבל קל לראות על ידי חישוב פשוט שהיא מקיימת \( \left|+\right\rangle \mapsto\left|0\right\rangle \) ו-\( \left|-\right\rangle \mapsto\left|1\right\rangle \). לכן, אחרי שבוב מפעיל את \( H \) ומודד, הוא מקבל בודאות 0 או 1 (הייתי יכול גם לומר שבוב פשוט מודד לפי הבסיס \( \left|+\right\rangle ,\left|-\right\rangle \), כמובן). נסכם את התוצאות האפשריות:

• אם הביטים הם 00 המדידה הראשונה מחזירה 0 והשניה מחזירה 0.
• אם הביטים הם 01 המדידה הראשונה מחזירה 1 והשניה מחזירה 0.
• אם הביטים הם 10 המדידה הראשונה מחזירה 1 והשניה מחזירה 1.
• אם הביטים הם 11 המדידה הראשונה מחזירה 0 והשניה מחזירה 1.

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

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