אוטומטים אי דטרמיניסטיים ושאר מריעין בישין

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

אוטומטים ושפות רגולריות – מבוא

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

בעיית המטבעות

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

חישוב קוונטי – דברי סיום ופרידה

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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