טרנספורם פורייה הקוונטי

למודול 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 שלך.

מודול זה נבדק והשתמש ב-13 שניות של זמן 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'

מבוא

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

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

טרנספורם פורייה הקלאסי

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

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

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

בבסיס התדירות, אנחנו יכולים לראות בקלות פסגה ברורה בכ-260 הרץ. זה דו אמצעי!

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

אבל ספקטרום התדירות מזהה בבירור שלוש פסגות:

זה היה אקורד דו מז'ור, עם התווים דו, מי ו-סול.

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

טרנספורם פורייה דיסקרטי

טרנספורם פורייה שימושי למגוון יישומי עיבוד אותות. אבל ברוב היישומים בעולם האמיתי (כולל דוגמת המוזיקה שהשתמשנו לעיל), אנחנו רוצים לטרנספורם קבוצה דיסקרטית של $N$ נקודות נתונים — לא פונקציה רציפה. במקרה הזה, אנחנו משתמשים בטרנספורם פורייה הדיסקרטי. טרנספורם פורייה הדיסקרטי (DFT) פועל על וקטור $(x_0, ..., x_{N-1})$ וממפה אותו לוקטור $(y_0, ..., y_{N-1})$ לפי הנוסחה:

$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$

כאשר אנחנו לוקחים $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (שים לב שיש מוסכמות אחרות שיש להן סימן מינוס בחזקה, אז היזהר כשאתה רואה את ה-DFT בחיים האמיתיים.) נזכור ש-$e^{2\pi i \frac{jk}{N}}$ היא פונקציה מחזורית, עם מחזור $\frac{N}{k}$. לכן, על ידי כפל בפונקציה זו, טרנספורם פורייה הוא בעצם דרך לפרק את הפונקציה (הדיסקרטית) $\{x_{j}\}$ לצירוף לינארי של הפונקציות המחזוריות המרכיבות אותה, כל אחת עם מחזור $\frac{N}{k}$.

טרנספורם פורייה הקוונטי

אז עכשיו, ראינו איך טרנספורם פורייה משמש לייצוג פונקציה כצירוף לינארי של קבוצה חדשה של "פונקציות בסיס". טרנספורמציות בסיס מתבצעות גם באופן קבוע על מצבי Qubit. לדוגמה, המצב של Qubit בודד $|\psi\rangle$ יכול להיות מבוטא בבסיס החישובי $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, עם מצבי הבסיס $|0\rangle$ ו-$|1\rangle$, או בבסיס $X$ כ-$|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ עם מצבי בסיס $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ ו-$|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. שניהם תקפים באותה מידה, אבל אחד עשוי להיות יותר טבעי מהשני, תלוי בסוג הבעיה שאתה מנסה לפתור.

מצבי Qubit יכולים גם להיות מבוטאים בבסיס פורייה, שבו מצב מבוטא במונחים של צירוף לינארי של מצבי בסיס פורייה $|\phi_y\rangle$, במקום מצבי הבסיס החישובי הרגילים $|x\rangle$. לשם כך, צריך להחיל טרנספורם פורייה קוונטי (QFT):

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

כאשר $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ כמו לעיל, ו-$N$ הוא מספר מצבי הבסיס במערכת הקוונטית שלך. שים לב שמכיוון שאנחנו עובדים עם Qubit עכשיו, $m$ Qubit נותנים לנו $2^m$ מצבי בסיס, ולכן $N=2^m$. כאן, מצבי הבסיס כתובים כמספר יחיד $|x\rangle$ כאשר $x$ נע מ-$0$ עד $N-1$, אבל בדרך כלל תראה את מצבי הבסיס מבוטאים כ-$|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, כאשר כל ספרה בינארית מייצגת את מצב ה-Qubit 0 עד $m-1$, מימין לשמאל. יש דרך פשוטה להמיר את המצבים הבינאריים האלה למספר יחיד: פשוט התייחס אליהם כמספרים בינאריים! לכן, $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, וכן הלאה, עד $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

בניית אינטואיציה למצבי בסיס פורייה

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

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

$|\phi_0\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

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

מצב בסיס פורייה הבא הוא זה שהפאזות של רכיביו עוטפות מ-$0$ עד $2\pi$ בדיוק פעם אחת:

$|\phi_1\rangle = \frac{1}{2} (|00\rangle + e^{i\pi/2}|01\rangle + e^{i\pi}|10\rangle + e^{3i\pi/2}|11\rangle) = \frac{1}{2}(|00\rangle + i|01\rangle - |10\rangle - i|11\rangle)$

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

אז, לכל מצב יש פאזה שגבוהה ב-$2\pi/4$ רדיאן מהמצב שלפניו כשהם מסודרים בדרך הסטנדרטית, מכיוון שבדוגמה זו יש לנו ארבעה מצבי בסיס ($N=4$). מצב הבסיס הבא עוטף מ-0 עד $2\pi$ פעמיים:

$|\phi_2\rangle = \frac{1}{2} (|00\rangle + e^{i\pi}|01\rangle + e^{2i\pi}|10\rangle + e^{3i\pi}|11\rangle) = \frac{1}{2} (|00\rangle - |01\rangle + |10\rangle - |11\rangle)$

לבסוף, רכיב פורייה הגבוה ביותר הוא זה עם הפאזה המשתנה הכי מהר. בדוגמה שלנו עם שני Qubit, זה זה שהפאזות שלו עוטפות מ-0 עד $2\pi$ שלוש פעמים:

$|\phi_3\rangle = \frac{1}{2} (|00\rangle + e^{3i\pi/2}|01\rangle + e^{6i\pi/2}|10\rangle + e^{9i\pi/2}|11\rangle) = \frac{1}{2} (|00\rangle - i|01\rangle - |10\rangle + i|11\rangle)$

בכלל, עבור מצב של $m$ Qubit, יהיו $2^m$ מצבי בסיס פורייה, שהתדירות בשינוי הפאזה שלהם נעה מקבועה, עבור $|\phi_0\rangle$, עד משתנה מהיר עבור $|\phi_{2^m-1}\rangle$, שמשלים $2^m-1$ עטיפות סביב $2\pi$ על פני הסופרפוזיציה של המצבים. אז, כשאנחנו לוקחים QFT של מצב קוונטי, אנחנו בעצם עושים את אותו ניתוח בסיסי שעשינו עבור צורת הגל המוסיקלית בהקדמה. אנחנו קובעים את רכיבי תדירות פורייה שתורמים ליצירת המצב הקוונטי שמעניין אותנו.

נסה כמה QFT לדוגמה

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

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

import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
from qiskit.circuit.library import QFTGate

# 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

service = QiskitRuntimeService()

# Use the least busy backend
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_pinguino2")

print(backend.name)

ibm_pinguino2

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

# 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

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)

# Alternatively, load a fake backend with generic properties and define a simulator.
from qiskit.providers.fake_provider import GenericBackendV2

backend_gen = GenericBackendV2(num_qubits=18)
sampler_gen = BackendSamplerV2(backend=backend_gen)

מצב בסיס חישובי בודד

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

# Step 1: Map

qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# flip state of random qubits to put in a random single computational basis state
for i in range(1, qubits):
    if np.random.randint(0, 2):
        qc.x(i)

# make a copy of the above circuit. (to be used when we apply the QFT in next part)
qc_qft = qc.copy()

qc.measure_all()
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 OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

עכשיו, בואו נטרנספורם פורייה את המצב הזה עם QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.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_qft)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

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

עובדה זו קשורה בעצם לאי-ודאות קוונטית! עקרון אי-הוודאות של היזנברג מנוסח בדרך כלל כ-$\Delta x \Delta p \ge \hbar / 2$. אז אם אי-הוודאות ב-$x$ ($\Delta x$) קטנה, אי-הוודאות בתנע ($\Delta p$) חייבת להיות גדולה, ולהיפך. מסתבר שטרנספורמציה מבסיס המיקום $x$ לבסיס התנע $p$ מתבצעת דרך טרנספורם פורייה.

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

שני מצבי בסיס חישובי

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

בואו נבחר את הסופרפוזיציה:

$|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle) = \frac{1}{\sqrt{2}} (|000...0\rangle + |100...0\rangle)$

# Step 1: Map
qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# To make this state, we just need to apply a Hadamard to the last qubit

qc.h(qubits - 1)

qc_qft = qc.copy()

qc.measure_all()

qc.draw("mpl")

# First, let's go through steps 2-4 for the first circuit, qc

# 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 - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

עכשיו, בואו נטרנספורם פורייה את המצב הזה עם QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.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_qft)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

זה אולי קצת יותר מפתיע. נראה שה-QFT של המצב $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ הוא סופרפוזיציה של כל מצבי הבסיס הזוגיים. אבל אם נחשוב בחזרה לדמות שלנו של כל מצב בסיס $|\phi_y\rangle$, ואיך הפאזה של כל רכיב עוטפת סביב $2\pi$ $y$ פעמים, אז הסיבה שאנחנו מקבלים את התוצאה הזאת עשויה להתבהר.

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

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

בעזרת הרמז למעלה, הסבר למה התוצאה שקיבלנו עבור ה-QFT של $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ צפויה.

תשובה:

למצב המקורי יש פאזה יחסית של 0 (או כפולה שלמה של $2\pi$) בין שני חלקי הסופרפוזיציה. אז אנחנו יודעים שלמצב הזה יש רכיבי פורייה שהפאזות שלהם גם תואמות באותה צורה: אלה שיש להם היסט פאזה 0 בין האיבר |0000> לאיבר |1000>. כל מצב בסיס פורייה $|\phi_y\rangle$ מורכב מאיברים שהפאזה שלהם מצטברת בקצב של $2\pi y/N$, כלומר, כשמסדרים בדרך הרגילה, לכל איבר בסופרפוזיציה יש פאזה של $2\pi y/N$ גדולה יותר מהאיבר שקדם לו. אז, בנקודת האמצע $N/2$, אנחנו רוצים שהפאזה $2\pi y/N * N/2$ תהיה כפולה שלמה של $2\pi$. זה קורה כאשר $y$ הוא זוגי.

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

תשובה:

אם לקחת את ה-QFT של המצב $\psi = |0\rangle - |N/2\rangle$, אז תראה פסגות על כל מצב בעל מספר בינארי אי-זוגי.

פירוק אלגוריתם ה-QFT

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

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

$|\phi_0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$|\phi_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

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

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

השתמש במשוואה עבור ה-QFT מהסעיף הקודם כדי לאמת את שני מצבי הבסיס של פורייה למעלה.

תשובה:

הנוסחה הכללית של QFT היא:

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

עבור Qubit יחיד ($n=1$), $N=2^n=2$, ו-$\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. אז, יש לנו

$| \phi_0 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {0 \times 0}{2}}|0\rangle + e^{2\pi i \frac {0 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$| \phi_1 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {1 \times 0}{2}}|0\rangle + e^{2\pi i \frac {1 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

תסתכל על שתי המשוואות האלה. אולי כבר אתה מכיר Gate קוונטי שאפשר להשתמש בו כדי לממש את הטרנספורמציה הזו. כלומר, יש Gate שהופך מצבי בסיס חישוביים $|0\rangle$ ו-$|1\rangle$ למצבי הבסיס של פורייה $|\phi_0\rangle$ ו-$|\phi_1\rangle$ בהתאמה. זה Hadamard Gate! זה נהיה אפילו יותר ברור אם נציג ייצוג מטריצי של הפעולה QFT$_N$:

$\text{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{xy} \vert x \rangle \langle y \vert$

אם אתה לא מכיר את הסימון הזה לביטוי אופרטור קוונטי, זה בסדר! זו דרך לייצג מטריצה מסדר $N \times N$, כאשר $x$ ו-$y$ מאנדקסים את העמודות והשורות של המטריצה, מ-$0$ עד $N-1$, ו-$\omega_N^{xy}$ הוא הערך של אותו ערך ספציפי. אז הערך בעמודה ה-0 ושורה ה-2, לדוגמה, יהיה פשוט $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

בייצוג הזה, כל אחד ממצבי הבסיס החישובי משויך לאחד מוקטורי הבסיס:

$$\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, |1\rangle = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, |N-1\rangle = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}.$$

אם תרצה ללמוד על הייצוג הזה לעומק, ראה את השיעור של John Watrous על מערכות מרובות בקורס יסודות מידע קוונטי.

בואו ננסה לבנות את המטריצה עבור QFT$_4$. בעזרת הנוסחה למעלה, נמצא ש-

\text\{QFT\}_4 = \frac\{1\}\{2\} \begin\{pmatrix\} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end\{pmatrix\}

כדי לממש את המטריצה הזו על מחשב קוונטי, נצטרך להבין איזה שילוב של Gates המוחלים על אילו Qubits ייתן לנו טרנספורמציה אוניטרית שתתאים למטריצה למעלה. כבר יודעים את אחד ה-Gates שיהיו נחוצים: Hadamard. Gate נוסף שנצטרך הוא ה-controlled-phase gate, שמחיל פאזה יחסית $\alpha$ על מצב ה-Qubit היעד, כל עוד ה-Qubit השולט נמצא במצב $|1\rangle$. בצורת מטריצה זה נראה כך:

\text\{CP\}_\alpha = \begin\{pmatrix\} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^\{i\alpha\} \\ \end\{pmatrix\}

מכיוון שרק המצב $|11\rangle$ משתנה, לא משנה באמת איזה Qubit נחשב ל"שולט" ואיזה ל"יעד". התוצאה תהיה זהה בכל מקרה.

לבסוף, נצטרך גם כמה SWAP Gates. SWAP Gate מחליף את המצבים של שני Qubits. זה נראה כך:

\text\{SWAP\}_\alpha = \begin\{pmatrix\} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end\{pmatrix\}

הנוהל לבנות Circuit של QFT$_{2^m}$ על $m$ Qubits הוא איטרטיבי — קודם מחילים QFT$_{2^{m-1}}$ על Qubits $1$ עד $m-1$, ואז מוסיפים כמה Gates בין Qubit $0$ לשאר $m-1$ ה-Qubits. אבל כדי להחיל QFT$_{2^{m-1}}$, קודם צריך להחיל QFT$_{2^{m-2}}$ על Qubits 2 עד $m-1$, ואז להוסיף Gates בין Qubit 1 ל-Qubits הנותרים $2$ עד $m-1$. זה כמו בובת מטריושקה רוסית: כל בובה מוסיפה פקטור של שתיים לממד ה-Circuit של QFT, כאשר הבובה הקטנה ביותר נמצאת במרכז, והיא QFT$_2$, או Hadamard Gate.

כדי לשים בובה בתוך הבובה הגדולה הבאה, ובכך להגדיל את ממד ה-QFT בפקטור שניים, תמיד עוקבים אחרי אותו נוהל:

1. קודם, מחילים QFT$_{2^{m-1}}$ על $m-1$ ה-Qubits התחתונים ביותר. זו ה"בובה הקטנה יותר" של סט המטריושקה שתכניס עוד רגע לתוך הבובה הבאה בגודלה.
2. משתמשים ב-Qubit הבא כשולט, ומחילים controlled phase gates על כל אחד מ-$m-1$ ה-Qubits התחתונים, עם פאזות למצבי הבסיס הסטנדרטיים של כל אחד מ-$m-1$ ה-Qubits הנותרים.
3. מבצעים Hadamard על אותו Qubit עליון ששימש כשולט ב-phase gates.
4. משתמשים ב-SWAP Gates כדי לסדר מחדש את סדר ה-Qubits כך שהביט הפחות משמעותי (עליון) יהפוך לביט המשמעותי ביותר (תחתון), וכל האחרים יזוזו למעלה ביחידה אחת.

כבר השתמשנו בפונקציה QFTGate מספריית ה-Circuit של Qiskit, אבל עכשיו בואו נסתכל בתוך חלק מ-Gates האלה של QFT כדי לאמת את הנוהל שתיארנו למעלה. אנחנו יכולים לעשות זאת עם decompose().

qc = QuantumCircuit(1)
qc.compose(QFTGate(1), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(2)
qc.compose(QFTGate(2), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(3)
qc.compose(QFTGate(3), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(4)
qc.compose(QFTGate(4), inplace=True)
qc.decompose().draw("mpl")

אז, אנחנו מקווים שמארבעת ה-QFTs הראשונים תוכלו להתחיל לראות איך כל אחד מקונן בתוך הגדול הבא. אולי שמתם לב, עם זאת, שחלק מ-phase gates לא בדיוק כמתואר בנוהל שתיארנו למעלה, וה-SWAPs לא מופיעים אחרי כל תת-שגרה, אלא רק בסוף ה-QFT המלא. זה חוסך לנו Gates מיותרים, שגורמים ל-Circuit לקחת יותר זמן ולהיות יותר מועד לשגיאות. במקום לממש את ה-SWAP אחרי כל בובה מקוננת, ה-Circuit עוקב אחרי איפה כל מצב Qubit אמור להיות ומתאים את ה-Qubits שעליהם הוא מחיל את ה-phase gates בהתאם. ואז, קבוצת SWAPs אחרונה בסוף מניחה את הכל במקומו הנכון.

יישום ה-QFT: אמידת פאזה

בואו נראה כיצד ניתן להשתמש ב-QFT כדי לפתור בעיה שימושית בחישוב קוונטי. חישוב הטרנספורמציה ההפוכה של פורייה הקוונטית הוא שלב הכרחי באלגוריתם המוכר בשם Quantum Phase Estimation (QPE), שהוא עצמו תת-שגרה בהרבה אלגוריתמים אחרים, כולל "אבן הכתר" של האלגוריתמים הקוונטיים, אלגוריתם הפירוק לגורמים של שור.

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

אז, מה הקשר לטרנספורמציית פורייה קוונטית? ובכן, כפי שאולי אתה זוכר, לכל ערך עצמי $\lambda$ של אופרטור אוניטרי יש גודל $|\lambda| = 1$. אז אנחנו יכולים לכתוב כל ערך עצמי כמספר מרוכב עם גודל אחד:

$\lambda = e^{2\pi i \theta}$

כאשר $\theta$ הוא מספר ממשי בין 0 ל-1. אם תרצה מידע נוסף על מטריצות אוניטריות, ראה את השיעור של John Watrous בנושא ביסודות מידע קוונטי.

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

כיצד QPE עובד

קודם, נתחיל עם אלגוריתם QPE הפשוט ביותר, שמאמד את הפאזה בערך לספרה בינארית אחת של דיוק. במילים אחרות, האלגוריתם הזה יכול להבחין בין $\theta = 0$ ו-$\theta = 1/2$, אבל לא יכול לעשות טוב מזה. הנה תרשים ה-Circuit:

ה-Qubits מוכנים במצב $|\pi_0\rangle = |\psi\rangle|0\rangle$, כאשר Qubit $0$ נמצא במצב $|0\rangle$ וה-Qubits הנותרים נמצאים במצב $|\psi\rangle$, שהוא מצב עצמי של $U$. אחרי Hadamard הראשון, מצב ה-Qubit הופך ל:

$|\pi_1\rangle = \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + |1\rangle)$

ה-Gate הבא הוא Gate "controlled-$U$". זה מחיל את הפעולה האוניטרית $U$ על ה-Qubits התחתונים שנמצאים במצב $|\psi\rangle$ אם Qubit 0 נמצא במצב $|1\rangle$, אבל לא עושה כלום ל-$|\psi\rangle$ אם Qubit 0 נמצא במצב $|0\rangle$. זה הופך את ה-Qubits למצב:

$|\pi_2\rangle = \frac{1}{\sqrt{2}}( |\psi\rangle|0\rangle + e^{2\pi i \theta}|\psi\rangle|1\rangle)$ $= \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + e^{2\pi i \theta}|1\rangle)$

משהו מוזר קרה כאן: ה-Gate controlled-$U$ משתמש רק ב-Qubit $0$ כ-Qubit שולט, אז אפשר היה לחשוב שה-Gate הזה לא ישנה כלל את המצב של Qubit 0. אבל איכשהו, כן! למרות שהפעולה הוחלה על ה-Qubits התחתונים, ההשפעה הכוללת של ה-Gate היא לשנות את הפאזה של Qubit $0$. זה ידוע בשם "מנגנון ה-phase kickback", ומשמש בהרבה אלגוריתמים קוונטיים, כולל אלגוריתמי Deutsch-Josza ו-Grover. אם תרצה ללמוד עוד על מנגנון ה-phase kickback, ראה את שיעורו של John Watrous על אלגוריתמי שאילתה קוונטיים ביסודות אלגוריתמים קוונטיים.

אחרי ה-phase kickback, מחילים עוד Hadamard על Qubit $0$, שמביא למצב:

$|\pi_3\rangle = |\psi\rangle ( \frac{1+e^{2\pi i \theta}}{2} |0\rangle + \frac{1 - e^{2\pi i \theta}}{2}|1\rangle) = |\psi\rangle ( \cos(\pi\theta) |0\rangle - i \sin(\pi\theta)|1\rangle)$

אז, כאשר אנחנו מודדים את Qubit $0$ בסוף, נמדוד $|0\rangle$ עם ודאות של 100% אם $\theta = 0$ ונמדוד $|1\rangle$ עם ודאות של 100% אם $\theta = \frac{1}{2}$ (ואם המחשב הקוונטי שלנו מושלם, ללא רעש). אם $\theta$ הוא משהו אחר, המדידה הסופית היא רק הסתברותית ומספרת לנו רק כל כך הרבה.

QPE עם יותר דיוק: יותר Qubits

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

Circuit ה-QPE המדויק יותר הזה מתחיל אותו דבר כמו גרסת הביט הבודד: Hadamards מוחלים על $m$ ה-Qubits הראשונים, וה-Qubits הנותרים מוכנים במצב $|\psi\rangle$, יוצרים את המצב:

$|\pi_1\rangle = \frac{1}{2^{m/2}}|\psi\rangle(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)...(|0\rangle+|1\rangle)$

עכשיו, ה-controlled-unitaries מוחלים. Qubit $0$ הוא השולט לאותו $U$ אוניטרי כמו קודם. אבל עכשיו, Qubit $1$ הוא השולט לאוניטרי $U^2$, שהוא פשוט $U$ המוחל פעמיים. אז, ערך העצמי של $U^2$ הוא $e^{2*2\pi i \theta}$. באופן כללי, כל Qubit $k$ מ-0 עד $m-1$ יהיה השולט לאוניטרי $U^{2^k}$. זה אומר שכל אחד מה-Qubits האלה יחווה phase kickback של $e^{2^k*2\pi i \theta}$. זה מביא למצב:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} (|0\rangle+e^{2^{m-1}2\pi i \theta}|1\rangle)(|0\rangle+e^{2^{m-2}2\pi i \theta}|1\rangle)...(|0\rangle+e^{2\pi i \theta}|1\rangle)$

זה ניתן לכתיבה מחדש כסכום על מצבי הבסיס החישובי:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} \sum_{k=0}^{2^{m}-1} e^{2\pi i k \theta} |k\rangle$

האם הסכום נראה מוכר? זה QFT! נזכיר את המשוואה לטרנספורמציית פורייה הקוונטית:

$\text{QFT}_{2^m}| y \rangle = \frac{1}{\sqrt{2^m}}\sum_{x=0}^{2^m-1}\omega_{2^m}^{y x} \vert x \rangle$

אז, אם הפאזה $\theta = y/2^m$ עבור מספר שלם $y$ בין $0$ ל-$2^m-1$, אז לקיחת ה-QFT ההפוך של המצב הזה תביא למצב:

$|\pi_3\rangle = |\psi\rangle \otimes |y\rangle$

ומ-$|y\rangle$, נוכל לגזור את $\theta$.

אם $\theta/2^m$ אינו כפולה שלמה, עם זאת, אז לקיחת ה-QFT ההפוך רק תקרב את $\theta$. עד כמה טוב הוא יקרב את $\theta$ יהיה הסתברותי, כלומר לא תמיד נקבל את הקירוב הטוב ביותר, אבל זה יהיה די קרוב, וככל שתשתמש ב-$m$ Qubits רבים יותר, כך תקבל קירוב טוב יותר. כדי ללמוד כיצד לכמת את הקירוב הזה של $\theta$, בדוק את שיעורו של John Watrous על אמידת פאזה ופירוק לגורמים ביסודות אלגוריתמים קוונטיים.

סיכום

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

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

• טרנספורמציית פורייה הקוונטית היא האנלוג הקוונטי לטרנספורמציית פורייה הדיסקרטית.
• ה-QFT הוא דוגמה לטרנספורמציית בסיס.
• נוהל Quantum Phase Estimation מסתמך על מנגנון ה-phase kickback מהפעולות controlled-unitary, וכן על QFT הפוך.
• QFT ו-QPE הם שניהם תת-שגרות בשימוש נרחב בהרבה אלגוריתמים קוונטיים.

שאלות

נכון/לא נכון

1. נ/לנ טרנספורמציית פורייה הקוונטית היא האנלוג הקוונטי של טרנספורמציית פורייה הדיסקרטית הקלאסית (DFT).
2. נ/לנ QFT ניתן למימוש רק בעזרת Hadamard ו-CNOT Gates.
3. נ/לנ QFT הוא מרכיב מרכזי באלגוריתם של שור.
4. נ/לנ הפלט של Quantum Phase Estimation הוא מצב קוונטי המייצג את וקטור העצמי של האופרטור.
5. נ/לנ QPE דורש שימוש בטרנספורמציית פורייה הקוונטית ההפוכה (QFT$^\dag$).
6. נ/לנ ב-QPE, אם הפאזה $\phi$ ניתנת לייצוג מדויק עם $n$ ביטים, האלגוריתם נותן את התוצאה הנכונה בהסתברות 1.

תשובות קצרות

1. כמה Qubits נדרשים לביצוע QFT על מערכת עם $2^n$ נקודות נתונים?
2. האם ניתן להשתמש ב-QFT על מצב שאינו מצב בסיס חישובי? אם כן, מה קורה?
3. כיצד מספר ה-Qubits השולטים המשמשים ב-QPE משפיע על הרזולוציה של אמידת הפאזה המתקבלת?

בעיות

1. השתמש בכפל מטריצות כדי לאמת שהשלבים באלגוריתם ה-QFT אכן מביאים למטריצה $\text{QFT}_4$:

$$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$$

(לא חייב לעשות את זה ביד!)

בעיות אתגר

1. צור מצב של ארבעה Qubits שהוא סופרפוזיציה שווה של כל הבסיסים החישוביים האי-זוגיים: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. ואז בצע QFT על המצב. מה המצב המתקבל? הסבר למה התוצאה שלך הגיונית, בעזרת הידע שלך על טרנספורמציות פורייה.