מדידת עלות חישובית

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

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

ניתן לדגמן או לתאר את החישוב עצמו בדרכים שונות, כמו תוכנת מחשב כתובה ב-Python, מכונת טיורינג, Circuit בוליאני, או Circuit קוונטי. נתמקד ב-Circuits (גם בוליאניים וגם קוונטיים).

קידודים ואורך קלט

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

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

מספר	קידוד בינארי	אורך
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

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

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

מספר	קידוד יוניארי	קידוד לקסיקוגרפי
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

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

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

לדוגמה, מספר הביטים הדרוש לביטוי מספר שלם אי-שלילי $N$ בסימון בינארי, שמסומן לפעמים $\operatorname{lg}(N),$ ניתן על ידי הנוסחה הבאה.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

בהנחה שאנחנו משתמשים בסימון בינארי לקידוד הקלט לבעיית פירוק לגורמים שלמים, אורך הקלט עבור המספר $N$ הוא לכן $\operatorname{lg}(N).$ שימו לב, בפרט, שאורך (או גודל) הקלט $N$ הוא לא $N$ עצמו; כאשר $N$ גדול אנחנו לא צריכים כמעט כל כך הרבה ביטים כדי לבטא את $N$ בסימון בינארי.

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

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

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

פעולות יסודיות

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

מבחינה פורמלית, ישנן בחירות שונות לגבי מה מהווה פעולה יסודית בהתאם למודל החישובי המשמש. נתמקד במודלים מבוססי Circuit, ובפרט ב-Circuits קוונטיים ובוליאניים.

קבוצות Gate אוניברסליות

במודלים מבוססי Circuit של חישוב, נהוג שכל Gate נחשב לפעולה יסודית. זה מוביל לשאלה בדיוק אילו Gates אנחנו מתירים ב-Circuits שלנו. בהתמקדות לרגע ב-Circuits קוונטיים, ראינו מספר Gates עד כה בסדרה זו, כולל $X,$ $Y,$ $Z,$ $H,$ $S,$ ו-$T$ gates, swap gates, גרסאות מבוקרות של Gates (כולל controlled-NOT, Toffoli, ו-Fredkin gates), וכן Gates המייצגים מדידות בסיס סטנדרטי. בהקשר של משחק CHSH ראינו גם כמה rotation gates נוספים.

דנו גם בquery gates בהקשר של מודל השאילתות, וראינו גם שכל פעולה אוניטרית $U,$ הפועלת על כל מספר של Qubits, יכולה להיחשב כ-Gate אם נבחר בכך — אבל נתעלם משתי האפשרויות האלה לצורך דיון זה. לא נעבוד במודל השאילתות (אם כי היישום של query gates באמצעות פעולות יסודיות נדון מאוחר יותר בשיעור), ותצוגה של Gates אוניטריות שרירותיות, הפועלות פוטנציאלית על מיליוני Qubits, כפעולות יסודיות אינה מובילה למושגים משמעותיים או ריאליסטיים של עלות חישובית.

בהצמדות ל-Gates קוונטיות הפועלות על מספרים קטנים של Qubits, גישה אחת להחלטה אילו מהן ייחשבו יסודיות היא לנסות להגיע לקריטריון מדויק — אבל זו לא הגישה הסטנדרטית ולא זו שנאמץ. במקום זאת, אנחנו פשוט עושים בחירה.

הנה בחירה סטנדרטית אחת, שנאמץ כקבוצת ה-Gate הברירת המחדל ל-Circuits קוונטיים:

• Gates אוניטריות חד-Qubit מהרשימה הזו: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ ו-$T^{\dagger}$
• Controlled-NOT gates
• מדידות בסיס סטנדרטי חד-Qubit

חלופה נפוצה היא לראות ב-Toffoli, Hadamard ו-$S$ gates כיסודיים, בנוסף למדידות בסיס סטנדרטי. לפעמים כל ה-Gates החד-Qubit נחשבים יסודיים, אם כי זה אכן מוביל למודל חזק בצורה לא ריאליסטית כאשר הדיוק שבו מבוצעים ה-Gates אינו נלקח בחשבון כראוי.

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

עבור Circuits בוליאניים, נתייחס ל-AND, OR, NOT ו-FANOUT gates כאלה המייצגים פעולות יסודיות. לא צריך גם AND gates וגם OR gates — אנחנו יכולים להשתמש בחוקי דה מורגן להמיר מאחד לשני על ידי הצבת NOT gates על כל שלושת חוטי הקלט/פלט — אבל בכל זאת נהוג ונוח לאפשר גם AND וגם OR gates. AND, OR, NOT ו-FANOUT gates מרכיבים קבוצה אוניברסלית לחישובים דטרמיניסטיים, כלומר שניתן לממש כל פונקציה ממספר קבוע כלשהו של ביטי קלט למספר קבוע כלשהו של ביטי פלט עם ה-Gates האלה.

עקרון המדידה הנדחית

Gates מדידת בסיס סטנדרטי יכולים להופיע בתוך Circuits קוונטיים, אבל לפעמים נוח לדחות אותם לסוף. זה מאפשר לנו להתייחס לחישובים קוונטיים כמורכבים מחלק אוניטרי (המייצג את החישוב עצמו), ואחריו שלב קריאה פשוט שבו מודדים Qubits והתוצאות מוצאות. ניתן לעשות זאת תמיד, בתנאי שאנחנו מוכנים להוסיף Qubit נוסף לכל מדידת בסיס סטנדרטי. בתרשים הבא, ה-Circuit מימין ממחיש כיצד ניתן לעשות זאת עבור ה-Gate משמאל.

באופן ספציפי, הביט הקלאסי ב-Circuit משמאל מוחלף ב-Qubit מימין (מאותחל למצב $\vert 0\rangle$), ומדידת הבסיס הסטנדרטי מוחלפת ב-Gate controlled-NOT, ואחריו מדידת בסיס סטנדרטי על ה-Qubit התחתון. הנקודה היא שמדידת הבסיס הסטנדרטי ב-Circuit הימני יכולה להידחות לסוף ה-Circuit. אם הביט הקלאסי ב-Circuit השמאלי משמש מאוחר יותר כביט שליטה, אנחנו יכולים להשתמש ב-Qubit התחתון ב-Circuit הימני כשליטה במקום, והאפקט הכולל יהיה זהה. (אנחנו מניחים שהביט הקלאסי ב-Circuit השמאלי לא נדרס לאחר המדידה על ידי מדידה נוספת — אבל אם היה כן, תמיד יכולנו פשוט להשתמש בביט קלאסי חדש במקום להחליף את זה שהשתמשנו בו למדידה קודמת.)

גודל ועומק של Circuit

גודל Circuit

המספר הכולל של שערים ב-Circuit נקרא גודל ה-Circuit. לפיכך, בהנחה שהשערים ב-Circuit שלנו מייצגים פעולות אלמנטריות, גודל ה-Circuit מייצג את מספר הפעולות האלמנטריות שהוא דורש — או, במילים אחרות, את עלות החישוב שלו. אנחנו כותבים $\operatorname{size}(C)$ כדי להתייחס לגודל של Circuit נתון $C.$

לדוגמה, שקול את ה-Circuit הבוליאני הבא לחישוב ה-XOR של שני ביטים.

גודל ה-Circuit הזה הוא 7 כי יש בו 7 שערים בסך הכול. (פעולות Fanout לא תמיד נספרות כשערים, אך לצורך השיעור הזה נספור אותן כשערים.)

זמן, עלות ועומק Circuit

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

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

אבל שימו לב שגודל Circuit לא בהכרח מתאים ישירות לזמן שלוקח להריץ אותו. ב-Circuit הבוליאני שלנו לחישוב XOR של שני ביטים, למשל, שני שערי FANOUT יכולים להתבצע בו-זמנית, וכך גם שני שערי NOT, וכמו כן שני שערי AND. דרך אחרת למדידת יעילות Circuit, שלוקחת בחשבון אפשרות זו של מקביליות, היא לפי עומקו. זהו המספר המינימלי של שכבות שערים הנדרשות ב-Circuit, כאשר השערים בכל שכבה פועלים על קווים שונים. באופן שקול, עומק ה-Circuit הוא המספר המקסימלי של שערים שנמצאים בכל נתיב מקו כניסה לקו יציאה. עבור ה-Circuit שלמעלה, למשל, העומק הוא 4.

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

הקצאת עלויות לשערים שונים

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

לדוגמה, כפי שכבר הוזכר, שערי FANOUT נחשבים לרוב כחינמיים עבור Circuit בוליאנים — כלומר, אנחנו יכולים לבחור שלשערי FANOUT יש עלות אפס. כדוגמה נוספת, כשאנחנו עובדים במודל השאילתות וסופרים את מספר השאילתות שה-Circuit שולח לפונקציית קלט (בצורת קופסה שחורה), אנחנו למעשה מקצים עלות יחידה לשערי שאילתות ועלות אפס לשערים אחרים, כמו שערי Hadamard. דוגמה אחרונה היא שאנחנו לפעמים מקצים עלויות שונות לשערים בהתאם לאיזה קושי יש ליישם אותם, מה שעשוי להשתנות בהתאם לחומרה הנדונה.

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

עלות כפונקציה של אורך הקלט

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

משפחות של Circuitים

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

לדוגמה, דמיין שיש לנו אלגוריתם קלאסי לפירוק גורמים שלמים, כמו זה שמשמש את factorint. כמו כל האלגוריתמים הקלאסיים, אלגוריתם זה יכול להיות מיושם באמצעות Circuitים בוליאניים — אבל לשם כך נצטרך Circuit נפרד לכל אורך קלט אפשרי. אם נסתכל על ה-Circuitים שנוצרו לאורכי קלט שונים, נראה שגודלם גדל באופן טבעי ככל שאורך הקלט גדל — משקף את העובדה שפירוק גורמים של מספרים בני 4 ביטים הרבה יותר קל ודורש פחות פעולות אלמנטריות בהרבה מאשר פירוק גורמים של מספרים בני 1024 ביטים, למשל.

זה מוביל אותנו לייצג את עלות החישוב של אלגוריתם בפונקציה $t,$ המוגדרת כך ש-$t(n)$ הוא מספר השערים ב-Circuit המיישם את האלגוריתם עבור קלטים בני $n$ ביטים. במונחים פורמליים יותר, אלגוריתם במודל ה-Circuit הבוליאני מתואר על ידי סדרת Circuitים $\{C_1, C_2, C_3,\ldots\},$ כאשר $C_n$ פותר את הבעיה הנדונה עבור קלטים בני $n$ ביטים (או, באופן כללי יותר, עבור קלטים שגודלם מפורמט בצורה כלשהי על ידי $n$), והפונקציה $t$ המייצגת את עלות האלגוריתם מוגדרת כ

$$t(n) = \operatorname{size}(C_n).$$

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

דוגמה: חיבור מספרים שלמים

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

חיבור מספרים שלמים

קלט: מספרים שלמים $N$ ו-$M$
פלט: $N+M$

כיצד נוכל לעצב Circuitים בוליאניים לפתרון בעיה זו?

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

$$0\leq N,M\leq 2^n - 1.$$

הפלט יהיה מחרוזת בינארית בת $(n+1)$ ביטים המייצגת את הסכום, שהוא המספר המקסימלי של ביטים שאנחנו צריכים לבטא את התוצאה.

אנחנו מתחילים עם אלגוריתם — האלגוריתם הסטנדרטי לחיבור ייצוגים בינאריים — שהוא האנלוגיה בבסיס $2$ לאופן שבו לומדים חיבור בבתי ספר יסודיים ברחבי העולם. אלגוריתם זה יכול להיות מיושם עם Circuitים בוליאניים כדלקמן.

מתחילים מהביטים בעלי המשמעות הנמוכה ביותר, אנחנו יכולים לחשב את ה-XOR שלהם כדי לקבוע את הביט בעל המשמעות הנמוכה ביותר של הסכום. לאחר מכן אנחנו מחשבים את ביט הנשיאה, שהוא ה-AND של שני הביטים בעלי המשמעות הנמוכה ביותר של $N$ ו-$M.$ לפעמים שתי הפעולות הללו יחד ידועות בתור חצי מוסיף (half adder).

באמצעות ה-Circuit של XOR שראינו כמה פעמים יחד עם שער AND ושני שערי FANOUT, אנחנו יכולים לבנות חצי מוסיף עם 10 שערים. אם מסיבה כלשהי שינינו דעתנו והחלטנו לכלול שערי XOR בקבוצת הפעולות האלמנטריות שלנו, היינו צריכים שער AND אחד, שער XOR אחד, ושני שערי FANOUT לבניית חצי מוסיף.

ממשיכים לביטים בעלי המשמעות הגבוהה יותר, אנחנו יכולים להשתמש בהליך דומה, אך הפעם כוללים את ביט הנשיאה מכל מיקום קודם בחישוב שלנו. על ידי חיבור בטור של שני חצאי מוסיפים ולקיחת ה-OR של ביטי הנשיאה שהם מייצרים, אנחנו יכולים ליצור מה שידוע בתור מוסיף מלא (full adder).

זה דורש 21 שערים בסך הכול: 2 שערי AND, 2 שערי XOR (כל אחד דורש 7 שערים ליישום), שער OR אחד, ו-4 שערי FANOUT.

לבסוף, על ידי חיבור בטור של המוסיפים המלאים, אנחנו מקבלים Circuit בוליאני לחיבור מספרים שלמים אי-שליליים. לדוגמה, ה-Circuit הבא מחשב את הסכום של שני מספרים שלמים בני 4 ביטים.

באופן כללי, זה דורש

$$21 (n-1) + 10 = 21 n - 11$$

שערים. אילו היינו מחליטים לכלול שערי XOR בקבוצת הפעולות האלמנטריות שלנו, היינו צריכים $2n-1$ שערי AND, $2n-1$ שערי XOR, $n-1$ שערי OR, ו-$4n-2$ שערי FANOUT, לסך כולל של $9n-5$ שערים. אם בנוסף אנחנו מחליטים לא לספור שערי FANOUT, זה $5n-3$ שערים.

סימון אסימפטוטי

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

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

בניסוח פורמלי, אם יש לנו שתי פונקציות $g(n)$ ו-$h(n),$ אנחנו כותבים ש-$g(n) = O(h(n))$ אם קיים מספר ממשי חיובי $c > 0$ ומספר שלם חיובי $n_0$ כך ש

$$g(n) \leq c\cdot h(n)$$

לכל $n \geq n_0.$ בדרך כלל $h(n)$ נבחרת להיות ביטוי פשוט ככל האפשר, כך שניתן להשתמש בסימון כדי לחשוף את ההתנהגות הגבולית של פונקציה במונחים פשוטים. לדוגמה, $17 n^3 - 257 n^2 + 65537 = O(n^3).$

ניתן להרחיב סימון זה לפונקציות בעלות מספר ארגומנטים בצורה די פשוטה. לדוגמה, אם יש לנו שתי פונקציות $g(n,m)$ ו-$h(n,m)$ המוגדרות על מספרים שלמים חיוביים $n$ ו-$m,$ אנחנו כותבים ש-$g(n,m) = O(h(n,m))$ אם קיים מספר ממשי חיובי $c > 0$ ומספר שלם חיובי $k_0$ כך ש

$$g(n,m) \leq c\cdot h(n,m)$$

בכל פעם ש-$n+m \geq k_0.$

חיבור סימון זה לדוגמה של חיבור מספרים שלמים אי-שליליים, אנחנו מסיקים שקיימת משפחה של Circuitים בוליאניים $\{C_1, C_2,\ldots,\},$ כאשר $C_n$ מחבר שני מספרים שלמים אי-שליליים בני $n$ ביטים, כך ש-$\operatorname{size}(C_n) = O(n).$ זה חושף את המאפיין החיוני ביותר של אופן שבו עלות החיבור מתרחבת עם גודל הקלט: היא מתרחבת ליניארית.

שימו לב גם שזה לא תלוי בפרט הספציפי של האם אנחנו רואים שערי XOR כבעלי עלות יחידה או עלות $7.$ באופן כללי, שימוש בסימון Big-O מאפשר לנו לעשות הצהרות על עלויות חישוב שאינן רגישות לפרטים ברמה נמוכה כזו.

דוגמאות נוספות

הנה כמה דוגמאות נוספות של בעיות מתורת המספרים החישובית, מתחילות עם כפל.

כפל מספרים שלמים

קלט: מספרים שלמים $N$ ו-$M$
פלט: $NM$

יצירת Circuitים בוליאניים לבעיה זו קשה יותר מיצירת Circuitים לחיבור — אך על ידי חשיבה על אלגוריתם הכפל הסטנדרטי, אנחנו יכולים לחשוב על Circuitים בגודל $O(n^2)$ לבעיה זו (בהנחה ש-$N$ ו-$M$ מיוצגים שניהם על ידי ייצוגים בינאריים בני $n$ ביטים). באופן כללי יותר, אם ל-$N$ יש $n$ ביטים ול-$M$ יש $m$ ביטים, קיימים Circuitים בוליאניים בגודל $O(nm)$ לכפל $N$ ו-$M.$

למעשה, קיימות דרכים אחרות לכפל שמתרחבות טוב יותר. לדוגמה, אלגוריתם הכפל של Schönhage-Strassen יכול לשמש ליצירת Circuitים בוליאניים לכפל שני מספרים שלמים בני $n$ ביטים בעלות $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ המורכבות של שיטה זו גורמת להרבה תקורה, עם זאת, מה שהופך אותה לפרקטית רק עבור מספרים בעלי עשרות אלפי ביטים.

בעיה בסיסית נוספת היא חילוק, שאנחנו מפרשים כחישוב הן של המנה והן של השאריות בהינתן חלק שלם ומחולק.

חילוק מספרים שלמים

קלט: מספרים שלמים $N$ ו-$M\neq0$
פלט: מספרים שלמים $q$ ו-$r$ המקיימים $0\leq r < |M|$ ו-$N = q M + r$

עלות החילוק השלם דומה לכפל: אם ל-$N$ יש $n$ ביטים ול-$M$ יש $m$ ביטים, קיימים Circuitים בוליאניים בגודל $O(nm)$ לפתרון בעיה זו. וכמו כפל, ידועות שיטות עדיפות אסימפטוטית.

אנחנו יכולים כעת להשוות אלגוריתמים ידועים לחישוב GCDים עם אלה לחיבור וכפל. אלגוריתם אוקלידס לחישוב GCD של מספר $N$ בן $n$ ביטים ומספר $M$ בן $m$ ביטים דורש Circuitים בוליאניים בגודל $O(nm),$ בדומה לאלגוריתמים הסטנדרטיים לכפל וחילוק. גם בדומה לכפל וחילוק, קיימים אלגוריתמי GCD מהירים יותר אסימפטוטית — כולל כאלה הדורשים $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ פעולות אלמנטריות לחישוב GCD של שני מספרים בני $n$ ביטים.

חישוב יקר יותר מעט שמופיע בתורת המספרים הוא חזקה מודולרית.

חזקה מודולרית של מספרים שלמים

קלט: מספרים שלמים $N,$ $K,$ ו-$M$ עם $K\geq 0$ ו-$M\geq 1$
פלט: $N^K \hspace{1mm} (\text{mod }M)$

ב-$N^K\hspace{1mm} (\text{mod }M)$ אנחנו מתכוונים לשארית כשמחלקים את $N^K$ ב-$M,$ כלומר המספר השלם הייחודי $r$ המקיים $0\leq r < M$ ו-$N^K = q M + r$ עבור מספר שלם $q$ כלשהו.

אם ל-$N$ יש $n$ ביטים, ל-$M$ יש $m$ ביטים, ול-$K$ יש $k$ ביטים, ניתן לפתור בעיה זו על ידי Circuitים בוליאניים בגודל $O(k m^2 + nm).$ זה לא מובן מאליו כלל. הפתרון אינו לחשב תחילה את $N^K$ ואז לקחת את השארית, מה שיצריך שימוש במספר אקספוננציאלי של ביטים רק לאחסון המספר $N^K.$ במקום זאת, אנחנו יכולים להשתמש באלגוריתם החזקה (הידוע לחלופין בשם שיטה בינארית וריבוע חוזר), המשתמש בייצוג הבינארי של $K$ כדי לבצע את החישוב כולו מודולו $M.$ בהנחה ש-$N,$ $M,$ ו-$K$ הם כולם מספרים בני $n$ ביטים, אנחנו מקבלים אלגוריתם $O(n^3)$ — או אלגוריתם קובי בזמן. ושוב, ידועים אלגוריתמים מורכבים יותר אך מהירים יותר אסימפטוטית.

עלות פירוק גורמים שלמים

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

גישה פשוטה אחת לפירוק גורמים היא חילוק ניסיון, שבה אלגוריתם מחפש ברשימה $2,\ldots,\sqrt{N}$ כדי למצוא גורם ראשוני של מספר קלט $N.$ זה דורש $O(2^{n/2})$ איטרציות במקרה הגרוע כשאשר $N$ הוא מספר בן $n$ ביטים. כל איטרציה דורשת חילוק ניסיון, מה שאומר $O(n^2)$ פעולות אלמנטריות לכל איטרציה (באמצעות אלגוריתם סטנדרטי לחילוק שלם). אנחנו מקבלים Circuitים בגודל $O(n^2 2^{n/2}),$ שהוא אקספוננציאלי בגודל הקלט $n.$

קיימים אלגוריתמים לפירוק גורמים שלמים עם סקלה טובה יותר. ה-number field sieve שהוזכר קודם, למשל, שהוא אלגוריתם המשתמש באקראיות, מאמינים בדרך כלל (אך לא הוכח בקפדנות) שהוא דורש

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

פעולות אלמנטריות לפירוק גורמים של מספרים שלמים בני $n$ ביטים בהסתברות גבוהה. אמנם חשוב למדי ש-$n$ מועלה לחזקה $1/3$ במעריך של ביטוי זה, אך העובדה שהוא מופיע במעריך עדיין בעיה הגורמת לסקלה גרועה — ומסבירה בחלקה מדוע RSA1024 נותר מחוץ לתחום הישימות שלו.

עלות פולינומית לעומת אקספוננציאלית

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

כולן הן דוגמאות לאלגוריתמים בעלי עלות פולינומית, כלומר שיש להם עלות $O(n^c)$ עבור בחירה כלשהי של קבוע קבוע $c > 0.$ כקירוב גס ראשוני, אלגוריתמים בעלי עלות פולינומית נתפסים בצורה מופשטת כמייצגים אלגוריתמים יעילים.

לעומת זאת, אלגוריתמים קלאסיים ידועים לפירוק גורמים שלמים בעלי עלות אקספוננציאלית. לפעמים עלות ה-number field sieve מתוארת כתת-אקספוננציאלית משום ש-$n$ מועלה לחזקה $1/3$ במעריך, אך בתורת הסיבוכיות יותר נהוג לשמור מונח זה לאלגוריתמים שעלותם היא

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

לכל $\varepsilon > 0.$ הבעיות הנקראות NP-שלמות הן מחלקה של בעיות שאינן ידועות כבעלות (ומשוערות באופן נרחב כלא בעלות) אלגוריתמים בעלות פולינומית. ניסוח מבוסס Circuit של השערת הזמן האקספוננציאלי מציב משהו חזק עוד יותר, והוא שאף בעיה NP-שלמה אינה יכולה לקבל אלגוריתם בעלות תת-אקספוננציאלית.

הקשר בין אלגוריתמים בעלות פולינומית לבין אלגוריתמים יעילים חייב להיות מובן כהפשטה רופפת. כמובן, אם עלות אלגוריתם מתרחבת כ-$n^{1000}$ או $n^{1000000}$ עבור קלטים בגודל $n,$ אז זה מתיחה לתאר את האלגוריתם הזה כיעיל. עם זאת, אפילו אלגוריתם שעלותו מתרחבת כ-$n^{1000000}$ חייב לעשות משהו חכם כדי להימנע מעלות אקספוננציאלית, שזה בדרך כלל מה שאנחנו מצפים מאלגוריתמים המבוססים בצורה כלשהי על "כוח גסה" או "חיפוש ממצה". אפילו שיפורי ה-number field sieve המתוחכמים, למשל, נכשלים בהימנעות מסקלה אקספוננציאלית זו בעלות. אלגוריתמים בעלות פולינומית, לעומת זאת, מצליחים לנצל את מבנה הבעיה בצורה כלשהי המונעת סקלה אקספוננציאלית.

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

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

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

עלות נסתרת של חישוב Circuit

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

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

אבל מה קורה אם קיימות עלויות חישוביות מונעות הקשורות בתבניות ב-Circuitים עצמם? לדוגמה, התיאור של כל איבר $C_n$ במשפחת Circuit יכול, באופן עקרוני, להיקבע על ידי פונקציה קשה מאוד לחישוב של $n.$

התשובה היא שזוהי אכן בעיה — ולכן עלינו להציב הגבלות נוספות על משפחות Circuitים מעבר לעלות פולינומית כדי שהן יייצגו באמת אלגוריתמים יעילים. התכונה של אחידות (uniformity) עבור Circuitים עושה זאת על ידי קביעה שבניסוחים מדויקים שונים, חייב להיות קל חישובית לקבל את תיאורו של כל Circuit במשפחה.