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

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

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

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

בעיית דויטש-ג'וזה

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

פונקציית הקלט לבעיה זו היא מהצורה $f:\Sigma^n \rightarrow \Sigma$ עבור מספר שלם חיובי שרירותי $n.$ כמו בבעיית דויטש, המשימה היא להוציא $0$ אם $f$ היא קבועה ו-$1$ אם $f$ היא מאוזנת, כלומר מספר מחרוזות הקלט שעליהן הפונקציה מקבלת ערך $0$ שווה למספר מחרוזות הקלט שעליהן הפונקציה מקבלת ערך $1$.

שימו לב שכאשר $n$ גדול מ-$1$, יש פונקציות מהצורה $f:\Sigma^n \rightarrow \Sigma$ שאינן קבועות ואינן מאוזנות. לדוגמה, הפונקציה $f:\Sigma^2\rightarrow\Sigma$ המוגדרת כך:

$$\begin{aligned} f(00) & = 0 \\ f(01) & = 0 \\ f(10) & = 0 \\ f(11) & = 1 \end{aligned}$$

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

בעיית דויטש-ג'וזה

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

אלגוריתם דויטש-ג'וזה, עם שאילתתו היחידה, פותר בעיה זו במובן הבא: אם כל אחד מ-$n$ תוצאות המדידה הוא $0$, אז הפונקציה $f$ קבועה; ואחרת, אם לפחות אחת מתוצאות המדידה היא $1$, אז הפונקציה $f$ מאוזנת. דרך נוספת לומר זאת היא שה-Circuit המתואר לעיל מלווה בשלב עיבוד קלאסי שבו מחושב ה-OR של תוצאות המדידה כדי לייצר את הפלט.

ניתוח האלגוריתם

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

$$H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix},$$

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

$$\begin{aligned} H \vert 0\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle\\[3mm] H \vert 1\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 \rangle. \end{aligned}$$

שתי המשוואות הללו ניתנות לשילוב לנוסחה יחידה,

$$H \vert a \rangle = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} (-1)^a \vert 1 \rangle = \frac{1}{\sqrt{2}} \sum_{b\in\{0,1\}} (-1)^{ab} \vert b\rangle,$$

הנכונה לשני הבחירות של $a\in\Sigma.$

עכשיו נניח שבמקום Qubit יחיד יש לנו $n$ Qubit-ים, ופעולת הדאמר מתבצעת על כל אחד מהם. הפעולה המשולבת על $n$ ה-Qubit-ים מתוארת על ידי המכפלה הטנזורית $H\otimes \cdots \otimes H$ ($n$ פעמים), אותה נכתוב כ-$H^{\otimes n}$ לשם תמציתיות ובהירות. באמצעות הנוסחה שלעיל, ולאחר הרחבה ופישוט, ניתן לבטא את פעולת הפעולה המשולבת הזו על מצבי הבסיס הסטנדרטיים של $n$ Qubit-ים כך:

$$\begin{aligned} & H^{\otimes n} \vert x_{n-1} \cdots x_1 x_0 \rangle \\ & \qquad = \bigl(H \vert x_{n-1} \rangle \bigr) \otimes \cdots \otimes \bigl(H \vert x_{0} \rangle \bigr) \\ & \qquad = \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{n-1}\in\Sigma} (-1)^{x_{n-1} y_{n-1}} \vert y_{n-1} \rangle \Biggr) \otimes \cdots \otimes \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{0}\in\Sigma} (-1)^{x_{0} y_{0}} \vert y_{0} \rangle \Biggr) \\ & \qquad = \frac{1}{\sqrt{2^n}} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle. \end{aligned}$$

אגב, כאן אנו כותבים מחרוזות בינאריות באורך $n$ כ-$x_{n-1}\cdots x_0$ ו-$y_{n-1}\cdots y_0$, בהתאם למוסכמת האינדקסים של Qiskit.

נוסחה זו מספקת לנו כלי שימושי לניתוח ה-Circuit הקוונטי שלעיל. לאחר ביצוע שכבת Gate-י הדאמר הראשונה, מצב $n+1$ ה-Qubit-ים (כולל ה-Qubit השמאלי/התחתון ביותר, המטופל בנפרד מהשאר) הוא:

$$\bigl( H \vert 1 \rangle \bigr) \bigl( H^{\otimes n} \vert 0 \cdots 0 \rangle \bigr) = \vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \vert x_{n-1} \cdots x_0 \rangle.$$

כאשר מתבצעת פעולת $U_f$, מצב זה מתמר ל-

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \vert x_{n-1} \cdots x_0 \rangle$$

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

לאחר מכן מתבצעת שכבת Gate-י הדאמר השנייה, שמתמרת (לפי הנוסחה שלעיל) מצב זה ל-

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0) + x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle.$$

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

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

$$\Biggl\vert \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \Biggr\vert^2 = \begin{cases} 1 & \text{if $f$ is constant}\\[1mm] 0 & \text{if $f$ is balanced} \end{cases}$$

ביתר פירוט, אם $f$ קבועה, אז או ש-$f(x_{n-1}\cdots x_0) = 0$ לכל מחרוזת $x_{n-1}\cdots x_0,$ ואז ערך הסכום הוא $2^n,$ או ש-$f(x_{n-1}\cdots x_0) = 1$ לכל מחרוזת $x_{n-1}\cdots x_0,$ ואז ערך הסכום הוא $-2^n.$ חלוקה ב-$2^n$ ולקיחת ריבוע הערך המוחלט נותנת $1.$

מצד שני, אם $f$ מאוזנת, אז $f$ מקבלת ערך $0$ על חצי מהמחרוזות $x_{n-1}\cdots x_0$ וערך $1$ על החצי השני, כך שאיברי $+1$ ו-$-1$ בסכום מתבטלים ואנחנו נשארים עם הערך $0$.

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

קושי קלאסי

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

ראשית, כל אלגוריתם קלאסי דטרמיניסטי שפותר נכונה את בעיית דויטש-ג'וזה חייב לבצע מספר אקספוננציאלי של שאילתות: $2^{n-1} + 1$ שאילתות נדרשות במקרה הגרוע ביותר. הנימוק הוא שאם אלגוריתם דטרמיניסטי שואל את $f$ על $2^{n-1}$ מחרוזות שונות או פחות, ומקבל כל פעם אותו ערך פונקציה, אז שתי התשובות עדיין אפשריות. הפונקציה עשויה להיות קבועה, או שהיא מאוזנת אך מחוסר מזל כל השאילתות מחזירות את אותו ערך פונקציה.

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

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

ליתר דיוק, אם נבחר $k$ מחרוזות קלט $x^1,\ldots,x^k \in \Sigma^n$ באחידות אקראית, נחשב $f(x^1),\ldots,f(x^k),$ ונענה $0$ אם ערכי הפונקציה זהים כולם, ו-$1$ אם לא, אז תמיד נצדק כשהפונקציה קבועה, ונטעה כשהפונקציה מאוזנת בהסתברות של $2^{-k + 1}$ בלבד. אם ניקח $k = 11$ לדוגמה, האלגוריתם הזה יענה נכון בהסתברות גדולה מ-$99.9$%.

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

דויטש-ג'וזה עם Qiskit

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

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

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

def dj_query(num_qubits):
    # Create a circuit implementing for a query gate for a random function
    # satisfying the promise for the Deutsch-Jozsa problem.

    qc = QuantumCircuit(num_qubits + 1)

    if np.random.randint(0, 2):
        # Flip output qubit with 50% chance
        qc.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance
        return qc

    # Choose half the possible input strings
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc.x(qubit)
        return qc

    for state in on_states:
        qc.barrier()  # Barriers are added to help visualize how the functions are created.
        qc = add_cx(qc, f"{state:0b}")
        qc.mcx(list(range(num_qubits)), num_qubits)
        qc = add_cx(qc, f"{state:0b}")

    qc.barrier()

    return qc

ניתן להציג את מימוש ה-Circuit הקוונטי של Gate השאילתה באמצעות מתודת draw כרגיל.

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

בשלב הבא נגדיר פונקציה שיוצרת את Circuit דויטש-ג'וזה, ומקבלת כארגומנט מימוש Circuit קוונטי של Gate שאילתה.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in the Deutsch-Jozsa algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)
    qc.h(range(n + 1))
    qc.compose(function, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

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

def dj_algorithm(function: QuantumCircuit):
    # Determine if a function is constant or balanced.

    qc = compile_circuit(function)

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

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

f = dj_query(3)
display(f.draw("mpl"))
display(dj_algorithm(f))

'balanced'

בעיית ברנשטיין-וזירני

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

ראשית, נציג סימון כלשהו. עבור כל שתי מחרוזות בינאריות $x = x_{n-1} \cdots x_0$ ו-$y = y_{n-1}\cdots y_0$ באורך $n,$ נגדיר

$$x \cdot y = x_{n-1} y_{n-1} \oplus \cdots \oplus x_0 y_0.$$

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

$$x \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is odd}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is even} \end{cases}$$

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

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

בעיית ברנשטיין-וזירני

קלט: פונקציה $f:\{0,1\}^n\rightarrow\{0,1\}$
הבטחה: קיימת מחרוזת בינארית $s = s_{n-1} \cdots s_0$ כך ש-$f(x) = s\cdot x$ לכל $x\in\Sigma^n$
פלט: המחרוזת $s$

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

ניתוח האלגוריתם

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

$$H^{\otimes n} \vert x \rangle = \frac{1}{\sqrt{2^n}} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert y\rangle$$

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

כשנפנה למעגל דויטש-ג'וזסה, לאחר ביצוע שכבת שערי הדאמרד הראשונה, מצב ה-$n+1$ Qubit-ים הוא

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} \vert x \rangle.$$

לאחר מכן מתבצע שער השאילתה, אשר (דרך תופעת ה-phase kickback) הופך את המצב ל-

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} (-1)^{f(x)} \vert x \rangle.$$

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

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{f(x) + x \cdot y} \vert y \rangle.$$

עכשיו נוכל לבצע כמה פישוטים בחזקה של $-1$ בתוך הסכום. מובטח לנו ש-$f(x) = s\cdot x$ עבור מחרוזת כלשהי $s = s_{n-1} \cdots s_0,$ ולכן נוכל לכתוב את המצב כ-

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{s\cdot x + x \cdot y} \vert y \rangle.$$

מכיוון ש-$s\cdot x$ ו-$x\cdot y$ הם ערכים בינאריים, נוכל להחליף את החיבור ב-XOR — שוב מפני שהדבר היחיד שחשוב עבור מספר שלם בחזקה של $-1$ הוא אם הוא זוגי או אי-זוגי. תוך שימוש בסימטריה של המכפלה הנקודתית הבינארית, נקבל את הביטוי הבא למצב:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\cdot x) \oplus (y \cdot x)} \vert y \rangle.$$

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

בשלב זה נעשה שימוש בנוסחה הבאה:

$$(s\cdot x) \oplus (y \cdot x) = (s \oplus y) \cdot x$$

נוכל לגזור נוסחה זו מנוסחה דומה עבור ביטים,

$$(a c) \oplus (b c) = (a \oplus b) c,$$

יחד עם פיתוח המכפלה הנקודתית הבינארית וה-XOR הביטי:

$$\begin{aligned} (s\cdot x) \oplus (y \cdot x) & = (s_{n-1} x_{n-1}) \oplus \cdots \oplus (s_{0} x_{0}) \oplus (y_{n-1} x_{n-1}) \oplus \cdots \oplus (y_{0} x_{0}) \\ & = (s_{n-1} \oplus y_{n-1}) x_{n-1} \oplus \cdots \oplus (s_{0} \oplus y_{0}) x_{0} \\ & = (s \oplus y) \cdot x \end{aligned}$$

זה מאפשר לנו לכתוב את מצב המעגל מיד לפני המדידות כך:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle.$$

השלב האחרון הוא להשתמש בנוסחה נוספת, המתקיימת לכל מחרוזת בינארית $z = z_{n-1}\cdots z_0.$

$$\frac{1}{2^n} \sum_{x \in \Sigma^n} (-1)^{z \cdot x} = \begin{cases} 1 & \text{if $z = 0^n$}\\ 0 & \text{if $z\neq 0^n$} \end{cases}$$

כאן אנו משתמשים בסימון פשוט למחרוזות שנשתמש בו עוד מספר פעמים בשיעור: $0^n$ היא המחרוזת כולה-אפסים באורך $n.$

דרך פשוטה להוכיח שנוסחה זו עובדת היא לבחון את שני המקרים בנפרד. אם $z = 0^n,$ אז $z\cdot x = 0$ לכל מחרוזת $x\in\Sigma^n,$ כך שערך כל איבר בסכום הוא $1,$ ונקבל $1$ לאחר הסכימה וחלוקה ב-$2^n.$ מאידך, אם אחד מן הביטים של $z$ שווה $1,$ אז המכפלה הנקודתית הבינארית $z\cdot x$ שווה $0$ עבור בדיוק מחצית מהבחירות האפשריות של $x\in\Sigma^n$ ו-$1$ עבור המחצית השנייה — מפני שערך המכפלה הנקודתית $z\cdot x$ מתהפך (מ-$0$ ל-$1$ או מ-$1$ ל-$0$) אם נהפוך כל ביט של $x$ במיקום שבו $z$ שווה $1.$

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

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle = \vert - \rangle \otimes \vert s \rangle,$$

בשל העובדה ש-$s\oplus y = 0^n$ אם ורק אם $y = s.$ לפיכך, המדידות חושפות בדיוק את המחרוזת $s$ שאנו מחפשים.

קושי קלאסי

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

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

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

ברנשטיין-וזירני עם Qiskit

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

def bv_query(s):
    # Create a quantum circuit implementing a query gate for the
    # Bernstein-Vazirani problem.

    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_query("1011").draw(output="mpl"))

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

def bv_algorithm(function: QuantumCircuit):
    qc = compile_circuit(function)
    result = AerSimulator().run(qc, shots=1, memory=True).result()
    return result.get_memory()[0]

display(bv_algorithm(bv_query("1011")))

'1011'

הערה על מינוח

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

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

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

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

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