שערים ומעגלים קוונטיים - מבוא על קצה המזלג

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

כרגיל, לפני שמדברים על איך זה עובד בקוונטים, לא יזיק להיזכר איך זה עובד בחישוב קלאסי. בחישוב קלאסי כל יחידת מידע בסיסית - ביט - היא בעלת שני ערכים אפשריים, 0 או 1. אפשר היה לבנות מעגלים קלאסיים שבהם יחידת מידע יכולה להכיל עוד ערכים אפשריים אבל פשוט אין בכך צורך. המטרה שלנו בחישוב קלאסי ניתנת לרוב לתיאור בתור חישוב של פונקציה: פורמלית, נתונה פונקציה בוליאנית \( f:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} \) ואנחנו רוצים לבנות מעגל שמורכב משערים בסיסיים שיש לו \( n \) “כניסות” ויציאה אחת, כך שאם הכניסות מקבלות את הערך \( a \) (חשבו על \( a \) בתור סדרה של \( n \) ביטים) אז היציאה תקבל, אחרי שהמעגל יבצע את החישוב שלו, את הערך \( f\left(a\right) \). אם אנחנו יודעים לעשות דבר כזה נוכל גם לטפל בסיטואציות יותר מורכבות כמו מעגלים עם יותר מפלט אחד, או מעגלים עם יחידות זכרון, וכדומה.

“שערים לוגיים” הם רכיבים פשוטים יחסית שמחשבים פונקציות פשוטות - לרוב כאלו על מספר מצומצם מאוד של משתנים - 1 או 2 זה כל מה שנדרש בדרך כלל (בעולם האמיתי יש גם רכיב שנקרא Field Programmable Gate Array - בקיצור FPGA - שמקבל מספר גדול יותר של משתנים וניתן לבנות אחד כזה לכל פונקציה אפשרית על אותם משתנים - אבל נעזוב את זה).

יש לנו בדיוק 4 פונקציות על משתנה יחיד, ובדיוק 16 פונקציות על שני משתנים. חלק מהן טריוויאליות ולא מעניינות כל כך (למשל, \( f\left(x\right)=x \) או \( f\left(x\right)=0 \)) ולכן אנחנו נוהגים להצטמצם לדיבור על תת-קבוצה מעניינת של פונקציות. שלוש הפונקציות הפופולריות ביותר הן NOT, AND ו-OR. אני משער שכולם מכירים אותן אבל אזכיר בכל זאת: NOT (שמסומנת לפעמים ב-\( \neg \)) מקבלת ביט יחיד והופכת אותו - אם קיבלה 0 מחזירה 1, ואם קיבלה 1 מחזירה 0. AND (שמסומנת לפעמים ב-\( \wedge \)) מקבלת שני ביטים ומחזירה 1 רק אם שניהם 1, אחרת מחזירה 0; ו-OR (שמסומנת לפעמים ב-\( \vee \)) מקבלת שני ביטים ומחזירה 0 רק אם שניהם 0, אחרת מחזירה 1.

מסתבר שאפשר לבנות כל פונקציה \( f:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} \) באמצעות הרכבות של שערים כאלו - זה מה שמוכיח קיום צורה קנונית דוגמת DNF לפונקציות בוליאניות. לא אכנס לפרטים הללו כרגע כי זה לא חשוב. מה שכן מעניין הוא שלמרות הפופולריות של שערים אלו, למעשה אפשר היה “לחסוך” אותם ולהשתמש רק בשער אחד - שער שנקרא NAND, והוא מעין שילוב בין AND ו-NOT; הוא מקבל שני ביטים ומחזיר 0 רק אם שניהם 1, אחרת מחזיר 1. כל פונקציה בוליאנית ניתן לתאר עם מעגל שבנוי רק משערי NAND, אבל לרוב יותר נוח לתאר ולממש מעגלים כאלו עם פונקציות אחרות. לי יוצא, למשל, להתעסק הרבה עם מעגלים שמיוצגים בפורמט שנקרא And-Inverter Graph (ובקיצור AIG): בפורמט הזה המעגל בנוי כולו רק משערי AND ו-NOT, באופן שמאפשר ייצוג קומפקטי (כל שער AND מקבל מספר טבעי; הכניסות שלו מיוצגות על ידי שני מספרים שלמים, כאשר מספר שלילי פירושו שמפעילים NOT על הקלט לשער ממש לפני שהוא נכנס). אין צורך בשער OR כאן כי בעזרת כללי דה-מורגן אפשר “לסמלץ” אותו עם שערי AND ו-NOT.

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

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

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

מה שאנחנו מחפשים, אם כן, הוא שער שיקבל שני קיוביטים \( \left|a\right\rangle \left|b\right\rangle \) ויחזיר \( \left|a^{\prime}\right\rangle \left|b^{\prime}\right\rangle \) כך שאם \( b=0 \) אז \( b^{\prime}=a \). שער כזה הוא קל למימוש: \( \left|a\right\rangle \left|b\right\rangle \mapsto\left|a\right\rangle \left|a\oplus b\right\rangle \). קל לראות שזה אופרטור אוניטרי (העובדה שהוא הפיך ברורה מכך שבהינתן \( \left|a^{\prime}\right\rangle \left|b^{\prime}\right\rangle \) קל לשחזר את המצב המקורי: \( a=a^{\prime} \) ו-\( b=a^{\prime}\oplus b^{\prime} \)). כבר נתקלנו באופרטור הזה בפוסט קודם וקראנו לו \( C_{not} \) קיצור של Controlled-Not, מכיוון שאם תחשבו על זה רגע תראו שמה שהוא עושה הוא לבצע NOT לקיוביט \( b \) אם ורק אם \( a \) היה 1 (ובקיוביט הראשון הוא לא נוגע).

הפעולה הזו היא מעין שער \( C_{not} \) מתוחכם: היא הופכת את \( c \) רק אם גם \( a \) וגם \( b \) שניהם 1. בשל כך נהוג לקרוא לה בשם שער \( CC_{not} \) (או לפעמים “שער טופולי” על שם ממציאו). אפשר, כמובן, גם להגדיר שער כזה בחישוב קלאסי: שני הביטים הראשונים של הפלט אינם מעניינים (כי אפשר לשכפל ביטים בחישוב קלאסי) כך שהשער בגרסתו הקלאסית הוא מהצורה \( CC_{not}\left(a,b,c\right)=c\oplus\left(a\wedge b\right) \). השער הקלאסי הזה, בדומה ל-NAND, הוא אוניברסלי. כדי להיווכח באוניברסליות הזו מספיק לשים לב שאפשר לסמלץ עם השער פעולות AND ו-NOT, וזה קל: \( \neg x=CC_{not}\left(1,1,x\right) \) ו-\( a\wedge b=CC_{not}\left(a,b,0\right) \).

המשמעות של האוניברסליות הזו עבור חישוב קוונטי היא זו: אם יש לנו פונקציה בוליאנית \( f:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} \) כלשהי, אז קיים מעגל שמכיל רק שערי טופולי, שמבצע את הטרנספורמציה הבאה: \( \left|x_{1}\dots x_{n}\right\rangle \left|0\dots0\right\rangle \mapsto\left|x_{1}\dots x_{n}\right\rangle \left|f\left(x\right)\right\rangle \left|b_{1}\dots b_{m}\right\rangle \). כאן ה-\( b_{1},\dots,,b_{m} \) הם קיוביטים “זבליים” שקיבלו ערך כלשהו במהלך החישוב ולכו תדעו מה קורה איתם עכשיו - פשוט לא מתעסקים איתם יותר. האוניברסליות הזו מראה לנו די בקלות שחישוב קוונטי מכליל חישוב רגיל - כל מה שצריך לעשות הוא לבצע את החישוב של המעגל ולמדוד את הקיוביט הנכון, שבודאות יהיה ב-\( f\left(x\right) \). יש כאן גם, כמובן, ענייני סיבוכיות שלא אכנס אליהם.

מה שצריך לשים לב אליו הוא שה”אוניברסליות” של שער טופולי אינה אוניברסליות של חישוב קוונטי. כלומר, קיימים אופרטורים קוונטיים שלא ניתן לסמלץ רק בעזרת שערי טופולי. למעשה, על פניו נראה ש”אוניברסליות” של סט שערים קוונטיים היא עניין בעייתי, בגלל העושר הגדול של אופרטורים שאפשר לדבר עליהם - לכל \( n \) יש אינסוף אופרטורים שפועלים על רגיסטר של \( n \) קיוביטים, והאופרטורים הללו הם מעל \( \mathbb{C} \), כלומר המקדמים שלהם הם מספרים מרוכבים כלליים - מספר לא בן מניה בכלל. לכן כשמדברים על אוניברסליות לא הולכים על הגישה התובענית ביותר, של לסמלץ את כל האופרטורים; מספיק מבחינתנו שאפשר יהיה לקרב אותם ברמה סבירה. אפשר להוכיח שבהינתן קירובים טובים שכאלו, החישוב הסופי יתנהג כמעט כמו חישוב עם האופרטורים האמיתיים ולא המקורבים - ומכיוון שתוצאת החישוב היא הסתברותית ממילא, זה לא משנה הרבה. אני לא אכנס כאן להגדרה הפורמלית של רמת הקירוב שנדרשת; מספיק שהבנו את הרעיון.

על מנת לבצע חישוב קוונטי אוניברסלי שכזה, מספיק להשתמש בשערי טופולי, בשערי הדאמר \( H \) ובשער נוסף שפועל על קיוביט יחיד ומסומן באות \( S \) ומתואר על ידי המטריצה \( \left[\begin{array}{cc}1 & 0\\0 & i\end{array}\right] \); לא אכנס להוכחה שהם מספיקים. בפועל משתמשים בהרבה יותר שערים כדי לתאר בנוחות חישובים קוונטיים. הזכרתי כבר את השערים \( X,Y,Z \) שמתאימים למטריצות פאולי - למשל \( X=\left[\begin{array}{cc}0 & 1\\1 & 0\end{array}\right] \). אולי כדאי לומר על \( X \) עוד מילה: על פניו \( X \) הוא האנלוג הקוונטי לשער NOT, שהרי \( X\left|0\right\rangle =\left|1\right\rangle \) ו-\( X\left|1\right\rangle =\left|0\right\rangle \); אבל שימו לב שמתקיים, למשל, \( X\left|+\right\rangle =X\left(\frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\right)=\left|+\right\rangle \), וזה כבר פחות מתאים לאינטואיציה שלנו לגבי NOT, כך שצריך להיזהר.

בעזרת השערים הללו וכמה תעלולים שלא אתאר כרגע ניתן לבנות שערים שהם מעין הכללה מרחיקת לכת של \( CC_{not} \). חשבו על אופרטור קוונטי \( U \) כלשהו, אז ניתן לבנות מעגל משערים קוונטיים בסיסיים כך ש-\( \left|x\right\rangle \left|y\right\rangle \mapsto\left|x\right\rangle U^{x_{1}\cdots x_{n}}\left|y\right\rangle \), כאשר \( x,y \) יכולים להיות מורכבים כל אחד ממספר קיוביטים. מה שזה אומר: אם כל ה-\( x \)-ים הם 1, אז הפעל את \( U \) על ה-\( y \); אחרת השאר אותו ללא שינוי. זה מעין Controlled-U. זה גם בדיוק השער שלו נזקקנו בפוסט הקודם של אלגוריתם גרובר - שער שבדק אם כל הקיוביטים במצב קוונטי כלשהו הם 0, ואם כן הוא העביר אותו למצב אחר ואחרת השאיר אותו ללא שינוי. אפשר לבנות מעגל עבור השער הזה די בקלות - לוקחים את הקיוביטים של המצב, מעתיקים אותם על גבי קיוביטים “לכתיבה בלבד” טריים, הופכים אותם עם \( X \) ואז משתמשים בשער ה-Controlled-U. הפרטים של הבניות הללו הם מעניינים למדי, אבל כאמור - בפוסט הזה לא התכוונתי להיכנס אליהם ברצינות. המטרה העיקרית שלי הייתה לקבל קצת יותר תחושה של “למה זה אפשרי” לפני שאנחנו מגיעים לאקשן האלגוריתמי הרציני שלנו.

נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ: