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

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

הגדרה

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

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

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

פתרון קלאסי

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

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

תיאור האלגוריתם

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

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

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

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

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

הערות שוליים

1. ליתר דיוק, האלגוריתם מקבל קופסה שחורה המממשת את הפונקציה ${\displaystyle f}$