חישוב קוונטי – האלגוריתם של שור

פרולוג, ובו סקירה מהירה של השור הנורא לפני שלוש וחצי שנים בערך, כשגילו של הבלוג היה חצי מגילו כיום, התחלתי סדרת פוסטים שכיניתי "פרוייקט תוצאות מפתיעות בסיבוכיות". המטרה שלי הייתה לקחת ארבע תוצאות ידועות בתורת הסיבוכיות שהופיעו במצגת של סקוט … להמשיך לקרוא

חישוב קוונטי – האלגוריתם של סימון

כמעט הגענו אל מה שהוא הגביע הקדוש של סדרת הפוסטים הזו: האלגוריתם הקוונטי של שור לפירוק מספרים לגורמים. ממש לפני שאנחנו נכנסים לפרטי האלגוריתם הזה, שהוא הדבר המסובך ביותר שניתקל בו, אני רוצה להציג אלגוריתם פשוט יותר שנותן טעימה כלשהי … להמשיך לקרוא

שערים ומעגלים קוונטיים – מבוא על קצה המזלג

הפוסט הזה הולך להתעסק בפרטי ה-Low level של חישוב קוונטי – הרכיבים הבסיסיים שבהם אנחנו משתמשים בחישוב כזה (שערים קוונטיים) ומה שאנחנו בונים באמצעותם (מעגלים קוונטיים). כשאני אומר Low-level הכוונה היא אך ורק לזה שאנחנו מתעסקים בפרטים הבסייסים שמהם מורכבים … להמשיך לקרוא

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

אלגוריתם גרובר הוא הדוגמה הראשונה שכדאי להראות כשמתחילים להראות אלגוריתמים בחישוב קוונטי, מכיוון שהוא פשוט יחסית, עובד בצורה מאוד אינטואיטיבית וציורית, ויש לו יתרון מוכח על אלגוריתמים קלאסיים שפותרים את אותה הבעיה. ומה הבעיה הזו? בעיה של חיפוש במבנה נתונים … להמשיך לקרוא

חישוב קוונטי – מה זה בדיוק

הפוסט הזה הוא הלב התיאורטי של כל סדרת הפוסטים שלי על חישוב קוונטי. עד עכשיו הצגתי את הרעיונות הפיזיקליים ואת המסגרת המתמטית שבה הם מתוארים, ונתתי דוגמאות לתעלולים שונים ומשונים שמתבצעים בעזרת הרעיונות הפיזיקליים הללו ומפורמלים בעזרת המתמטיקה, אבל לא … להמשיך לקרוא

חישוב קוונטי – טלפורטציה, קידוד צפוף ושערים קוונטיים

את הפוסט הקודם שלי סיימתי באזכור של משפט בסיסי באינפורמציה קוונטית – משפט ה-No Cloning, שאומר שאין לנו יכולת לשכפל מצב קוונטי כללי. הוכחתי את המשפט בפוסט הקודם – הוא נובע מבחינה מתמטית בצורה פשוטה מאוד מאקסיומות תורת הקוונטים – … להמשיך לקרוא

קריפטוגרפיה קוונטית

אני רוצה להציג הפעם יישום חזק ומעניין של הרעיונות הבסיסיים בקוונטים שראינו עד כה עבור הצפנה. ומכיוון שזה נושא מעניין למדי אני אשתדל להפוך את הפוסט הזה לעומד בפני עצמו ככל הניתן (למעט אולי בכניסה לחישובים הטכניים שתהיה בסוף, אחרי … להמשיך לקרוא

חישוב קוונטי – עקרון אי הודאות של הייזנברג, פרדוקס EPR ומשפט בל

בפוסט הקודם שלי על חישוב קוונטי הצגתי פרוטוקול קטן וחביב שבאמצעותו אליס ובוב יכולים לעשות מה שנראה כמו "תקשורת מיידית בלי מגבלת מרחק" בעזרת המצב הקוונטי \(\left|00\right\rangle +\left|11\right\rangle \). בפוסט הזה אני רוצה לדבר קצת על ההשלכות הפיזיקליות של התכונות המוזרות … להמשיך לקרוא

חישוב קוונטי – דוגמה ראשונה

אני רוצה להתחיל עם הדגמה לאופן שבו חישוב קוונטי מסוגל לסייע בתקשורת. זו דוגמה טובה כי מצד אחד קורה בה "קסם" של ממש: אנחנו מצליחים לעשות משהו שמבחינה "קלאסית" הוא פשוט בלתי אפשרי. מצד שני, אנחנו גם רואים בדיוק עד … להמשיך לקרוא

חישוב קוונטי – ועכשיו פורמלית

הפוסטים שלי עד כה על חישוב קוונטי ותורת הקוונטים דיברו מאוד באוויר. עכשיו הגיע הזמן לתכל'ס – לתאר את המודל המתמטי הבסיסי של תורת הקוונטים שבו אנחנו הולכים להשתמש. לפני שאני מתחיל אני רק רוצה להזכיר שהרעיון בתורת הקוונטים הוא … להמשיך לקרוא

מבוא לאפקטים קוונטיים על קצה המזלג

אצהיר מראש: הבלוג הזה אינו בלוג פיזיקה ואין לי שליטה מספקת בחומר כדי לכתוב פוסטים בפיזיקה. עם זאת, אין לי מנוס מלכתוב אחד עכשיו, כי לפני שנותנים מבוא לחישוב קוונטי צריך לתת תיאור כללי של הרקע, גם אם אחר כך … להמשיך לקרוא

חישוב קוונטי – מה זה אומר ומה זה לא אומר?

תחושת הבטן שלי היא שאין עוד תחום מדעי כלשהו שנקשרת סביבו הילה מיסטית כמו תורת הקוונטים; ושמעטים (אם בכלל קיימים) התחומים המדעיים שזוכים לתיאורים פופולריים שגויים לחלוטין או מטעים כמו תורת הקוונטים. בין שלל העיוותים של חלקים מתורת הקוונטים יש … להמשיך לקרוא

בניות בסרגל ומחוגה – המשחק!

בתור סטודנט למתמטיקה, נתקלתי לראשונה במושג של בניות בסרגל ומחוגה בקורס בתורת השדות. מה שעושים שם הוא להוכיח תוצאה שכיום היא כבר קלאסית לגמרי – ששלוש בעיות בניה מפורסמות אינן פתירות כלל. יש לי פוסט על התוצאה הנפלאה הזו, אבל … להמשיך לקרוא

מכפלות טנזוריות (של מרחבים וקטוריים)

בסדרת הפוסטים שלי על אלגברה לינארית יש נושא אחד שהזנחתי בצד – מכפלה טנזורית של מרחבים וקטוריים. לא הזנחתי אותו במקרה, וזה גם לא מקרה שספרי הלימוד הסטנדרטיים באלגברה לינארית לא מתעסקים בו יותר מדי – לרוב אין בו צורך, … להמשיך לקרוא

התמרת פורייה המהירה

בפוסט הקודם הצגתי את התמרת פורייה הבדידה, והבאתי דוגמה אחת לשימוש בה – כפל מהיר של פולינומים. אמרתי גם שכדי שהכפל באמת יהיה מהיר, עלינו לדעת לבצע את התמרת פורייה מהר; ואמרתי גם שהתמרת פורייה הבדידה מיוחדת בכך שהיא עוסקת … להמשיך לקרוא

התמרת פורייה הבדידה – מה זה בכלל?

עד עכשיו ראינו שני סוגים של התמרות פורייה: אחת עבור פונקציות מחזוריות מעל הממשיים, כלומר פונקציות שמוגדרות מעל הקטע \(\left[-\pi,\pi\right]\) ואנחנו יכולים "להרחיב" אותן לכל \(\mathbb{R}\) באופן מחזורי; ופונקציות שהוגדרו מראש על כל \(\mathbb{R}\). להתמרה במקרה הראשון קראנו "טורי פורייה" … להמשיך לקרוא

התמרת פורייה – מה זה בכלל?

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

טורי פורייה – מה זה בכלל?




יש עוד נקודה שכדאי לתת עליה את הדעת בדוגמה שלי. אמרנו שטור פורייה הוא טור של סינוסים וקוסינוסים, אז איפה הקוסינוסים? ובכן, בחישוב הפורמלי ראינו שהמקדמים של כולם יצאו 0, אבל האם זה מקרי? כמובן שלא. \(f\) שלנו היא בבירור פונקציה אנטי-סימטרית סביב \(x=0\) כמעט בכל נקודה, בדיוק כמו סינוס עצמה. זה מבטיח שהמקדמים של \(\cos x\) עבורה יצאו 0 ונקבל טור טיילור שהוא טור סינוסים בלבד. באופן דומה, פונקציה סימטרית תהיה בעלת טור קוסינוסים בלבד. בשני המקרים הסימטריה או האנטי-סימטריה לא חייבות להיות מושלמות – גם אם הן נכשלות במספר סופי של נקודות זה לא ישפיע על כלום כי אינטגרל של פונקציה לא משתנה אם משנים את הפונקציה במספר סופי של נקודות. יותר מכך, אם \(f\) היא אנטיסימטרית אז \(f\left(x\right)\sin nx\) היא סימטרית, ואם \(f\) סימטרית כך גם \(f\left(x\right)\cos nx\). זה אומר שאפשר לפשט טיפה את נוסחת האינטגרל ולהתעסק רק עם חצי מהתחום:

אם \(f\) אנטיסימטרית אז \(f\left(x\right)=\sum b_{n}\sin nx\) כאשר \(b_{n}=\frac{2}{\pi}\int_{0}^{\pi}f\left(x\right)\sin nxdx\)

אם \(f\) סימטרית אז \(f\left(x\right)=\sum a_{n}\cos nx\) כאשר \(a_{n}=\frac{2}{\pi}\int_{0}^{\pi}f\left(x\right)\cos nxdx\)

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

עכשיו בואו נעבור לדבר קצת על שאלת ההתכנסות הנקודתית. נניח ש-\(f\left(x\right)=\frac{a_{0}}{2}+\sum a_{n}\cos nx+\sum b_{n}\sin nx\), כשהשוויון מייצג, כרגיל, התכנסות בנורמה. מה בעצם הבעיה המרכזית שמונעת מאיתנו להיות בטוחים שיש גם התכנסות נקודתית? פשוט מאוד, העובדה שציינתי כבר קודם: המקדמים נקבעים על ידי חישוב של אינטגרל שכולל את \(f\); אבל אם נשנה את הערך של \(f\) בנקודה אחת, זה לא ישנה את הערך של האינטגרלים. בעצם, לכל טור פורייה \(\frac{a_{0}}{2}+\sum a_{n}\cos nx+\sum b_{n}\sin nx\) אנחנו מסוגלים למצוא מחלקה לא קטנה של פונקציות שמתוארות על ידו. אם תחשבו על זה רגע, תשימו לב שכל הפונקציות הללו יהיו במרחק 0 אחת מהשניה כשאנחנו מודדים מרחקים עם הנורמה שנובעת מהמכפלה הפנימית שלנו, וזה לא הכי תקין מתמטית כי פונקציית מרחק ("מטריקה") אמורה להבטיח ששני איברים הם במרחק 0 אחד מהשני רק אם הם זהים. למטריקה שכושלת בעניין הזה קוראים "פסאודומטריקה" והדרך המקובלת "לתקן" אותה היא להגדיר יחס שקילות על אברי המרחב שלנו – שני איברים הם שקולים אם המרחק ביניהם הוא 0. עכשיו אפשר לעבור מהמרחב שלנו למרחב חדש, שהוא מרחב המנה שמתקבל מיחס השקילות הזה, ובו המטריקה תהיה תקינה. ועכשיו, איזה נציג אנחנו רוצים לבחור לכל מחלקת שקילות?

אתם לא חייבים להבין את כל הנאום שלמעלה כדי להבין את הרעיון: אותו טור פורייה מייצג כמה פונקציות שונות, והשאלה היא מי מביניהן היא הפונקציה ה"מוצלחת" ביותר, מבחינת זה שההתכנסות הנקודתית בה אופטימלית. באופן כללי זו גם לא שאלה טריוויאלית, אבל תחת תנאים מסויימים אפשר להבטיח התכנסות נקודתית. אתן אחד מהם שיחסית קל לנסח, למרות שיש עוד: אם הפונקציה רציפה וגזירה אז הטור שלה מתכנס אליה נקודתית. גם אם נקלקל ונוסיף נקודות אי רציפות של "קפיצה" בין שני ערכים, הטור עדיין יתכנס נקודתית פרט לנקודות אי הרציפות שבה הטור יתכנס לממוצע של שני הערכים (בדיוק מה שקרה עם הדוגמה שלנו). מה שכן, ההתכנסות הזו היא לא בהכרח התכנסות במידה שווה, למי שמכירים את המושג. לא פורמלית, התכנסות במידה שווה פירושו שאם נסכום מספיק איברים של הטור, אז לא תהיה לנו בשום מקום שגיאה "גדולה". אפקט גיבס – הצ'ופצ'יקים ליד נקודות אי הרציפות – הוא דוגמה נגדית במקרה שלנו להתכנסות במידה שווה; ככל שנסכום יותר איברים כך הצ'ופצ'יק יתכווץ – יהיו פחות ערכים שבהם יש צ'ופצ'יק – אבל הוא לעולם לא יקטן מספיק בגובה שלו, כלומר תמיד תהיה נקודה כלשהי שבה יש שגיאה גדולה יחסית (אם נחבר עוד ערכים אז הנקודה הזו תהפוך למדוייקת יותר, אבל עדיין תהיה נקודה אחרת שבה יש שגיאה גדולה).

מה על פונקציות שהן "סתם" רציפות, בלי הנחות מיוחדות לגבי הנגזרת שלהן? רציפות היא תכונה מאוד נחמדה מצד אחד, שמונעת מאיתנו "לקלקל" פונקציות בצורה נקודתית כדי להבטיח שטור הפורייה שלהן יטעה באותן נקודות – אבל עדיין, אם אין לנו שליטה על גודל הנגזרת, הפונקציה יכולה להיות די משוגעת. לא אתן דוגמאות נגדיות מפורשות, אבל ניתן לבנות פונקציות רציפות שטור הפורייה שלהן בכלל לא מתכנס נקודתית בשום מקום. אז מה עושים? ובכן, מסתבר שגרסה יותר כללית של התכנסות עדיין עובדת כאן. בואו נסתכל שניה על סדרת הסכומים החלקיים של טור פורייה כלשהו, כלומר נגדיר \(S_{m}\left(x\right)=\frac{a_{0}}{2}+\sum_{n=1}^{m}\left(a_{n}\cos nx+b_{n}\sin nx\right)\). ייתכן, כאמור, שהסדרה \(S_{0}\left(x\right),S_{1}\left(x\right),S_{2}\left(x\right),\dots\) לא מתכנסת בכלל עבור ערכים מסויימים של \(x\), אבל אפשר להסתכל על סדרת הממוצעים שלה:

\(\sigma_{m}\left(x\right)=\frac{S_{0}\left(x\right)+\dots+S_{m}\left(x\right)}{m+1}\)

ניתן להוכיח – ושוב, לא אעשה זאת כרגע – שאם \(f\) היא פונקציה רציפה ואנו סוכמים את טור הפורייה שלה בצורה הזו של סדרת הממוצעים, אז הסכום הזה מתכנס לערך של \(f\) בכל נקודה שבה \(f\) רציפה. שיטת הסכימה הזו – סכימה של הממוצעים – נקראת "סכימת צזארו" והזכרתי אותה לא מזמן בפוסט שעסק בשוויון המוזר \(1+2+3+\dots=-\frac{1}{12}\). שם הסכימה הזו נתנה את הסכום הלא אינטואיטיבי \(1-1+1-1+1-\dots=\frac{1}{2}\), ולא מעט אנשים התקשו לקבל אותו כלגיטימי; אני מקווה שהשימוש הנוכחי של סכימת צזארו, שמראה שאפשר עם קצת תושייה לשחזר את הפונקציה המקורית גם מתוך טור פורייה שאינו מתכנס נקודתית, יסייע קצת להפחתת הסקפטיות בנוגע לשיטת הסכימה הנחמדה הזו.

לסיום הפוסט הזה אני רוצה לחשב את טור הפורייה של עוד פונקציה פשוטה – מכיוון שהחישוב הזה יניב תוצאה יפה ולא טריוויאלית (שכבר הראיתי בבלוג בדיוק באותו האופן אבל מי זוכר). הפונקציה היא \(f\left(x\right)=x\) בתחום \(\left[-\pi,\pi\right]\). זו פונקציה אנטיסימטרית ולכן הפיתוח שלה הוא לטור סינוסים \(f\left(x\right)=\sum b_{n}\sin nx\) כאשר \(b_{n}\) נתון על ידי האינטגרל \(\frac{2}{\pi}\int_{0}^{\pi}x\sin nxdx\). זה לא אינטגרל מסובך, אבל צריך להשתמש בתעלול אינטגרציה בסיסי בשבילו – אינטגרציה בחלקים. נקבל:

\(\int_{0}^{\pi}x\sin nxdx=\left[-\frac{x\cos nx}{n}\right]_{0}^{\pi}-\int_{0}^{\pi}\frac{\cos nx}{n}dx=\left(-1\right)^{n+1}\frac{\pi}{n}\)

(האינטגרל עם הקוסינוס מתאפס, כפי שכבר ראינו לא מעט בפוסט)

מסקנה, אחרי שנכפול מחדש ב-\(\frac{2}{\pi}\): \(b_{n}=\frac{2}{n}\left(-1\right)^{n+1}\). כלומר, ניתן לכתוב את הטור במפורש כך:

\(x=2\sin x-\sin2x+\frac{2}{3}\sin3x-\frac{1}{2}\sin4x+\dots\)

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

\(\|x\|^{2}=\frac{1}{\pi}\int_{-\pi}^{\pi}x^{2}dx=\frac{1}{\pi}\left[\frac{x^{3}}{3}\right]_{-\pi}^{\pi}=\frac{1}{\pi}\frac{\pi^{3}+\pi^{3}}{3}=\frac{2}{3}\pi^{2}\)

עדיין לא נראה מעניין במיוחד, אבל אפשר להשתמש ב"משפט פיתגורס" של מרחבי מכפלה פנימית אינסוף ממדיים – שוויון פרסבל, שאומר שאם \(f=\sum a_{n}e_{n}\) כאשר \(e_{n}\) הם אברי בסיס אורתונורמלי, אז \(\|f\|^{2}=\sum a_{n}^{2}\). במקרה שלנו, \(b_{n}^{2}=\frac{4}{n^{2}}\), אז קיבלנו את השוויון הבא:

\(\frac{2}{3}\pi^{2}=\sum_{n=1}^{\infty}\frac{4}{n^{2}}\)

ועל ידי חלוקה ב-4 של שני האגפים נקבל:

\(\sum_{n=1}^{\infty}\frac{1}{n^{2}}=\frac{\pi^{2}}{6}\)

השוויון הזה הוא אחת התוצאות החביבות עלי במתמטיקה – באגף שמאל יש לנו את אחד הטורים המתכנסים הפשוטים ביותר. על פניו בכלל לא ברור איך לחשב את סכומו; ופתאום, באגף ימין יש לנו את הסכום באופן מדויק, וצץ שם \(\pi\) השד יודע מאיפה למרות שלסכום הזה אין לכאורה שום קשר למעגלים. לדעתי זה נפלא. אם אתם רוצים לראות עוד הוכחות (ההוכחה של אוילר נפלאה אפילו עוד יותר) – כאמור, כבר יש לי פוסט על התוצאה הזו. עם זאת, אפשר להשתמש בטורי פורייה של פונקציות נוספות כדי לקבל עוד סכומים דומים, אבל לבינתיים נראה לי שהנקודה הובהרה.

-->

מתמטיקאים אוהבים לפרק דברים לגורמים. כל מספר טבעי קל יותר להבין אם מפרקים אותו למכפלה של ראשוניים. גם עם פונקציות ממשיות זה עובד כך – אחד מהדברים האהובים על מתמטיקאים הוא לקחת פונקציה ממשית \(f\left(x\right)\) ולכתוב אותה בתור טור חזקות: … להמשיך לקרוא

פוסט של בעיית ההתאמה של פוסט

"בעיית ההתאמה של פוסט" – Post Correspondence Problem, ובקיצור PCP – היא בעיה נחמדה במדעי המחשב שנקראת על שם אמיל פוסט, אחד מחלוצי מדעי המחשב (ואינה קשורה לדואר, כמו שחשבתי הרבה זמן) שתיאר אותה ב-1946. מה שנחמד בבעיה הזו הוא … להמשיך לקרוא

על גבולות עליונים ותחתונים של קבוצות וממשיים

אחד הדברים הנחמדים במתמטיקה הוא שאם אנחנו נתקלים באותו מושג בשני הקשרים שונים, יש סיכוי טוב שיש מושג כללי יותר שעומד מאחורי שניהם ומסביר אותם. זו חוויה שבוודאי מוכרת מאוד לסטודנטים במתמטיקה; אני עצמי זוכר סמסטר אחד שלי שבו בכל … להמשיך לקרוא