אלגוריתמים קוונטיים: אומדן פאזה

הערה

Kento Ueda (15 May 2024)

מחברת זו מספקת את המושגים הבסיסיים ואת היישום של טרנספורמציית פורייה הקוונטית (QFT) ואומדן הפאזה הקוונטי (QPE).

הורד את ה-PDF של ההרצאה המקורית. שים לב שחלק מקטעי הקוד עשויים להיות מיושנים כיוון שמדובר בתמונות סטטיות.

זמן QPU משוער להרצת הניסוי הוא 7 שניות.

1. מבוא

טרנספורמציית פורייה הקוונטית (QFT)

טרנספורמציית פורייה הקוונטית היא המקבילה הקוונטית של טרנספורמציית פורייה הדיסקרטית הקלאסית. זוהי טרנספורמציה לינארית המוחלת על מצבים קוונטיים, הממפה בסיסי חישוב לייצוגי הבסיס של פורייה שלהם. ה-QFT ממלא תפקיד מרכזי באלגוריתמים קוונטיים רבים, ומציע שיטה יעילה לחילוץ מידע תקופתיות ממצבים קוונטיים. ניתן לממש את ה-QFT עם $O(N^2)$ פעולות באמצעות Gates קוונטיים כמו Hadamard gates ו-Control-Phase gates עבור $N$ Qubits, מה שמאפשר האצה אקספוננציאלית על פני טרנספורמציית פורייה הקלאסית.

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

אומדן פאזה קוונטי (QPE)

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

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

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

2. יסודות טרנספורמציית פורייה הקוונטית (QFT)

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

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from qiskit.quantum_info import Statevector
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import Sampler

from numpy import pi

בהקבלה לטרנספורמציית פורייה הדיסקרטית, ה-QFT פועל על מצב קוונטי $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ עבור $N$ Qubits וממפה אותו למצב הקוונטי $\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$.

$$QFT_{N}: \vert j \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk} \vert k \rangle$$

כאשר $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$.

או בייצוג מטריצה יוניטרית:

$$U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} \omega_N^{jk} \vert k \rangle \langle j \vert$$

2.1. אינטואיציה

טרנספורמציית פורייה הקוונטית (QFT) עושה מיפוי בין שני בסיסים: בסיס החישוב (Z) ובסיס פורייה. אבל מה משמעות בסיס פורייה בהקשר זה? סביר להניח שאתה זוכר שטרנספורמציית פורייה $F(\omega)$ של פונקציה $f(x)$ מתארת את הקונבולוציה של $f(x)$ על פונקציה סינוסואידלית בתדר $\omega$. במילים פשוטות: טרנספורמציית פורייה היא פונקציה המתארת כמה מכל תדר $\omega$ נצטרך כדי לבנות פונקציה $f(x)$ מפונקציות סינוס (או קוסינוס). כדי לקבל תחושה טובה יותר למה ה-QFT אומר בהקשר זה, שקול את התמונות המדורגות למטה המציגות מספר המקודד בבינארי, באמצעות ארבעה Qubits:

בבסיס החישוב, אנו מאחסנים מספרים בבינארי באמצעות המצבים $|0\rangle$ ו-$|1\rangle$.

שים לב לתדירות שבה Qubits שונים משתנים; ה-Qubit השמאלי ביותר מתהפך עם כל תוספת במספר, הבא עם כל 2 תוספות, השלישי עם כל 4 תוספות, וכן הלאה.

אם נחיל טרנספורמציית פורייה קוונטית על מצבים אלה, נבצע מיפוי

$$|\text{State in Computational Basis}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{State in Fourier Basis}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(לעיתים קרובות אנו מסמנים מצבים בבסיס פורייה באמצעות טילדה (~)).

בבסיס פורייה, אנו מאחסנים מספרים באמצעות סיבובים שונים סביב ציר ה-Z:

IFRAME

המספר שאנחנו רוצים לאחסן קובע את הזווית שבה כל Qubit מסתובב סביב ציר ה-Z. במצב $|\widetilde{0}\rangle$, כל ה-Qubits נמצאים במצב $|{+}\rangle$. כפי שנראה בדוגמה לעיל, כדי לקודד את המצב $|\widetilde{5}\rangle$ על 4 Qubits, סובבנו את ה-Qubit השמאלי ביותר ב-$\tfrac{5}{2^n} = \tfrac{5}{16}$ סיבובים מלאים ($\tfrac{5}{16}\times 2\pi$ רדיאנים). ה-Qubit הבא מסתובב כפליים מזה ($\tfrac{10}{16}\times 2\pi$ רדיאנים, או $10/16$ סיבובים מלאים), זווית זו מוכפלת שוב עבור ה-Qubit שאחריו, וכן הלאה.

שוב, שים לב לתדירות שבה כל Qubit משתנה. ה-Qubit השמאלי ביותר (qubit 0) במקרה זה בעל התדר הנמוך ביותר, והימני ביותר בעל הגבוה ביותר.

2.2 דוגמה: QFT של Qubit אחד

נשקול את המקרה של $N = 2^1 = 2$.

ניתן לכתוב את המטריצה היוניטרית:

$$\begin{aligned} U_{QFT} & = \frac{1}{\sqrt{2}} \sum_{j=0}^{1} \sum_{k=0}^{1} \omega_2^{jk} \vert k \rangle \langle j \vert \\ & = \frac{1}{\sqrt{2}} (\omega_2^{0} \vert 0 \rangle \langle 0 \vert + \omega_2^{0} \vert 0 \rangle \langle 1 \vert + \omega_2^{0} \vert 1 \rangle \langle 0 \vert + \omega_2^{1} \vert 1 \rangle \langle 1 \vert) \\ & = \frac{1}{\sqrt{2}} (\vert 0 \rangle \langle 0 \vert + \vert 0 \rangle \langle 1 \vert + \vert 1 \rangle \langle 0 \vert - \vert 1 \rangle \langle 1 \vert) \\ & = H \end{aligned}$$

פעולה זו היא תוצאה של החלת שער ה-Hadamard ($H$).

2.3 ייצוג מכפלה של QFT

נכליל טרנספורמציה עבור $N = 2^n$, $QFT_{N}$ הפועל על המצב $\vert x \rangle = \vert x_1\ldots x_n \rangle$.

$$\begin{aligned} QFT_N\vert x \rangle & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1}\omega_N^{xy} \vert y \rangle \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i xy / 2^n} \vert y \rangle ~\text{since}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{and}\: N = 2^n \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i \left(\sum_{k=1}^n y_k/2^k\right) x} \vert y_1 \ldots y_n \rangle \:\text{rewriting in fractional binary notation}\: y = y_1\ldots y_n, y/2^n = \sum_{k=1}^n y_k/2^k \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \prod_{k=1}^n e^{2 \pi i x y_k/2^k } \vert y_1 \ldots y_n \rangle \:\text{after expanding the exponential of a sum to a product of exponentials,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{after rearranging the sum and products, and expanding} \sum_{y=0}^{N-1} = \sum_{y_1=0}^{1}\sum_{y_2=0}^{1}\ldots\sum_{y_n=0}^{1} \\ & = \frac{1}{\sqrt{N}} \left(\vert0\rangle + e^{\frac{2\pi i}{2}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^2}x} \vert1\rangle\right) \otimes \ldots \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^{n-1}}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^n}x} \vert1\rangle\right) \end{aligned}$$

2.4 דוגמה: בניית Circuit של QFT עם 3 Qubits

מהתיאור לעיל, אולי לא ברור כיצד לבנות Circuit של QFT. לעת עתה, פשוט שים לב שאנחנו מצפים לשלושה Qubits שיהיו להם פאזות המתפתחות בקצבים "שונים". ההבנה של כיצד זה מתורגם לـCircuit נשארת כתרגיל לקורא. ישנם מספר דיאגרמות ודוגמאות ב-PDF של ההרצאה. משאבים נוספים כוללים שיעור זה מקורס יסודות האלגוריתמים הקוונטיים.

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

# Prepare for 3 qubits circuit
qr = QuantumRegister(3)
cr = ClassicalRegister(3)
qc = QuantumCircuit(qr, cr)

qc.h(2)
qc.cp(pi / 2, 1, 2)  # Controlled-phase gate from qubit 1 to qubit 2
qc.cp(pi / 4, 0, 2)  # Controlled-phase gate from qubit 0 to qubit 2
qc.draw(output="mpl")

qc.h(1)
qc.cp(pi / 2, 0, 1)  # Controlled-phase gate from qubit 0 to qubit 1

qc.draw(output="mpl")

qc.h(0)

qc.draw(output="mpl")

qc.swap(0, 2)

qc.draw(output="mpl")

ננסה להחיל QFT על $|5\rangle$ כדוגמה.

ראשית, נאשר את הסימון הבינארי של המספר 5 וניצור את ה-Circuit המקודד את המצב 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

qc.x(0)
qc.x(2)
qc.draw(output="mpl")

נבדוק את המצבים הקוונטיים באמצעות סימולטור Aer:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

לבסוף, נוסיף QFT ונצפה במצב הסופי של ה-Qubits שלנו:

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

אנחנו יכולים לראות שפונקציית ה-QFT שלנו עבדה נכון. Qubit 0 סובב ב-$\tfrac{5}{8}$ מסיבוב מלא, Qubit 1 ב-$\tfrac{10}{8}$ סיבובים מלאים (שווה ערך ל-$\tfrac{1}{4}$ מסיבוב מלא), ו-Qubit 2 ב-$\tfrac{20}{8}$ סיבובים מלאים (שווה ערך ל-$\tfrac{1}{2}$ מסיבוב מלא).

2.5 תרגיל: QFT

(1) מממש QFT של 4 Qubits.

##your code goes here##

(2) החל QFT על $|14\rangle$, סמלץ ושרטט את וקטור המצב באמצעות כדור בלוך.

##your code goes here##

פתרון התרגיל: QFT

(1)

qr = QuantumRegister(4)
cr = ClassicalRegister(4)
qc = QuantumCircuit(qr, cr)

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

(2)

bin(14)

'0b1110'

qc = QuantumCircuit(4)

qc.x(1)
qc.x(2)
qc.x(3)
qc.draw("mpl")

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)
qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

3. יסודות אומדן הפאזה הקוונטי (QPE)

בהינתן פעולה יוניטרית $U$, אלגוריתם QPE מעריך את $\theta$ ב-$U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$. מכיוון ש-$U$ יוניטרי, לכל ערכי העצם שלו יש נורמה של 1.

3.1 הליך

1. הגדרה

$\vert\psi\rangle$ נמצא בקבוצה אחת של רשמי Qubit. קבוצה נוספת של $n$ Qubit יוצרת את רשם הספירה, שבו נאחסן את הערך $2^n\theta$:

$$|\psi_0\rangle = \lvert 0 \rangle^{\otimes n} \lvert \psi \rangle$$

2. סופרפוזיציה

מחילים פעולת Gate הדאמרד $n$-סיבית $H^{\otimes n}$ על רשם הספירה:

$$|\psi_1\rangle = {\frac {1}{2^{\frac {n}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes n} \lvert \psi \rangle$$

3. פעולות יוניטריות מבוקרות

צריך להכיר את ה-$CU$ היוניטרי המבוקר, שמחיל את האופרטור היוניטרי $U$ על רשם היעד רק אם סיבית הבקרה המתאימה היא $|1\rangle$. מכיוון ש-$U$ הוא אופרטור יוניטרי עם וקטור עצם $|\psi\rangle$ כך ש-$U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, מתקיים:

$$U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$$

3.2 דוגמה: QPE עם T-gate

בואו נשתמש ב-Gate מסוג $T$ כדוגמה ל-QPE ונעריך את הפאזה $\theta$ שלו.

$$T|1\rangle = \begin{pmatrix} 1 & 0\\ 0 & e^\frac{i\pi}{4}\\ \end{pmatrix} \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = e^\frac{i\pi}{4}|1\rangle$$

אנחנו מצפים למצוא:

$$\theta = \frac{1}{8}$$

כאשר

$$T|1\rangle = e^{2i\pi\theta}|1\rangle$$

אנחנו מאתחלים את $\vert\psi\rangle = \vert1\rangle$ של וקטור העצם של Gate מסוג $T$ על ידי החלת Gate מסוג $X$:

qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw(output="mpl")

לאחר מכן, מחילים Gate מסוג הדאמרד על Qubit הספירה:

for qubit in range(3):
    qpe.h(qubit)
qpe.draw(output="mpl")

מבצעים את הפעולות היוניטריות המבוקרות:

repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.draw(output="mpl")

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

from qiskit.circuit.library import QFT

# Apply inverse QFT
qpe.append(QFT(3, inverse=True), [0, 1, 2])
qpe.draw(output="mpl")

for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

ניתן לדמות באמצעות הסימולטור Aer:

aer_sim = AerSimulator()
shots = 2048

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

אנחנו רואים שמקבלים תוצאה אחת (001) בוודאות, שמתורגמת לערך העשרוני: 1. עכשיו צריך לחלק את התוצאה (1) ב-$2^n$ כדי לקבל את $\theta$:

$$\theta = \frac{1}{2^3} = \frac{1}{8}$$

האלגוריתם של שור מאפשר לנו לפרק גורמים של מספר על ידי בניית Circuit עם $\theta$ לא ידוע ולאחר מכן להשיג את $\theta$.

3.3 תרגיל

העריכו את $\theta = 1/3$ תוך שימוש ב-3 Qubit לספירה ו-Qubit אחד עבור וקטור עצם.

$P|1\rangle = e^{i\lambda}|1\rangle$. מכיוון שאנחנו רוצים לממש $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$, צריך להגדיר $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

פתרון התרגיל: $\theta = 1/3$

# Create and set up circuit
qpe = QuantumCircuit(4, 3)

# Apply H-Gates to counting qubits:
for qubit in range(3):
    qpe.h(qubit)

# Prepare our eigenstate |psi>:
qpe.x(3)

# Do the controlled-U operations:
angle = 2 * pi / 3
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(angle, counting_qubit, 3)
    repetitions *= 2

# Do the inverse QFT:
qpe.append(QFT(3, inverse=True), [0, 1, 2])

for n in range(3):
    qpe.measure(n, n)

qpe.draw(output="mpl")

aer_sim = AerSimulator()
shots = 4096

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

4. הרצה באמצעות ה-Sampler primitive של Qiskit Runtime

נבצע QPE באמצעות המכשיר הקוונטי האמיתי ונעקוב אחר 4 שלבים של תבניות Qiskit.

1. מיפוי הבעיה לפורמט ילידי-קוונטי
2. אופטימיזציה של ה-Circuit
3. הרצת ה-Circuit היעד
4. עיבוד לאחר של התוצאות

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 שלב 1: מיפוי הבעיה ל-Circuit ואופרטורים קוונטיים

qpe = QuantumCircuit(4, 3)
qpe.x(3)
for qubit in range(3):
    qpe.h(qubit)
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.append(QFT(3, inverse=True), [0, 1, 2])
for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

backend = service.least_busy(simulator=False, operational=True, min_num_qubits=4)

print(backend)

<IBMBackend('ibm_strasbourg')>

4.2 שלב 2: אופטימיזציה לחומרת היעד

# Transpile the circuit into basis gates executable on the hardware
pm = generate_preset_pass_manager(backend=backend, optimization_level=2)
qc_compiled = pm.run(qpe)

qc_compiled.draw("mpl", idle_wires=False)

4.3 שלב 3: הרצה על חומרת היעד

real_sampler = Sampler(mode=backend)
job = real_sampler.run([qc_compiled], shots=1024)
job_id = job.job_id()
print("job id:", job_id)

job id: d13p4zb5z6q00087ag00

job = service.job(job_id)  # Input your job-id between the quotations
job.status()

'DONE'

result_real = job.result()
print(result_real)

PrimitiveResult([SamplerPubResult(data=DataBin(c=BitArray(<shape=(), num_shots=1024, num_bits=3>)), metadata={'circuit_metadata': {}})], metadata={'execution': {'execution_spans': ExecutionSpans([DoubleSliceSpan(<start='2025-06-09 22:39:00', stop='2025-06-09 22:39:00', size=1024>)])}, 'version': 2})

4.4 שלב 4: עיבוד לאחר של התוצאות

from qiskit.visualization import plot_histogram

plot_histogram(result_real[0].data.c.get_counts())

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'