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

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

הגדרה

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

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

אלגוריתם דויטש-ג'וזה מקבל כקלט את הפונקציה $f\left(x\right)$ ‏‏, ומחזיר כפלט האם היא קבועה או מאוזנת. האלוגריתם עושה זאת על ידי הפעלה הפונקציה $f\left(x\right)$ פעם יחידה בלבד.

פתרון קלאסי

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

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

1. אם הפונקציה הייתה קבועה לערך 0, אזי האוגר היה מהצורה ${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|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}$.