הצגת המקור של הדף "אלגוריתם דויטש-ג'וזה"

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

== הגדרה ==
תהי <math>f:\{0,1\}^n \to \{0,1\}</math> פונקציה המקבלת [[קלט]] באורך <math>\left.n\right.</math> ביטים, ופולטת פלט באורך ביט יחיד, כך שמתקיים אחד מהשניים:
# <math>f</math> היא פונקציה קבועה, כלומר, לכל <math>x\in\{0,1\}^n</math> מתקיים <math>f\left(x\right)=0</math>, או שלכל <math>x\in\{0,1\}^n</math> מתקיים <math>f\left(x\right)=1</math>; '''או'''
# <math>f</math> היא פונקציה מאוזנת, כלומר למחצית מה-<math>\left.x\right.</math>-ים מתקיים <math>f\left(x\right)=0</math> ולשאר <math>f\left(x\right)=1</math>

אלגוריתם דויטש-ג'וזה מקבל כקלט את הפונקציה <math>f</math>{{הערה|ליתר דיוק, האלגוריתם מקבל [[אורקל (מדעי המחשב)|קופסה שחורה]] המממשת את הפונקציה <math>f</math> }}, ומחזיר כפלט האם היא קבועה או מאוזנת. האלגוריתם עושה זאת על ידי הפעלה של הפונקציה <math>f</math> פעם יחידה בלבד.

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

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

== תיאור האלגוריתם ==
[[קובץ:Deutsch-Jozsa_Algorithm.svg|ממוסגר|מעגל קוונטי המממש את אלגוריתם דויטש-ג'וזה]]
האלגוריתם הקוונטי מתואר בתרשים משמאל. המעגל מקבל כקלט [[אוגר (מחשבים)|אוגר]] קוונטי המכיל <math>\left.n+1\right.</math> [[קיוביט]]ים. ניתן להסתכל על הקלט כשני אוגרים המאותחלים ל <math> |0\rangle^{\otimes n} |1\rangle</math>. על כל אחת מהכניסות מופעל [[שער אדמר]], ומצבם המשותף ניתן כעת לביטוי בתור <math>\frac{1}{\sqrt{2^{n+1}}}\sum_{x \in \{0,1\}^n} |x\rangle (|0\rangle - |1\rangle )</math>.
כעת מופעלת [[פונקציה קוונטית|הפונקציה הקוונטית]] <math>f\left(x\right)</math> על האוגר, כאשר <math>\left.n\right.</math> הכניסות הראשונות הן הקלט, ואילו הכניסה האחרונה משמשת עבור הפלט. לאחר הפעלת הפונקציה מצב האוגר הוא <math>\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in \{0,1\}^n} |x\rangle (|0\oplus f(x)\rangle - |1\oplus f(x)\rangle )</math>.

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

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

==קישורים חיצוניים==
* {{לא מדויק|2022/08/07/quantum_computing_math_5|חישוב קוונטי בגישה מתמטית, חלק ה': אלגוריתם דויטש-ג'וזה}}

== הערות שוליים ==
{{הערות שוליים}}

[[קטגוריה:אלגוריתמים קוונטיים|דויטש-ג'וזה]]