הפחתת שגיאות קריאה עבור ה-Sampler primitive באמצעות M3

אומדן שימוש: פחות מדקה על מעבד Heron r2 (הערה: זהו אומדן בלבד. זמן הריצה בפועל עשוי להשתנות.)

רקע

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

תוסף ה-M3 של Qiskit מממש שיטה יעילה להפחתת שגיאות קריאה. מדריך זה מסביר כיצד להשתמש בתוסף M3 של Qiskit להפחתת שגיאות קריאה עבור ה-Sampler primitive.

מהי שגיאת קריאה?

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

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

רקע תיאורטי

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

ביתר דיוק, עבור כל זוג מחרוזות ביטים $(i, j)$, קיימת הסתברות (מותנית) ${M}_{i,j}$ ש-$i$ נקרא, בהינתן שהערך האמיתי הוא $j.$ כלומר,

$${M}_{i,j} = \Pr(\text{readout value is } i | \text{true value is } j) \text{ for } i,j \in (0,...,2^n - 1), \tag{1}$$

כאשר $n$ הוא מספר הביטים ברשומת הקריאה. לשם הבהרה, אנו מניחים ש-$i$ הוא מספר שלם עשרוני שייצוגו הבינארי הוא מחרוזת הביטים המתייגת את מצבי הבסיס החישובי. אנו מכנים את המטריצה ${M}$ בגודל $2^n \times 2^n$ מטריצת ההשמה. עבור ערך אמיתי קבוע $j$, סכום ההסתברויות על כל התוצאות הרועשות $i$ חייב להיות $1$. כלומר

$$\sum_{i=0}^{2^n - 1} {M}_{i,j} = 1 \text{ for all } j$$

מטריצה ללא ערכים שליליים המקיימת (1) נקראת סטוכסטית-שמאלית. מטריצה סטוכסטית-שמאלית נקראת גם סטוכסטית-עמודה מאחר שכל אחת מעמודותיה מסתכמת ל-$1$. אנו קובעים בניסוי ערכים משוערים לכל איבר ${M}_{i,j}$ על ידי הכנה חוזרת של כל מצב בסיס $|j \rangle$ ולאחר מכן חישוב התדירויות של התרחשות מחרוזות הביטים הדגומות.

אם ניסוי כולל אמידת התפלגות הסתברות על מחרוזות ביטים פלט באמצעות דגימה חוזרת, אז נוכל להשתמש ב-${M}$ להפחתת שגיאות קריאה ברמת ההתפלגות. הצעד הראשון הוא להריץ מעגל קבוע המעניין אותנו פעמים רבות, וליצור היסטוגרמה של מחרוזות ביטים דגומות. ההיסטוגרמה המנורמלת היא התפלגות ההסתברות הנמדדת על $2^n$ מחרוזות הביטים האפשריות, שאנו מסמנים אותה ב-${\tilde{p}} \in \mathbb{R}^{2^n}$. ההסתברות (המשוערת) ${{\tilde{p}}}_i$ לדגימת מחרוזת הביטים $i$ שווה לסכום על כל מחרוזות הביטים האמיתיות $j$, כל אחת משוקללת לפי ההסתברות שהיא תתפרש בטעות כ-$i$. הצהרה זו בצורה מטריציאלית היא

$${\tilde{p}} = {M} {\vec{p}}, \tag{2},$$

כאשר ${\vec{p}}$ היא ההתפלגות האמיתית. במילים אחרות, לשגיאת הקריאה יש השפעה של הכפלת ההתפלגות האידיאלית על מחרוזות הביטים ${\vec{p}}$ במטריצת ההשמה ${M}$ לייצור ההתפלגות הנצפית ${\tilde{p}}$. מדדנו את ${\tilde{p}}$ ואת ${M}$, אך אין לנו גישה ישירה ל-${\vec{p}}$. באופן עקרוני, נקבל את ההתפלגות האמיתית של מחרוזות הביטים עבור המעגל שלנו על ידי פתרון משוואה (2) עבור ${\vec{p}}$ באופן נומרי.

לפני שנמשיך, כדאי לציין כמה תכונות חשובות של גישה נאיבית זו.

• בפועל, משוואה (2) אינה נפתרת על ידי היפוך ${M}$. שגרות אלגברה לינארית בספריות תוכנה משתמשות בשיטות יציבות, מדויקות ויעילות יותר.
• בעת אמידת ${M}$, הנחנו שאירעו רק שגיאות קריאה. בפרט, הנחנו שלא היו שגיאות הכנת מצב ומדידה קוונטית — או לפחות שהן הופחתו בדרכים אחרות. במידה שהנחה זו טובה, ${M}$ מייצגת רק שגיאת קריאה. אך כאשר אנו משתמשים ב-${M}$ לתיקון התפלגות נמדדת על מחרוזות ביטים, אין אנו עושים הנחה כזו. למעשה, אנו מצפים שמעגל מעניין יכניס רעש, למשל שגיאות Gate. ההתפלגות "האמיתית" עדיין כוללת השפעות מכל שגיאות שלא הופחתו בדרכים אחרות.

שיטה זו, אף שהיא שימושית בנסיבות מסוימות, סובלת ממספר מגבלות.

משאבי המרחב והזמן הדרושים לאמידת ${M}$ גדלים באופן אקספוננציאלי ב-$n$:

• האמידה של ${M}$ ו-${\tilde{p}}$ כפופה לשגיאה סטטיסטית עקב דגימה סופית. רעש זה יכול להיות קטן כרצוי על חשבון יריות נוספות (עד לסקאלת הזמן של שינוי פרמטרי חומרה הגורמים לשגיאות שיטתיות ב-${M}$). אולם, אם אין הנחות לגבי מחרוזות הביטים שנצפות בעת ביצוע ההפחתה, מספר היריות הדרוש לאמידת ${M}$ גדל לפחות אקספוננציאלית ב-$n$.
• ${M}$ היא מטריצה בגודל $2^n \times 2^n$. כאשר $n>10$, כמות הזיכרון הדרושה לאחסון ${M}$ גדולה מהזיכרון הזמין במחשב נייד רב-עוצמה.

מגבלות נוספות הן:

• ההתפלגות המשוחזרת ${\vec{p}}$ עשויה לכלול הסתברות שלילית אחת או יותר (תוך כדי סכימה לאחד). פתרון אחד הוא למזער את $||{M} {\vec{p}} - {\tilde{p}}||^2$ בכפוף לאילוץ שכל ערך ב-${\vec{p}}$ יהיה אי-שלילי. עם זאת, זמן הריצה של שיטה כזו ארוך בסדרי גודל מאשר פתרון ישיר של משוואה (2).
• הליך הפחתה זה פועל ברמת התפלגות הסתברות על מחרוזות ביטים. בפרט, הוא אינו יכול לתקן שגיאה במחרוזת ביטים בודדת שנצפתה.

תוסף ה-M3 של Qiskit: התאמה למחרוזות ביטים ארוכות יותר

פתרון משוואה (2) באמצעות שגרות אלגברה לינארית נומרית סטנדרטיות מוגבל למחרוזות ביטים שאינן ארוכות מכ-10 ביטים. אולם M3 מסוגל לטפל במחרוזות ביטים ארוכות הרבה יותר. שתי תכונות מפתח של M3 המאפשרות זאת הן:

• מתאמים בשגיאת קריאה מסדר שלוש ומעלה בין אוספי ביטים מניחים שהם זניחים ומתעלמים מהם. באופן עקרוני, במחיר של יריות נוספות, ניתן לאמוד מתאמים גבוהים יותר גם כן.
• במקום לבנות את ${M}$ באופן מפורש, אנו משתמשים במטריצה יעילה קטנה בהרבה שמתעדת הסתברויות רק עבור מחרוזות ביטים שנאספו בעת בניית ${\tilde{p}}$.

ברמה גבוהה, ההליך פועל כדלקמן.

ראשית, אנו בונים אבני בניין שמהן ניתן לבנות תיאור יעיל ומפושט של ${M}$. לאחר מכן, אנו מריצים שוב ושוב את המעגל המעניין ואוספים מחרוזות ביטים שמשמשות לבניית הן ${\tilde{p}}$ והן, בעזרת אבני הבניין, ${M}$ יעילה.

ביתר דיוק,

• מטריצות השמה של Qubit יחיד מאומדות עבור כל Qubit. לשם כך, אנו מכינים שוב ושוב את רשומת ה-Qubit במצב האפסים הכולל $|0 ... 0 \rangle$ ואז במצב האחדות הכולל $|1 ... 1 \rangle$, ומתעדים את ההסתברות עבור כל Qubit שנקרא בטעות.

• מתאמים מסדר שלוש ומעלה מניחים שהם זניחים ומתעלמים מהם.

  במקום זאת אנו בונים $n$ מטריצות השמה של Qubit יחיד בגודל $2 \times 2$, ו-$n(n-1)/2$ מטריצות השמה של שני Qubit בגודל $4 \times 4$. מטריצות ה-Qubit היחיד ושני ה-Qubit הללו מאוחסנות לשימוש מאוחר יותר.

• לאחר דגימה חוזרת של מעגל לבניית ${\tilde{p}}$, אנו בונים קירוב יעיל ל-${M}$ תוך שימוש רק במחרוזות ביטים שנדגמו בעת בניית ${\tilde{p}}$. מטריצה יעילה זו נבנית באמצעות מטריצות ה-Qubit היחיד ושני ה-Qubit המוזכרות בסעיף הקודם. הממד הלינארי של מטריצה זו הוא לכל היותר מסדר גודל מספר היריות שנעשה בהן שימוש בבניית ${\tilde{p}}$, שהוא קטן בהרבה מהממד $2^n$ של מטריצת ההשמה המלאה ${M}$.

לפרטים טכניים על M3, ניתן לעיין ב-Scalable Mitigation of Measurement Errors on Quantum Computers.

יישום M3 על אלגוריתם קוונטי

נישם את הפחתת שגיאות הקריאה של M3 על בעיית ההזזה הנסתרת. בעיית ההזזה הנסתרת, ובעיות קשורות כגון בעיית תת-הקבוצה הנסתרת, נוצרו במקור בהקשר של סביבה עמידה לתקלות (ביתר דיוק, לפני שהוכח שמחשבים קוונטיים עמידים לתקלות אפשריים!). אך הן נחקרות גם עם מעבדים זמינים. דוגמה לאצת מהירות אלגוריתמית אקספוננציאלית שהושגה לגרסה של בעיית ההזזה הנסתרת על מחשבי IBM® QPUs בני 127 Qubit ניתן למצוא במאמר זה (גרסת arXiv).

בהמשך, כל האריתמטיקה היא בוליאנית. כלומר, עבור $a, b \in \mathbb{Z}_2 = \{0, 1\}$, חיבור $a + b$ הוא פונקציית ה-XOR הלוגית. יתר על כן, כפל $a \times b$ (או $a b$) הוא פונקציית ה-AND הלוגית. עבור $x, y \in \{0, 1\}^n$, $x + y$ מוגדר על ידי יישום ביטי של XOR. מכפלה הפנימית $\cdot: {\mathbb{Z}_2^n} \rightarrow \mathbb{Z}_2$ מוגדרת על ידי $x \cdot y = \sum_i x_i y_i$.

אופרטור ה-Hadamard והתמרת פורייה

ביישום אלגוריתמים קוונטיים, נפוץ מאוד להשתמש באופרטור ה-Hadamard כתמרת פורייה. מצבי הבסיס החישובי נקראים לעתים מצבים קלאסיים. הם עומדים ב יחס חד-חד-ערכי למחרוזות הביטים הקלאסיות. אופרטור ה-Hadamard של $n$ Qubit על מצבים קלאסיים ניתן לראות כתמרת פורייה על ה-hypercube הבוליאני:

$$H^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x,y \in {\mathbb{Z}_2^n}} (-1)^{x \cdot y} {|{y}\rangle}{\langle{x}|}.$$

נשקול מצב ${|{s}\rangle}$ המתאים למחרוזת ביטים קבועה $s$. על ידי יישום $H^{\otimes n}$, ושימוש ב-${\langle {x}|{s}\rangle} = \delta_{x,s}$, נראה שתמרת פורייה של ${|{s}\rangle}$ ניתן לכתיבה כ-

$$H^{\otimes n} {|{s}\rangle} = \frac{1}{\sqrt{2^n}} \sum_{y \in {\mathbb{Z}_2^n}} (-1)^{s \cdot y} {|{y}\rangle}.$$

ה-Hadamard הוא ההופכי של עצמו, כלומר $H^{\otimes n} H^{\otimes n} = (H H)^{\otimes n} = I^{\otimes n}$. לכן, תמרת הפורייה ההופכית היא אותו האופרטור, $H^{\otimes n}$. באופן מפורש, יש לנו,

$${|{s}\rangle} = H^{\otimes n} H^{\otimes n} {|{s}\rangle} = H^{\otimes n} \frac{1}{\sqrt{2^n}} \sum_{y \in {\mathbb{Z}_2^n}} (-1)^{s \cdot y} {|{y}\rangle}.$$

בעיית ההזזה הנסתרת

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

תהי $x,y \in {\mathbb{Z}_2^m}$ מחרוזות ביטים באורך $m$. נגדיר ${f}: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ על ידי

$${f}(x, y) = (-1)^{x \cdot y}.$$

תהי $a,b \in {\mathbb{Z}_2^m}$ מחרוזות ביטים קבועות באורך $m$. אנו מגדירים עוד $g: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ על ידי

$$g(x, y) = {f}(x+a, y+b) = (-1)^{(x+a) \cdot (y+b)},$$

כאשר $a$ ו-$b$ הם פרמטרים (נסתרים). ניתן לנו שתי קופסאות שחורות, אחת ממשת את $f$, והשנייה את $g$. אנו מניחים שאנו יודעים שהן מחשבות את הפונקציות המוגדרות לעיל, פרט לכך שאיננו יודעים לא את $a$ ולא את $b$. המשחק הוא לקבוע את מחרוזות הביטים הנסתרות (ההזזות) $a$ ו-$b$ על ידי ביצוע שאילתות ל-$f$ ול-$g$. ברור שאם נשחק את המשחק בצורה קלאסית, נדרשות $O(2m)$ שאילתות לקביעת $a$ ו-$b$. לדוגמה, ניתן לשאול את $g$ עם כל הזוגות של מחרוזות כך שאחד מאיברי הזוג הוא אפסים בלבד, והאיבר האחר כולל בדיוק אחד שווה ל-$1$. בכל שאילתה, אנו לומדים איבר אחד מ-$a$ או מ-$b$. אולם, נראה שאם הקופסאות השחורות ממומשות כמעגלי Circuit קוונטיים, נוכל לקבוע את $a$ ו-$b$ עם שאילתה בודדת לכל אחת מ-$f$ ו-$g$.

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

מעגלי Circuit עבור $f$ ו-$g$

אנו זקוקים לרכיבים הבאים כדי לממש את $f$ ו-$g$ כמעגלי Circuit קוונטיים.

עבור מצבים קלאסיים של Qubit יחיד ${|{x_1}\rangle}, {|{y_1}\rangle}$, עם $x_1,y_1 \in \mathbb{Z}_2$, ה-Gate הנשלט $Z$ ${CZ}$ ניתן לכתיבה כ-

$${CZ} {|{x_1}\rangle}{|{y_1}\rangle}{x_1} = (-1)^{x_1 y_1} {|{x_1}\rangle}{x_1}{|{y_1}\rangle}.$$

נפעיל עם $m$ שערי CZ, אחד על $(x_1, y_1)$, ואחד על $(x_2, y_2)$, וכן הלאה, עד $(x_m, y_m)$. אנו מכנים אופרטור זה ${CZ}_{x,y}$.

$U_f = {CZ}_{x,y}$ הוא גרסה קוונטית של ${f} = {f}(x,y)$:

$$U_f {|{x}\rangle}{|{y}\rangle} = {CZ}_{x,y} {|{x}\rangle}{|{y}\rangle} = (-1)^{x \cdot y} {|{x}\rangle}{|{y}\rangle}.$$

אנו גם צריכים לממש הזזת מחרוזת ביטים. אנו מסמנים את האופרטור על הרשומה $x$ ב-$X^{a_1}\cdots X^{a_m}$ על ידי $X_a$ ובאופן דומה על הרשומה $y$ $X_b = X^{b_1}\cdots X^{b_m}$. אופרטורים אלה מיישמים $X$ בכל מקום שביט יחיד הוא $1$, וה-Identity $I$ בכל מקום שהוא $0$. אז יש לנו

$$X_a X_b {|{x}\rangle}{|{y}\rangle} = {|{x+a}\rangle}{|{y+b}\rangle}.$$

הקופסה השחורה השנייה $g$ ממומשת על ידי הU-אוניטרית $U_g$, הניתן על ידי

$$U_g = X_aX_b {CZ}_{x,y} X_aX_b.$$

כדי לראות זאת, אנו מיישמים את האופרטורים מימין לשמאל על המצב ${|{x}\rangle}{|{y}\rangle}$. תחילה

$$X_a X_b {|{x}\rangle}{|{y}\rangle} = {|{x+a}\rangle}{|{y+b}\rangle}.$$

לאחר מכן,

$${CZ}_{x,y} {|{x+a}\rangle}{|{y+b}\rangle} = (-1)^{(x+a)\cdot (y+b)} {|{x+a}\rangle}{|{y+b}\rangle}.$$

לבסוף,

$$X^a X^b (-1)^{(x+a)\cdot (y+b)} {|{x+a}\rangle}{|{y+b}\rangle} = (-1)^{(x+a)\cdot (y+b)} {|{x}\rangle}{|{y}\rangle},$$

שהיא אכן הגרסה הקוונטית של $f(x+a, y+b)$.

אלגוריתם ההזזה הנסתרת

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

$$H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} = \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot y} {|{x}\rangle}{|{y}\rangle}.$$

לאחר מכן, אנו שואלים את האורקל $g$ להגיע אל

$$U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} = \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{(x+a) \cdot (y+b)} {|{x}\rangle}{|{y}\rangle}$$ $$\approx \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot y + x \cdot b + y \cdot a} {|{x}\rangle}{|{y}\rangle}.$$

בשורה האחרונה, השמטנו את גורם הפאזה הגלובלית הקבועה $(-1)^{a \cdot b}$, ומסמנים שוויון עד כדי פאזה ב-$\approx$. לאחר מכן, יישום האורקל $f$ מכניס גורם נוסף של $(-1)^{x \cdot y}$, המבטל את זה שכבר קיים. אז יש לנו:

$$U_f U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} \approx \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot b + y \cdot a} {|{x}\rangle}{|{y}\rangle}.$$

הצעד הסופי הוא יישום תמרת הפורייה ההופכית, $H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m}$, מה שמביא ל-

$$H^{\otimes 2m} U_f U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} \approx {|{b}\rangle}{|{a}\rangle}.$$

המעגל הסתיים. בהיעדר רעש, דגימת הרשומות הקוונטיות תחזיר את מחרוזות הביטים $b, a$ בהסתברות $1$.

המכפלה הפנימית הבוליאנית היא דוגמה של פונקציות הנקראות bent. לא נגדיר פונקציות bent כאן אך רק נציין שהן "עמידות ביותר מול התקפות המנסות לנצל תלות של הפלטים בתת-מרחב לינארי כלשהו של הקלטים." ציטוט זה הוא מהמאמר Quantum algorithms for highly non-linear Boolean functions, שנותן אלגוריתמי הזזה נסתרת יעילים למספר מחלקות של פונקציות bent. האלגוריתם במדריך זה מופיע בסעיף 3.1 של המאמר.

במקרה הכללי יותר, המעגל למציאת הזזה נסתרת $s \in \mathbb{Z}^n$ הוא

$$H^{\otimes n} U_{\tilde{f}} H^{\otimes n} U_g H^{\otimes n} {|{0}\rangle}^{\otimes n} = {|{s}\rangle}.$$

במקרה הכללי, $f$ ו-$g$ הן פונקציות של משתנה יחיד. הדוגמה שלנו של המכפלה הפנימית היא בצורה זו אם נניח $f(x, y) \to f(z)$, כאשר $z$ שווה לשרשור של $x$ ו-$y$, ו-$s$ שווה לשרשור של $a$ ו-$b$. המקרה הכללי דורש בדיוק שני אורקלים: אורקל אחד עבור $g$ ואחד עבור $\tilde{f}$, כאשר האחרון הוא פונקציה הידועה כ_פונקציה הדואלית_ של פונקציית ה-bent $f$. לפונקציית המכפלה הפנימית יש תכונת האוטו-דואליות $\tilde{f}=f$.

במעגל שלנו להזזה הנסתרת על המכפלה הפנימית השמטנו את שכבת ה-Hadamard האמצעית המופיעה במעגל למקרה הכללי. בעוד שבמקרה הכללי שכבה זו הכרחית, חסכנו בעומק המעגל על ידי השמטתה, במחיר של מעט עיבוד לאחר המדידה מאחר שהפלט הוא ${|{b}\rangle}{|{a}\rangle}$ במקום הרצוי ${|{a}\rangle}{|{b}\rangle}$.

דרישות

לפני תחילת מדריך זה, וודא שהתקנת את הדברים הבאים:

• Qiskit SDK גרסה v2.1 ומעלה, עם תמיכת visualization
• Qiskit Runtime גרסה v0.41 ומעלה (pip install qiskit-ibm-runtime)
• M3 Qiskit addon גרסה v3.0 (pip install mthree)

הגדרה

# Added by doQumentation — required packages for this notebook
!pip install -q matplotlib mthree qiskit qiskit-ibm-runtime

from collections.abc import Iterator, Sequence
from random import Random
from qiskit.circuit import (
    CircuitInstruction,
    QuantumCircuit,
    QuantumRegister,
    Qubit,
)
from qiskit.circuit.library import CZGate, HGate, XGate
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import QiskitRuntimeService
import timeit
import matplotlib.pyplot as plt
from qiskit_ibm_runtime import SamplerV2 as Sampler
import mthree

שלב 1: מיפוי קלטים קלאסיים לבעיה קוונטית

ראשית, נכתוב את הפונקציות לממש את בעיית ההזזה הנסתרת כ-QuantumCircuit.

def apply_hadamards(qubits: Sequence[Qubit]) -> Iterator[CircuitInstruction]:
    """Apply a Hadamard gate to every qubit."""
    for q in qubits:
        yield CircuitInstruction(HGate(), [q], [])

def apply_shift(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Apply X gates where the bits of the shift are equal to 1."""
    for i, q in zip(range(shift.bit_length()), qubits):
        if shift >> i & 1:
            yield CircuitInstruction(XGate(), [q], [])

def oracle_f(qubits: Sequence[Qubit]) -> Iterator[CircuitInstruction]:
    """Apply the f oracle."""
    for i in range(0, len(qubits) - 1, 2):
        yield CircuitInstruction(CZGate(), [qubits[i], qubits[i + 1]])

def oracle_g(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Apply the g oracle."""
    yield from apply_shift(qubits, shift)
    yield from oracle_f(qubits)
    yield from apply_shift(qubits, shift)

def determine_hidden_shift(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Determine the hidden shift."""
    yield from apply_hadamards(qubits)
    yield from oracle_g(qubits, shift)
    # We omit this layer in exchange for post processing
    # yield from apply_hadamards(qubits)
    yield from oracle_f(qubits)
    yield from apply_hadamards(qubits)

def run_hidden_shift_circuit(n_qubits, rng):
    hidden_shift = rng.getrandbits(n_qubits)

    qubits = QuantumRegister(n_qubits, name="q")
    circuit = QuantumCircuit.from_instructions(
        determine_hidden_shift(qubits, hidden_shift), qubits=qubits
    )
    circuit.measure_all()
    # Format the hidden shift as a string.
    hidden_shift_string = format(hidden_shift, f"0{n_qubits}b")
    return (circuit, hidden_shift, hidden_shift_string)

def display_circuit(circuit):
    return circuit.remove_final_measurements(inplace=False).draw(
        "mpl", idle_wires=False, scale=0.5, fold=-1
    )

נתחיל עם דוגמה קטנה:

n_qubits = 6
random_seed = 12345
rng = Random(random_seed)
circuit, hidden_shift, hidden_shift_string = run_hidden_shift_circuit(
    n_qubits, rng
)

print(f"Hidden shift string {hidden_shift_string}")

display_circuit(circuit)

Hidden shift string 011010

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

job_tags = [
    f"shift {hidden_shift_string}",
    f"n_qubits {n_qubits}",
    f"seed = {random_seed}",
]
job_tags

['shift 011010', 'n_qubits 6', 'seed = 12345']

# Uncomment this to run the circuits on a quantum computer on IBMCloud.
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=100
)

# from qiskit_ibm_runtime.fake_provider import FakeMelbourneV2
# backend = FakeMelbourneV2()
# backend.refresh(service)

print(f"Using backend {backend.name}")

def get_isa_circuit(circuit, backend):
    pass_manager = generate_preset_pass_manager(
        optimization_level=3, backend=backend, seed_transpiler=1234
    )
    isa_circuit = pass_manager.run(circuit)
    return isa_circuit

isa_circuit = get_isa_circuit(circuit, backend)
display_circuit(isa_circuit)

Using backend ibm_kingston

שלב 3: הרצת מעגלים באמצעות פרימיטיבים של Qiskit

# submit job for solving the hidden shift problem using the Sampler primitive
NUM_SHOTS = 50_000

def run_sampler(backend, isa_circuit, num_shots):
    sampler = Sampler(mode=backend)
    sampler.options.environment.job_tags
    pubs = [(isa_circuit, None, NUM_SHOTS)]
    job = sampler.run(pubs)
    return job

def setup_mthree_mitigation(isa_circuit, backend):
    # retrieve the final qubit mapping so mthree knows which qubits to calibrate
    qubit_mapping = mthree.utils.final_measurement_mapping(isa_circuit)

    # submit jobs for readout error calibration
    mit = mthree.M3Mitigation(backend)
    mit.cals_from_system(qubit_mapping, rep_delay=None)

    return mit, qubit_mapping

job = run_sampler(backend, isa_circuit, NUM_SHOTS)
mit, qubit_mapping = setup_mthree_mitigation(isa_circuit, backend)

שלב 4: עיבוד לאחר ביצוע והחזרת תוצאות בפורמט קלאסי

בדיון התיאורטי לעיל, קבענו שעבור קלט $ab$, אנו מצפים לקבל פלט $ba$. סיבוך נוסף הוא שכדי לקבל מעגל פשוט יותר (לפני transpilation), הוספנו שערי CZ נדרשים בין זוגות שכנים של Qubits. פעולה זו שקולה לסירוג (interleaving) מחרוזות הביטים $a$ ו-$b$ כך: $a1 b1 a2 b2 \ldots$. מחרוזת הפלט $ba$ תהיה מסורגת באופן דומה: $b1 a1 b2 a2 \ldots$. הפונקציה unscramble שלהלן ממירה את מחרוזת הפלט מ-$b1 a1 b2 a2 \ldots$ ל-$a1 b1 a2 b2 \ldots$, כך שניתן להשוות ישירות בין מחרוזות הקלט והפלט.

# retrieve bitstring counts
def get_bitstring_counts(job):
    result = job.result()
    pub_result = result[0]
    counts = pub_result.data.meas.get_counts()
    return counts, pub_result

counts, pub_result = get_bitstring_counts(job)

מרחק ה-Hamming בין שתי מחרוזות ביטים הוא מספר המיקומים שבהם הביטים שונים זה מזה.

def hamming_distance(s1, s2):
    weight = 0
    for c1, c2 in zip(s1, s2):
        (c1, c2) = (int(c1), int(c2))
        if (c1 == 1 and c2 == 1) or (c1 == 0 and c2 == 0):
            weight += 1

    return weight

# Replace string of form a1b1a2b2... with b1a1b2a1...
# That is, reverse order of successive pairs of bits.
def unscramble(bitstring):
    ps = [bitstring[i : i + 2][::-1] for i in range(0, len(bitstring), 2)]
    return "".join(ps)

def find_hidden_shift_bitstring(counts, hidden_shift_string):
    # convert counts to probabilities
    probs = {
        unscramble(bitstring): count / NUM_SHOTS
        for bitstring, count in counts.items()
    }

    # Retrieve the most probable bitstring.
    most_probable = max(probs, key=lambda x: probs[x])

    print(f"Expected hidden shift string: {hidden_shift_string}")
    if most_probable == hidden_shift_string:
        print("Most probable bitstring matches hidden shift 😊.")
    else:
        print("Most probable bitstring didn't match hidden shift ☹️.")
    print("Top 10 bitstrings and their probabilities:")
    display(
        {
            k: (v, hamming_distance(hidden_shift_string, k))
            for k, v in sorted(
                probs.items(), key=lambda x: x[1], reverse=True
            )[:10]
        }
    )

    return probs, most_probable

probs, most_probable = find_hidden_shift_bitstring(
    counts, hidden_shift_string
)

Expected hidden shift string: 011010
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their probabilities:

{'011010': (0.9743, 6),
 '001010': (0.00812, 5),
 '010010': (0.0063, 5),
 '011000': (0.00554, 5),
 '011011': (0.00492, 5),
 '011110': (0.00044, 5),
 '001000': (0.00012, 4),
 '010000': (8e-05, 4),
 '001011': (6e-05, 4),
 '000010': (6e-05, 4)}

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

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.9743

כעת נחיל את תיקון הקריאה שנלמד על ידי M3 על הספירות. הפונקציה apply_corrections מחזירה התפלגות מעין-הסתברותית (quasi-probability distribution). זוהי רשימה של אובייקטי float שסכומם הוא $1$, אך חלק מהערכים עשויים להיות שליליים.

def perform_mitigation(mit, counts, qubit_mapping):
    # mitigate readout error
    quasis = mit.apply_correction(counts, qubit_mapping)

    # print results
    most_probable_after_m3 = unscramble(max(quasis, key=lambda x: quasis[x]))

    is_hidden_shift_identified = most_probable_after_m3 == hidden_shift_string
    if is_hidden_shift_identified:
        print("Most probable bitstring matches hidden shift 😊.")
    else:
        print("Most probable bitstring didn't match hidden shift ☹️.")
    print("Top 10 bitstrings and their quasi-probabilities:")
    topten = {
        unscramble(k): f"{v:.2e}"
        for k, v in sorted(quasis.items(), key=lambda x: x[1], reverse=True)[
            :10
        ]
    }
    max_probability_after_M3 = float(topten[most_probable_after_m3])
    display(topten)

    return max_probability_after_M3, is_hidden_shift_identified

print(f"Expected hidden shift string: {hidden_shift_string}")
max_probability_after_M3, is_hidden_shift_identified = perform_mitigation(
    mit, counts, qubit_mapping
)

Expected hidden shift string: 011010
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their quasi-probabilities:

{'011010': '1.01e+00',
 '001010': '8.75e-04',
 '001000': '7.38e-05',
 '010000': '4.51e-05',
 '111000': '2.18e-05',
 '001011': '1.74e-05',
 '000010': '6.42e-06',
 '011001': '-7.18e-06',
 '011000': '-4.53e-04',
 '010010': '-1.28e-03'}

השוואה בין זיהוי מחרוזת ה-hidden shift לפני ואחרי תיקון M3

def compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
):
    is_probability_improved = (
        max_probability_after_M3 > max_probability_before_M3
    )
    print(f"Most probable probability before M3: {max_probability_before_M3}")
    print(f"Most probable probability after M3: {max_probability_after_M3}")
    if is_hidden_shift_identified and is_probability_improved:
        print("Readout error mitigation effective! 😊")
    else:
        print("Readout error mitigation not effective. ☹️")

compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
)

Most probable probability before M3: 0.9743
Most probable probability after M3: 1.01
Readout error mitigation effective! 😊

כיצד זמן ה-CPU הנדרש על ידי M3 משתנה עם מספר הירויות

# Collect samples for numbers of shots varying from 5000 to 25000.
shots_range = range(5000, NUM_SHOTS + 1, 2500)
times = []
for shots in shots_range:
    print(f"Applying M3 correction to {shots} shots...")
    t0 = timeit.default_timer()
    _ = mit.apply_correction(
        pub_result.data.meas.slice_shots(range(shots)).get_counts(),
        qubit_mapping,
    )
    t1 = timeit.default_timer()
    print(f"\tDone in {t1 - t0} seconds.")
    times.append(t1 - t0)

fig, ax = plt.subplots()
ax.plot(shots_range, times, "o--")
ax.set_xlabel("Shots")
ax.set_ylabel("Time (s)")
ax.set_title("Time to apply M3 correction")

Applying M3 correction to 5000 shots...
	Done in 0.003321983851492405 seconds.
Applying M3 correction to 7500 shots...
	Done in 0.004425413906574249 seconds.
Applying M3 correction to 10000 shots...
	Done in 0.006366567220538855 seconds.
Applying M3 correction to 12500 shots...
	Done in 0.0071477219462394714 seconds.
Applying M3 correction to 15000 shots...
	Done in 0.00860048783943057 seconds.
Applying M3 correction to 17500 shots...
	Done in 0.010026784148067236 seconds.
Applying M3 correction to 20000 shots...
	Done in 0.011459112167358398 seconds.
Applying M3 correction to 22500 shots...
	Done in 0.012727141845971346 seconds.
Applying M3 correction to 25000 shots...
	Done in 0.01406092382967472 seconds.
Applying M3 correction to 27500 shots...
	Done in 0.01546052098274231 seconds.
Applying M3 correction to 30000 shots...
	Done in 0.016769016161561012 seconds.
Applying M3 correction to 32500 shots...
	Done in 0.019537431187927723 seconds.
Applying M3 correction to 35000 shots...
	Done in 0.019739801064133644 seconds.
Applying M3 correction to 37500 shots...
	Done in 0.021093040239065886 seconds.
Applying M3 correction to 40000 shots...
	Done in 0.022840639110654593 seconds.
Applying M3 correction to 42500 shots...
	Done in 0.023974396288394928 seconds.
Applying M3 correction to 45000 shots...
	Done in 0.026412792038172483 seconds.
Applying M3 correction to 47500 shots...
	Done in 0.026364430785179138 seconds.
Applying M3 correction to 50000 shots...
	Done in 0.02820305060595274 seconds.

Text(0.5, 1.0, 'Time to apply M3 correction')

פרשנות הגרף

הגרף לעיל מראה שהזמן הנדרש להחלת תיקון M3 גדל באופן ליניארי עם מספר הירויות.

הרחבת הגודל

n_qubits = 80
rng = Random(12345)
circuit, hidden_shift, hidden_shift_string = run_hidden_shift_circuit(
    n_qubits, rng
)

print(f"Hidden shift string {hidden_shift_string}")

Hidden shift string 00000010100110101011101110010001010000110011101001101010101001111001100110000111

isa_circuit = get_isa_circuit(circuit, backend)

job = run_sampler(backend, isa_circuit, NUM_SHOTS)
mit, qubit_mapping = setup_mthree_mitigation(isa_circuit, backend)

counts, pub_result = get_bitstring_counts(job)

probs, most_probable = find_hidden_shift_bitstring(
    counts, hidden_shift_string
)

Expected hidden shift string: 00000010100110101011101110010001010000110011101001101010101001111001100110000111
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their probabilities:

{'00000010100110101011101110010001010000110011101001101010101001111001100110000111': (0.50402,
  80),
 '00000010100110101011101110010001010000110011100001101010101001111001100110000111': (0.0396,
  79),
 '00000010100110101011101110010001010000110011101001101010101001111001100100000111': (0.0323,
  79),
 '00000010100110101011101110010001010000110011101001101010101001101001100110000111': (0.01936,
  79),
 '00000010100110101011101110010011010000110011101001101010101001111001100110000111': (0.01432,
  79),
 '00000010100110101011101110010001010000110011101001101010101001011001100110000111': (0.0101,
  79),
 '00000010100110101011101110010001010000110011101001101010101001110001100110000111': (0.00924,
  79),
 '00000010100110101011101110010001010000010011101001101010101001111001100110000111': (0.00908,
  79),
 '00000010100110101011100110010001010000110011101001101010101001111001100110000111': (0.00888,
  79),
 '00000010100110101011101110010001010000110011101001100010101001111001100110000111': (0.0082,
  79)}

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

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.50402

print(f"Expected hidden shift string: {hidden_shift_string}")
max_probability_after_M3, is_hidden_shift_identified = perform_mitigation(
    mit, counts, qubit_mapping
)

Expected hidden shift string: 00000010100110101011101110010001010000110011101001101010101001111001100110000111
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their quasi-probabilities:

{'00000010100110101011101110010001010000110011101001101010101001111001100110000111': '9.85e-01',
 '00000010100110101011101110010001010000110011100001101010101001111001100110000111': '6.84e-03',
 '00000010100110101011100110010001010000110011101001101010101001111001100110000111': '3.87e-03',
 '00000010100110101011101110010011010000110011101001101010101001111001100110000111': '3.42e-03',
 '00000010100110101011101110010001010000110011101001101010101001111001100100000111': '3.30e-03',
 '00000010100110101011101110010001010000110011101001101010101001110001100110000111': '3.28e-03',
 '00000010100010101011101110010001010000110011101001101010101001111001100110000111': '2.62e-03',
 '00000010100110101011101110010001010000110011101001101010101001101001100110000111': '2.43e-03',
 '00000010100110101011101110010000010000110011101001101010101001111001100110000111': '1.73e-03',
 '00000010100110101011101110010001010000110011101001101010101001111001000110000111': '1.63e-03'}

compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
)

Most probable probability before M3: 0.54348
Most probable probability after M3: 0.99
Readout error mitigation effective! 😊