אלגוריתם דויטש-ג'וזה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

הגדרה[עריכת קוד מקור | עריכה]

תהי f:\{0,1\}^n \to \{0,1\} פונקציה המקבלת קלט באורך \left.n\right. ביטים, ופולטת פלט באורך ביט יחיד, כך שמתקיים אחד מהשניים:

  1. f הינה פונקציה קבועה, כלומר, לכל x\in\{0,1\}^n מתקיים f\left(x\right)=0, או שלכל x\in\{0,1\}^n מתקיים f\left(x\right)=1; או
  2. f הינה פונקציה מאוזנת, כלומר למחצית מה-\left.x\right.-ים מתקיים f\left(x\right)=0 ולשאר f\left(x\right)=1

אלגוריתם דויטש-ג'וזה מקבל כקלט את הפונקציה f ‏‏[1], ומחזיר כפלט האם היא קבועה או מאוזנת. האלוגריתם עושה זאת על ידי הפעלה של הפונקציה f פעם יחידה בלבד.

פתרון קלאסי[עריכת קוד מקור | עריכה]

באופן קלאסי, זיהוי האם פונקציה קבועה או מאוזנת מצריך לכל הפחות \left.2^{n-1}+1\right. הפעלות של פונקציית הקלט עם ערכי \left.x\right. שונים. אם בכלל הפעלות הפונקציה מתקבל אותו ערך אזי היא קבועה, ואם בשתי ההפעלות מתקבלים שני ערכים שונים הפונקציה מאוזנת. לא קיים פתרון דטרמיניסטי המפעיל את הפונקציה פחות מ\left.2^{n-1}+1\right. פעמים, שכן תמיד ייתכן מצב בו \left.2^{n-1}\right. הערכים שעליהם נשאלה הפונקציה מקיימים f\left(x\right)=0 ועדיין שאר הערכים מקיימים f\left(x\right)=1, כלומר הפונקציה מאוזנת.

מצד שני, קיימים פתרונות הסתברותיים לבעיה זו. לדוגמה, ניתן להגריל כמות של \left.k\right. קלטים שונים ולבדוק את ערך הפונקציה עבור קלטים אלו בלבד. במידה ומתקיים k<\left.2^{n-1}+1\right. קיימת הסתברות שהאלגוריתם יטעה, אך הסתברות זו נחשבת זניחה מכיוון שהיא קטנה מ-\left.2^{-k+1}\right..

תיאור האלגוריתם[עריכת קוד מקור | עריכה]

מעגל קוונטי המממש את אלגוריתם דויטש-ג'וזה

האלגוריתם הקוונטי מתואר בתרשים משמאל. המעגל מקבל כקלט אוגר קוונטי המכיל \left.n+1\right. קיוביטים. ניתן להסתכל על הקלט כשני אוגרים המאותחלים ל  |0\rangle^{\otimes n} |1\rangle. על כל אחת מהכניסות מופעל שער הדמר, ומצבם המשותף ניתן כעת לביטוי בתור \frac{1}{\sqrt{2^{n+1}}}\sum_{x \in \{0,1\}^n} |x\rangle (|0\rangle - |1\rangle ). כעת מופעלת הפונקציה הקוונטית f\left(x\right) על האוגר, כאשר \left.n\right. הכניסות הראשונות הינן הקלט, ואילו הכניסה האחרונה משמשת עבור הפלט. לאחר הפעלת הפונקציה מצב האוגר הינו \frac{1}{\sqrt{2^{n+1}}}\sum_{x\in \{0,1\}^n} |x\rangle (|0\oplus f(x)\rangle - |1\oplus f(x)\rangle ).

העקרון עליו מבוסס האלגוריתם הוא הבא: אם f\left(x\right)=0 קיוביט הפלט ניתן לרישום בתור |f(x)\rangle - |1\oplus f(x)\rangle = |0\rangle-|1\rangle ואילו עבור אותם \left.x\right.-ים עבורם f\left(x\right)=1 נקבל |f(x)\rangle - |1\oplus f(x)\rangle = |1\rangle-|0\rangle=-(|0\rangle-|1\rangle) כלומר הסימן של האוגר משתנה בהתאם לערך הפונקציה f\left(x\right), והאוגר ניתן לרישום בתור \frac{1}{\sqrt{2^{n+1}}}\sum_{x\in \{0,1\}^n} (-1)^{f(x)} |x\rangle (|0\rangle - |1\rangle ). נשים לב שהקיוביט האחרון אינו תלוי בערך של הפונקציה, ערכו תמיד (|0\rangle-|1\rangle) וניתן להתעלם ממנו בהמשך.

כעת נפעיל בשנית שער הדמר על האוגר ונבדוק את שני המצבים האפשריים:

  1. אם הפונקציה הייתה קבועה לערך 0, אזי האוגר היה מהצורה \frac{1}{\sqrt{2^{n+1}}}\sum_{x\in \{0,1\}^n} |x\rangle. לאחר הפעלת השער יהיה ערכו |0\rangle^{\otimes n} ועל כן מדידתו בבסיס החישוב תתן את התוצאה |0\rangle^{\otimes n} בהסתברות 1.
  2. אם הפונקציה הייתה מאוזנת, אזי חצי מהערכים \left. x\right. הינם בעלי פאזה חיובית ומחציתם בעלי פאזה שלילית. נשים לב שלאחר הפעלת שער הדמר על אוגר בעל ערך |x\rangle כלשהו, התוצאה הינה סכום משוקלל של כלל \left.2^n\right. הערכים האפשרים כאשר הפאזה של כל אבר נקבעת בהתאם לערך \left. x\right.. כמו כן, נשים לב שהפאזה של האבר |0\rangle^{\otimes n} בסכום זה הינה תמיד חיובית, ללא תלות בערכו של \left. x\right.. לפיכך, כאשר נפעיל את השער הדמר על סופרפוזיציה של \left.2^n\right. אברי הבסיס האפשריים כאשר הפאזה של חציים חיובית ושל חציים שלילית - במוצא השער האבר |0\rangle^{\otimes n} יתאפס, ומדידה בבסיס החישוב לעולם לא תפיק את התוצאה |0\rangle^{\otimes n}.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ ‏ליתר דיוק, האלגוריתם מקבל קופסה שחורה‏ המממשת את הפונקציה f