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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

פרוייקט "תוצאות מפתיעות בסיבוכיות" יוצא לדרך!

בשלהי מהומת ה"הוכחה" ש-$latex \mbox{P}\ne\mbox{NP}$ בקיץ האחרון נתקלתי במצגת של סקוט אהרונסון שניסתה לדבר על בעיית $latex \mbox{P}\ne\mbox{NP}$ ומדוע היא כה קשה. אחד מהשקפים ניסה להמחיש עד כמה הוכחה שמתקיים דווקא $latex \mbox{P}=\mbox{NP}$ תהיה מפתיעה – הבאתי אותו בבלוג גם בעבר, והנה הוא שוב: מנקודת מבטו של מי שמכיר קצת את תורת הסיבוכיות השקף הזה …