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

למודול 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 — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

# 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: ביצוע באמצעות Qiskit Runtime Primitives
• שלב 4: עיבוד לאחר ביצוע וניתוח קלאסי

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

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

# Load the Qiskit Runtime 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
# blackbox = twobit_function(2).to_gate()  # you may edit the number inside "twobit_function()" to select among the four valid functions
# 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 המתורגם שלנו על המחשב הקוונטי ומדמיינים את התוצאות:

# 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 בכל צילום. כמו תמיד ב-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
).to_gate()  # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
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$ מוחל על ה-Qubit. ה-Gate הזה ייקח את $n$ ה-Qubit הראשונים כקלט (שנמצאים כעת בסופרפוזיציה שווה של כל מחרוזות ה-$n$-ביטים האפשריות) ומחיל את הפונקציה $f(x)=s \cdot x$ על ה-Qubit של הפלט, כך שה-Qubit הזה נמצא עכשיו במצב: $|- \oplus f(x)\rangle$. בזכות מנגנון ה-phase kickback, מצב ה-Qubit הזה נשאר ללא שינוי, אבל חלק מהאיברים במצב ה-Qubit של הקלט מקבלים סימן מינוס:

$$|\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 גורם ל-Qubit הקלט להיות במצב $|s\rangle$. אז, כדי לגלות מהי המחרוזת הסודית $s$, פשוט תצטרך למדוד את ה-Qubit!

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

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

אמת שהמצב מצעד 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$.