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