|
'''אלגוריתם דויטש-ג'וזה''' הינוהוא [[אלגוריתם קוונטי]] להבדלה בין [[פונקציה קבועה]] לבין [[פונקציה מאוזנת]]. האלגוריתם מהווה דוגמה ליתרון המתקבל משימוש של [[מחשב קוונטי]] על פני [[מחשב|מחשב קלאסי]]. האלגוריתם פורסם על ידי מדעני המחשב [[ריצ'רד ג'וזה]] ו[[דוידדייוויד דויטש]] בשנת 1992, והניח את היסודות לפיתוח [[אלגוריתם גרובר]] ו[[אלגוריתם שור|אלוגריתםאלגוריתם הפיקטור]] של [[פיטר שור]].
== הגדרה ==
תהי <math>f:\{0,1\}^n \to \{0,1\}</math> פונקציה המקבלת [[קלט]] באורך <math>\left.n\right.</math> ביטים, ופולטת פלט באורך ביט יחיד, כך שמתקיים אחד מהשניים:
# <math>f\left(x\right)</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)=01</math>,; '''או'''
# <math>f\left(x\right)</math> הינההיא פונקציה מאוזנת, כלומר למחצית מה -<math>\left.x\right.</math>-ים מתקיים <math>f\left(x\right)=0</math> ולשאר <math>f\left(x\right)=1</math>
אלגוריתם דויטש-ג'וזה מקבל כקלט את הפונקציה <math>f\left(x\right)</math> <ref>ליתר{{הערה|ליתר דיוק, האלגוריתם מקבל [[קופסהאורקל שחורה(מדעי (הנדסההמחשב)|קופסה שחורהשחורה]] המממשת את הפונקציה <math>f\left(x\right)</math> </ref>}}, ומחזיר כפלט האם היא קבועה או מאוזנת. האלוגריתםהאלגוריתם עושה זאת על ידי הפעלה של הפונקציה <math>f\left(x\right)</math> פעם יחידה בלבד.
== פתרון קלאסי ==
באופן קלאסי, זיהוי האם פונקציה קבועה או מאוזנת מצריך לכל הפחות <math>\left.2^{n-1}+1\right.</math> הפעלות של פונקציית הקלט עם ערכי <math>\left.x\right.</math> שונים. אם בכלל הפעלות הפונקציה מתקבל הערךאותו 0ערך אזי היא קבועה, ואם מתקבלבשתיים הערךמההפעלות 1מתקבלים באחתערכים ההפעלותשונים, אזי הפונקציה היא מאוזנת. לא קיים פתרון [[אלגוריתם דטרמיניסטי|דטרמיניסטי]] המפעיל את הפונקציה פחות מ<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\}^{2^n-1} |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\}^{2^n-1} |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\}^{2^n-1} (-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=0}^{2^n-1} |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>. ▼
▲כעת נפעיל בשנית [[שער הדמראדמר]] על האוגר ונבדוק את שני המצבים האפשריים:
▲:# אם הפונקציה הייתה קבועה לערך 0, אזי האוגר היה מהצורה <math>\frac{1}{\sqrt{2^{n+1}}}\sum_{x =\in \{0 ,1\} ^{2^n -1} |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|חישוב קוונטי בגישה מתמטית, חלק ה': אלגוריתם דויטש-ג'וזה}}
== הערות שוליים ==
{{הערות שוליים}}
<references />
[[קטגוריה:חישוב קוונטי]]
▲[[קטגוריה:אלגוריתמים קוונטיים|דויטש-ג'וזה]]
[[en:Deutsch–Jozsa algorithm]]
[[de:Deutsch-Jozsa-Algorithmus]]
[[es:Algoritmo de Deutsch-Jozsa]]
[[fr:Algorithme de Deutsch-Jozsa]]
[[lt:Doičo-Džozo algoritmas]]
[[pt:Algoritmo de Deutsch-Jozsa]]
[[ru:Алгоритм Дойча — Джоза]]
| 