דלג לתוכן הראשי

חישובים קלאסיים על מחשבים קוונטיים

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

סימולציה של Circuit בוליאני עם Circuit קוונטי​

Circuit בוליאני מורכב משערי AND, OR, NOT ו-FANOUT. כדי לסמלץ Circuit בוליאני עם Circuit קוונטי, נתחיל בהראות כיצד ניתן לסמלץ כל אחד מארבעת השערים האלה באמצעות שערים קוונטיים. לאחר שנעשה זאת, המרת Circuit בוליאני נתון ל-Circuit קוונטי היא עניין פשוט של סימולציה שער אחר שער. לשם כך נזדקק רק לשערי NOT, שערי controlled-NOT ושערי Toffoli, שכולם פעולות דטרמיניסטיות בנוסף להיותן אוניטריות.

שערי Toffoli​

שערי Toffoli ניתנים לתיאור חלופי כשערי controlled-controlled-NOT, שפעולתם על מצבי הבסיס הסטנדרטי מוצגת באיור הבא.

שער Toffoli

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

(1000000001000000001000000000000100001000000001000000001000010000)\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}

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

שערי Toffoli אינם כלולים בסט השערים ברירת המחדל שנדון קודם בשיעור, אך ניתן לבנות שער Toffoli מתוך שערי H,H, T,T, T†T^{\dagger} ו-CNOT כדלקמן.

Circuit קוונטי לשער Toffoli

סימולציה של שערים בוליאניים עם שערי Toffoli, controlled-NOT ו-NOT​

שער Toffoli בודד, בשילוב עם מספר שערי NOT, יכול לממש שערי AND ו-OR, ושערי FANOUT ניתנים למימוש בקלות באמצעות שערי controlled-NOT, כפי שהדיאגרמות הבאות מציעות.

סימולציה של שערי AND ו-OR עם שערי Toffoli

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

עבור שערי AND ו-OR נותרים לנו גם שני Qubitים עודפים, בנוסף ל-Qubit הפלט. לדוגמה, בתוך התיבה בדיאגרמה המייצגת את הסימולציה של שער AND, שני ה-Qubitים העליונים נותרים במצבים ∣a⟩\vert a\rangle ו-∣b⟩.\vert b\rangle. Qubitים אלה מתוארים כנותרים בתוך התיבות מכיוון שאינם נדרשים עוד ואינם חלק מהפלט. ניתן להתעלם מהם לעת עתה, אם כי נחזור אליהם בקרוב.

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

סימולציה שער אחר שער של Circuit בוליאני​

נניח עכשיו שיש לנו Circuit בוליאני רגיל בשם C,C, המורכב משערי AND, OR, NOT ו-FANOUT, ובעל nn סיביות קלט ו-mm סיביות פלט. תהי t=size⁡(C)t = \operatorname{size}(C) מספר השערים ב-C,C, ונקרא בשם ff לפונקציה ש-CC מחשב, שנוטלת את הצורה

f:Σn→Σmf:\Sigma^n\rightarrow\Sigma^m

עבור Σ={0,1}.\Sigma = \{0,1\}.

עכשיו נשקול מה קורה כשאנחנו עוברים אחד אחד על שערי AND, OR ו-FANOUT של C,C, ומחליפים כל אחד בסימולציה המתאימה שתוארה לעיל, כולל הוספת Qubitי סביבת העבודה הנדרשים. נקרא ל-Circuit המתקבל R,R, ונסדר את ה-Qubitים של RR כך ש-nn סיביות הקלט של CC יתאימו ל-nn ה-Qubitים העליונים של RR ו-Qubitי סביבת העבודה יהיו בתחתית.

סימולציה של Circuit הפיך

כאן, kk הוא מספר Qubitי סביבת העבודה הנדרשים — אחד עבור כל שער AND, OR ו-FANOUT של CC — ו-gg היא פונקציה מהצורה g:Σn→Σn+k−mg:\Sigma^n \rightarrow \Sigma^{n+k-m} המתארת את המצבים של ה-Qubitים העודפים שנוצרו על ידי סימולציות השערים לאחר הרצת RR. באיור, ה-Qubitים המתאימים לפלט f(x)f(x) נמצאים בחלק העליון וה-Qubitים הנותרים שמאחסנים את g(x)g(x) נמצאים בתחתית. אנחנו יכולים לאלץ זאת לקרות אם נרצה על ידי סידור מחדש של ה-Qubitים באמצעות שערי SWAP, שניתנים למימוש עם שלושה שערי controlled-NOT כך:

החלפה עם שערי cNOT

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

הפונקציה gg המתארת את המצבים הקלאסיים של ה-Qubitים העודפים נקבעת על ידי ה-Circuit C,C, אך למעשה אין צורך לדאוג יותר מדי לגביה; לא אכפת לנו ספציפית באיזה מצב נמצאים ה-Qubitים האלה כשהחישוב מסתיים. האות gg מגיעה אחרי f,f, אז זה שם סביר לפונקציה זו מסיבה זו, אך יש סיבה טובה יותר לבחור בשם gg — זו קיצור של garbage (פסולת).

ניקוי הפסולת​

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

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

למרבה המזל, לא קשה לנקות את הפסולת, כביכול. המפתח הוא להשתמש בעובדה שמאחר ש-RR הוא Circuit קוונטי, אנחנו יכולים להריצו הפוך, פשוט על ידי החלפת כל שער בהופכי שלו והחלתם בסדר הפוך, ובכך לקבל Circuit קוונטי לפעולה R†.R^{\dagger}. שערי Toffoli, שערי CNOT ושערי NOT הם למעשה ההופכיים של עצמם, כך שהרצת RR הפוך היא ממש עניין של החלת השערים בסדר הפוך — אך באופן כללי יותר, כל Circuit קוונטי ניתן להיפוך כפי שתואר זה עתה.

באופן ספציפי, מה שאנחנו יכולים לעשות הוא להוסיף mm Qubitים נוספים (תוך זכירה שלפונקציה ff יש mm סיביות פלט), להשתמש בשערי CNOT להעתקת פלט RR ל-Qubitים האלה, ולהפוך את RR לניקוי הפסולת. האיור הבא ממחיש את ה-Circuit המתקבל ומתאר את פעולתו על מצבי הבסיס הסטנדרטי.

חישוב ללא פסולת

אם נכניס תיבה סביב כל ה-Circuit ונקרא לו Q,Q, הוא נראה כך:

סימולציה כשער שאילתה

בהינתן ש-CC בעל tt שערים, ל-Circuit QQ יהיו O(t)O(t) שערים.

אם נתעלם מ-kk Qubitי סביבת העבודה הנוספים, מה שיש לנו הוא Circuit QQ שמתפקד בדיוק כמו שער שאילתה לפונקציה f.f. אם אנחנו פשוט רוצים לחשב את הפונקציה ff על מחרוזת כלשהי x,x, נוכל להגדיר y=0my = 0^m והערך המתקבל f(x)f(x) יופיע ב-mm ה-Qubitים התחתונים — או שנוכל להזין מצב שונה ל-mm ה-Qubitים התחתונים אם נרצה (אולי כדי לנצל phase kickback, כמו באלגוריתם של Deutsch או Deutsch-Jozsa).

המשמעות היא שעבור כל אלגוריתם שאילתה, אם יש לנו Circuit בוליאני שמחשב את פונקציית הקלט, נוכל להחליף כל שער שאילתה במימוש Circuit שלו, והאלגוריתם יפעל כראוי.

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

מימוש פונקציות הפיכות​

הבנייה שתוארה מאפשרת לנו לסמלץ כל Circuit בוליאני עם Circuit קוונטי ללא פסולת. אם CC הוא Circuit בוליאני המממש פונקציה f:Σn→Σm,f:\Sigma^n \rightarrow \Sigma^m, אז אנחנו מקבלים Circuit קוונטי QQ שפועל כדלקמן על מצבי הבסיס הסטנדרטי.

Q(∣y⟩∣0k⟩∣x⟩)=∣y⊕f(x)⟩∣0k⟩∣x⟩Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle

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

ליתר דיוק, נניח שהפונקציה ff נוטלת את הצורה f:Σn→Σn,f:\Sigma^n \rightarrow \Sigma^n, ונניח גם שקיימת פונקציה f−1f^{-1} כך ש-f−1(f(x))=xf^{-1}(f(x)) = x עבור כל x∈Σnx\in\Sigma^n (שהיא בהכרח ייחודית כשהיא קיימת). המשמעות היא שהפעולה שממירה ∣x⟩\vert x \rangle ל-∣f(x)⟩\vert f(x) \rangle עבור כל x∈Σnx\in\Sigma^n היא אוניטרית, ולכן אולי נוכל לבנות Circuit קוונטי שמממש את הפעולה האוניטרית המוגדרת על ידי

U∣x⟩=∣f(x)⟩U \vert x \rangle = \vert f(x) \rangle

עבור כל x∈Σn.x\in\Sigma^n.

כדי להבהיר, העובדה שזו פעולה אוניטרית מסתמכת על הפיכות ff — היא אינה אוניטרית כש-ff אינה הפיכה. בהתעלם מ-Qubitי סביבת העבודה, UU שונה מהפעולה שה-Circuit QQ מממש מכיוון שאנחנו לא שומרים עותק של הקלט ועושים XOR עם מחרוזת שרירותית, אלא מחליפים את xx ב-f(x).f(x).

השאלה היא: כש-ff הפיכה, האם ניתן לעשות זאת?

התשובה היא כן, בתנאי שמותר לנו להשתמש ב-Qubitי סביבת עבודה ובנוסף לכך שיש לנו Circuit בוליאני שמחשב את f,f, יש לנו גם כזה שמחשב את f−1.f^{-1}. לכן, זו אינה קיצור לחישוב הופכי של פונקציות כשאיננו יודעים כבר איך לעשות זאת! הדיאגרמה הבאה ממחישה כיצד ניתן לעשות זאת על ידי הרכבת שני Circuitים קוונטיים, QfQ_f ו-Qf−1,Q_{f^{-1}}, שמתקבלים בנפרד עבור הפונקציות ff ו-f−1f^{-1} באמצעות השיטה שתוארה לעיל, יחד עם nn שערי swap, כאשר kk הוא המקסימום של מספרי Qubitי סביבת העבודה הנדרשים על ידי QfQ_f ו-Qf−1.Q_{f^{-1}}.

סימולציה של פונקציה הפיכה