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

למודול Qiskit in Classrooms הזה, הסטודנטים צריכים סביבת Python פעילה עם החבילות הבאות מותקנות:

• qiskit v2.1.0 או חדש יותר
• qiskit-ibm-runtime v0.40.1 או חדש יותר
• qiskit-aer v0.17.0 או חדש יותר
• qiskit.visualization
• numpy
• pylatexenc

להגדרה והתקנת החבילות למעלה, ראה את מדריך התקנת Qiskit. כדי להריץ משימות על מחשבים קוונטיים אמיתיים, הסטודנטים יצטרכו להגדיר חשבון ב-IBM Quantum® על ידי ביצוע השלבים במדריך הגדרת חשבון IBM Cloud שלך.

מודול זה נבדק והשתמש בארבע שניות של זמן QPU. זו הערכה בלבד. השימוש בפועל שלך עשוי להשתנות.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"numpy": "numpy", "qiskit": "qiskit", "qiskit_aer": "qiskit-aer", "qiskit_ibm_runtime": "qiskit-ibm-runtime"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

צפה בסקירת המודול של ד"ר קייטי מקורמיק למטה, או לחץ כאן כדי לצפות ב-YouTube.

---

מבוא

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

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

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

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

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

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

פרלליזם קוונטי ומגבלותיו

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

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

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

נרצה לגלות איזו מהפונקציות האלה (1-4) היא $f(x)$ שלנו. קלאסית, נצטרך להריץ את הפונקציה פעמיים — פעם עבור $x=0$, פעם עבור $x=1$. אבל נראה אם נוכל לעשות טוב יותר עם Circuit קוונטי. נוכל ללמוד על הפונקציה עם ה-Gate הבא:

כאן, ה-Gate $U_f$ מחשב את $f(x)$, כאשר $x$ הוא המצב של qubit 0, ומחיל זאת על qubit 1. אז, המצב המתקבל, $|x\rangle|y\oplus f(x)\rangle$, פשוט הופך ל-$|x\rangle|f(x)\rangle$ כאשר $|y\rangle = |0\rangle$. זה מכיל את כל המידע שאנחנו צריכים כדי לדעת את הפונקציה $f(x)$: Qubit 0 אומר לנו מה $x$ הוא, ו-Qubit 1 אומר לנו מה $f(x)$ הוא. אז, אם נאתחל $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, אז המצב הסופי של שני ה-Qubits יהיה: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. אבל איך נגשים למידע הזה?

2.1. נסה את זה ב-Qiskit:

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

בניסוי הראשון הזה ולאורך המודול, נשתמש במסגרת למחשוב קוונטי הידועה בשם "Qiskit patterns", שמחלקת תהליכי עבודה לשלבים הבאים:

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

• שלב 2: אופטימיזציה של הבעיה לביצוע קוונטי

• שלב 3: הרצה באמצעות פרימיטיבים של IBM Quantum

• שלב 4: עיבוד לאחר ביצוע וניתוח קלאסי

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

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

# Load IBM Quantum Compute Service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

# Syntax for first saving your token.  Delete these lines after saving your credentials.

# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',
# instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

# Use the least busy backend, or uncomment the loading of a specific backend like "ibm_brisbane".
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_brisbane")
print(backend.name)

sampler = Sampler(mode=backend)

ibm_brisbane

התא למטה יאפשר לך לעבור בין שימוש בסימולטור או חומרה אמיתית לאורך המחברת. מומלץ להריץ אותו עכשיו:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

# Alternatively, load a fake backend with generic properties and define a simulator.

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# You could also define a simulator-based sampler using a generic backend:
# backend_gen = GenericBackendV2(num_qubits=18)
# sampler_gen = BackendSamplerV2(backend=backend_gen)

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

# Step 1: Map

from qiskit import QuantumCircuit

qc = QuantumCircuit(2)

def twobit_function(case: int):
    """
    Generate a valid two-bit function as a `QuantumCircuit`.
    """
    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

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the
# circuit is too large to display

# you may edit the number inside "twobit_function()" to select among the four valid functions:
# blackbox = twobit_function(2).to_gate()

# blackbox.label = "$U_f$"

qc.h(0)
qc.barrier()
qc.compose(twobit_function(2), inplace=True)
qc.measure_all()

qc.draw("mpl")

ב-Circuit למעלה, ה-Gate של הדמארד "H" לוקח את qubit 0, שנמצא בתחילה במצב $|0\rangle$, למצב הסופרפוזיציה $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. לאחר מכן, $U_f$ מעריך את הפונקציה $f(x)$ ומחיל זאת על qubit 1.

לאחר מכן אנחנו צריכים לייעל ולבצע Transpile ל-Circuit כדי להריץ אותו על המחשב הקוונטי:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

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

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.meas.get_counts()

# Step 4: Visualize and analyze results

## Analysis
from qiskit.visualization import plot_histogram

plot_histogram(counts)

למעלה היסטוגרמה של התוצאות שלנו. בהתאם למספר ההרצות (shots) שבחרת להריץ את ה-Circuit בשלב 3 למעלה, תוכל לראות עמודה אחת או שתיים, המייצגות את המצבים הנמדדים של שני ה-Qubits בכל shot. כמו תמיד ב-Qiskit ובמחברת זו, אנחנו משתמשים בסימון "little endian", כלומר מצבי qubits 0 עד n נכתבים בסדר עולה מימין לשמאל, כך ש-Qubit 0 הוא תמיד הכי ימני.

אז, מכיוון ש-Qubit 0 היה במצב סופרפוזיציה, ה-Circuit העריך את הפונקציה עבור שניהם $x=0$ ו-$x=1$ בו זמנית — משהו שמחשבים קלאסיים לא יכולים לעשות! אבל הבעיה מגיעה כאשר אנחנו רוצים ללמוד על הפונקציה $f(x)$ — כאשר אנחנו מודדים את ה-Qubits, אנחנו מקריסים את מצבם. אם תבחר "shots = 1" כדי להריץ את ה-Circuit רק פעם אחת, תראה רק עמודה אחת בהיסטוגרמה למעלה, והמידע שלך על הפונקציה יהיה חלקי.

בדוק את הבנתך

כמה פעמים עלינו להריץ את האלגוריתם למעלה כדי ללמוד את הפונקציה $f(x)$? האם זה טוב יותר מהמקרה הקלאסי? האם תעדיף מחשב קלאסי או קוונטי לפתרון הבעיה הזו?

תשובה

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

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

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

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

הבעיה

הנה הייתה הבעיה:

בהינתן ביט כניסה, $x = \{0,1\}$, ופונקציית כניסה $f(x) = \{0,1\}$, קבע האם הפונקציה היא מאוזנת (balanced) או קבועה (constant). כלומר, אם היא מאוזנת, אז פלט הפונקציה הוא 0 חצי מהזמן ו-1 בחצי האחר. אם היא קבועה, אז פלט הפונקציה הוא תמיד 0 או תמיד 1. נזכיר את טבלת ארבע הפונקציות האפשריות הלוקחות ביט בודד לביט בודד אחר:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

הפונקציה הראשונה והאחרונה, $f_1(x)$ ו-$f_4(x)$, הן קבועות, בעוד ששתי הפונקציות האמצעיות, $f_2(x)$ ו-$f_3(x)$, מאוזנות.

האלגוריתם

הדרך שבה דויטש ניגש לבעיה זו הייתה דרך "מודל השאילתה". במודל השאילתה, פונקציית הכניסה ($f_i(x)$ למעלה) נמצאת ב"קופסה שחורה" — אין לנו גישה ישירה לתוכנה, אבל אנחנו יכולים לשאול את הקופסה השחורה והיא תיתן לנו את פלט הפונקציה. לפעמים אנחנו אומרים ש"oracle" מספק מידע זה. ראה שיעור 1: אלגוריתמי שאילתה קוונטיים של קורס היסודות של אלגוריתמים קוונטיים למידע נוסף על מודל השאילתה.

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

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

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

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

בדוק את הבנתך

מה הוא המצב $|\pi_1\rangle$?

תשובה

החלת Hadamard ממירה את המצב $|0\rangle$ ל-$\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ ואת המצב $|1\rangle$ ל- $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. לכן, המצב המלא הופך ל: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

מה הוא המצב $|\pi_2\rangle$?

תשובה

לפני שאנחנו מחילים את $U_f$, נזכור מה הוא עושה. הוא ישנה את מצב qubit 1 בהתבסס על מצב qubit 0. אז הגיוני לפרק את מצב qubit 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. לאחר מכן, אם $f(0)=f(1)$, שני האיברים יתמירו באותה דרך וסימן היחסי בין שני האיברים יישאר חיובי, אבל אם $f(0)\neq f(1)$, אז האיבר השני יקבל מינוס יחסית לאיבר הראשון, ומשנה את מצב qubit 0 מ-$\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ ל-$\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. אז:

$$|\pi_2\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}] & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}] &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

מה הוא המצב $|\pi_3\rangle$?

תשובה

עכשיו, מצב qubit 0 הוא $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ או $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, בהתאם לפונקציה. החלת Hadamard תניב $|0\rangle$ או $|1\rangle$, בהתאמה.

$$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

כאשר בוחנים את התשובות לשאלות למעלה, שים לב שמשהו מפתיע קצת קורה. למרות ש-$U_f$ לא עושה כלום במפורש למצב של qubit 0, מכיוון שהוא משנה את qubit 1 בהתבסס על מצב qubit 0, יכול לקרות שזה גורם להזזת פאזה ב-Qubit 0. זה ידוע כתופעת "phase-kickback", ומדובר בה בפירוט רב יותר ב-שיעור 1: אלגוריתמי שאילתה קוונטיים של קורס היסודות של אלגוריתמים קוונטיים.

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

## Deutsch's algorithm:

## Step 1: Map the problem

# first, convert oracle circuit (above) to a single gate for drawing purposes.
# otherwise, the circuit is too large to display
blackbox = twobit_function(
    3
    # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
).to_gate()
blackbox.label = "$U_f$"

qc_deutsch = QuantumCircuit(2, 1)

qc_deutsch.x(1)
qc_deutsch.h(range(2))

qc_deutsch.barrier()
qc_deutsch.compose(twobit_function(2), inplace=True)
qc_deutsch.barrier()

qc_deutsch.h(0)
qc_deutsch.measure(0, 0)

qc_deutsch.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_deutsch)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)
if "1" in counts:
    print("balanced")
else:
    print("constant")

{'1': 1}
balanced

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

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

הנה תרשים Circuit של האלגוריתם:

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

כדי לראות כיצד האלגוריתם עובד ב-Qiskit, ראשית עלינו לייצר את ה-oracle שלנו: הפונקציה האקראית שמובטח שהיא קבועה או מאוזנת. הקוד למטה ייצור פונקציה מאוזנת ב-50% מהמקרים, ופונקציה קבועה ב-50% מהמקרים. אל תדאג אם לא לגמרי עוקב אחרי הקוד — הוא מורכב ולא הכרחי להבנת האלגוריתם הקוונטי.

from qiskit import QuantumCircuit
import numpy as np

def dj_function(num_qubits):
    """
    Create a random Deutsch-Jozsa function.
    """

    qc_dj = QuantumCircuit(num_qubits + 1)
    if np.random.randint(0, 2):
        # Flip output qubits with 50% chance
        qc_dj.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance.
        return qc_dj

    # If the "if" statement above was "TRUE" then we've returned the constant
    # function and the function is complete. If not, we proceed in creating our
    # balanced function. Everything below is to produce the balanced function:

    # select half of all possible states at random:
    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_dj, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc_dj.x(qubit)
        return qc_dj

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

    # qc_dj.barrier()

    return qc_dj

n = 3  # number of input qubits

oracle = dj_function(n)

display(oracle.draw("mpl"))

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

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

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

blackbox = oracle.to_gate()
blackbox.label = "$U_f$"

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(blackbox, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 1: Map the problem

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(oracle, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_dj)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

if (
    "0" * n in counts
):  # The D-J algorithm returns all zeroes if the function was constant
    print("constant")
else:
    print("balanced")  # anything other than all zeroes means the function is balanced.

{'110': 1}
balanced

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

בדוק את ההבנה שלך

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

תשובה

יש $2^n$ מחרוזות ביטים אפשריות לבדיקה, ובמקרה הגרוע, היית צריך לבדוק $2^n/2+1$ מהן. לדוגמה, אם הפונקציה הייתה קבועה, ואתה המשכת למדוד "1" כפלט הפונקציה, לא יכולת להיות בטוח שהיא באמת קבועה עד שבדקת יותר ממחצית התוצאות. לפני כן, ייתכן שפשוט לא היה לך מזל למדוד "1" כל הזמן על פונקציה מאוזנת. זה כמו להטיל מטבע שוב ושוב ולקבל עץ בכל פעם. זה לא סביר, אבל לא בלתי אפשרי.

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

תשובה

במקרה זה, יכולת פשוט למדוד פעמיים. אם שתי המדידות שונות, אתה יודע שהפונקציה מאוזנת. אם שתי המדידות זהות, אז היא עשויה להיות מאוזנת, או שהיא עשויה להיות קבועה. ההסתברות שהיא מאוזנת עם קבוצת מדידות זו היא: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. זה פחות מ-1/2, אז יותר סביר שהפונקציה קבועה במקרה זה.

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

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

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

הפונקציה $f:\{0,1\}^n \rightarrow \{0,1\}$ עדיין לוקחת מחרוזת $n$-ביטים ומוציאה ביט בודד. אבל עכשיו, במקום להבטיח שהפונקציה מאוזנת או קבועה, מובטח לנו שהפונקציה היא המכפלה הנקודתית בין מחרוזת הקלט $x$ לבין מחרוזת $n$-ביטים סודית $s$, מודולו 2. (המכפלה הנקודתית הזו מודולו 2 נקראת "מכפלה נקודתית בינארית".) הבעיה היא לגלות מהי המחרוזת הסודית בת $n$ הביטים.

בניסוח אחר, ניתן לנו פונקציה קופסה שחורה $f: {0,1}^n \rightarrow {0,1}$ שמקיימת $f(x) = s \cdot x$ עבור מחרוזת כלשהי $s$, ואנחנו רוצים ללמוד את המחרוזת $s$.

בואו נסתכל כיצד אלגוריתם D-J פותר בעיה זו:

1. ראשית, Gate של Hadamard מוחל על $n$ ה-Qubit הראשונים, ו-Gate NOT בתוספת Hadamard מוחל על ה-Qubit של הפלט, וייצר את המצב:

$$|\Psi\rangle = |-\rangle_{n} \otimes |+\rangle_{n-1} \otimes |+\rangle_{n-2} \otimes ... \otimes |+\rangle_0$$

מצב ה-Qubit מ-1 עד $n$ ניתן לכתיבה פשוטה יותר כסכום על כל $2^n$ מצבי הבסיס בני ה-$n$-Qubit $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. אנחנו מכנים את קבוצת מצבי הבסיס האלה $\Sigma^n$. (ראה יסודות אלגוריתמים קוונטיים לפרטים נוספים.)

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{|x\rangle}$$

2. לאחר מכן, ה-Gate $U_f$ מוחל על ה-qubits. ה-Gate הזה ייקח את n ה-qubits הראשונים כקלט (שנמצאים כעת בסופרפוזיציה שווה של כל מחרוזות ה-n-ביטים האפשריות) ומחיל את הפונקציה $f(x)=s \cdot x$ על qubit הפלט, כך שה-qubit הזה נמצא כעת במצב: $|- \oplus f(x)\rangle$. הודות למנגנון ה-phase kickback, מצב ה-qubit הזה נשאר ללא שינוי, אך חלק מהאיברים במצב של qubits הקלט מקבלים סימן מינוס:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{(-1)^{f(x)}|x\rangle}$$

3. עכשיו, הסט הבא של Hadamard מוחל על qubit 0 עד $n-1$. מעקב אחרי סימני המינוס במקרה זה יכול להיות מסובך. כדאי לדעת שהחלת שכבת Hadamard על $n$ qubit במצב בסיס סטנדרטי $|x\rangle$ ניתן לכתיבה כ:

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

אז המצב הופך ל:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{2^n}\sum\limits_{x \in \Sigma^n}\sum\limits_{y \in \Sigma^n}{(-1)^{(s \cdot x) + (x \cdot y)}|y\rangle}$$

4. הצעד הבא הוא למדוד את $n$ הביטים הראשונים. אבל מה נמדוד? מסתבר שהמצב לעיל מצטמצם ל-$|\Psi\rangle = |-\rangle \otimes |s\rangle$, אבל זה רחוק מלהיות מובן מאליו. אם תרצה לעקוב אחרי המתמטיקה, ראה את הקורס יסודות אלגוריתמים קוונטיים של ג'ון ווטרוס. הנקודה היא שמנגנון ה-phase kickback מביא את qubits הקלט למצב $|s\rangle$. אז, כדי לגלות מהי המחרוזת הסודית $s$, פשוט צריך למדוד את ה-qubits!

בדוק את ההבנה שלך

אמת שהמצב מצעד 3 לעיל הוא אכן המצב $|s\rangle$ עבור המקרה הפרטי של $n=1$.

תשובה

כאשר אתה כותב במפורש את שני הסכומים, אתה אמור לקבל מצב עם ארבעה איברים (בואו נשמיט את מצב הפלט $|-\rangle$ לצורך זה):

$$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$$

אם $s=0$, אז שני האיברים הראשונים מתחברים בצורה קונסטרוקטיבית ושני האיברים האחרונים מתבטלים, ומותירים אותנו עם $|\Psi\rangle = |0\rangle$. אם $s=1$, אז שני האיברים האחרונים מתחברים בצורה קונסטרוקטיבית ושני האיברים הראשונים מתבטלים, ומותירים אותנו עם $|\Psi\rangle = |1\rangle$. לכן, בכל מקרה, $|\Psi\rangle = |s\rangle$. אנו מקווים שהמקרה הפשוט הזה ייתן לך תחושה לגבי האופן שבו פועל המקרה הכללי עם $n$ qubit: כל האיברים שאינם $|s\rangle$ מתבטלים בהתאבכות, ומותירים רק את המצב $|s\rangle$.

כיצד אותו אלגוריתם פותר גם את בעיית ברנשטיין-וזירני וגם את בעיית דויטש-ג'וזה? כדי להבין זאת, חשוב על פונקציות ברנשטיין-וזירני, שהן בצורה $f(x) = s \cdot x$. האם הפונקציות האלה הן גם פונקציות דויטש-ג'וזה? כלומר, קבע האם פונקציות מהצורה הזו מקיימות את ההבטחה של בעיית דויטש-ג'וזה: שהן קבועות או מאוזנות. כיצד זה עוזר לנו להבין כיצד אותו אלגוריתם פותר שתי בעיות שונות?

תשובה

כל פונקציית ברנשטיין-וזירני מהצורה $f(x) = s \cdot x$ מקיימת גם את ההבטחה של בעיית דויטש-ג'וזה: אם s=00...00, אז הפונקציה קבועה (תמיד מחזירה 0 לכל מחרוזת x). אם s היא כל מחרוזת אחרת, אז הפונקציה מאוזנת. לכן, החלת אלגוריתם דויטש-ג'וזה על אחת מהפונקציות האלה פותרת בו-זמנית את שתי הבעיות! הוא מחזיר את המחרוזת, ואם המחרוזת היא 00...00 אז אנחנו יודעים שהיא קבועה; אם יש לפחות "1" אחד במחרוזת, אנחנו יודעים שהיא מאוזנת.

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

# Step 1: Map the problem

def bv_function(s):
    """
    Create a Bernstein-Vazirani function from a string of 1s and 0s.
    """
    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_function("1000").draw("mpl"))

string = "1000"  # secret string that we'll pretend we don't know or have access to
n = len(string)

qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
# qc.compose(oracle, inplace = True)
qc.compose(bv_function(string), inplace=True)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))

qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

{'0000': 1}

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

סיכום

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

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

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

שאלות

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

מושגים מרכזיים

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

• מנגנון ה-phase kickback הוא תופעה קוונטית לא-אינטואיטיבית שמעבירה פעולות על qubit אחד לפאזה של qubit אחר. אלגוריתמי דויטש ודויטש-ג'וזה מנצלים מנגנון זה.

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

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

נכון/לא נכון

1. נ/לא נ אלגוריתם דויטש הוא מקרה פרטי של אלגוריתם דויטש-ג'וזה שבו הקלט הוא qubit בודד.

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

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

4. נ/לא נ "אלגוריתם ברנשטיין-וזירני" הוא למעשה אותו אלגוריתם כמו דויטש-ג'וזה, המוחל על בעיה שונה.

5. נ/לא נ אלגוריתם ברנשטיין-וזירני יכול למצוא מחרוזות סודיות מרובות בו-זמנית.

תשובה קצרה

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

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

3. תאר את מנגנון ה-phase-kickback וכיצד הוא עובד לפתרון בעיות דויטש-ג'וזה וברנשטיין-וזירני.

בעיית אתגר

1. אלגוריתם דויטש-ג'וזה: זכור שהיה לך שאלה למעלה שביקשה ממך לחשב את מצבי ה-Qubit הביניים $\pi_1$ ו-$\pi_2$ של אלגוריתם דויטש. עשה את אותו הדבר עבור מצבי ה-$n+1$ qubit הביניים $\pi_1$ ו-$\pi_2$ של אלגוריתם דויטש-ג'וזה, עבור המקרה הספציפי שבו $n=2$. לאחר מכן, אמת ש-$\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, שוב, עבור המקרה הספציפי שבו $n=2$.