האלגוריתם של דויטש

האלגוריתם של דויטש פותר את בעיית הזוגיות עבור המקרה המיוחד שבו $n = 1.$ בהקשר של חישוב קוונטי, בעיה זו מכונה לעיתים בעיית דויטש, ונאמץ מינוח זה לאורך השיעור.

ליתר דיוק, הקלט מיוצג על-ידי פונקציה $f:\Sigma \rightarrow \Sigma$ מביט אחד לביט אחד. ישנן ארבע פונקציות כאלה:

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

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

בעיית דויטש

קלט: פונקציה $f:\{0,1\}\rightarrow\{0,1\}$
פלט: $0$ אם $f$ קבועה, $1$ אם $f$ מאוזנת

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

$$\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

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

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

תיאור מעגל קוונטי

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

הנה מעגל קוונטי המתאר את האלגוריתם של דויטש:

ניתוח

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

המצב ההתחלתי הוא $\vert 1\rangle \vert 0 \rangle,$ ושתי פעולות ה-Hadamard בצד שמאל של המעגל ממירות מצב זה ל

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

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

לאחר מכן מתבצעת פעולת השער $U_f$. לפי הגדרת השער $U_f$, ערך הפונקציה $f$ עבור המצב הקלסי של ה-Qubit העליון/הימני ביותר מבוצע עליו XOR על ה-Qubit התחתון/השמאלי ביותר, מה שממיר את $\vert \pi_1\rangle$ למצב

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

אפשר לפשט את הביטוי הזה על-ידי הבחנה שהנוסחה

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

עובדת עבור שני הערכים האפשריים $a\in\Sigma.$ בצורה מפורשת יותר, שני המקרים הם כדלקמן.

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

כך, אפשר לבטא את $\vert\pi_2\rangle$ באופן חלופי כך:

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

קרה כאן משהו מעניין! למרות שפעולת השער $U_f$ על מצבי בסיס סטנדרטיים משאירה את ה-Qubit העליון/הימני כפי שהוא ומבצעת XOR של ערך הפונקציה על ה-Qubit התחתון/השמאלי, כאן אנו רואים שמצב ה-Qubit העליון/הימני השתנה (בדרך כלל) בעוד שמצב ה-Qubit התחתון/השמאלי נותר זהה — הוא נמצא במצב $\vert - \rangle$ לפני ואחרי פעולת השער $U_f$. תופעה זו ידועה בשם בעיטת הפאזה, ועוד נרחיב עליה בקרוב.

עם פישוט סופי אחד — הוצאת הגורם $(-1)^{f(0)}$ מחוץ לסכום — מקבלים את הביטוי הבא למצב $\vert\pi_2\rangle$:

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{if $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

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

הפעלת שער Hadamard הסופי על ה-Qubit העליון מותירה אותנו עם המצב

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{if $f(0) \oplus f(1) = 1$}, \end{cases}$$

מה שמוביל לתוצאה הנכונה בהסתברות $1$ כשה-Qubit הימני/העליון נמדד.

הערות נוספות על בעיטת הפאזה

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

ראשית, שימו לב שהנוסחה הבאה עובדת לכל ביטים $b,c\in\Sigma.$

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

ניתן לאמת זאת בבדיקה עבור שני הערכים האפשריים $c = 0$ ו-$c = 1$:

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

בעזרת נוסחה זו, אנחנו רואים ש

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

לכל בחירה של ביטים $a,b\in\Sigma.$ מכיוון שנוסחה זו נכונה עבור $b=0$ ו-$b=1$, אנחנו רואים בעזרת לינאריות ש

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

לכל וקטורי מצב Qubit $\vert \psi\rangle,$ ולכן

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

המפתח שהופך את זה לעבוד הוא ש-$X\vert - \rangle = - \vert - \rangle.$ במונחים מתמטיים, הוקטור $\vert - \rangle$ הוא וקטור עצמי של המטריצה $X$ בעל ערך עצמי $-1.$

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

תוך כדי זכירה שסקלרים עפים חופשי דרך מכפלות טנסוריות, מוצאים דרך חלופית להסביר כיצד הפעולה $U_f$ ממירה את $\vert \pi_1\rangle$ ל-$\vert \pi_2\rangle$ בניתוח לעיל:

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

מימוש ב-Qiskit

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

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

תחילה נגדיר מעגל קוונטי שמממש שער שאילתה לאחת מארבע הפונקציות $f_1,$ $f_2,$ $f_3,$ או $f_4$ מביט אחד לביט אחד שתוארו קודם. כפי שכבר ציינו, מימוש שערי שאילתות אינו חלק מהאלגוריתם של דויטש עצמו; כאן אנחנו בעצם רק מראים דרך אחת להכין את הקלט, בצורת מימוש מעגלי של שער שאילתה.

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

אפשר לראות איך כל מעגל נראה בעזרת מתודת draw. הנה המעגל עבור הפונקציה $f_3.$

display(deutsch_function(3).draw(output="mpl"))

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

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

שוב, אפשר לראות איך המעגל נראה בעזרת מתודת draw.

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

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

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

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

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'